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