4d3c56b23fac65c7407ebd9738804487fe42bdc3
[dragonfly.git] / bin / sh / expand.c
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  * Redistribution and use in source and binary forms, with or without
9  * modification, are permitted provided that the following conditions
10  * are met:
11  * 1. Redistributions of source code must retain the above copyright
12  *    notice, this list of conditions and the following disclaimer.
13  * 2. Redistributions in binary form must reproduce the above copyright
14  *    notice, this list of conditions and the following disclaimer in the
15  *    documentation and/or other materials provided with the distribution.
16  * 3. All advertising materials mentioning features or use of this software
17  *    must display the following acknowledgement:
18  *      This product includes software developed by the University of
19  *      California, Berkeley and its contributors.
20  * 4. Neither the name of the University nor the names of its contributors
21  *    may be used to endorse or promote products derived from this software
22  *    without specific prior written permission.
23  *
24  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
25  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
26  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
27  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
28  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
29  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
30  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
31  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
32  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
33  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
34  * SUCH DAMAGE.
35  *
36  * @(#)expand.c 8.5 (Berkeley) 5/15/95
37  * $FreeBSD: src/bin/sh/expand.c,v 1.51 2006/11/07 22:46:13 stefanf Exp $
38  * $DragonFly: src/bin/sh/expand.c,v 1.9 2007/01/07 16:58:30 pavalos Exp $
39  */
40
41 #include <sys/types.h>
42 #include <sys/time.h>
43 #include <sys/stat.h>
44 #include <errno.h>
45 #include <dirent.h>
46 #include <unistd.h>
47 #include <pwd.h>
48 #include <stdlib.h>
49 #include <limits.h>
50 #include <stdio.h>
51 #include <string.h>
52
53 /*
54  * Routines to expand arguments to commands.  We have to deal with
55  * backquotes, shell variables, and file metacharacters.
56  */
57
58 #include "shell.h"
59 #include "main.h"
60 #include "nodes.h"
61 #include "eval.h"
62 #include "expand.h"
63 #include "syntax.h"
64 #include "parser.h"
65 #include "jobs.h"
66 #include "options.h"
67 #include "var.h"
68 #include "input.h"
69 #include "output.h"
70 #include "memalloc.h"
71 #include "error.h"
72 #include "mystring.h"
73 #include "arith.h"
74 #include "show.h"
75
76 /*
77  * Structure specifying which parts of the string should be searched
78  * for IFS characters.
79  */
80
81 struct ifsregion {
82         struct ifsregion *next; /* next region in list */
83         int begoff;             /* offset of start of region */
84         int endoff;             /* offset of end of region */
85         int nulonly;            /* search for nul bytes only */
86 };
87
88
89 STATIC char *expdest;                   /* output of current string */
90 STATIC struct nodelist *argbackq;       /* list of back quote expressions */
91 STATIC struct ifsregion ifsfirst;       /* first struct in list of ifs regions */
92 STATIC struct ifsregion *ifslastp;      /* last struct in list */
93 STATIC struct arglist exparg;           /* holds expanded arg list */
94
95 STATIC void argstr(char *, int);
96 STATIC char *exptilde(char *, int);
97 STATIC void expbackq(union node *, int, int);
98 STATIC int subevalvar(char *, char *, int, int, int, int);
99 STATIC char *evalvar(char *, int);
100 STATIC int varisset(char *, int);
101 STATIC void varvalue(char *, int, int, int);
102 STATIC void recordregion(int, int, int);
103 STATIC void removerecordregions(int);
104 STATIC void ifsbreakup(char *, struct arglist *);
105 STATIC void expandmeta(struct strlist *, int);
106 STATIC void expmeta(char *, char *);
107 STATIC void addfname(char *);
108 STATIC struct strlist *expsort(struct strlist *);
109 STATIC struct strlist *msort(struct strlist *, int);
110 STATIC int pmatch(char *, char *, int);
111 STATIC char *cvtnum(int, char *);
112 STATIC int collate_range_cmp(int, int);
113
114 STATIC int
115 collate_range_cmp(int c1, int c2)
116 {
117         static char s1[2], s2[2];
118
119         s1[0] = c1;
120         s2[0] = c2;
121         return (strcoll(s1, s2));
122 }
123
124 extern int oexitstatus;
125
126 /*
127  * Expand shell variables and backquotes inside a here document.
128  *      union node *arg         the document
129  *      int fd;                 where to write the expanded version
130  */
131
132 void
133 expandhere(union node *arg, int fd)
134 {
135         herefd = fd;
136         expandarg(arg, NULL, 0);
137         xwrite(fd, stackblock(), expdest - stackblock());
138 }
139
140
141 /*
142  * Perform variable substitution and command substitution on an argument,
143  * placing the resulting list of arguments in arglist.  If EXP_FULL is true,
144  * perform splitting and file name expansion.  When arglist is NULL, perform
145  * here document expansion.
146  */
147
148 void
149 expandarg(union node *arg, struct arglist *arglist, int flag)
150 {
151         struct strlist *sp;
152         char *p;
153
154         argbackq = arg->narg.backquote;
155         STARTSTACKSTR(expdest);
156         ifsfirst.next = NULL;
157         ifslastp = NULL;
158         argstr(arg->narg.text, flag);
159         if (arglist == NULL) {
160                 return;                 /* here document expanded */
161         }
162         STPUTC('\0', expdest);
163         p = grabstackstr(expdest);
164         exparg.lastp = &exparg.list;
165         /*
166          * TODO - EXP_REDIR
167          */
168         if (flag & EXP_FULL) {
169                 ifsbreakup(p, &exparg);
170                 *exparg.lastp = NULL;
171                 exparg.lastp = &exparg.list;
172                 expandmeta(exparg.list, flag);
173         } else {
174                 if (flag & EXP_REDIR) /*XXX - for now, just remove escapes */
175                         rmescapes(p);
176                 sp = (struct strlist *)stalloc(sizeof (struct strlist));
177                 sp->text = p;
178                 *exparg.lastp = sp;
179                 exparg.lastp = &sp->next;
180         }
181         while (ifsfirst.next != NULL) {
182                 struct ifsregion *ifsp;
183                 INTOFF;
184                 ifsp = ifsfirst.next->next;
185                 ckfree(ifsfirst.next);
186                 ifsfirst.next = ifsp;
187                 INTON;
188         }
189         *exparg.lastp = NULL;
190         if (exparg.list) {
191                 *arglist->lastp = exparg.list;
192                 arglist->lastp = exparg.lastp;
193         }
194 }
195
196
197
198 /*
199  * Perform variable and command substitution.  If EXP_FULL is set, output CTLESC
200  * characters to allow for further processing.  Otherwise treat
201  * $@ like $* since no splitting will be performed.
202  */
203
204 STATIC void
205 argstr(char *p, int flag)
206 {
207         char c;
208         int quotes = flag & (EXP_FULL | EXP_CASE | EXP_REDIR);  /* do CTLESC */
209         int firsteq = 1;
210
211         if (*p == '~' && (flag & (EXP_TILDE | EXP_VARTILDE)))
212                 p = exptilde(p, flag);
213         for (;;) {
214                 switch (c = *p++) {
215                 case '\0':
216                 case CTLENDVAR: /* ??? */
217                         goto breakloop;
218                 case CTLQUOTEMARK:
219                         /* "$@" syntax adherence hack */
220                         if (p[0] == CTLVAR && p[2] == '@' && p[3] == '=')
221                                 break;
222                         if ((flag & EXP_FULL) != 0)
223                                 STPUTC(c, expdest);
224                         break;
225                 case CTLESC:
226                         if (quotes)
227                                 STPUTC(c, expdest);
228                         c = *p++;
229                         STPUTC(c, expdest);
230                         break;
231                 case CTLVAR:
232                         p = evalvar(p, flag);
233                         break;
234                 case CTLBACKQ:
235                 case CTLBACKQ|CTLQUOTE:
236                         expbackq(argbackq->n, c & CTLQUOTE, flag);
237                         argbackq = argbackq->next;
238                         break;
239                 case CTLENDARI:
240                         expari(flag);
241                         break;
242                 case ':':
243                 case '=':
244                         /*
245                          * sort of a hack - expand tildes in variable
246                          * assignments (after the first '=' and after ':'s).
247                          */
248                         STPUTC(c, expdest);
249                         if (flag & EXP_VARTILDE && *p == '~') {
250                                 if (c == '=') {
251                                         if (firsteq)
252                                                 firsteq = 0;
253                                         else
254                                                 break;
255                                 }
256                                 p = exptilde(p, flag);
257                         }
258                         break;
259                 default:
260                         STPUTC(c, expdest);
261                 }
262         }
263 breakloop:;
264 }
265
266 STATIC char *
267 exptilde(char *p, int flag)
268 {
269         char c, *startp = p;
270         struct passwd *pw;
271         char *home;
272         int quotes = flag & (EXP_FULL | EXP_CASE | EXP_REDIR);
273
274         while ((c = *p) != '\0') {
275                 switch(c) {
276                 case CTLESC:
277                         return (startp);
278                 case CTLQUOTEMARK:
279                         return (startp);
280                 case ':':
281                         if (flag & EXP_VARTILDE)
282                                 goto done;
283                         break;
284                 case '/':
285                         goto done;
286                 }
287                 p++;
288         }
289 done:
290         *p = '\0';
291         if (*(startp+1) == '\0') {
292                 if ((home = lookupvar("HOME")) == NULL)
293                         goto lose;
294         } else {
295                 if ((pw = getpwnam(startp+1)) == NULL)
296                         goto lose;
297                 home = pw->pw_dir;
298         }
299         if (*home == '\0')
300                 goto lose;
301         *p = c;
302         while ((c = *home++) != '\0') {
303                 if (quotes && SQSYNTAX[(int)c] == CCTL)
304                         STPUTC(CTLESC, expdest);
305                 STPUTC(c, expdest);
306         }
307         return (p);
308 lose:
309         *p = c;
310         return (startp);
311 }
312
313
314 STATIC void
315 removerecordregions(int endoff)
316 {
317         if (ifslastp == NULL)
318                 return;
319
320         if (ifsfirst.endoff > endoff) {
321                 while (ifsfirst.next != NULL) {
322                         struct ifsregion *ifsp;
323                         INTOFF;
324                         ifsp = ifsfirst.next->next;
325                         ckfree(ifsfirst.next);
326                         ifsfirst.next = ifsp;
327                         INTON;
328                 }
329                 if (ifsfirst.begoff > endoff)
330                         ifslastp = NULL;
331                 else {
332                         ifslastp = &ifsfirst;
333                         ifsfirst.endoff = endoff;
334                 }
335                 return;
336         }
337
338         ifslastp = &ifsfirst;
339         while (ifslastp->next && ifslastp->next->begoff < endoff)
340                 ifslastp=ifslastp->next;
341         while (ifslastp->next != NULL) {
342                 struct ifsregion *ifsp;
343                 INTOFF;
344                 ifsp = ifslastp->next->next;
345                 ckfree(ifslastp->next);
346                 ifslastp->next = ifsp;
347                 INTON;
348         }
349         if (ifslastp->endoff > endoff)
350                 ifslastp->endoff = endoff;
351 }
352
353 /*
354  * Expand arithmetic expression.  Backup to start of expression,
355  * evaluate, place result in (backed up) result, adjust string position.
356  */
357 void
358 expari(int flag)
359 {
360         char *p, *start;
361         int result;
362         int begoff;
363         int quotes = flag & (EXP_FULL | EXP_CASE | EXP_REDIR);
364         int quoted;
365
366
367         /*
368          * This routine is slightly over-complicated for
369          * efficiency.  First we make sure there is
370          * enough space for the result, which may be bigger
371          * than the expression if we add exponentiation.  Next we
372          * scan backwards looking for the start of arithmetic.  If the
373          * next previous character is a CTLESC character, then we
374          * have to rescan starting from the beginning since CTLESC
375          * characters have to be processed left to right.
376          */
377 #if INT_MAX / 1000000000 >= 10 || INT_MIN / 1000000000 <= -10
378 #error "integers with more than 10 digits are not supported"
379 #endif
380         CHECKSTRSPACE(12 - 2, expdest);
381         USTPUTC('\0', expdest);
382         start = stackblock();
383         p = expdest - 2;
384         while (p >= start && *p != CTLARI)
385                 --p;
386         if (p < start || *p != CTLARI)
387                 error("missing CTLARI (shouldn't happen)");
388         if (p > start && *(p - 1) == CTLESC)
389                 for (p = start; *p != CTLARI; p++)
390                         if (*p == CTLESC)
391                                 p++;
392
393         if (p[1] == '"')
394                 quoted=1;
395         else
396                 quoted=0;
397         begoff = p - start;
398         removerecordregions(begoff);
399         if (quotes)
400                 rmescapes(p+2);
401         result = arith(p+2);
402         fmtstr(p, 12, "%d", result);
403         while (*p++)
404                 ;
405         if (quoted == 0)
406                 recordregion(begoff, p - 1 - start, 0);
407         result = expdest - p + 1;
408         STADJUST(-result, expdest);
409 }
410
411
412 /*
413  * Expand stuff in backwards quotes.
414  */
415
416 STATIC void
417 expbackq(union node *cmd, int quoted, int flag)
418 {
419         struct backcmd in;
420         int i;
421         char buf[128];
422         char *p;
423         char *dest = expdest;
424         struct ifsregion saveifs, *savelastp;
425         struct nodelist *saveargbackq;
426         char lastc;
427         int startloc = dest - stackblock();
428         char const *syntax = quoted? DQSYNTAX : BASESYNTAX;
429         int saveherefd;
430         int quotes = flag & (EXP_FULL | EXP_CASE | EXP_REDIR);
431         int nnl;
432
433         INTOFF;
434         saveifs = ifsfirst;
435         savelastp = ifslastp;
436         saveargbackq = argbackq;
437         saveherefd = herefd;
438         herefd = -1;
439         p = grabstackstr(dest);
440         evalbackcmd(cmd, &in);
441         ungrabstackstr(p, dest);
442         ifsfirst = saveifs;
443         ifslastp = savelastp;
444         argbackq = saveargbackq;
445         herefd = saveherefd;
446
447         p = in.buf;
448         lastc = '\0';
449         nnl = 0;
450         /* Don't copy trailing newlines */
451         for (;;) {
452                 if (--in.nleft < 0) {
453                         if (in.fd < 0)
454                                 break;
455                         while ((i = read(in.fd, buf, sizeof buf)) < 0 && errno == EINTR);
456                         TRACE(("expbackq: read returns %d\n", i));
457                         if (i <= 0)
458                                 break;
459                         p = buf;
460                         in.nleft = i - 1;
461                 }
462                 lastc = *p++;
463                 if (lastc != '\0') {
464                         if (quotes && syntax[(int)lastc] == CCTL)
465                                 STPUTC(CTLESC, dest);
466                         if (lastc == '\n') {
467                                 nnl++;
468                         } else {
469                                 while (nnl > 0) {
470                                         nnl--;
471                                         STPUTC('\n', dest);
472                                 }
473                                 STPUTC(lastc, dest);
474                         }
475                 }
476         }
477
478         if (in.fd >= 0)
479                 close(in.fd);
480         if (in.buf)
481                 ckfree(in.buf);
482         if (in.jp)
483                 exitstatus = waitforjob(in.jp, NULL);
484         if (quoted == 0)
485                 recordregion(startloc, dest - stackblock(), 0);
486         TRACE(("evalbackq: size=%d: \"%.*s\"\n",
487                 (dest - stackblock()) - startloc,
488                 (dest - stackblock()) - startloc,
489                 stackblock() + startloc));
490         expdest = dest;
491         INTON;
492 }
493
494
495
496 STATIC int
497 subevalvar(char *p, char *str, int strloc, int subtype, int startloc,
498   int varflags)
499 {
500         char *startp;
501         char *loc = NULL;
502         char *q;
503         int c = 0;
504         int saveherefd = herefd;
505         struct nodelist *saveargbackq = argbackq;
506         int amount;
507
508         herefd = -1;
509         argstr(p, 0);
510         STACKSTRNUL(expdest);
511         herefd = saveherefd;
512         argbackq = saveargbackq;
513         startp = stackblock() + startloc;
514         if (str == NULL)
515             str = stackblock() + strloc;
516
517         switch (subtype) {
518         case VSASSIGN:
519                 setvar(str, startp, 0);
520                 amount = startp - expdest;
521                 STADJUST(amount, expdest);
522                 varflags &= ~VSNUL;
523                 if (c != 0)
524                         *loc = c;
525                 return 1;
526
527         case VSQUESTION:
528                 if (*p != CTLENDVAR) {
529                         outfmt(&errout, "%s\n", startp);
530                         error(NULL);
531                 }
532                 error("%.*s: parameter %snot set", (int)(p - str - 1),
533                       str, (varflags & VSNUL) ? "null or "
534                                               : nullstr);
535                 return 0;
536
537         case VSTRIMLEFT:
538                 for (loc = startp; loc < str; loc++) {
539                         c = *loc;
540                         *loc = '\0';
541                         if (patmatch(str, startp, varflags & VSQUOTE)) {
542                                 *loc = c;
543                                 goto recordleft;
544                         }
545                         *loc = c;
546                         if ((varflags & VSQUOTE) && *loc == CTLESC)
547                                 loc++;
548                 }
549                 return 0;
550
551         case VSTRIMLEFTMAX:
552                 for (loc = str - 1; loc >= startp;) {
553                         c = *loc;
554                         *loc = '\0';
555                         if (patmatch(str, startp, varflags & VSQUOTE)) {
556                                 *loc = c;
557                                 goto recordleft;
558                         }
559                         *loc = c;
560                         loc--;
561                         if ((varflags & VSQUOTE) && loc > startp &&
562                             *(loc - 1) == CTLESC) {
563                                 for (q = startp; q < loc; q++)
564                                         if (*q == CTLESC)
565                                                 q++;
566                                 if (q > loc)
567                                         loc--;
568                         }
569                 }
570                 return 0;
571
572         case VSTRIMRIGHT:
573                 for (loc = str - 1; loc >= startp;) {
574                         if (patmatch(str, loc, varflags & VSQUOTE)) {
575                                 amount = loc - expdest;
576                                 STADJUST(amount, expdest);
577                                 return 1;
578                         }
579                         loc--;
580                         if ((varflags & VSQUOTE) && loc > startp &&
581                             *(loc - 1) == CTLESC) {
582                                 for (q = startp; q < loc; q++)
583                                         if (*q == CTLESC)
584                                                 q++;
585                                 if (q > loc)
586                                         loc--;
587                         }
588                 }
589                 return 0;
590
591         case VSTRIMRIGHTMAX:
592                 for (loc = startp; loc < str - 1; loc++) {
593                         if (patmatch(str, loc, varflags & VSQUOTE)) {
594                                 amount = loc - expdest;
595                                 STADJUST(amount, expdest);
596                                 return 1;
597                         }
598                         if ((varflags & VSQUOTE) && *loc == CTLESC)
599                                 loc++;
600                 }
601                 return 0;
602
603
604         default:
605                 abort();
606         }
607
608 recordleft:
609         amount = ((str - 1) - (loc - startp)) - expdest;
610         STADJUST(amount, expdest);
611         while (loc != str - 1)
612                 *startp++ = *loc++;
613         return 1;
614 }
615
616
617 /*
618  * Expand a variable, and return a pointer to the next character in the
619  * input string.
620  */
621
622 STATIC char *
623 evalvar(char *p, int flag)
624 {
625         int subtype;
626         int varflags;
627         char *var;
628         char *val;
629         int patloc;
630         int c;
631         int set;
632         int special;
633         int startloc;
634         int varlen;
635         int easy;
636         int quotes = flag & (EXP_FULL | EXP_CASE | EXP_REDIR);
637
638         varflags = (unsigned char)*p++;
639         subtype = varflags & VSTYPE;
640         var = p;
641         special = 0;
642         if (! is_name(*p))
643                 special = 1;
644         p = strchr(p, '=') + 1;
645 again: /* jump here after setting a variable with ${var=text} */
646         if (varflags & VSLINENO) {
647                 set = 1;
648                 special = 0;
649                 val = var;
650                 p[-1] = '\0';   /* temporarily overwrite '=' to have \0
651                                    terminated string */
652         } else if (special) {
653                 set = varisset(var, varflags & VSNUL);
654                 val = NULL;
655         } else {
656                 val = bltinlookup(var, 1);
657                 if (val == NULL || ((varflags & VSNUL) && val[0] == '\0')) {
658                         val = NULL;
659                         set = 0;
660                 } else
661                         set = 1;
662         }
663         varlen = 0;
664         startloc = expdest - stackblock();
665         if (!set && uflag) {
666                 switch (subtype) {
667                 case VSNORMAL:
668                 case VSTRIMLEFT:
669                 case VSTRIMLEFTMAX:
670                 case VSTRIMRIGHT:
671                 case VSTRIMRIGHTMAX:
672                 case VSLENGTH:
673                         error("%.*s: parameter not set", (int)(p - var - 1),
674                             var);
675                 }
676         }
677         if (set && subtype != VSPLUS) {
678                 /* insert the value of the variable */
679                 if (special) {
680                         varvalue(var, varflags & VSQUOTE, subtype, flag);
681                         if (subtype == VSLENGTH) {
682                                 varlen = expdest - stackblock() - startloc;
683                                 STADJUST(-varlen, expdest);
684                         }
685                 } else {
686                         char const *syntax = (varflags & VSQUOTE) ? DQSYNTAX
687                                                                   : BASESYNTAX;
688
689                         if (subtype == VSLENGTH) {
690                                 for (;*val; val++)
691                                         varlen++;
692                         }
693                         else {
694                                 while (*val) {
695                                         if (quotes &&
696                                             syntax[(int)*val] == CCTL)
697                                                 STPUTC(CTLESC, expdest);
698                                         STPUTC(*val++, expdest);
699                                 }
700
701                         }
702                 }
703         }
704
705         if (subtype == VSPLUS)
706                 set = ! set;
707
708         easy = ((varflags & VSQUOTE) == 0 ||
709                 (*var == '@' && shellparam.nparam != 1));
710
711
712         switch (subtype) {
713         case VSLENGTH:
714                 expdest = cvtnum(varlen, expdest);
715                 goto record;
716
717         case VSNORMAL:
718                 if (!easy)
719                         break;
720 record:
721                 recordregion(startloc, expdest - stackblock(),
722                              varflags & VSQUOTE);
723                 break;
724
725         case VSPLUS:
726         case VSMINUS:
727                 if (!set) {
728                         argstr(p, flag);
729                         break;
730                 }
731                 if (easy)
732                         goto record;
733                 break;
734
735         case VSTRIMLEFT:
736         case VSTRIMLEFTMAX:
737         case VSTRIMRIGHT:
738         case VSTRIMRIGHTMAX:
739                 if (!set)
740                         break;
741                 /*
742                  * Terminate the string and start recording the pattern
743                  * right after it
744                  */
745                 STPUTC('\0', expdest);
746                 patloc = expdest - stackblock();
747                 if (subevalvar(p, NULL, patloc, subtype,
748                                startloc, varflags) == 0) {
749                         int amount = (expdest - stackblock() - patloc) + 1;
750                         STADJUST(-amount, expdest);
751                 }
752                 /* Remove any recorded regions beyond start of variable */
753                 removerecordregions(startloc);
754                 goto record;
755
756         case VSASSIGN:
757         case VSQUESTION:
758                 if (!set) {
759                         if (subevalvar(p, var, 0, subtype, startloc, varflags)) {
760                                 varflags &= ~VSNUL;
761                                 /*
762                                  * Remove any recorded regions beyond
763                                  * start of variable
764                                  */
765                                 removerecordregions(startloc);
766                                 goto again;
767                         }
768                         break;
769                 }
770                 if (easy)
771                         goto record;
772                 break;
773
774         case VSERROR:
775                 c = p - var - 1;
776                 error("${%.*s%s}: Bad substitution", c, var,
777                     (c > 0 && *p != CTLENDVAR) ? "..." : "");
778
779         default:
780                 abort();
781         }
782         p[-1] = '=';    /* recover overwritten '=' */
783
784         if (subtype != VSNORMAL) {      /* skip to end of alternative */
785                 int nesting = 1;
786                 for (;;) {
787                         if ((c = *p++) == CTLESC)
788                                 p++;
789                         else if (c == CTLBACKQ || c == (CTLBACKQ|CTLQUOTE)) {
790                                 if (set)
791                                         argbackq = argbackq->next;
792                         } else if (c == CTLVAR) {
793                                 if ((*p++ & VSTYPE) != VSNORMAL)
794                                         nesting++;
795                         } else if (c == CTLENDVAR) {
796                                 if (--nesting == 0)
797                                         break;
798                         }
799                 }
800         }
801         return p;
802 }
803
804
805
806 /*
807  * Test whether a specialized variable is set.
808  */
809
810 STATIC int
811 varisset(char *name, int nulok)
812 {
813
814         if (*name == '!')
815                 return backgndpid != -1;
816         else if (*name == '@' || *name == '*') {
817                 if (*shellparam.p == NULL)
818                         return 0;
819
820                 if (nulok) {
821                         char **av;
822
823                         for (av = shellparam.p; *av; av++)
824                                 if (**av != '\0')
825                                         return 1;
826                         return 0;
827                 }
828         } else if (is_digit(*name)) {
829                 char *ap;
830                 int num = atoi(name);
831
832                 if (num > shellparam.nparam)
833                         return 0;
834
835                 if (num == 0)
836                         ap = arg0;
837                 else
838                         ap = shellparam.p[num - 1];
839
840                 if (nulok && (ap == NULL || *ap == '\0'))
841                         return 0;
842         }
843         return 1;
844 }
845
846
847
848 /*
849  * Add the value of a specialized variable to the stack string.
850  */
851
852 STATIC void
853 varvalue(char *name, int quoted, int subtype, int flag)
854 {
855         int num;
856         char *p;
857         int i;
858         char sep;
859         char **ap;
860         char const *syntax;
861
862 #define STRTODEST(p) \
863         do {\
864         if (flag & (EXP_FULL | EXP_CASE) && subtype != VSLENGTH) { \
865                 syntax = quoted? DQSYNTAX : BASESYNTAX; \
866                 while (*p) { \
867                         if (syntax[(int)*p] == CCTL) \
868                                 STPUTC(CTLESC, expdest); \
869                         STPUTC(*p++, expdest); \
870                 } \
871         } else \
872                 while (*p) \
873                         STPUTC(*p++, expdest); \
874         } while (0)
875
876
877         switch (*name) {
878         case '$':
879                 num = rootpid;
880                 goto numvar;
881         case '?':
882                 num = oexitstatus;
883                 goto numvar;
884         case '#':
885                 num = shellparam.nparam;
886                 goto numvar;
887         case '!':
888                 num = backgndpid;
889 numvar:
890                 expdest = cvtnum(num, expdest);
891                 break;
892         case '-':
893                 for (i = 0 ; i < NOPTS ; i++) {
894                         if (optlist[i].val)
895                                 STPUTC(optlist[i].letter, expdest);
896                 }
897                 break;
898         case '@':
899                 if (flag & EXP_FULL && quoted) {
900                         for (ap = shellparam.p ; (p = *ap++) != NULL ; ) {
901                                 STRTODEST(p);
902                                 if (*ap)
903                                         STPUTC('\0', expdest);
904                         }
905                         break;
906                 }
907                 /* FALLTHROUGH */
908         case '*':
909                 if (ifsset())
910                         sep = ifsval()[0];
911                 else
912                         sep = ' ';
913                 for (ap = shellparam.p ; (p = *ap++) != NULL ; ) {
914                         STRTODEST(p);
915                         if (*ap && sep)
916                                 STPUTC(sep, expdest);
917                 }
918                 break;
919         case '0':
920                 p = arg0;
921                 STRTODEST(p);
922                 break;
923         default:
924                 if (is_digit(*name)) {
925                         num = atoi(name);
926                         if (num > 0 && num <= shellparam.nparam) {
927                                 p = shellparam.p[num - 1];
928                                 STRTODEST(p);
929                         }
930                 }
931                 break;
932         }
933 }
934
935
936
937 /*
938  * Record the the fact that we have to scan this region of the
939  * string for IFS characters.
940  */
941
942 STATIC void
943 recordregion(int start, int end, int nulonly)
944 {
945         struct ifsregion *ifsp;
946
947         if (ifslastp == NULL) {
948                 ifsp = &ifsfirst;
949         } else {
950                 ifsp = (struct ifsregion *)ckmalloc(sizeof (struct ifsregion));
951                 ifslastp->next = ifsp;
952         }
953         ifslastp = ifsp;
954         ifslastp->next = NULL;
955         ifslastp->begoff = start;
956         ifslastp->endoff = end;
957         ifslastp->nulonly = nulonly;
958 }
959
960
961
962 /*
963  * Break the argument string into pieces based upon IFS and add the
964  * strings to the argument list.  The regions of the string to be
965  * searched for IFS characters have been stored by recordregion.
966  */
967 STATIC void
968 ifsbreakup(char *string, struct arglist *arglist)
969 {
970         struct ifsregion *ifsp;
971         struct strlist *sp;
972         char *start;
973         char *p;
974         char *q;
975         const char *ifs;
976         int ifsspc;
977         int nulonly;
978
979
980         start = string;
981         ifsspc = 0;
982         nulonly = 0;
983         if (ifslastp != NULL) {
984                 ifsp = &ifsfirst;
985                 do {
986                         p = string + ifsp->begoff;
987                         nulonly = ifsp->nulonly;
988                         ifs = nulonly ? nullstr :
989                                 ( ifsset() ? ifsval() : " \t\n" );
990                         ifsspc = 0;
991                         while (p < string + ifsp->endoff) {
992                                 q = p;
993                                 if (*p == CTLESC)
994                                         p++;
995                                 if (strchr(ifs, *p)) {
996                                         if (!nulonly)
997                                                 ifsspc = (strchr(" \t\n", *p) != NULL);
998                                         /* Ignore IFS whitespace at start */
999                                         if (q == start && ifsspc) {
1000                                                 p++;
1001                                                 start = p;
1002                                                 continue;
1003                                         }
1004                                         *q = '\0';
1005                                         sp = (struct strlist *)stalloc(sizeof *sp);
1006                                         sp->text = start;
1007                                         *arglist->lastp = sp;
1008                                         arglist->lastp = &sp->next;
1009                                         p++;
1010                                         if (!nulonly) {
1011                                                 for (;;) {
1012                                                         if (p >= string + ifsp->endoff) {
1013                                                                 break;
1014                                                         }
1015                                                         q = p;
1016                                                         if (*p == CTLESC)
1017                                                                 p++;
1018                                                         if (strchr(ifs, *p) == NULL ) {
1019                                                                 p = q;
1020                                                                 break;
1021                                                         } else if (strchr(" \t\n",*p) == NULL) {
1022                                                                 if (ifsspc) {
1023                                                                         p++;
1024                                                                         ifsspc = 0;
1025                                                                 } else {
1026                                                                         p = q;
1027                                                                         break;
1028                                                                 }
1029                                                         } else
1030                                                                 p++;
1031                                                 }
1032                                         }
1033                                         start = p;
1034                                 } else
1035                                         p++;
1036                         }
1037                 } while ((ifsp = ifsp->next) != NULL);
1038                 if (*start || (!ifsspc && start > string)) {
1039                         sp = (struct strlist *)stalloc(sizeof *sp);
1040                         sp->text = start;
1041                         *arglist->lastp = sp;
1042                         arglist->lastp = &sp->next;
1043                 }
1044         } else {
1045                 sp = (struct strlist *)stalloc(sizeof *sp);
1046                 sp->text = start;
1047                 *arglist->lastp = sp;
1048                 arglist->lastp = &sp->next;
1049         }
1050 }
1051
1052
1053
1054 /*
1055  * Expand shell metacharacters.  At this point, the only control characters
1056  * should be escapes.  The results are stored in the list exparg.
1057  */
1058
1059 STATIC char *expdir;
1060
1061
1062 STATIC void
1063 expandmeta(struct strlist *str, int flag __unused)
1064 {
1065         char *p;
1066         struct strlist **savelastp;
1067         struct strlist *sp;
1068         char c;
1069         /* TODO - EXP_REDIR */
1070
1071         while (str) {
1072                 if (fflag)
1073                         goto nometa;
1074                 p = str->text;
1075                 for (;;) {                      /* fast check for meta chars */
1076                         if ((c = *p++) == '\0')
1077                                 goto nometa;
1078                         if (c == '*' || c == '?' || c == '[' || c == '!')
1079                                 break;
1080                 }
1081                 savelastp = exparg.lastp;
1082                 INTOFF;
1083                 if (expdir == NULL) {
1084                         int i = strlen(str->text);
1085                         expdir = ckmalloc(i < 2048 ? 2048 : i); /* XXX */
1086                 }
1087
1088                 expmeta(expdir, str->text);
1089                 ckfree(expdir);
1090                 expdir = NULL;
1091                 INTON;
1092                 if (exparg.lastp == savelastp) {
1093                         /*
1094                          * no matches
1095                          */
1096 nometa:
1097                         *exparg.lastp = str;
1098                         rmescapes(str->text);
1099                         exparg.lastp = &str->next;
1100                 } else {
1101                         *exparg.lastp = NULL;
1102                         *savelastp = sp = expsort(*savelastp);
1103                         while (sp->next != NULL)
1104                                 sp = sp->next;
1105                         exparg.lastp = &sp->next;
1106                 }
1107                 str = str->next;
1108         }
1109 }
1110
1111
1112 /*
1113  * Do metacharacter (i.e. *, ?, [...]) expansion.
1114  */
1115
1116 STATIC void
1117 expmeta(char *enddir, char *name)
1118 {
1119         char *p;
1120         const char *q;
1121         char *start;
1122         char *endname;
1123         int metaflag;
1124         struct stat statb;
1125         DIR *dirp;
1126         struct dirent *dp;
1127         int atend;
1128         int matchdot;
1129
1130         metaflag = 0;
1131         start = name;
1132         for (p = name ; ; p++) {
1133                 if (*p == '*' || *p == '?')
1134                         metaflag = 1;
1135                 else if (*p == '[') {
1136                         q = p + 1;
1137                         if (*q == '!' || *q == '^')
1138                                 q++;
1139                         for (;;) {
1140                                 while (*q == CTLQUOTEMARK)
1141                                         q++;
1142                                 if (*q == CTLESC)
1143                                         q++;
1144                                 if (*q == '/' || *q == '\0')
1145                                         break;
1146                                 if (*++q == ']') {
1147                                         metaflag = 1;
1148                                         break;
1149                                 }
1150                         }
1151                 } else if (*p == '!' && p[1] == '!'     && (p == name || p[-1] == '/')) {
1152                         metaflag = 1;
1153                 } else if (*p == '\0')
1154                         break;
1155                 else if (*p == CTLQUOTEMARK)
1156                         continue;
1157                 else if (*p == CTLESC)
1158                         p++;
1159                 if (*p == '/') {
1160                         if (metaflag)
1161                                 break;
1162                         start = p + 1;
1163                 }
1164         }
1165         if (metaflag == 0) {    /* we've reached the end of the file name */
1166                 if (enddir != expdir)
1167                         metaflag++;
1168                 for (p = name ; ; p++) {
1169                         if (*p == CTLQUOTEMARK)
1170                                 continue;
1171                         if (*p == CTLESC)
1172                                 p++;
1173                         *enddir++ = *p;
1174                         if (*p == '\0')
1175                                 break;
1176                 }
1177                 if (metaflag == 0 || lstat(expdir, &statb) >= 0)
1178                         addfname(expdir);
1179                 return;
1180         }
1181         endname = p;
1182         if (start != name) {
1183                 p = name;
1184                 while (p < start) {
1185                         while (*p == CTLQUOTEMARK)
1186                                 p++;
1187                         if (*p == CTLESC)
1188                                 p++;
1189                         *enddir++ = *p++;
1190                 }
1191         }
1192         if (enddir == expdir) {
1193                 q = ".";
1194         } else if (enddir == expdir + 1 && *expdir == '/') {
1195                 q = "/";
1196         } else {
1197                 q = expdir;
1198                 enddir[-1] = '\0';
1199         }
1200         if ((dirp = opendir(q)) == NULL)
1201                 return;
1202         if (enddir != expdir)
1203                 enddir[-1] = '/';
1204         if (*endname == 0) {
1205                 atend = 1;
1206         } else {
1207                 atend = 0;
1208                 *endname++ = '\0';
1209         }
1210         matchdot = 0;
1211         p = start;
1212         while (*p == CTLQUOTEMARK)
1213                 p++;
1214         if (*p == CTLESC)
1215                 p++;
1216         if (*p == '.')
1217                 matchdot++;
1218         while (! int_pending() && (dp = readdir(dirp)) != NULL) {
1219                 if (dp->d_name[0] == '.' && ! matchdot)
1220                         continue;
1221                 if (patmatch(start, dp->d_name, 0)) {
1222                         if (atend) {
1223                                 scopy(dp->d_name, enddir);
1224                                 addfname(expdir);
1225                         } else {
1226                                 char *t;
1227                                 for (t = enddir, q = dp->d_name;
1228                                      (*t++ = *q++) != '\0';)
1229                                         continue;
1230                                 t[-1] = '/';
1231                                 expmeta(t, endname);
1232                         }
1233                 }
1234         }
1235         closedir(dirp);
1236         if (! atend)
1237                 endname[-1] = '/';
1238 }
1239
1240
1241 /*
1242  * Add a file name to the list.
1243  */
1244
1245 STATIC void
1246 addfname(char *name)
1247 {
1248         char *p;
1249         struct strlist *sp;
1250
1251         p = stalloc(strlen(name) + 1);
1252         scopy(name, p);
1253         sp = (struct strlist *)stalloc(sizeof *sp);
1254         sp->text = p;
1255         *exparg.lastp = sp;
1256         exparg.lastp = &sp->next;
1257 }
1258
1259
1260 /*
1261  * Sort the results of file name expansion.  It calculates the number of
1262  * strings to sort and then calls msort (short for merge sort) to do the
1263  * work.
1264  */
1265
1266 STATIC struct strlist *
1267 expsort(struct strlist *str)
1268 {
1269         int len;
1270         struct strlist *sp;
1271
1272         len = 0;
1273         for (sp = str ; sp ; sp = sp->next)
1274                 len++;
1275         return msort(str, len);
1276 }
1277
1278
1279 STATIC struct strlist *
1280 msort(struct strlist *list, int len)
1281 {
1282         struct strlist *p, *q = NULL;
1283         struct strlist **lpp;
1284         int half;
1285         int n;
1286
1287         if (len <= 1)
1288                 return list;
1289         half = len >> 1;
1290         p = list;
1291         for (n = half ; --n >= 0 ; ) {
1292                 q = p;
1293                 p = p->next;
1294         }
1295         q->next = NULL;                 /* terminate first half of list */
1296         q = msort(list, half);          /* sort first half of list */
1297         p = msort(p, len - half);               /* sort second half */
1298         lpp = &list;
1299         for (;;) {
1300                 if (strcmp(p->text, q->text) < 0) {
1301                         *lpp = p;
1302                         lpp = &p->next;
1303                         if ((p = *lpp) == NULL) {
1304                                 *lpp = q;
1305                                 break;
1306                         }
1307                 } else {
1308                         *lpp = q;
1309                         lpp = &q->next;
1310                         if ((q = *lpp) == NULL) {
1311                                 *lpp = p;
1312                                 break;
1313                         }
1314                 }
1315         }
1316         return list;
1317 }
1318
1319
1320
1321 /*
1322  * Returns true if the pattern matches the string.
1323  */
1324
1325 int
1326 patmatch(char *pattern, char *string, int squoted)
1327 {
1328 #ifdef notdef
1329         if (pattern[0] == '!' && pattern[1] == '!')
1330                 return 1 - pmatch(pattern + 2, string);
1331         else
1332 #endif
1333                 return pmatch(pattern, string, squoted);
1334 }
1335
1336
1337 STATIC int
1338 pmatch(char *pattern, char *string, int squoted)
1339 {
1340         char *p, *q;
1341         char c;
1342
1343         p = pattern;
1344         q = string;
1345         for (;;) {
1346                 switch (c = *p++) {
1347                 case '\0':
1348                         goto breakloop;
1349                 case CTLESC:
1350                         if (squoted && *q == CTLESC)
1351                                 q++;
1352                         if (*q++ != *p++)
1353                                 return 0;
1354                         break;
1355                 case CTLQUOTEMARK:
1356                         continue;
1357                 case '?':
1358                         if (squoted && *q == CTLESC)
1359                                 q++;
1360                         if (*q++ == '\0')
1361                                 return 0;
1362                         break;
1363                 case '*':
1364                         c = *p;
1365                         while (c == CTLQUOTEMARK || c == '*')
1366                                 c = *++p;
1367                         if (c != CTLESC &&  c != CTLQUOTEMARK &&
1368                             c != '?' && c != '*' && c != '[') {
1369                                 while (*q != c) {
1370                                         if (squoted && *q == CTLESC &&
1371                                             q[1] == c)
1372                                                 break;
1373                                         if (*q == '\0')
1374                                                 return 0;
1375                                         if (squoted && *q == CTLESC)
1376                                                 q++;
1377                                         q++;
1378                                 }
1379                         }
1380                         do {
1381                                 if (pmatch(p, q, squoted))
1382                                         return 1;
1383                                 if (squoted && *q == CTLESC)
1384                                         q++;
1385                         } while (*q++ != '\0');
1386                         return 0;
1387                 case '[': {
1388                         char *endp;
1389                         int invert, found;
1390                         char chr;
1391
1392                         endp = p;
1393                         if (*endp == '!' || *endp == '^')
1394                                 endp++;
1395                         for (;;) {
1396                                 while (*endp == CTLQUOTEMARK)
1397                                         endp++;
1398                                 if (*endp == '\0')
1399                                         goto dft;               /* no matching ] */
1400                                 if (*endp == CTLESC)
1401                                         endp++;
1402                                 if (*++endp == ']')
1403                                         break;
1404                         }
1405                         invert = 0;
1406                         if (*p == '!' || *p == '^') {
1407                                 invert++;
1408                                 p++;
1409                         }
1410                         found = 0;
1411                         chr = *q++;
1412                         if (squoted && chr == CTLESC)
1413                                 chr = *q++;
1414                         if (chr == '\0')
1415                                 return 0;
1416                         c = *p++;
1417                         do {
1418                                 if (c == CTLQUOTEMARK)
1419                                         continue;
1420                                 if (c == CTLESC)
1421                                         c = *p++;
1422                                 if (*p == '-' && p[1] != ']') {
1423                                         p++;
1424                                         while (*p == CTLQUOTEMARK)
1425                                                 p++;
1426                                         if (*p == CTLESC)
1427                                                 p++;
1428                                         if (   collate_range_cmp(chr, c) >= 0
1429                                             && collate_range_cmp(chr, *p) <= 0
1430                                            )
1431                                                 found = 1;
1432                                         p++;
1433                                 } else {
1434                                         if (chr == c)
1435                                                 found = 1;
1436                                 }
1437                         } while ((c = *p++) != ']');
1438                         if (found == invert)
1439                                 return 0;
1440                         break;
1441                 }
1442 dft:            default:
1443                         if (squoted && *q == CTLESC)
1444                                 q++;
1445                         if (*q++ != c)
1446                                 return 0;
1447                         break;
1448                 }
1449         }
1450 breakloop:
1451         if (*q != '\0')
1452                 return 0;
1453         return 1;
1454 }
1455
1456
1457
1458 /*
1459  * Remove any CTLESC characters from a string.
1460  */
1461
1462 void
1463 rmescapes(char *str)
1464 {
1465         char *p, *q;
1466
1467         p = str;
1468         while (*p != CTLESC && *p != CTLQUOTEMARK) {
1469                 if (*p++ == '\0')
1470                         return;
1471         }
1472         q = p;
1473         while (*p) {
1474                 if (*p == CTLQUOTEMARK) {
1475                         p++;
1476                         continue;
1477                 }
1478                 if (*p == CTLESC)
1479                         p++;
1480                 *q++ = *p++;
1481         }
1482         *q = '\0';
1483 }
1484
1485
1486
1487 /*
1488  * See if a pattern matches in a case statement.
1489  */
1490
1491 int
1492 casematch(union node *pattern, char *val)
1493 {
1494         struct stackmark smark;
1495         int result;
1496         char *p;
1497
1498         setstackmark(&smark);
1499         argbackq = pattern->narg.backquote;
1500         STARTSTACKSTR(expdest);
1501         ifslastp = NULL;
1502         argstr(pattern->narg.text, EXP_TILDE | EXP_CASE);
1503         STPUTC('\0', expdest);
1504         p = grabstackstr(expdest);
1505         result = patmatch(p, val, 0);
1506         popstackmark(&smark);
1507         return result;
1508 }
1509
1510 /*
1511  * Our own itoa().
1512  */
1513
1514 STATIC char *
1515 cvtnum(int num, char *buf)
1516 {
1517         char temp[32];
1518         int neg = num < 0;
1519         char *p = temp + 31;
1520
1521         temp[31] = '\0';
1522
1523         do {
1524                 *--p = num % 10 + '0';
1525         } while ((num /= 10) != 0);
1526
1527         if (neg)
1528                 *--p = '-';
1529
1530         while (*p)
1531                 STPUTC(*p++, buf);
1532         return buf;
1533 }
1534
1535 /*
1536  * Do most of the work for wordexp(3).
1537  */
1538
1539 int
1540 wordexpcmd(int argc, char **argv)
1541 {
1542         size_t len;
1543         int i;
1544
1545         out1fmt("%08x", argc - 1);
1546         for (i = 1, len = 0; i < argc; i++)
1547                 len += strlen(argv[i]);
1548         out1fmt("%08x", (int)len);
1549         for (i = 1; i < argc; i++) {
1550                 out1str(argv[i]);
1551                 out1c('\0');
1552         }
1553         return (0);
1554 }