2 * Copyright (c) 1991, 1993
3 * The Regents of the University of California. All rights reserved.
5 * This code is derived from software contributed to Berkeley by
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
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.
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
39 static char sccsid[] = "@(#)expand.c 8.5 (Berkeley) 5/15/95";
41 static const char rcsid[] =
42 "$Id: expand.c,v 1.23 1998/09/06 21:13:09 tegge Exp $";
45 #include <sys/types.h>
57 * Routines to expand arguments to commands. We have to deal with
58 * backquotes, shell variables, and file metacharacters.
80 * Structure specifying which parts of the string should be searched
85 struct ifsregion *next; /* next region in list */
86 int begoff; /* offset of start of region */
87 int endoff; /* offset of end of region */
88 int nulonly; /* search for nul bytes only */
92 char *expdest; /* output of current string */
93 struct nodelist *argbackq; /* list of back quote expressions */
94 struct ifsregion ifsfirst; /* first struct in list of ifs regions */
95 struct ifsregion *ifslastp; /* last struct in list */
96 struct arglist exparg; /* holds expanded arg list */
98 STATIC void argstr __P((char *, int));
99 STATIC char *exptilde __P((char *, int));
100 STATIC void expbackq __P((union node *, int, int));
101 STATIC int subevalvar __P((char *, char *, int, int, int, int));
102 STATIC char *evalvar __P((char *, int));
103 STATIC int varisset __P((char *, int));
104 STATIC void varvalue __P((char *, int, int));
105 STATIC void recordregion __P((int, int, int));
106 STATIC void removerecordregions __P((int));
107 STATIC void ifsbreakup __P((char *, struct arglist *));
108 STATIC void expandmeta __P((struct strlist *, int));
109 STATIC void expmeta __P((char *, char *));
110 STATIC void addfname __P((char *));
111 STATIC struct strlist *expsort __P((struct strlist *));
112 STATIC struct strlist *msort __P((struct strlist *, int));
113 STATIC int pmatch __P((char *, char *));
114 STATIC char *cvtnum __P((int, char *));
115 STATIC int collate_range_cmp __P((int, int));
117 STATIC int collate_range_cmp (c1, c2)
120 static char s1[2], s2[2];
129 if ((ret = strcoll(s1, s2)) != 0)
135 * Expand shell variables and backquotes inside a here document.
140 union node *arg; /* the document */
141 int fd; /* where to write the expanded version */
144 expandarg(arg, (struct arglist *)NULL, 0);
145 xwrite(fd, stackblock(), expdest - stackblock());
150 * Perform variable substitution and command substitution on an argument,
151 * placing the resulting list of arguments in arglist. If EXP_FULL is true,
152 * perform splitting and file name expansion. When arglist is NULL, perform
153 * here document expansion.
157 expandarg(arg, arglist, flag)
159 struct arglist *arglist;
165 argbackq = arg->narg.backquote;
166 STARTSTACKSTR(expdest);
167 ifsfirst.next = NULL;
169 argstr(arg->narg.text, flag);
170 if (arglist == NULL) {
171 return; /* here document expanded */
173 STPUTC('\0', expdest);
174 p = grabstackstr(expdest);
175 exparg.lastp = &exparg.list;
179 if (flag & EXP_FULL) {
180 ifsbreakup(p, &exparg);
181 *exparg.lastp = NULL;
182 exparg.lastp = &exparg.list;
183 expandmeta(exparg.list, flag);
185 if (flag & EXP_REDIR) /*XXX - for now, just remove escapes */
187 sp = (struct strlist *)stalloc(sizeof (struct strlist));
190 exparg.lastp = &sp->next;
192 while (ifsfirst.next != NULL) {
193 struct ifsregion *ifsp;
195 ifsp = ifsfirst.next->next;
196 ckfree(ifsfirst.next);
197 ifsfirst.next = ifsp;
200 *exparg.lastp = NULL;
202 *arglist->lastp = exparg.list;
203 arglist->lastp = exparg.lastp;
210 * Perform variable and command substitution. If EXP_FULL is set, output CTLESC
211 * characters to allow for further processing. Otherwise treat
212 * $@ like $* since no splitting will be performed.
221 int quotes = flag & (EXP_FULL | EXP_CASE); /* do CTLESC */
224 if (*p == '~' && (flag & (EXP_TILDE | EXP_VARTILDE)))
225 p = exptilde(p, flag);
229 case CTLENDVAR: /* ??? */
232 /* "$@" syntax adherence hack */
233 if (p[0] == CTLVAR && p[2] == '@' && p[3] == '=')
235 if ((flag & EXP_FULL) != 0)
245 p = evalvar(p, flag);
248 case CTLBACKQ|CTLQUOTE:
249 expbackq(argbackq->n, c & CTLQUOTE, flag);
250 argbackq = argbackq->next;
258 * sort of a hack - expand tildes in variable
259 * assignments (after the first '=' and after ':'s).
262 if (flag & EXP_VARTILDE && *p == '~') {
269 p = exptilde(p, flag);
287 int quotes = flag & (EXP_FULL | EXP_CASE);
289 while ((c = *p) != '\0') {
296 if (flag & EXP_VARTILDE)
306 if (*(startp+1) == '\0') {
307 if ((home = lookupvar("HOME")) == NULL)
310 if ((pw = getpwnam(startp+1)) == NULL)
317 while ((c = *home++) != '\0') {
318 if (quotes && SQSYNTAX[c] == CCTL)
319 STPUTC(CTLESC, expdest);
330 removerecordregions(endoff)
333 if (ifslastp == NULL)
336 if (ifsfirst.endoff > endoff) {
337 while (ifsfirst.next != NULL) {
338 struct ifsregion *ifsp;
340 ifsp = ifsfirst.next->next;
341 ckfree(ifsfirst.next);
342 ifsfirst.next = ifsp;
345 if (ifsfirst.begoff > endoff)
348 ifslastp = &ifsfirst;
349 ifsfirst.endoff = endoff;
354 ifslastp = &ifsfirst;
355 while (ifslastp->next && ifslastp->next->begoff < endoff)
356 ifslastp=ifslastp->next;
357 while (ifslastp->next != NULL) {
358 struct ifsregion *ifsp;
360 ifsp = ifslastp->next->next;
361 ckfree(ifslastp->next);
362 ifslastp->next = ifsp;
365 if (ifslastp->endoff > endoff)
366 ifslastp->endoff = endoff;
370 * Expand arithmetic expression. Backup to start of expression,
371 * evaluate, place result in (backed up) result, adjust string position.
380 int quotes = flag & (EXP_FULL | EXP_CASE);
385 * This routine is slightly over-compilcated for
386 * efficiency. First we make sure there is
387 * enough space for the result, which may be bigger
388 * than the expression if we add exponentation. Next we
389 * scan backwards looking for the start of arithmetic. If the
390 * next previous character is a CTLESC character, then we
391 * have to rescan starting from the beginning since CTLESC
392 * characters have to be processed left to right.
394 #if INT_MAX / 1000000000 >= 10 || INT_MIN / 1000000000 <= -10
395 #error "integers with more than 10 digits are not supported"
397 CHECKSTRSPACE(12 - 2, expdest);
398 USTPUTC('\0', expdest);
399 start = stackblock();
401 while (*p != CTLARI && p >= start)
404 error("missing CTLARI (shouldn't happen)");
405 if (p > start && *(p-1) == CTLESC)
406 for (p = start; *p != CTLARI; p++)
415 removerecordregions(begoff);
419 fmtstr(p, 12, "%d", result);
423 recordregion(begoff, p - 1 - start, 0);
424 result = expdest - p + 1;
425 STADJUST(-result, expdest);
430 * Expand stuff in backwards quotes.
434 expbackq(cmd, quoted, flag)
443 char *dest = expdest;
444 struct ifsregion saveifs, *savelastp;
445 struct nodelist *saveargbackq;
447 int startloc = dest - stackblock();
448 char const *syntax = quoted? DQSYNTAX : BASESYNTAX;
450 int quotes = flag & (EXP_FULL | EXP_CASE);
454 savelastp = ifslastp;
455 saveargbackq = argbackq;
458 p = grabstackstr(dest);
459 evalbackcmd(cmd, &in);
460 ungrabstackstr(p, dest);
462 ifslastp = savelastp;
463 argbackq = saveargbackq;
469 if (--in.nleft < 0) {
472 while ((i = read(in.fd, buf, sizeof buf)) < 0 && errno == EINTR);
473 TRACE(("expbackq: read returns %d\n", i));
481 if (quotes && syntax[lastc] == CCTL)
482 STPUTC(CTLESC, dest);
487 /* Eat all trailing newlines */
488 for (p--; lastc == '\n'; lastc = *--p)
496 exitstatus = waitforjob(in.jp);
498 recordregion(startloc, dest - stackblock(), 0);
499 TRACE(("evalbackq: size=%d: \"%.*s\"\n",
500 (dest - stackblock()) - startloc,
501 (dest - stackblock()) - startloc,
502 stackblock() + startloc));
510 subevalvar(p, str, strloc, subtype, startloc, varflags)
521 int saveherefd = herefd;
522 struct nodelist *saveargbackq = argbackq;
527 STACKSTRNUL(expdest);
529 argbackq = saveargbackq;
530 startp = stackblock() + startloc;
532 str = stackblock() + strloc;
536 setvar(str, startp, 0);
537 amount = startp - expdest;
538 STADJUST(amount, expdest);
545 if (*p != CTLENDVAR) {
546 outfmt(&errout, "%s\n", startp);
549 error("%.*s: parameter %snot set", p - str - 1,
550 str, (varflags & VSNUL) ? "null or "
555 for (loc = startp; loc < str; loc++) {
558 if (patmatch(str, startp)) {
567 for (loc = str - 1; loc >= startp; loc--) {
570 if (patmatch(str, startp)) {
579 for (loc = str - 1; loc >= startp; loc--) {
580 if (patmatch(str, loc)) {
581 amount = loc - expdest;
582 STADJUST(amount, expdest);
589 for (loc = startp; loc < str - 1; loc++) {
590 if (patmatch(str, loc)) {
591 amount = loc - expdest;
592 STADJUST(amount, expdest);
604 amount = ((str - 1) - (loc - startp)) - expdest;
605 STADJUST(amount, expdest);
606 while (loc != str - 1)
613 * Expand a variable, and return a pointer to the next character in the
633 int quotes = flag & (EXP_FULL | EXP_CASE);
636 subtype = varflags & VSTYPE;
641 p = strchr(p, '=') + 1;
642 again: /* jump here after setting a variable with ${var=text} */
644 set = varisset(var, varflags & VSNUL);
647 val = lookupvar(var);
648 if (val == NULL || ((varflags & VSNUL) && val[0] == '\0')) {
655 startloc = expdest - stackblock();
656 if (set && subtype != VSPLUS) {
657 /* insert the value of the variable */
659 varvalue(var, varflags & VSQUOTE, flag & EXP_FULL);
660 if (subtype == VSLENGTH) {
661 varlen = expdest - stackblock() - startloc;
662 STADJUST(-varlen, expdest);
665 char const *syntax = (varflags & VSQUOTE) ? DQSYNTAX
668 if (subtype == VSLENGTH) {
674 if (quotes && syntax[*val] == CCTL)
675 STPUTC(CTLESC, expdest);
676 STPUTC(*val++, expdest);
683 if (subtype == VSPLUS)
686 easy = ((varflags & VSQUOTE) == 0 ||
687 (*var == '@' && shellparam.nparam != 1));
692 expdest = cvtnum(varlen, expdest);
699 recordregion(startloc, expdest - stackblock(),
720 * Terminate the string and start recording the pattern
723 STPUTC('\0', expdest);
725 if (subevalvar(p, NULL, expdest - stackblock(), subtype,
726 startloc, varflags) == 0) {
727 int amount = (expdest - pat) + 1;
728 STADJUST(-amount, expdest);
730 /* Remove any recorded regions beyond start of variable */
731 removerecordregions(startloc);
737 if (subevalvar(p, var, 0, subtype, startloc, varflags)) {
740 * Remove any recorded regions beyond
743 removerecordregions(startloc);
756 if (subtype != VSNORMAL) { /* skip to end of alternative */
759 if ((c = *p++) == CTLESC)
761 else if (c == CTLBACKQ || c == (CTLBACKQ|CTLQUOTE)) {
763 argbackq = argbackq->next;
764 } else if (c == CTLVAR) {
765 if ((*p++ & VSTYPE) != VSNORMAL)
767 } else if (c == CTLENDVAR) {
779 * Test whether a specialized variable is set.
783 varisset(name, nulok)
789 return backgndpid != -1;
790 else if (*name == '@' || *name == '*') {
791 if (*shellparam.p == NULL)
797 for (av = shellparam.p; *av; av++)
802 } else if (is_digit(*name)) {
804 int num = atoi(name);
806 if (num > shellparam.nparam)
812 ap = shellparam.p[num - 1];
814 if (nulok && (ap == NULL || *ap == '\0'))
823 * Add the value of a specialized variable to the stack string.
827 varvalue(name, quoted, allow_split)
835 extern int oexitstatus;
840 #define STRTODEST(p) \
843 syntax = quoted? DQSYNTAX : BASESYNTAX; \
845 if (syntax[*p] == CCTL) \
846 STPUTC(CTLESC, expdest); \
847 STPUTC(*p++, expdest); \
851 STPUTC(*p++, expdest); \
863 num = shellparam.nparam;
868 expdest = cvtnum(num, expdest);
871 for (i = 0 ; i < NOPTS ; i++) {
873 STPUTC(optlist[i].letter, expdest);
877 if (allow_split && quoted) {
878 for (ap = shellparam.p ; (p = *ap++) != NULL ; ) {
881 STPUTC('\0', expdest);
891 for (ap = shellparam.p ; (p = *ap++) != NULL ; ) {
894 STPUTC(sep, expdest);
902 if (is_digit(*name)) {
904 if (num > 0 && num <= shellparam.nparam) {
905 p = shellparam.p[num - 1];
916 * Record the the fact that we have to scan this region of the
917 * string for IFS characters.
921 recordregion(start, end, nulonly)
926 struct ifsregion *ifsp;
928 if (ifslastp == NULL) {
931 ifsp = (struct ifsregion *)ckmalloc(sizeof (struct ifsregion));
932 ifslastp->next = ifsp;
935 ifslastp->next = NULL;
936 ifslastp->begoff = start;
937 ifslastp->endoff = end;
938 ifslastp->nulonly = nulonly;
944 * Break the argument string into pieces based upon IFS and add the
945 * strings to the argument list. The regions of the string to be
946 * searched for IFS characters have been stored by recordregion.
949 ifsbreakup(string, arglist)
951 struct arglist *arglist;
953 struct ifsregion *ifsp;
966 if (ifslastp != NULL) {
969 p = string + ifsp->begoff;
970 nulonly = ifsp->nulonly;
971 ifs = nulonly ? nullstr :
972 ( ifsset() ? ifsval() : " \t\n" );
974 while (p < string + ifsp->endoff) {
978 if (strchr(ifs, *p)) {
980 ifsspc = (strchr(" \t\n", *p) != NULL);
981 /* Ignore IFS whitespace at start */
982 if (q == start && ifsspc) {
988 sp = (struct strlist *)stalloc(sizeof *sp);
990 *arglist->lastp = sp;
991 arglist->lastp = &sp->next;
995 if (p >= string + ifsp->endoff) {
1001 if (strchr(ifs, *p) == NULL ) {
1004 } else if (strchr(" \t\n",*p) == NULL) {
1020 } while ((ifsp = ifsp->next) != NULL);
1021 if (*start || (!ifsspc && start > string &&
1023 sp = (struct strlist *)stalloc(sizeof *sp);
1025 *arglist->lastp = sp;
1026 arglist->lastp = &sp->next;
1029 sp = (struct strlist *)stalloc(sizeof *sp);
1031 *arglist->lastp = sp;
1032 arglist->lastp = &sp->next;
1039 * Expand shell metacharacters. At this point, the only control characters
1040 * should be escapes. The results are stored in the list exparg.
1047 expandmeta(str, flag)
1048 struct strlist *str;
1052 struct strlist **savelastp;
1055 /* TODO - EXP_REDIR */
1061 for (;;) { /* fast check for meta chars */
1062 if ((c = *p++) == '\0')
1064 if (c == '*' || c == '?' || c == '[' || c == '!')
1067 savelastp = exparg.lastp;
1069 if (expdir == NULL) {
1070 int i = strlen(str->text);
1071 expdir = ckmalloc(i < 2048 ? 2048 : i); /* XXX */
1074 expmeta(expdir, str->text);
1078 if (exparg.lastp == savelastp) {
1083 *exparg.lastp = str;
1084 rmescapes(str->text);
1085 exparg.lastp = &str->next;
1087 *exparg.lastp = NULL;
1088 *savelastp = sp = expsort(*savelastp);
1089 while (sp->next != NULL)
1091 exparg.lastp = &sp->next;
1099 * Do metacharacter (i.e. *, ?, [...]) expansion.
1103 expmeta(enddir, name)
1120 for (p = name ; ; p++) {
1121 if (*p == '*' || *p == '?')
1123 else if (*p == '[') {
1125 if (*q == '!' || *q == '^')
1128 while (*q == CTLQUOTEMARK)
1132 if (*q == '/' || *q == '\0')
1139 } else if (*p == '!' && p[1] == '!' && (p == name || p[-1] == '/')) {
1141 } else if (*p == '\0')
1143 else if (*p == CTLQUOTEMARK)
1145 else if (*p == CTLESC)
1153 if (metaflag == 0) { /* we've reached the end of the file name */
1154 if (enddir != expdir)
1156 for (p = name ; ; p++) {
1157 if (*p == CTLQUOTEMARK)
1165 if (metaflag == 0 || stat(expdir, &statb) >= 0)
1170 if (start != name) {
1173 while (*p == CTLQUOTEMARK)
1180 if (enddir == expdir) {
1182 } else if (enddir == expdir + 1 && *expdir == '/') {
1188 if ((dirp = opendir(p)) == NULL)
1190 if (enddir != expdir)
1192 if (*endname == 0) {
1200 while (*p == CTLQUOTEMARK)
1206 while (! int_pending() && (dp = readdir(dirp)) != NULL) {
1207 if (dp->d_name[0] == '.' && ! matchdot)
1209 if (patmatch(start, dp->d_name)) {
1211 scopy(dp->d_name, enddir);
1215 for (p = enddir, q = dp->d_name;
1216 (*p++ = *q++) != '\0';)
1219 expmeta(p, endname);
1230 * Add a file name to the list.
1240 p = stalloc(strlen(name) + 1);
1242 sp = (struct strlist *)stalloc(sizeof *sp);
1245 exparg.lastp = &sp->next;
1250 * Sort the results of file name expansion. It calculates the number of
1251 * strings to sort and then calls msort (short for merge sort) to do the
1255 STATIC struct strlist *
1257 struct strlist *str;
1263 for (sp = str ; sp ; sp = sp->next)
1265 return msort(str, len);
1269 STATIC struct strlist *
1271 struct strlist *list;
1274 struct strlist *p, *q = NULL;
1275 struct strlist **lpp;
1283 for (n = half ; --n >= 0 ; ) {
1287 q->next = NULL; /* terminate first half of list */
1288 q = msort(list, half); /* sort first half of list */
1289 p = msort(p, len - half); /* sort second half */
1292 if (strcmp(p->text, q->text) < 0) {
1295 if ((p = *lpp) == NULL) {
1302 if ((q = *lpp) == NULL) {
1314 * Returns true if the pattern matches the string.
1318 patmatch(pattern, string)
1323 if (pattern[0] == '!' && pattern[1] == '!')
1324 return 1 - pmatch(pattern + 2, string);
1327 return pmatch(pattern, string);
1332 pmatch(pattern, string)
1357 while (c == CTLQUOTEMARK || c == '*')
1359 if (c != CTLESC && c != CTLQUOTEMARK &&
1360 c != '?' && c != '*' && c != '[') {
1370 } while (*q++ != '\0');
1378 if (*endp == '!' || *endp == '^')
1381 while (*endp == CTLQUOTEMARK)
1384 goto dft; /* no matching ] */
1385 if (*endp == CTLESC)
1391 if (*p == '!' || *p == '^') {
1401 if (c == CTLQUOTEMARK)
1405 if (*p == '-' && p[1] != ']') {
1407 while (*p == CTLQUOTEMARK)
1411 if ( collate_range_cmp(chr, c) >= 0
1412 && collate_range_cmp(chr, *p) <= 0
1420 } while ((c = *p++) != ']');
1421 if (found == invert)
1440 * Remove any CTLESC characters from a string.
1450 while (*p != CTLESC && *p != CTLQUOTEMARK) {
1456 if (*p == CTLQUOTEMARK) {
1470 * See if a pattern matches in a case statement.
1474 casematch(pattern, val)
1475 union node *pattern;
1478 struct stackmark smark;
1482 setstackmark(&smark);
1483 argbackq = pattern->narg.backquote;
1484 STARTSTACKSTR(expdest);
1486 argstr(pattern->narg.text, EXP_TILDE | EXP_CASE);
1487 STPUTC('\0', expdest);
1488 p = grabstackstr(expdest);
1489 result = patmatch(p, val);
1490 popstackmark(&smark);
1505 char *p = temp + 31;
1510 *--p = num % 10 + '0';
1511 } while ((num /= 10) != 0);