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