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";
42 #include <sys/cdefs.h>
43 __FBSDID("$FreeBSD: src/bin/sh/expand.c,v 1.31.2.5 2003/01/17 07:44:01 tjr 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(char *, int);
99 STATIC char *exptilde(char *, int);
100 STATIC void expbackq(union node *, int, int);
101 STATIC int subevalvar(char *, char *, int, int, int, int);
102 STATIC char *evalvar(char *, int);
103 STATIC int varisset(char *, int);
104 STATIC void varvalue(char *, int, int);
105 STATIC void recordregion(int, int, int);
106 STATIC void removerecordregions(int);
107 STATIC void ifsbreakup(char *, struct arglist *);
108 STATIC void expandmeta(struct strlist *, int);
109 STATIC void expmeta(char *, char *);
110 STATIC void addfname(char *);
111 STATIC struct strlist *expsort(struct strlist *);
112 STATIC struct strlist *msort(struct strlist *, int);
113 STATIC int pmatch(char *, char *, int);
114 STATIC char *cvtnum(int, char *);
115 STATIC int collate_range_cmp(int, int);
118 collate_range_cmp (int c1, int 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.
136 * union node *arg the document
137 * int fd; where to write the expanded version
141 expandhere(union node *arg, int fd)
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(union node *arg, struct arglist *arglist, int flag)
162 argbackq = arg->narg.backquote;
163 STARTSTACKSTR(expdest);
164 ifsfirst.next = NULL;
166 argstr(arg->narg.text, flag);
167 if (arglist == NULL) {
168 return; /* here document expanded */
170 STPUTC('\0', expdest);
171 p = grabstackstr(expdest);
172 exparg.lastp = &exparg.list;
176 if (flag & EXP_FULL) {
177 ifsbreakup(p, &exparg);
178 *exparg.lastp = NULL;
179 exparg.lastp = &exparg.list;
180 expandmeta(exparg.list, flag);
182 if (flag & EXP_REDIR) /*XXX - for now, just remove escapes */
184 sp = (struct strlist *)stalloc(sizeof (struct strlist));
187 exparg.lastp = &sp->next;
189 while (ifsfirst.next != NULL) {
190 struct ifsregion *ifsp;
192 ifsp = ifsfirst.next->next;
193 ckfree(ifsfirst.next);
194 ifsfirst.next = ifsp;
197 *exparg.lastp = NULL;
199 *arglist->lastp = exparg.list;
200 arglist->lastp = exparg.lastp;
207 * Perform variable and command substitution. If EXP_FULL is set, output CTLESC
208 * characters to allow for further processing. Otherwise treat
209 * $@ like $* since no splitting will be performed.
213 argstr(char *p, int flag)
216 int quotes = flag & (EXP_FULL | EXP_CASE | EXP_REDIR); /* do CTLESC */
219 if (*p == '~' && (flag & (EXP_TILDE | EXP_VARTILDE)))
220 p = exptilde(p, flag);
224 case CTLENDVAR: /* ??? */
227 /* "$@" syntax adherence hack */
228 if (p[0] == CTLVAR && p[2] == '@' && p[3] == '=')
230 if ((flag & EXP_FULL) != 0)
240 p = evalvar(p, flag);
243 case CTLBACKQ|CTLQUOTE:
244 expbackq(argbackq->n, c & CTLQUOTE, flag);
245 argbackq = argbackq->next;
253 * sort of a hack - expand tildes in variable
254 * assignments (after the first '=' and after ':'s).
257 if (flag & EXP_VARTILDE && *p == '~') {
264 p = exptilde(p, flag);
275 exptilde(char *p, int flag)
280 int quotes = flag & (EXP_FULL | EXP_CASE | EXP_REDIR);
282 while ((c = *p) != '\0') {
289 if (flag & EXP_VARTILDE)
299 if (*(startp+1) == '\0') {
300 if ((home = lookupvar("HOME")) == NULL)
303 if ((pw = getpwnam(startp+1)) == NULL)
310 while ((c = *home++) != '\0') {
311 if (quotes && SQSYNTAX[(int)c] == CCTL)
312 STPUTC(CTLESC, expdest);
323 removerecordregions(int endoff)
325 if (ifslastp == NULL)
328 if (ifsfirst.endoff > endoff) {
329 while (ifsfirst.next != NULL) {
330 struct ifsregion *ifsp;
332 ifsp = ifsfirst.next->next;
333 ckfree(ifsfirst.next);
334 ifsfirst.next = ifsp;
337 if (ifsfirst.begoff > endoff)
340 ifslastp = &ifsfirst;
341 ifsfirst.endoff = endoff;
346 ifslastp = &ifsfirst;
347 while (ifslastp->next && ifslastp->next->begoff < endoff)
348 ifslastp=ifslastp->next;
349 while (ifslastp->next != NULL) {
350 struct ifsregion *ifsp;
352 ifsp = ifslastp->next->next;
353 ckfree(ifslastp->next);
354 ifslastp->next = ifsp;
357 if (ifslastp->endoff > endoff)
358 ifslastp->endoff = endoff;
362 * Expand arithmetic expression. Backup to start of expression,
363 * evaluate, place result in (backed up) result, adjust string position.
371 int quotes = flag & (EXP_FULL | EXP_CASE | EXP_REDIR);
376 * This routine is slightly over-complicated for
377 * efficiency. First we make sure there is
378 * enough space for the result, which may be bigger
379 * than the expression if we add exponentiation. Next we
380 * scan backwards looking for the start of arithmetic. If the
381 * next previous character is a CTLESC character, then we
382 * have to rescan starting from the beginning since CTLESC
383 * characters have to be processed left to right.
385 #if INT_MAX / 1000000000 >= 10 || INT_MIN / 1000000000 <= -10
386 #error "integers with more than 10 digits are not supported"
388 CHECKSTRSPACE(12 - 2, expdest);
389 USTPUTC('\0', expdest);
390 start = stackblock();
392 while (p >= start && *p != CTLARI)
394 if (p < start || *p != CTLARI)
395 error("missing CTLARI (shouldn't happen)");
396 if (p > start && *(p - 1) == CTLESC)
397 for (p = start; *p != CTLARI; p++)
406 removerecordregions(begoff);
410 fmtstr(p, 12, "%d", result);
414 recordregion(begoff, p - 1 - start, 0);
415 result = expdest - p + 1;
416 STADJUST(-result, expdest);
421 * Expand stuff in backwards quotes.
425 expbackq(union node *cmd, int quoted, int flag)
431 char *dest = expdest;
432 struct ifsregion saveifs, *savelastp;
433 struct nodelist *saveargbackq;
435 int startloc = dest - stackblock();
436 char const *syntax = quoted? DQSYNTAX : BASESYNTAX;
438 int quotes = flag & (EXP_FULL | EXP_CASE | EXP_REDIR);
442 savelastp = ifslastp;
443 saveargbackq = argbackq;
446 p = grabstackstr(dest);
447 evalbackcmd(cmd, &in);
448 ungrabstackstr(p, dest);
450 ifslastp = savelastp;
451 argbackq = saveargbackq;
457 if (--in.nleft < 0) {
460 while ((i = read(in.fd, buf, sizeof buf)) < 0 && errno == EINTR);
461 TRACE(("expbackq: read returns %d\n", i));
469 if (quotes && syntax[(int)lastc] == CCTL)
470 STPUTC(CTLESC, dest);
475 /* Eat all trailing newlines */
476 for (p--; lastc == '\n'; lastc = *--p)
484 exitstatus = waitforjob(in.jp, (int *)NULL);
486 recordregion(startloc, dest - stackblock(), 0);
487 TRACE(("evalbackq: size=%d: \"%.*s\"\n",
488 (dest - stackblock()) - startloc,
489 (dest - stackblock()) - startloc,
490 stackblock() + startloc));
498 subevalvar(char *p, char *str, int strloc, int subtype, int startloc,
505 int saveherefd = herefd;
506 struct nodelist *saveargbackq = argbackq;
511 STACKSTRNUL(expdest);
513 argbackq = saveargbackq;
514 startp = stackblock() + startloc;
516 str = stackblock() + strloc;
520 setvar(str, startp, 0);
521 amount = startp - expdest;
522 STADJUST(amount, expdest);
529 if (*p != CTLENDVAR) {
530 outfmt(&errout, "%s\n", startp);
533 error("%.*s: parameter %snot set", p - str - 1,
534 str, (varflags & VSNUL) ? "null or "
539 for (loc = startp; loc < str; loc++) {
542 if (patmatch(str, startp, varflags & VSQUOTE)) {
547 if ((varflags & VSQUOTE) && *loc == CTLESC)
553 for (loc = str - 1; loc >= startp;) {
556 if (patmatch(str, startp, varflags & VSQUOTE)) {
562 if ((varflags & VSQUOTE) && loc > startp &&
563 *(loc - 1) == CTLESC) {
564 for (q = startp; q < loc; q++)
574 for (loc = str - 1; loc >= startp;) {
575 if (patmatch(str, loc, varflags & VSQUOTE)) {
576 amount = loc - expdest;
577 STADJUST(amount, expdest);
581 if ((varflags & VSQUOTE) && loc > startp &&
582 *(loc - 1) == CTLESC) {
583 for (q = startp; q < loc; q++)
593 for (loc = startp; loc < str - 1; loc++) {
594 if (patmatch(str, loc, varflags & VSQUOTE)) {
595 amount = loc - expdest;
596 STADJUST(amount, expdest);
599 if ((varflags & VSQUOTE) && *loc == CTLESC)
610 amount = ((str - 1) - (loc - startp)) - expdest;
611 STADJUST(amount, expdest);
612 while (loc != str - 1)
619 * Expand a variable, and return a pointer to the next character in the
624 evalvar(char *p, int flag)
637 int quotes = flag & (EXP_FULL | EXP_CASE | EXP_REDIR);
640 subtype = varflags & VSTYPE;
645 p = strchr(p, '=') + 1;
646 again: /* jump here after setting a variable with ${var=text} */
648 set = varisset(var, varflags & VSNUL);
651 val = bltinlookup(var, 1);
652 if (val == NULL || ((varflags & VSNUL) && val[0] == '\0')) {
659 startloc = expdest - stackblock();
668 error("%.*s: parameter not set", p - var - 1, var);
671 if (set && subtype != VSPLUS) {
672 /* insert the value of the variable */
674 varvalue(var, varflags & VSQUOTE, flag & EXP_FULL);
675 if (subtype == VSLENGTH) {
676 varlen = expdest - stackblock() - startloc;
677 STADJUST(-varlen, expdest);
680 char const *syntax = (varflags & VSQUOTE) ? DQSYNTAX
683 if (subtype == VSLENGTH) {
690 syntax[(int)*val] == CCTL)
691 STPUTC(CTLESC, expdest);
692 STPUTC(*val++, expdest);
699 if (subtype == VSPLUS)
702 easy = ((varflags & VSQUOTE) == 0 ||
703 (*var == '@' && shellparam.nparam != 1));
708 expdest = cvtnum(varlen, expdest);
715 recordregion(startloc, expdest - stackblock(),
736 * Terminate the string and start recording the pattern
739 STPUTC('\0', expdest);
740 patloc = expdest - stackblock();
741 if (subevalvar(p, NULL, patloc, subtype,
742 startloc, varflags) == 0) {
743 int amount = (expdest - stackblock() - patloc) + 1;
744 STADJUST(-amount, expdest);
746 /* Remove any recorded regions beyond start of variable */
747 removerecordregions(startloc);
753 if (subevalvar(p, var, 0, subtype, startloc, varflags)) {
756 * Remove any recorded regions beyond
759 removerecordregions(startloc);
772 if (subtype != VSNORMAL) { /* skip to end of alternative */
775 if ((c = *p++) == CTLESC)
777 else if (c == CTLBACKQ || c == (CTLBACKQ|CTLQUOTE)) {
779 argbackq = argbackq->next;
780 } else if (c == CTLVAR) {
781 if ((*p++ & VSTYPE) != VSNORMAL)
783 } else if (c == CTLENDVAR) {
795 * Test whether a specialized variable is set.
799 varisset(char *name, int nulok)
803 return backgndpid != -1;
804 else if (*name == '@' || *name == '*') {
805 if (*shellparam.p == NULL)
811 for (av = shellparam.p; *av; av++)
816 } else if (is_digit(*name)) {
818 int num = atoi(name);
820 if (num > shellparam.nparam)
826 ap = shellparam.p[num - 1];
828 if (nulok && (ap == NULL || *ap == '\0'))
837 * Add the value of a specialized variable to the stack string.
841 varvalue(char *name, int quoted, int allow_split)
846 extern int oexitstatus;
851 #define STRTODEST(p) \
854 syntax = quoted? DQSYNTAX : BASESYNTAX; \
856 if (syntax[(int)*p] == CCTL) \
857 STPUTC(CTLESC, expdest); \
858 STPUTC(*p++, expdest); \
862 STPUTC(*p++, expdest); \
874 num = shellparam.nparam;
879 expdest = cvtnum(num, expdest);
882 for (i = 0 ; i < NOPTS ; i++) {
884 STPUTC(optlist[i].letter, expdest);
888 if (allow_split && quoted) {
889 for (ap = shellparam.p ; (p = *ap++) != NULL ; ) {
892 STPUTC('\0', expdest);
902 for (ap = shellparam.p ; (p = *ap++) != NULL ; ) {
905 STPUTC(sep, expdest);
913 if (is_digit(*name)) {
915 if (num > 0 && num <= shellparam.nparam) {
916 p = shellparam.p[num - 1];
927 * Record the the fact that we have to scan this region of the
928 * string for IFS characters.
932 recordregion(int start, int end, int nulonly)
934 struct ifsregion *ifsp;
936 if (ifslastp == NULL) {
939 ifsp = (struct ifsregion *)ckmalloc(sizeof (struct ifsregion));
940 ifslastp->next = ifsp;
943 ifslastp->next = NULL;
944 ifslastp->begoff = start;
945 ifslastp->endoff = end;
946 ifslastp->nulonly = nulonly;
952 * Break the argument string into pieces based upon IFS and add the
953 * strings to the argument list. The regions of the string to be
954 * searched for IFS characters have been stored by recordregion.
957 ifsbreakup(char *string, struct arglist *arglist)
959 struct ifsregion *ifsp;
972 if (ifslastp != NULL) {
975 p = string + ifsp->begoff;
976 nulonly = ifsp->nulonly;
977 ifs = nulonly ? nullstr :
978 ( ifsset() ? ifsval() : " \t\n" );
980 while (p < string + ifsp->endoff) {
984 if (strchr(ifs, *p)) {
986 ifsspc = (strchr(" \t\n", *p) != NULL);
987 /* Ignore IFS whitespace at start */
988 if (q == start && ifsspc) {
994 sp = (struct strlist *)stalloc(sizeof *sp);
996 *arglist->lastp = sp;
997 arglist->lastp = &sp->next;
1001 if (p >= string + ifsp->endoff) {
1007 if (strchr(ifs, *p) == NULL ) {
1010 } else if (strchr(" \t\n",*p) == NULL) {
1026 } while ((ifsp = ifsp->next) != NULL);
1027 if (*start || (!ifsspc && start > string &&
1029 sp = (struct strlist *)stalloc(sizeof *sp);
1031 *arglist->lastp = sp;
1032 arglist->lastp = &sp->next;
1035 sp = (struct strlist *)stalloc(sizeof *sp);
1037 *arglist->lastp = sp;
1038 arglist->lastp = &sp->next;
1045 * Expand shell metacharacters. At this point, the only control characters
1046 * should be escapes. The results are stored in the list exparg.
1053 expandmeta(struct strlist *str, int flag __unused)
1056 struct strlist **savelastp;
1059 /* TODO - EXP_REDIR */
1065 for (;;) { /* fast check for meta chars */
1066 if ((c = *p++) == '\0')
1068 if (c == '*' || c == '?' || c == '[' || c == '!')
1071 savelastp = exparg.lastp;
1073 if (expdir == NULL) {
1074 int i = strlen(str->text);
1075 expdir = ckmalloc(i < 2048 ? 2048 : i); /* XXX */
1078 expmeta(expdir, str->text);
1082 if (exparg.lastp == savelastp) {
1087 *exparg.lastp = str;
1088 rmescapes(str->text);
1089 exparg.lastp = &str->next;
1091 *exparg.lastp = NULL;
1092 *savelastp = sp = expsort(*savelastp);
1093 while (sp->next != NULL)
1095 exparg.lastp = &sp->next;
1103 * Do metacharacter (i.e. *, ?, [...]) expansion.
1107 expmeta(char *enddir, char *name)
1122 for (p = name ; ; p++) {
1123 if (*p == '*' || *p == '?')
1125 else if (*p == '[') {
1127 if (*q == '!' || *q == '^')
1130 while (*q == CTLQUOTEMARK)
1134 if (*q == '/' || *q == '\0')
1141 } else if (*p == '!' && p[1] == '!' && (p == name || p[-1] == '/')) {
1143 } else if (*p == '\0')
1145 else if (*p == CTLQUOTEMARK)
1147 else if (*p == CTLESC)
1155 if (metaflag == 0) { /* we've reached the end of the file name */
1156 if (enddir != expdir)
1158 for (p = name ; ; p++) {
1159 if (*p == CTLQUOTEMARK)
1167 if (metaflag == 0 || stat(expdir, &statb) >= 0)
1172 if (start != name) {
1175 while (*p == CTLQUOTEMARK)
1182 if (enddir == expdir) {
1184 } else if (enddir == expdir + 1 && *expdir == '/') {
1190 if ((dirp = opendir(p)) == NULL)
1192 if (enddir != expdir)
1194 if (*endname == 0) {
1202 while (*p == CTLQUOTEMARK)
1208 while (! int_pending() && (dp = readdir(dirp)) != NULL) {
1209 if (dp->d_name[0] == '.' && ! matchdot)
1211 if (patmatch(start, dp->d_name, 0)) {
1213 scopy(dp->d_name, enddir);
1217 for (p = enddir, q = dp->d_name;
1218 (*p++ = *q++) != '\0';)
1221 expmeta(p, endname);
1232 * Add a file name to the list.
1236 addfname(char *name)
1241 p = stalloc(strlen(name) + 1);
1243 sp = (struct strlist *)stalloc(sizeof *sp);
1246 exparg.lastp = &sp->next;
1251 * Sort the results of file name expansion. It calculates the number of
1252 * strings to sort and then calls msort (short for merge sort) to do the
1256 STATIC struct strlist *
1257 expsort(struct strlist *str)
1263 for (sp = str ; sp ; sp = sp->next)
1265 return msort(str, len);
1269 STATIC struct strlist *
1270 msort(struct strlist *list, int len)
1272 struct strlist *p, *q = NULL;
1273 struct strlist **lpp;
1281 for (n = half ; --n >= 0 ; ) {
1285 q->next = NULL; /* terminate first half of list */
1286 q = msort(list, half); /* sort first half of list */
1287 p = msort(p, len - half); /* sort second half */
1290 if (strcmp(p->text, q->text) < 0) {
1293 if ((p = *lpp) == NULL) {
1300 if ((q = *lpp) == NULL) {
1312 * Returns true if the pattern matches the string.
1316 patmatch(char *pattern, char *string, int squoted)
1319 if (pattern[0] == '!' && pattern[1] == '!')
1320 return 1 - pmatch(pattern + 2, string);
1323 return pmatch(pattern, string, squoted);
1328 pmatch(char *pattern, char *string, int squoted)
1340 if (squoted && *q == CTLESC)
1348 if (squoted && *q == CTLESC)
1355 while (c == CTLQUOTEMARK || c == '*')
1357 if (c != CTLESC && c != CTLQUOTEMARK &&
1358 c != '?' && c != '*' && c != '[') {
1360 if (squoted && *q == CTLESC &&
1365 if (squoted && *q == CTLESC)
1371 if (pmatch(p, q, squoted))
1373 if (squoted && *q == CTLESC)
1375 } while (*q++ != '\0');
1383 if (*endp == '!' || *endp == '^')
1386 while (*endp == CTLQUOTEMARK)
1389 goto dft; /* no matching ] */
1390 if (*endp == CTLESC)
1396 if (*p == '!' || *p == '^') {
1402 if (squoted && chr == CTLESC)
1408 if (c == CTLQUOTEMARK)
1412 if (*p == '-' && p[1] != ']') {
1414 while (*p == CTLQUOTEMARK)
1418 if ( collate_range_cmp(chr, c) >= 0
1419 && collate_range_cmp(chr, *p) <= 0
1427 } while ((c = *p++) != ']');
1428 if (found == invert)
1433 if (squoted && *q == CTLESC)
1449 * Remove any CTLESC characters from a string.
1453 rmescapes(char *str)
1458 while (*p != CTLESC && *p != CTLQUOTEMARK) {
1464 if (*p == CTLQUOTEMARK) {
1478 * See if a pattern matches in a case statement.
1482 casematch(union node *pattern, char *val)
1484 struct stackmark smark;
1488 setstackmark(&smark);
1489 argbackq = pattern->narg.backquote;
1490 STARTSTACKSTR(expdest);
1492 argstr(pattern->narg.text, EXP_TILDE | EXP_CASE);
1493 STPUTC('\0', expdest);
1494 p = grabstackstr(expdest);
1495 result = patmatch(p, val, 0);
1496 popstackmark(&smark);
1505 cvtnum(int num, char *buf)
1509 char *p = temp + 31;
1514 *--p = num % 10 + '0';
1515 } while ((num /= 10) != 0);