src/expand.c

   1 /*-
   2  * Copyright (c) 1991, 1993
   3  *      The Regents of the University of California.  All rights reserved.
   4  * Copyright (c) 1997-2005
   5  *      Herbert Xu <herbert@gondor.apana.org.au>.  All rights reserved.
   6  *
   7  * This code is derived from software contributed to Berkeley by
   8  * Kenneth Almquist.
   9  *
  10  * Redistribution and use in source and binary forms, with or without
  11  * modification, are permitted provided that the following conditions
  12  * are met:
  13  * 1. Redistributions of source code must retain the above copyright
  14  *    notice, this list of conditions and the following disclaimer.
  15  * 2. Redistributions in binary form must reproduce the above copyright
  16  *    notice, this list of conditions and the following disclaimer in the
  17  *    documentation and/or other materials provided with the distribution.
  18  * 3. Neither the name of the University nor the names of its contributors
  19  *    may be used to endorse or promote products derived from this software
  20  *    without specific prior written permission.
  21  *
  22  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  23  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  24  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  25  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  26  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  27  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  28  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  29  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  30  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  31  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  32  * SUCH DAMAGE.
  33  */
  34
  35 #include <ctype.h>
  36 #include <dirent.h>
  37 #ifdef HAVE_FNMATCH
  38 #include <fnmatch.h>
  39 #endif
  40 #ifdef HAVE_GLOB
  41 #include <glob.h>
  42 #endif
  43 #include <inttypes.h>
  44 #include <limits.h>
  45 #ifdef HAVE_GETPWNAM
  46 #include <pwd.h>
  47 #endif
  48 #include <setjmp.h>
  49 #include <stdbool.h>
  50 #include <stdio.h>
  51 #include <stdlib.h>
  52 #include <string.h>
  53 #include <sys/types.h>
  54 #include <sys/time.h>
  55 #include <sys/stat.h>
  56 #include <unistd.h>
  57
  58 /*
  59  * Routines to expand arguments to commands.  We have to deal with
  60  * backquotes, shell variables, and file metacharacters.
  61  */
  62
  63 #include "error.h"
  64 #include "eval.h"
  65 #include "expand.h"
  66 #include "jobs.h"
  67 #include "main.h"
  68 #include "memalloc.h"
  69 #include "mystring.h"
  70 #include "nodes.h"
  71 #include "options.h"
  72 #include "output.h"
  73 #include "parser.h"
  74 #include "shell.h"
  75 #include "show.h"
  76 #include "syntax.h"
  77 #include "system.h"
  78 #include "var.h"
  79
  80 /*
  81  * _rmescape() flags
  82  */
  83 #define RMESCAPE_ALLOC  0x1     /* Allocate a new string */
  84 #define RMESCAPE_GLOB   0x2     /* Add backslashes for glob */
  85 #define RMESCAPE_GROW   0x8     /* Grow strings instead of stalloc */
  86 #define RMESCAPE_HEAP   0x10    /* Malloc strings instead of stalloc */
  87
  88 /* Add CTLESC when necessary. */
  89 #define QUOTES_ESC      (EXP_FULL | EXP_CASE)
  90
  91 /*
  92  * Structure specifying which parts of the string should be searched
  93  * for IFS characters.
  94  */
  95
  96 struct ifsregion {
  97         struct ifsregion *next; /* next region in list */
  98         int begoff;             /* offset of start of region */
  99         int endoff;             /* offset of end of region */
 100         int nulonly;            /* search for nul bytes only */
 101 };
 102
 103 /* output of current string */
 104 static char *expdest;
 105 /* list of back quote expressions */
 106 static struct nodelist *argbackq;
 107 /* first struct in list of ifs regions */
 108 static struct ifsregion ifsfirst;
 109 /* last struct in list */
 110 static struct ifsregion *ifslastp;
 111 /* holds expanded arg list */
 112 static struct arglist exparg;
 113
 114 static char *argstr(char *p, int flag);
 115 static char *exptilde(char *startp, int flag);
 116 static char *expari(char *start, int flag);
 117 STATIC void expbackq(union node *, int);
 118 STATIC char *evalvar(char *, int);
 119 static size_t strtodest(const char *p, int flags);
 120 static size_t memtodest(const char *p, size_t len, int flags);
 121 STATIC ssize_t varvalue(char *, int, int, int);
 122 STATIC void expandmeta(struct strlist *);
 123 static void addglob(const glob64_t *);
 124 static char *expmeta(char *, unsigned, size_t);
 125 STATIC struct strlist *expsort(struct strlist *);
 126 STATIC struct strlist *msort(struct strlist *, int);
 127 STATIC void addfname(char *);
 128 STATIC int patmatch(char *, const char *);
 129 STATIC int pmatch(const char *, const char *);
 130 static size_t cvtnum(intmax_t num, int flags);
 131 STATIC size_t esclen(const char *, const char *);
 132 STATIC void varunset(const char *, const char *, const char *, int)
 133         __attribute__((__noreturn__));
 134
 135
 136 /*
 137  * Prepare a pattern for a glob(3) call.
 138  *
 139  * Returns an stalloced string.
 140  */
 141
 142 STATIC inline char *
 143 preglob(const char *pattern, int flag) {
 144         flag |= RMESCAPE_GLOB;
 145         return _rmescapes((char *)pattern, flag);
 146 }
 147
 148
 149 STATIC size_t
 150 esclen(const char *start, const char *p) {
 151         size_t esc = 0;
 152
 153         while (p > start && *--p == (char)CTLESC) {
 154                 esc++;
 155         }
 156         return esc;
 157 }
 158
 159
 160 static inline const char *getpwhome(const char *name)
 161 {
 162 #ifdef HAVE_GETPWNAM
 163         struct passwd *pw = getpwnam(name);
 164         return pw ? pw->pw_dir : 0;
 165 #else
 166         return 0;
 167 #endif
 168 }
 169
 170
 171 /*
 172  * Perform variable substitution and command substitution on an argument,
 173  * placing the resulting list of arguments in arglist.  If EXP_FULL is true,
 174  * perform splitting and file name expansion.  When arglist is NULL, perform
 175  * here document expansion.
 176  */
 177
 178 void
 179 expandarg(union node *arg, struct arglist *arglist, int flag)
 180 {
 181         struct strlist *sp;
 182         char *p;
 183
 184         argbackq = arg->narg.backquote;
 185         STARTSTACKSTR(expdest);
 186         argstr(arg->narg.text, flag);
 187         if (arglist == NULL) {
 188                 /* here document expanded */
 189                 goto out;
 190         }
 191         p = grabstackstr(expdest);
 192         exparg.lastp = &exparg.list;
 193         /*
 194          * TODO - EXP_REDIR
 195          */
 196         if (flag & EXP_FULL) {
 197                 ifsbreakup(p, -1, &exparg);
 198                 *exparg.lastp = NULL;
 199                 exparg.lastp = &exparg.list;
 200                 expandmeta(exparg.list);
 201         } else {
 202                 sp = (struct strlist *)stalloc(sizeof (struct strlist));
 203                 sp->text = p;
 204                 *exparg.lastp = sp;
 205                 exparg.lastp = &sp->next;
 206         }
 207         *exparg.lastp = NULL;
 208         if (exparg.list) {
 209                 *arglist->lastp = exparg.list;
 210                 arglist->lastp = exparg.lastp;
 211         }
 212
 213 out:
 214         ifsfree();
 215 }
 216
 217
 218
 219 /*
 220  * Perform variable and command substitution.  If EXP_FULL is set, output CTLESC
 221  * characters to allow for further processing.  Otherwise treat
 222  * $@ like $* since no splitting will be performed.
 223  */
 224
 225 static char *argstr(char *p, int flag)
 226 {
 227         static const char spclchars[] = {
 228                 '=',
 229                 ':',
 230                 CTLQUOTEMARK,
 231                 CTLENDVAR,
 232                 CTLESC,
 233                 CTLVAR,
 234                 CTLBACKQ,
 235                 CTLARI,
 236                 CTLENDARI,
 237                 0
 238         };
 239         const char *reject = spclchars;
 240         int c;
 241         int breakall = (flag & (EXP_WORD | EXP_QUOTED)) == EXP_WORD;
 242         int inquotes;
 243         size_t length;
 244         int startloc;
 245
 246         reject += !!(flag & EXP_VARTILDE2);
 247         reject += flag & EXP_VARTILDE ? 0 : 2;
 248         inquotes = 0;
 249         length = 0;
 250         if (flag & EXP_TILDE) {
 251                 flag &= ~EXP_TILDE;
 252 tilde:
 253                 if (*p == '~')
 254                         p = exptilde(p, flag);
 255         }
 256 start:
 257         startloc = expdest - (char *)stackblock();
 258         for (;;) {
 259                 int end;
 260
 261                 length += strcspn(p + length, reject);
 262                 end = 0;
 263                 c = (signed char)p[length];
 264                 if (!(c & 0x80) || c == CTLENDARI || c == CTLENDVAR) {
 265                         /*
 266                          * c == '=' || c == ':' || c == '\0' ||
 267                          * c == CTLENDARI || c == CTLENDVAR
 268                          */
 269                         length++;
 270                         /* c == '\0' || c == CTLENDARI || c == CTLENDVAR */
 271                         end = !!((c - 1) & 0x80);
 272                 }
 273                 if (length > 0 && !(flag & EXP_DISCARD)) {
 274                         int newloc;
 275                         char *q;
 276
 277                         q = stnputs(p, length, expdest);
 278                         q[-1] &= end - 1;
 279                         expdest = q - (flag & EXP_WORD ? end : 0);
 280                         newloc = q - (char *)stackblock() - end;
 281                         if (breakall && !inquotes && newloc > startloc) {
 282                                 recordregion(startloc, newloc, 0);
 283                         }
 284                         startloc = newloc;
 285                 }
 286                 p += length + 1;
 287                 length = 0;
 288
 289                 if (end)
 290                         break;
 291
 292                 switch (c) {
 293                 case '=':
 294                         flag |= EXP_VARTILDE2;
 295                         reject++;
 296                         /* fall through */
 297                 case ':':
 298                         /*
 299                          * sort of a hack - expand tildes in variable
 300                          * assignments (after the first '=' and after ':'s).
 301                          */
 302                         if (*--p == '~') {
 303                                 goto tilde;
 304                         }
 305                         continue;
 306                 case CTLQUOTEMARK:
 307                         /* "$@" syntax adherence hack */
 308                         if (!inquotes && !memcmp(p, dolatstr + 1,
 309                                                  DOLATSTRLEN - 1)) {
 310                                 p = evalvar(p + 1, flag | EXP_QUOTED) + 1;
 311                                 goto start;
 312                         }
 313                         inquotes ^= EXP_QUOTED;
 314 addquote:
 315                         if (flag & QUOTES_ESC) {
 316                                 p--;
 317                                 length++;
 318                                 startloc++;
 319                         }
 320                         break;
 321                 case CTLESC:
 322                         startloc++;
 323                         length++;
 324                         goto addquote;
 325                 case CTLVAR:
 326                         p = evalvar(p, flag | inquotes);
 327                         goto start;
 328                 case CTLBACKQ:
 329                         expbackq(argbackq->n, flag | inquotes);
 330                         goto start;
 331                 case CTLARI:
 332                         p = expari(p, flag | inquotes);
 333                         goto start;
 334                 }
 335         }
 336         return p - 1;
 337 }
 338
 339 static char *exptilde(char *startp, int flag)
 340 {
 341         signed char c;
 342         char *name;
 343         const char *home;
 344         char *p;
 345
 346         p = startp;
 347         name = p + 1;
 348
 349         while ((c = *++p) != '\0') {
 350                 switch(c) {
 351                 case CTLESC:
 352                         return (startp);
 353                 case CTLQUOTEMARK:
 354                         return (startp);
 355                 case ':':
 356                         if (flag & EXP_VARTILDE)
 357                                 goto done;
 358                         break;
 359                 case '/':
 360                 case CTLENDVAR:
 361                         goto done;
 362                 }
 363         }
 364 done:
 365         if (flag & EXP_DISCARD)
 366                 goto out;
 367         *p = '\0';
 368         if (*name == '\0') {
 369                 home = lookupvar(homestr);
 370         } else {
 371                 home = getpwhome(name);
 372         }
 373         *p = c;
 374         if (!home)
 375                 goto lose;
 376         strtodest(home, flag | EXP_QUOTED);
 377 out:
 378         return (p);
 379 lose:
 380         return (startp);
 381 }
 382
 383
 384 void
 385 removerecordregions(int endoff)
 386 {
 387         if (ifslastp == NULL)
 388                 return;
 389
 390         if (ifsfirst.endoff > endoff) {
 391                 while (ifsfirst.next != NULL) {
 392                         struct ifsregion *ifsp;
 393                         INTOFF;
 394                         ifsp = ifsfirst.next->next;
 395                         ckfree(ifsfirst.next);
 396                         ifsfirst.next = ifsp;
 397                         INTON;
 398                 }
 399                 if (ifsfirst.begoff > endoff)
 400                         ifslastp = NULL;
 401                 else {
 402                         ifslastp = &ifsfirst;
 403                         ifsfirst.endoff = endoff;
 404                 }
 405                 return;
 406         }
 407
 408         ifslastp = &ifsfirst;
 409         while (ifslastp->next && ifslastp->next->begoff < endoff)
 410                 ifslastp=ifslastp->next;
 411         while (ifslastp->next != NULL) {
 412                 struct ifsregion *ifsp;
 413                 INTOFF;
 414                 ifsp = ifslastp->next->next;
 415                 ckfree(ifslastp->next);
 416                 ifslastp->next = ifsp;
 417                 INTON;
 418         }
 419         if (ifslastp->endoff > endoff)
 420                 ifslastp->endoff = endoff;
 421 }
 422
 423
 424 /*
 425  * Expand arithmetic expression.  Backup to start of expression,
 426  * evaluate, place result in (backed up) result, adjust string position.
 427  */
 428 static char *expari(char *start, int flag)
 429 {
 430         struct stackmark sm;
 431         int begoff;
 432         int endoff;
 433         int len;
 434         intmax_t result;
 435         char *p;
 436
 437         p = stackblock();
 438         begoff = expdest - p;
 439         p = argstr(start, flag & EXP_DISCARD);
 440
 441         if (flag & EXP_DISCARD)
 442                 goto out;
 443
 444         start = stackblock();
 445         endoff = expdest - start;
 446         start += begoff;
 447         STADJUST(start - expdest, expdest);
 448
 449         removerecordregions(begoff);
 450
 451         if (likely(flag & QUOTES_ESC))
 452                 rmescapes(start);
 453
 454         pushstackmark(&sm, endoff);
 455         result = arith(start);
 456         popstackmark(&sm);
 457
 458         len = cvtnum(result, flag);
 459
 460         if (likely(!(flag & EXP_QUOTED)))
 461                 recordregion(begoff, begoff + len, 0);
 462
 463 out:
 464         return p;
 465 }
 466
 467
 468 /*
 469  * Expand stuff in backwards quotes.
 470  */
 471
 472 STATIC void
 473 expbackq(union node *cmd, int flag)
 474 {
 475         struct backcmd in;
 476         int i;
 477         char buf[128];
 478         char *p;
 479         char *dest;
 480         int startloc;
 481         struct stackmark smark;
 482
 483         if (flag & EXP_DISCARD)
 484                 goto out;
 485
 486         INTOFF;
 487         startloc = expdest - (char *)stackblock();
 488         pushstackmark(&smark, startloc);
 489         evalbackcmd(cmd, (struct backcmd *) &in);
 490         popstackmark(&smark);
 491
 492         p = in.buf;
 493         i = in.nleft;
 494         if (i == 0)
 495                 goto read;
 496         for (;;) {
 497                 memtodest(p, i, flag);
 498 read:
 499                 if (in.fd < 0)
 500                         break;
 501                 do {
 502                         i = read(in.fd, buf, sizeof buf);
 503                 } while (i < 0 && errno == EINTR);
 504                 TRACE(("expbackq: read returns %d\n", i));
 505                 if (i <= 0)
 506                         break;
 507                 p = buf;
 508         }
 509
 510         if (in.buf)
 511                 ckfree(in.buf);
 512         if (in.fd >= 0) {
 513                 close(in.fd);
 514                 back_exitstatus = waitforjob(in.jp);
 515         }
 516         INTON;
 517
 518         /* Eat all trailing newlines */
 519         dest = expdest;
 520         for (; dest > ((char *)stackblock() + startloc) && dest[-1] == '\n';)
 521                 STUNPUTC(dest);
 522         expdest = dest;
 523
 524         if (!(flag & EXP_QUOTED))
 525                 recordregion(startloc, dest - (char *)stackblock(), 0);
 526         TRACE(("evalbackq: size=%d: \"%.*s\"\n",
 527                 (dest - (char *)stackblock()) - startloc,
 528                 (dest - (char *)stackblock()) - startloc,
 529                 stackblock() + startloc));
 530
 531 out:
 532         argbackq = argbackq->next;
 533 }
 534
 535
 536 static char *scanleft(char *startp, char *endp, char *rmesc, char *rmescend,
 537                       char *str, int quotes, int zero
 538 ) {
 539         char *loc;
 540         char *loc2;
 541         char c;
 542
 543         loc = startp;
 544         loc2 = rmesc;
 545         do {
 546                 int match;
 547                 const char *s = loc2;
 548                 c = *loc2;
 549                 if (zero) {
 550                         *loc2 = '\0';
 551                         s = rmesc;
 552                 }
 553                 match = pmatch(str, s);
 554                 *loc2 = c;
 555                 if (match)
 556                         return loc;
 557                 if (quotes && *loc == (char)CTLESC)
 558                         loc++;
 559                 loc++;
 560                 loc2++;
 561         } while (c);
 562         return 0;
 563 }
 564
 565
 566 static char *scanright(char *startp, char *endp, char *rmesc, char *rmescend,
 567                        char *str, int quotes, int zero
 568 ) {
 569         int esc = 0;
 570         char *loc;
 571         char *loc2;
 572
 573         for (loc = endp, loc2 = rmescend; loc >= startp; loc2--) {
 574                 int match;
 575                 char c = *loc2;
 576                 const char *s = loc2;
 577                 if (zero) {
 578                         *loc2 = '\0';
 579                         s = rmesc;
 580                 }
 581                 match = pmatch(str, s);
 582                 *loc2 = c;
 583                 if (match)
 584                         return loc;
 585                 loc--;
 586                 if (quotes) {
 587                         if (--esc < 0) {
 588                                 esc = esclen(startp, loc);
 589                         }
 590                         if (esc % 2) {
 591                                 esc--;
 592                                 loc--;
 593                         }
 594                 }
 595         }
 596         return 0;
 597 }
 598
 599 static char *subevalvar(char *start, char *str, int strloc, int startloc,
 600                         int varflags, int flag)
 601 {
 602         int subtype = varflags & VSTYPE;
 603         int quotes = flag & QUOTES_ESC;
 604         char *startp;
 605         char *loc;
 606         long amount;
 607         char *rmesc, *rmescend;
 608         int zero;
 609         char *(*scan)(char *, char *, char *, char *, char *, int , int);
 610         int nstrloc = strloc;
 611         char *endp;
 612         char *p;
 613
 614         p = argstr(start, (flag & EXP_DISCARD) | EXP_TILDE |
 615                           (str ?  0 : EXP_CASE));
 616         if (flag & EXP_DISCARD)
 617                 return p;
 618
 619         startp = stackblock() + startloc;
 620
 621         switch (subtype) {
 622         case VSASSIGN:
 623                 setvar(str, startp, 0);
 624
 625                 loc = startp;
 626                 goto out;
 627
 628         case VSQUESTION:
 629                 varunset(start, str, startp, varflags);
 630                 /* NOTREACHED */
 631         }
 632
 633         subtype -= VSTRIMRIGHT;
 634 #ifdef DEBUG
 635         if (subtype < 0 || subtype > 3)
 636                 abort();
 637 #endif
 638
 639         rmescend = stackblock() + strloc;
 640         str = preglob(rmescend, FNMATCH_IS_ENABLED ?
 641                                 RMESCAPE_ALLOC | RMESCAPE_GROW : 0);
 642         if (FNMATCH_IS_ENABLED) {
 643                 startp = stackblock() + startloc;
 644                 rmescend = stackblock() + strloc;
 645                 nstrloc = str - (char *)stackblock();
 646         }
 647
 648         rmesc = startp;
 649         if (quotes) {
 650                 rmesc = _rmescapes(startp, RMESCAPE_ALLOC | RMESCAPE_GROW);
 651                 if (rmesc != startp)
 652                         rmescend = expdest;
 653                 startp = stackblock() + startloc;
 654                 str = stackblock() + nstrloc;
 655         }
 656         rmescend--;
 657
 658         /* zero = subtype == VSTRIMLEFT || subtype == VSTRIMLEFTMAX */
 659         zero = subtype >> 1;
 660         /* VSTRIMLEFT/VSTRIMRIGHTMAX -> scanleft */
 661         scan = (subtype & 1) ^ zero ? scanleft : scanright;
 662
 663         endp = stackblock() + strloc - 1;
 664         loc = scan(startp, endp, rmesc, rmescend, str, quotes, zero);
 665         if (loc) {
 666                 if (zero) {
 667                         memmove(startp, loc, endp - loc);
 668                         loc = startp + (endp - loc);
 669                 }
 670                 *loc = '\0';
 671         } else
 672                 loc = endp;
 673
 674 out:
 675         amount = loc - expdest;
 676         STADJUST(amount, expdest);
 677
 678         /* Remove any recorded regions beyond start of variable */
 679         removerecordregions(startloc);
 680
 681         return p;
 682 }
 683
 684
 685 /*
 686  * Expand a variable, and return a pointer to the next character in the
 687  * input string.
 688  */
 689 STATIC char *
 690 evalvar(char *p, int flag)
 691 {
 692         int subtype;
 693         int varflags;
 694         char *var;
 695         int patloc;
 696         int startloc;
 697         ssize_t varlen;
 698         int discard;
 699         int quoted;
 700
 701         varflags = *p++ & ~VSBIT;
 702         subtype = varflags & VSTYPE;
 703
 704         quoted = flag & EXP_QUOTED;
 705         var = p;
 706         startloc = expdest - (char *)stackblock();
 707         p = strchr(p, '=') + 1;
 708
 709 again:
 710         varlen = varvalue(var, varflags, flag, quoted);
 711         if (varflags & VSNUL)
 712                 varlen--;
 713
 714         discard = varlen < 0 ? EXP_DISCARD : 0;
 715
 716         switch (subtype) {
 717         case VSPLUS:
 718                 discard ^= EXP_DISCARD;
 719                 /* fall through */
 720
 721         case 0:
 722         case VSMINUS:
 723                 p = argstr(p, flag | EXP_TILDE | EXP_WORD |
 724                               (discard ^ EXP_DISCARD));
 725                 goto record;
 726
 727         case VSASSIGN:
 728         case VSQUESTION:
 729                 p = subevalvar(p, var, 0, startloc, varflags,
 730                                (flag & ~QUOTES_ESC) |
 731                                (discard ^ EXP_DISCARD));
 732
 733                 if ((flag | ~discard) & EXP_DISCARD)
 734                         goto record;
 735
 736                 varflags &= ~VSNUL;
 737                 subtype = VSNORMAL;
 738                 goto again;
 739         }
 740
 741         if ((discard & ~flag) && uflag)
 742                 varunset(p, var, 0, 0);
 743
 744         if (subtype == VSLENGTH) {
 745                 p++;
 746                 if (flag & EXP_DISCARD)
 747                         return p;
 748                 cvtnum(varlen > 0 ? varlen : 0, flag);
 749                 goto really_record;
 750         }
 751
 752         if (subtype == VSNORMAL)
 753                 goto record;
 754
 755 #ifdef DEBUG
 756         switch (subtype) {
 757         case VSTRIMLEFT:
 758         case VSTRIMLEFTMAX:
 759         case VSTRIMRIGHT:
 760         case VSTRIMRIGHTMAX:
 761                 break;
 762         default:
 763                 abort();
 764         }
 765 #endif
 766
 767         flag |= discard;
 768         if (!(flag & EXP_DISCARD)) {
 769                 /*
 770                  * Terminate the string and start recording the pattern
 771                  * right after it
 772                  */
 773                 STPUTC('\0', expdest);
 774         }
 775
 776         patloc = expdest - (char *)stackblock();
 777         p = subevalvar(p, NULL, patloc, startloc, varflags, flag);
 778
 779 record:
 780         if ((flag | discard) & EXP_DISCARD)
 781                 return p;
 782
 783 really_record:
 784         if (quoted) {
 785                 quoted = *var == '@' && shellparam.nparam;
 786                 if (!quoted)
 787                         return p;
 788         }
 789         recordregion(startloc, expdest - (char *)stackblock(), quoted);
 790         return p;
 791 }
 792
 793
 794 /*
 795  * Put a string on the stack.
 796  */
 797
 798 static size_t memtodest(const char *p, size_t len, int flags)
 799 {
 800         const char *syntax = flags & EXP_QUOTED ? DQSYNTAX : BASESYNTAX;
 801         char *q;
 802         char *s;
 803
 804         if (unlikely(!len))
 805                 return 0;
 806
 807         q = makestrspace(len * 2, expdest);
 808         s = q;
 809
 810         do {
 811                 int c = (signed char)*p++;
 812                 if (c) {
 813                         if ((flags & QUOTES_ESC) &&
 814                             ((syntax[c] == CCTL) ||
 815                              (flags & EXP_QUOTED && syntax[c] == CBACK)))
 816                                 USTPUTC(CTLESC, q);
 817                 } else if (!(flags & EXP_KEEPNUL))
 818                         continue;
 819                 USTPUTC(c, q);
 820         } while (--len);
 821
 822         expdest = q;
 823         return q - s;
 824 }
 825
 826
 827 static size_t strtodest(const char *p, int flags)
 828 {
 829         size_t len = strlen(p);
 830         memtodest(p, len, flags);
 831         return len;
 832 }
 833
 834
 835
 836 /*
 837  * Add the value of a specialized variable to the stack string.
 838  */
 839
 840 STATIC ssize_t
 841 varvalue(char *name, int varflags, int flags, int quoted)
 842 {
 843         int num;
 844         char *p;
 845         int i;
 846         int sep;
 847         char sepc;
 848         char **ap;
 849         int subtype = varflags & VSTYPE;
 850         int discard = (subtype == VSPLUS || subtype == VSLENGTH) |
 851                       (flags & EXP_DISCARD);
 852         ssize_t len = 0;
 853         char c;
 854
 855         if (!subtype) {
 856                 if (discard)
 857                         return -1;
 858
 859                 sh_error("Bad substitution");
 860         }
 861
 862         flags |= EXP_KEEPNUL;
 863         flags &= discard ? ~QUOTES_ESC : ~0;
 864         sep = (flags & EXP_FULL) << CHAR_BIT;
 865
 866         switch (*name) {
 867         case '$':
 868                 num = rootpid;
 869                 goto numvar;
 870         case '?':
 871                 num = exitstatus;
 872                 goto numvar;
 873         case '#':
 874                 num = shellparam.nparam;
 875                 goto numvar;
 876         case '!':
 877                 num = backgndpid;
 878                 if (num == 0)
 879                         return -1;
 880 numvar:
 881                 len = cvtnum(num, flags);
 882                 break;
 883         case '-':
 884                 p = makestrspace(NOPTS, expdest);
 885                 for (i = NOPTS - 1; i >= 0; i--) {
 886                         if (optlist[i] && optletters[i]) {
 887                                 USTPUTC(optletters[i], p);
 888                                 len++;
 889                         }
 890                 }
 891                 expdest = p;
 892                 break;
 893         case '@':
 894                 if (quoted && sep)
 895                         goto param;
 896                 /* fall through */
 897         case '*':
 898                 /* We will set c to 0 or ~0 depending on whether
 899                  * we're doing field splitting.  We won't do field
 900                  * splitting if either we're quoted or sep is zero.
 901                  *
 902                  * Instead of testing (quoted || !sep) the following
 903                  * trick optimises away any branches by using the
 904                  * fact that EXP_QUOTED (which is the only bit that
 905                  * can be set in quoted) is the same as EXP_FULL <<
 906                  * CHAR_BIT (which is the only bit that can be set
 907                  * in sep).
 908                  */
 909 #if EXP_QUOTED >> CHAR_BIT != EXP_FULL
 910 #error The following two lines expect EXP_QUOTED == EXP_FULL << CHAR_BIT
 911 #endif
 912                 c = !((quoted | ~sep) & EXP_QUOTED) - 1;
 913                 sep &= ~quoted;
 914                 sep |= ifsset() ? (unsigned char)(c & ifsval()[0]) : ' ';
 915 param:
 916                 sepc = sep;
 917                 if (!(ap = shellparam.p))
 918                         return -1;
 919                 while ((p = *ap++)) {
 920                         len += strtodest(p, flags);
 921
 922                         if (*ap && sep) {
 923                                 len++;
 924                                 memtodest(&sepc, 1, flags);
 925                         }
 926                 }
 927                 break;
 928         case '0':
 929         case '1':
 930         case '2':
 931         case '3':
 932         case '4':
 933         case '5':
 934         case '6':
 935         case '7':
 936         case '8':
 937         case '9':
 938                 num = atoi(name);
 939                 if (num < 0 || num > shellparam.nparam)
 940                         return -1;
 941                 p = num ? shellparam.p[num - 1] : arg0;
 942                 goto value;
 943         default:
 944                 p = lookupvar(name);
 945 value:
 946                 if (!p)
 947                         return -1;
 948
 949                 len = strtodest(p, flags);
 950                 break;
 951         }
 952
 953         if (discard)
 954                 STADJUST(-len, expdest);
 955
 956         return len;
 957 }
 958
 959
 960
 961 /*
 962  * Record the fact that we have to scan this region of the
 963  * string for IFS characters.
 964  */
 965
 966 void
 967 recordregion(int start, int end, int nulonly)
 968 {
 969         struct ifsregion *ifsp;
 970
 971         if (ifslastp == NULL) {
 972                 ifsp = &ifsfirst;
 973         } else {
 974                 INTOFF;
 975                 ifsp = (struct ifsregion *)ckmalloc(sizeof (struct ifsregion));
 976                 ifsp->next = NULL;
 977                 ifslastp->next = ifsp;
 978                 INTON;
 979         }
 980         ifslastp = ifsp;
 981         ifslastp->begoff = start;
 982         ifslastp->endoff = end;
 983         ifslastp->nulonly = nulonly;
 984 }
 985
 986
 987
 988 /*
 989  * Break the argument string into pieces based upon IFS and add the
 990  * strings to the argument list.  The regions of the string to be
 991  * searched for IFS characters have been stored by recordregion.
 992  * If maxargs is non-negative, at most maxargs arguments will be created, by
 993  * joining together the last arguments.
 994  */
 995 void
 996 ifsbreakup(char *string, int maxargs, struct arglist *arglist)
 997 {
 998         struct ifsregion *ifsp;
 999         struct strlist *sp;
1000         char *start;
1001         char *p;
1002         char *q;
1003         char *r = NULL;
1004         const char *ifs, *realifs;
1005         int ifsspc;
1006         int nulonly;
1007
1008
1009         start = string;
1010         if (ifslastp != NULL) {
1011                 ifsspc = 0;
1012                 nulonly = 0;
1013                 realifs = ifsset() ? ifsval() : defifs;
1014                 ifsp = &ifsfirst;
1015                 do {
1016                         int afternul;
1017
1018                         p = string + ifsp->begoff;
1019                         afternul = nulonly;
1020                         nulonly = ifsp->nulonly;
1021                         ifs = nulonly ? nullstr : realifs;
1022                         ifsspc = 0;
1023                         while (p < string + ifsp->endoff) {
1024                                 int c;
1025                                 bool isifs;
1026                                 bool isdefifs;
1027
1028                                 q = p;
1029                                 c = *p++;
1030                                 if (c == (char)CTLESC)
1031                                         c = *p++;
1032
1033                                 isifs = strchr(ifs, c);
1034                                 isdefifs = false;
1035                                 if (isifs)
1036                                         isdefifs = strchr(defifs, c);
1037
1038                                 /* If only reading one more argument:
1039                                  * If we have exactly one field,
1040                                  * read that field without its terminator.
1041                                  * If we have more than one field,
1042                                  * read all fields including their terminators,
1043                                  * except for trailing IFS whitespace.
1044                                  *
1045                                  * This means that if we have only IFS
1046                                  * characters left, and at most one
1047                                  * of them is non-whitespace, we stop
1048                                  * reading here.
1049                                  * Otherwise, we read all the remaining
1050                                  * characters except for trailing
1051                                  * IFS whitespace.
1052                                  *
1053                                  * In any case, r indicates the start
1054                                  * of the characters to remove, or NULL
1055                                  * if no characters should be removed.
1056                                  */
1057                                 if (!maxargs) {
1058                                         if (isdefifs) {
1059                                                 if (!r)
1060                                                         r = q;
1061                                                 continue;
1062                                         }
1063
1064                                         if (!(isifs && ifsspc))
1065                                                 r = NULL;
1066
1067                                         ifsspc = 0;
1068                                         continue;
1069                                 }
1070
1071                                 if (ifsspc) {
1072                                         if (isifs)
1073                                                 q = p;
1074
1075                                         start = q;
1076
1077                                         if (isdefifs)
1078                                                 continue;
1079
1080                                         isifs = false;
1081                                 }
1082
1083                                 if (isifs) {
1084                                         if (!(afternul || nulonly))
1085                                                 ifsspc = isdefifs;
1086                                         /* Ignore IFS whitespace at start */
1087                                         if (q == start && ifsspc) {
1088                                                 start = p;
1089                                                 ifsspc = 0;
1090                                                 continue;
1091                                         }
1092                                         if (maxargs > 0 && !--maxargs) {
1093                                                 r = q;
1094                                                 continue;
1095                                         }
1096                                         *q = '\0';
1097                                         sp = (struct strlist *)stalloc(sizeof *sp);
1098                                         sp->text = start;
1099                                         *arglist->lastp = sp;
1100                                         arglist->lastp = &sp->next;
1101                                         start = p;
1102                                         continue;
1103                                 }
1104
1105                                 ifsspc = 0;
1106                         }
1107                 } while ((ifsp = ifsp->next) != NULL);
1108                 if (nulonly)
1109                         goto add;
1110         }
1111
1112         if (r)
1113                 *r = '\0';
1114
1115         if (!*start)
1116                 return;
1117
1118 add:
1119         sp = (struct strlist *)stalloc(sizeof *sp);
1120         sp->text = start;
1121         *arglist->lastp = sp;
1122         arglist->lastp = &sp->next;
1123 }
1124
1125 void ifsfree(void)
1126 {
1127         struct ifsregion *p = ifsfirst.next;
1128
1129         if (!p)
1130                 goto out;
1131
1132         INTOFF;
1133         do {
1134                 struct ifsregion *ifsp;
1135                 ifsp = p->next;
1136                 ckfree(p);
1137                 p = ifsp;
1138         } while (p);
1139         ifsfirst.next = NULL;
1140         INTON;
1141
1142 out:
1143         ifslastp = NULL;
1144 }
1145
1146
1147
1148 /*
1149  * Expand shell metacharacters.  At this point, the only control characters
1150  * should be escapes.  The results are stored in the list exparg.
1151  */
1152
1153 #ifdef __GLIBC__
1154 static void *opendir_interruptible(const char *pathname)
1155 {
1156         if (int_pending()) {
1157                 suppressint = 0;
1158                 onint();
1159         }
1160
1161         return opendir(pathname);
1162 }
1163 #else
1164 #define GLOB_ALTDIRFUNC 0
1165 #endif
1166
1167 static void expandmeta_glob(struct strlist *str)
1168 {
1169         while (str) {
1170                 const char *p;
1171                 glob64_t pglob;
1172                 int i;
1173
1174                 if (fflag)
1175                         goto nometa;
1176
1177 #ifdef __GLIBC__
1178                 pglob.gl_closedir = (void *)closedir;
1179                 pglob.gl_readdir = (void *)readdir64;
1180                 pglob.gl_opendir = opendir_interruptible;
1181                 pglob.gl_lstat = lstat64;
1182                 pglob.gl_stat = stat64;
1183 #endif
1184
1185                 INTOFF;
1186                 p = preglob(str->text, RMESCAPE_ALLOC | RMESCAPE_HEAP);
1187                 i = glob64(p, GLOB_ALTDIRFUNC | GLOB_NOMAGIC, 0, &pglob);
1188                 if (p != str->text)
1189                         ckfree(p);
1190                 switch (i) {
1191                 case 0:
1192                         if ((pglob.gl_flags & (GLOB_NOMAGIC | GLOB_NOCHECK)) ==
1193                             (GLOB_NOMAGIC | GLOB_NOCHECK))
1194                                 goto nometa2;
1195                         addglob(&pglob);
1196                         globfree64(&pglob);
1197                         INTON;
1198                         break;
1199                 case GLOB_NOMATCH:
1200 nometa2:
1201                         globfree64(&pglob);
1202                         INTON;
1203 nometa:
1204                         *exparg.lastp = str;
1205                         rmescapes(str->text);
1206                         exparg.lastp = &str->next;
1207                         break;
1208                 default:        /* GLOB_NOSPACE */
1209                         sh_error("Out of space");
1210                 }
1211                 str = str->next;
1212         }
1213 }
1214
1215
1216 /*
1217  * Add the result of glob(3) to the list.
1218  */
1219
1220 static void addglob(const glob64_t *pglob)
1221 {
1222         char **p = pglob->gl_pathv;
1223
1224         do {
1225                 addfname(*p);
1226         } while (*++p);
1227 }
1228
1229 STATIC void
1230 expandmeta(struct strlist *str)
1231 {
1232         static const char metachars[] = {
1233                 '*', '?', '[', 0
1234         };
1235         /* TODO - EXP_REDIR */
1236
1237         if (GLOB_IS_ENABLED)
1238                 return expandmeta_glob(str);
1239
1240         while (str) {
1241                 struct strlist **savelastp;
1242                 struct strlist *sp;
1243                 char *p;
1244                 unsigned len;
1245
1246                 if (fflag)
1247                         goto nometa;
1248                 if (!strpbrk(str->text, metachars))
1249                         goto nometa;
1250                 savelastp = exparg.lastp;
1251
1252                 INTOFF;
1253                 p = preglob(str->text, RMESCAPE_ALLOC | RMESCAPE_HEAP);
1254                 len = strlen(p);
1255
1256                 expmeta(p, len, 0);
1257                 if (p != str->text)
1258                         ckfree(p);
1259                 INTON;
1260                 if (exparg.lastp == savelastp) {
1261                         /*
1262                          * no matches
1263                          */
1264 nometa:
1265                         *exparg.lastp = str;
1266                         rmescapes(str->text);
1267                         exparg.lastp = &str->next;
1268                 } else {
1269                         *exparg.lastp = NULL;
1270                         *savelastp = sp = expsort(*savelastp);
1271                         while (sp->next != NULL)
1272                                 sp = sp->next;
1273                         exparg.lastp = &sp->next;
1274                 }
1275                 str = str->next;
1276         }
1277 }
1278
1279 static void addfname_common(char *name)
1280 {
1281         struct strlist *sp;
1282
1283         sp = (struct strlist *)stalloc(sizeof *sp);
1284         sp->text = name;
1285         *exparg.lastp = sp;
1286         exparg.lastp = &sp->next;
1287 }
1288
1289 static char *addfnamealt(char *enddir, size_t expdir_len)
1290 {
1291         char *name;
1292
1293         name = grabstackstr(enddir);
1294         addfname_common(name);
1295
1296         STARTSTACKSTR(enddir);
1297         return stnputs(name, expdir_len, enddir) - expdir_len;
1298 }
1299
1300 /*
1301  * Do metacharacter (i.e. *, ?, [...]) expansion.
1302  */
1303
1304 static char *expmeta(char *name, unsigned name_len, size_t expdir_len)
1305 {
1306         struct jmploc *volatile savehandler;
1307         struct jmploc jmploc;
1308         struct stat64 statb;
1309         struct dirent64 *dp;
1310         volatile int err;
1311         char *endname;
1312         char *enddir;
1313         int metaflag;
1314         int matchdot;
1315         char *start;
1316         size_t len;
1317         DIR *dirp;
1318         int atend;
1319         char *cp;
1320         char *p;
1321         int esc;
1322
1323         *(DIR *volatile *)&dirp = NULL;
1324         savehandler = handler;
1325         if (unlikely(err = setjmp(jmploc.loc)))
1326                 goto out;
1327
1328         len = expdir_len + name_len + 1;
1329         cp = growstackto(len);
1330         enddir = cp + expdir_len;
1331
1332         metaflag = 0;
1333         start = name;
1334         for (p = name; esc = 0, *p; p += esc + 1) {
1335                 if (*p == '*' || *p == '?')
1336                         metaflag = 1;
1337                 else if (*p == '[') {
1338                         char *q = p + 1;
1339                         if (*q == '!')
1340                                 q++;
1341                         for (;;) {
1342                                 if (*q == '\\')
1343                                         q++;
1344                                 if (*q == '/' || *q == '\0')
1345                                         break;
1346                                 if (*++q == ']') {
1347                                         metaflag = 1;
1348                                         break;
1349                                 }
1350                         }
1351                 } else {
1352                         if (*p == '\\' && p[1])
1353                                 esc++;
1354                         if (p[esc] == '/') {
1355                                 if (metaflag)
1356                                         break;
1357                                 start = p + esc + 1;
1358                         }
1359                 }
1360         }
1361         if (metaflag == 0) {    /* we've reached the end of the file name */
1362                 if (!expdir_len)
1363                         goto out_opendir;
1364                 p = name;
1365                 do {
1366                         if (*p == '\\' && p[1])
1367                                 p++;
1368                         *enddir++ = *p;
1369                 } while (*p++);
1370                 if (lstat64(cp, &statb) >= 0)
1371                         cp = addfnamealt(enddir, expdir_len);
1372                 goto out_opendir;
1373         }
1374         endname = p;
1375         if (name < start) {
1376                 p = name;
1377                 do {
1378                         if (*p == '\\' && p[1])
1379                                 p++;
1380                         *enddir++ = *p++;
1381                 } while (p < start);
1382         }
1383         *enddir = 0;
1384         expdir_len = enddir - cp;
1385
1386         *(DIR *volatile *)&dirp = opendir(expdir_len ? cp : dotdir);
1387         if (!dirp)
1388                 goto out_opendir;
1389         if (*endname == 0) {
1390                 atend = 1;
1391         } else {
1392                 atend = 0;
1393                 *endname = '\0';
1394                 endname += esc + 1;
1395         }
1396         name_len -= endname - name;
1397         matchdot = 0;
1398         p = start;
1399         if (*p == '\\')
1400                 p++;
1401         if (*p == '.')
1402                 matchdot++;
1403         while (! int_pending() && (dp = readdir64(dirp)) != NULL) {
1404                 if (dp->d_name[0] == '.' && ! matchdot)
1405                         continue;
1406                 if (pmatch(start, dp->d_name)) {
1407                         len = strlen(dp->d_name) + 1;
1408
1409                         enddir = cp + expdir_len;
1410                         enddir = stnputs(dp->d_name, len, enddir);
1411                         if (atend)
1412                                 cp = addfnamealt(enddir, expdir_len);
1413                         else {
1414                                 enddir[-1] = '/';
1415                                 len += expdir_len;
1416                                 cp = expmeta(endname, name_len, len);
1417                         }
1418                 }
1419         }
1420         if (! atend)
1421                 endname[-esc - 1] = esc ? '\\' : '/';
1422
1423 out:
1424         closedir(*(DIR *volatile *)&dirp);
1425 out_opendir:
1426         handler = savehandler;
1427         if (err)
1428                 longjmp(handler->loc, 1);
1429         return cp;
1430 }
1431
1432
1433 /*
1434  * Add a file name to the list.
1435  */
1436
1437 STATIC void
1438 addfname(char *name)
1439 {
1440         addfname_common(sstrdup(name));
1441 }
1442
1443
1444 /*
1445  * Sort the results of file name expansion.  It calculates the number of
1446  * strings to sort and then calls msort (short for merge sort) to do the
1447  * work.
1448  */
1449
1450 STATIC struct strlist *
1451 expsort(struct strlist *str)
1452 {
1453         int len;
1454         struct strlist *sp;
1455
1456         len = 0;
1457         for (sp = str ; sp ; sp = sp->next)
1458                 len++;
1459         return msort(str, len);
1460 }
1461
1462
1463 STATIC struct strlist *
1464 msort(struct strlist *list, int len)
1465 {
1466         struct strlist *p, *q = NULL;
1467         struct strlist **lpp;
1468         int half;
1469         int n;
1470
1471         if (len <= 1)
1472                 return list;
1473         half = len >> 1;
1474         p = list;
1475         for (n = half ; --n >= 0 ; ) {
1476                 q = p;
1477                 p = p->next;
1478         }
1479         q->next = NULL;                 /* terminate first half of list */
1480         q = msort(list, half);          /* sort first half of list */
1481         p = msort(p, len - half);               /* sort second half */
1482         lpp = &list;
1483         for (;;) {
1484                 if (strcoll(p->text, q->text) < 0) {
1485                         *lpp = p;
1486                         lpp = &p->next;
1487                         if ((p = *lpp) == NULL) {
1488                                 *lpp = q;
1489                                 break;
1490                         }
1491                 } else {
1492                         *lpp = q;
1493                         lpp = &q->next;
1494                         if ((q = *lpp) == NULL) {
1495                                 *lpp = p;
1496                                 break;
1497                         }
1498                 }
1499         }
1500         return list;
1501 }
1502
1503
1504 /*
1505  * Returns true if the pattern matches the string.
1506  */
1507
1508 STATIC inline int
1509 patmatch(char *pattern, const char *string)
1510 {
1511         return pmatch(preglob(pattern, FNMATCH_IS_ENABLED ?
1512                                        RMESCAPE_ALLOC | RMESCAPE_GROW : 0),
1513                       string);
1514 }
1515
1516
1517 STATIC int ccmatch(const char *p, int chr, const char **r)
1518 {
1519         static const struct class {
1520                 char name[10];
1521                 int (*fn)(int);
1522         } classes[] = {
1523                 { .name = ":alnum:]", .fn = isalnum },
1524                 { .name = ":cntrl:]", .fn = iscntrl },
1525                 { .name = ":lower:]", .fn = islower },
1526                 { .name = ":space:]", .fn = isspace },
1527                 { .name = ":alpha:]", .fn = isalpha },
1528                 { .name = ":digit:]", .fn = isdigit },
1529                 { .name = ":print:]", .fn = isprint },
1530                 { .name = ":upper:]", .fn = isupper },
1531                 { .name = ":blank:]", .fn = isblank },
1532                 { .name = ":graph:]", .fn = isgraph },
1533                 { .name = ":punct:]", .fn = ispunct },
1534                 { .name = ":xdigit:]", .fn = isxdigit },
1535         };
1536         const struct class *class, *end;
1537
1538         end = classes + sizeof(classes) / sizeof(classes[0]);
1539         for (class = classes; class < end; class++) {
1540                 const char *q;
1541
1542                 q = prefix(p, class->name);
1543                 if (!q)
1544                         continue;
1545                 *r = q;
1546                 return class->fn(chr);
1547         }
1548
1549         *r = 0;
1550         return 0;
1551 }
1552
1553 STATIC int
1554 pmatch(const char *pattern, const char *string)
1555 {
1556         const char *p, *q;
1557         char c;
1558
1559         if (FNMATCH_IS_ENABLED)
1560                 return !fnmatch(pattern, string, 0);
1561
1562         p = pattern;
1563         q = string;
1564         for (;;) {
1565                 switch (c = *p++) {
1566                 case '\0':
1567                         goto breakloop;
1568                 case '\\':
1569                         if (*p) {
1570                                 c = *p++;
1571                         }
1572                         goto dft;
1573                 case '?':
1574                         if (*q++ == '\0')
1575                                 return 0;
1576                         break;
1577                 case '*':
1578                         c = *p;
1579                         while (c == '*')
1580                                 c = *++p;
1581                         if (c != '\\' && c != '?' && c != '*' && c != '[') {
1582                                 while (*q != c) {
1583                                         if (*q == '\0')
1584                                                 return 0;
1585                                         q++;
1586                                 }
1587                         }
1588                         do {
1589                                 if (pmatch(p, q))
1590                                         return 1;
1591                         } while (*q++ != '\0');
1592                         return 0;
1593                 case '[': {
1594                         const char *startp;
1595                         int invert, found;
1596                         char chr;
1597
1598                         startp = p;
1599                         invert = 0;
1600                         if (*p == '!' || *p == '^') {
1601                                 invert++;
1602                                 p++;
1603                         }
1604                         found = 0;
1605                         chr = *q;
1606                         if (chr == '\0')
1607                                 return 0;
1608                         c = *p++;
1609                         do {
1610                                 if (!c) {
1611                                         p = startp;
1612                                         c = '[';
1613                                         goto dft;
1614                                 }
1615                                 if (c == '[') {
1616                                         const char *r;
1617
1618                                         found |= !!ccmatch(p, chr, &r);
1619                                         if (r) {
1620                                                 p = r;
1621                                                 continue;
1622                                         }
1623                                 } else if (c == '\\')
1624                                         c = *p++;
1625                                 if (*p == '-' && p[1] != ']') {
1626                                         p++;
1627                                         if (*p == '\\')
1628                                                 p++;
1629                                         if (chr >= c && chr <= *p)
1630                                                 found = 1;
1631                                         p++;
1632                                 } else {
1633                                         if (chr == c)
1634                                                 found = 1;
1635                                 }
1636                         } while ((c = *p++) != ']');
1637                         if (found == invert)
1638                                 return 0;
1639                         q++;
1640                         break;
1641                 }
1642 dft:            default:
1643                         if (*q++ != c)
1644                                 return 0;
1645                         break;
1646                 }
1647         }
1648 breakloop:
1649         if (*q != '\0')
1650                 return 0;
1651         return 1;
1652 }
1653
1654
1655
1656 /*
1657  * Remove any CTLESC characters from a string.
1658  */
1659
1660 char *
1661 _rmescapes(char *str, int flag)
1662 {
1663         char *p, *q, *r;
1664         int notescaped;
1665         int globbing;
1666         int inquotes;
1667
1668         p = strpbrk(str, cqchars);
1669         if (!p) {
1670                 return str;
1671         }
1672         q = p;
1673         r = str;
1674         globbing = flag & RMESCAPE_GLOB;
1675
1676         if (flag & RMESCAPE_ALLOC) {
1677                 size_t len = p - str;
1678                 size_t fulllen = strlen(p);
1679
1680                 if (FNMATCH_IS_ENABLED && globbing)
1681                         fulllen *= 2;
1682
1683                 fulllen += len + 1;
1684
1685                 if (flag & RMESCAPE_GROW) {
1686                         int strloc = str - (char *)stackblock();
1687
1688                         r = makestrspace(fulllen, expdest);
1689                         str = (char *)stackblock() + strloc;
1690                         p = str + len;
1691                 } else if (flag & RMESCAPE_HEAP) {
1692                         r = ckmalloc(fulllen);
1693                 } else {
1694                         r = stalloc(fulllen);
1695                 }
1696                 q = r;
1697                 if (len > 0) {
1698                         q = mempcpy(q, str, len);
1699                 }
1700         }
1701         inquotes = 0;
1702         notescaped = globbing;
1703         while (*p) {
1704                 if (*p == (char)CTLQUOTEMARK) {
1705                         p++;
1706                         inquotes ^= globbing;
1707                         continue;
1708                 }
1709                 if (*p == '\\') {
1710                         /* naked back slash */
1711                         notescaped ^= globbing;
1712                         goto copy;
1713                 }
1714                 if (*p == (char)CTLESC) {
1715                         p++;
1716                         if (notescaped)
1717                                 *q++ = '\\';
1718                         else if (inquotes) {
1719                                 *q++ = '\\';
1720                                 *q++ = '\\';
1721                         }
1722                 }
1723                 notescaped = globbing;
1724 copy:
1725                 *q++ = *p++;
1726         }
1727         *q = '\0';
1728         if (flag & RMESCAPE_GROW) {
1729                 expdest = r;
1730                 STADJUST(q - r + 1, expdest);
1731         }
1732         return r;
1733 }
1734
1735
1736
1737 /*
1738  * See if a pattern matches in a case statement.
1739  */
1740
1741 int
1742 casematch(union node *pattern, char *val)
1743 {
1744         struct stackmark smark;
1745         int result;
1746
1747         setstackmark(&smark);
1748         argbackq = pattern->narg.backquote;
1749         STARTSTACKSTR(expdest);
1750         argstr(pattern->narg.text, EXP_TILDE | EXP_CASE);
1751         ifsfree();
1752         result = patmatch(stackblock(), val);
1753         popstackmark(&smark);
1754         return result;
1755 }
1756
1757 /*
1758  * Our own itoa().
1759  */
1760
1761 static size_t cvtnum(intmax_t num, int flags)
1762 {
1763         int len = max_int_length(sizeof(num));
1764         char buf[len];
1765
1766         len = fmtstr(buf, len, "%" PRIdMAX, num);
1767         return memtodest(buf, len, flags);
1768 }
1769
1770 STATIC void
1771 varunset(const char *end, const char *var, const char *umsg, int varflags)
1772 {
1773         const char *msg;
1774         const char *tail;
1775
1776         tail = nullstr;
1777         msg = "parameter not set";
1778         if (umsg) {
1779                 if (*end == (char)CTLENDVAR) {
1780                         if (varflags & VSNUL)
1781                                 tail = " or null";
1782                 } else
1783                         msg = umsg;
1784         }
1785         sh_error("%.*s: %s%s", end - var - 1, var, msg, tail);
1786 }
1787
1788 void restore_handler_expandarg(struct jmploc *savehandler, int err)
1789 {
1790         handler = savehandler;
1791         if (err) {
1792                 if (exception != EXERROR)
1793                         longjmp(handler->loc, 1);
1794                 ifsfree();
1795         }
1796 }
1797
1798 #ifdef mkinit
1799
1800 INCLUDE "expand.h"
1801
1802 EXITRESET {
1803         ifsfree();
1804 }
1805
1806 #endif