contrib/tcsh/sh.glob.c

   1 /* $Header: /src/pub/tcsh/sh.glob.c,v 3.54 2002/07/04 19:28:29 christos Exp $ */
   2 /*
   3  * sh.glob.c: Regular expression expansion
   4  */
   5 /*-
   6  * Copyright (c) 1980, 1991 The Regents of the University of California.
   7  * All rights reserved.
   8  *
   9  * Redistribution and use in source and binary forms, with or without
  10  * modification, are permitted provided that the following conditions
  11  * are met:
  12  * 1. Redistributions of source code must retain the above copyright
  13  *    notice, this list of conditions and the following disclaimer.
  14  * 2. Redistributions in binary form must reproduce the above copyright
  15  *    notice, this list of conditions and the following disclaimer in the
  16  *    documentation and/or other materials provided with the distribution.
  17  * 3. Neither the name of the University nor the names of its contributors
  18  *    may be used to endorse or promote products derived from this software
  19  *    without specific prior written permission.
  20  *
  21  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  22  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  23  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  24  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  25  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  26  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  27  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  28  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  29  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  30  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  31  * SUCH DAMAGE.
  32  */
  33 #include "sh.h"
  34
  35 RCSID("$Id: sh.glob.c,v 3.54 2002/07/04 19:28:29 christos Exp $")
  36
  37 #include "tc.h"
  38 #include "tw.h"
  39
  40 #include "glob.h"
  41
  42 static int noglob;
  43 static int pargsiz, gargsiz;
  44
  45 /*
  46  * Values for gflag
  47  */
  48 #define G_NONE  0               /* No globbing needed                   */
  49 #define G_GLOB  1               /* string contains *?[] characters      */
  50 #define G_CSH   2               /* string contains ~`{ characters       */
  51
  52 #define GLOBSPACE       100     /* Alloc increment                      */
  53 #define LONGBSIZE       10240   /* Backquote expansion buffer size      */
  54
  55
  56 #define LBRC '{'
  57 #define RBRC '}'
  58 #define LBRK '['
  59 #define RBRK ']'
  60 #define EOS '\0'
  61
  62 Char  **gargv = NULL;
  63 int     gargc = 0;
  64 Char  **pargv = NULL;
  65 static int pargc = 0;
  66
  67 /*
  68  * globbing is now done in two stages. In the first pass we expand
  69  * csh globbing idioms ~`{ and then we proceed doing the normal
  70  * globbing if needed ?*[
  71  *
  72  * Csh type globbing is handled in globexpand() and the rest is
  73  * handled in glob() which is part of the 4.4BSD libc.
  74  *
  75  */
  76 static  Char     *globtilde     __P((Char **, Char *));
  77 static  Char     *handleone     __P((Char *, Char **, int));
  78 static  Char    **libglob       __P((Char **));
  79 static  Char    **globexpand    __P((Char **));
  80 static  int       globbrace     __P((Char *, Char *, Char ***));
  81 static  void      expbrace      __P((Char ***, Char ***, int));
  82 static  int       pmatch        __P((Char *, Char *, Char **));
  83 static  void      pword         __P((int));
  84 static  void      psave         __P((int));
  85 static  void      backeval      __P((Char *, bool));
  86
  87 static Char *
  88 globtilde(nv, s)
  89     Char  **nv, *s;
  90 {
  91     Char    gbuf[BUFSIZE], *gstart, *b, *u, *e;
  92 #ifdef apollo
  93     int slash;
  94 #endif
  95
  96     gstart = gbuf;
  97     *gstart++ = *s++;
  98     u = s;
  99     for (b = gstart, e = &gbuf[BUFSIZE - 1];
 100          *s && *s != '/' && *s != ':' && b < e;
 101          *b++ = *s++)
 102         continue;
 103     *b = EOS;
 104     if (gethdir(gstart)) {
 105         if (adrof(STRnonomatch))
 106             return (--u);
 107         blkfree(nv);
 108         if (*gstart)
 109             stderror(ERR_UNKUSER, short2str(gstart));
 110         else
 111             stderror(ERR_NOHOME);
 112     }
 113     b = &gstart[Strlen(gstart)];
 114 #ifdef apollo
 115     slash = gstart[0] == '/' && gstart[1] == '\0';
 116 #endif
 117     while (*s)
 118         *b++ = *s++;
 119     *b = EOS;
 120     --u;
 121     xfree((ptr_t) u);
 122 #ifdef apollo
 123     if (slash && gstart[1] == '/')
 124         gstart++;
 125 #endif
 126     return (Strsave(gstart));
 127 }
 128
 129 Char *
 130 globequal(new, old)
 131     Char *new, *old;
 132 {
 133     int     dig;
 134     Char    *b, *d;
 135
 136     /*
 137      * kfk - 17 Jan 1984 - stack hack allows user to get at arbitrary dir names
 138      * in stack. PWP: let =foobar pass through (for X windows)
 139      */
 140     if (old[1] == '-' && (old[2] == '\0' || old[2] == '/')) {
 141         /* =- */
 142         dig = -1;
 143         b = &old[2];
 144     }
 145     else if (Isdigit(old[1])) {
 146         /* =<number> */
 147         dig = old[1] - '0';
 148         for (b = &old[2]; Isdigit(*b); b++)
 149             dig = dig * 10 + (*b - '0');
 150         if (*b != '\0' && *b != '/')
 151             /* =<number>foobar */
 152             return old;
 153     }
 154     else
 155         /* =foobar */
 156         return old;
 157
 158     if (!getstakd(new, dig))
 159         return NULL;
 160
 161     /* Copy the rest of the string */
 162     for (d = &new[Strlen(new)];
 163          d < &new[BUFSIZE - 1] && (*d++ = *b++) != '\0';)
 164         continue;
 165     *d = '\0';
 166
 167     return new;
 168 }
 169
 170 static int
 171 globbrace(s, p, bl)
 172     Char   *s, *p, ***bl;
 173 {
 174     int     i, len;
 175     Char   *pm, *pe, *lm, *pl;
 176     Char  **nv, **vl;
 177     Char    gbuf[BUFSIZE];
 178     int     size = GLOBSPACE;
 179
 180     nv = vl = (Char **) xmalloc((size_t) (sizeof(Char *) * size));
 181     *vl = NULL;
 182
 183     len = 0;
 184     /* copy part up to the brace */
 185     for (lm = gbuf, p = s; *p != LBRC; *lm++ = *p++)
 186         continue;
 187
 188     /* check for balanced braces */
 189     for (i = 0, pe = ++p; *pe; pe++)
 190 #ifdef DSPMBYTE
 191         if (Ismbyte1(*pe) && *(pe + 1) != EOS)
 192             pe ++;
 193         else
 194 #endif /* DSPMBYTE */
 195         if (*pe == LBRK) {
 196             /* Ignore everything between [] */
 197             for (++pe; *pe != RBRK && *pe != EOS; pe++)
 198 #ifdef DSPMBYTE
 199               if (Ismbyte1(*pe) && *(pe + 1) != EOS)
 200                 pe ++;
 201               else
 202 #endif /* DSPMBYTE */
 203                 continue;
 204             if (*pe == EOS) {
 205                 blkfree(nv);
 206                 return (-RBRK);
 207             }
 208         }
 209         else if (*pe == LBRC)
 210             i++;
 211         else if (*pe == RBRC) {
 212             if (i == 0)
 213                 break;
 214             i--;
 215         }
 216
 217     if (i != 0 || *pe == '\0') {
 218         blkfree(nv);
 219         return (-RBRC);
 220     }
 221
 222     for (i = 0, pl = pm = p; pm <= pe; pm++)
 223 #ifdef DSPMBYTE
 224         if (Ismbyte1(*pm) && pm + 1 <= pe)
 225             pm ++;
 226         else
 227 #endif /* DSPMBYTE */
 228         switch (*pm) {
 229         case LBRK:
 230             for (++pm; *pm != RBRK && *pm != EOS; pm++)
 231 #ifdef DSPMBYTE
 232               if (Ismbyte1(*pm) && *(pm + 1) != EOS)
 233                 pm ++;
 234               else
 235 #endif /* DSPMBYTE */
 236                 continue;
 237             if (*pm == EOS) {
 238                 *vl = NULL;
 239                 blkfree(nv);
 240                 return (-RBRK);
 241             }
 242             break;
 243         case LBRC:
 244             i++;
 245             break;
 246         case RBRC:
 247             if (i) {
 248                 i--;
 249                 break;
 250             }
 251             /* FALLTHROUGH */
 252         case ',':
 253             if (i && *pm == ',')
 254                 break;
 255             else {
 256                 Char    savec = *pm;
 257
 258                 *pm = EOS;
 259                 (void) Strcpy(lm, pl);
 260                 (void) Strcat(gbuf, pe + 1);
 261                 *pm = savec;
 262                 *vl++ = Strsave(gbuf);
 263                 len++;
 264                 pl = pm + 1;
 265                 if (vl == &nv[size]) {
 266                     size += GLOBSPACE;
 267                     nv = (Char **) xrealloc((ptr_t) nv,
 268                                             (size_t) (size * sizeof(Char *)));
 269                     vl = &nv[size - GLOBSPACE];
 270                 }
 271             }
 272             break;
 273         default:
 274             break;
 275         }
 276     *vl = NULL;
 277     *bl = nv;
 278     return (len);
 279 }
 280
 281
 282 static void
 283 expbrace(nvp, elp, size)
 284     Char ***nvp, ***elp;
 285     int size;
 286 {
 287     Char **vl, **el, **nv, *s;
 288
 289     vl = nv = *nvp;
 290     if (elp != NULL)
 291         el = *elp;
 292     else
 293         for (el = vl; *el; el++)
 294             continue;
 295
 296     for (s = *vl; s; s = *++vl) {
 297         Char   *b;
 298         Char  **vp, **bp;
 299
 300         /* leave {} untouched for find */
 301         if (s[0] == '{' && (s[1] == '\0' || (s[1] == '}' && s[2] == '\0')))
 302             continue;
 303         if ((b = Strchr(s, '{')) != NULL) {
 304             Char  **bl;
 305             int     len;
 306
 307 #if defined (DSPMBYTE)
 308             if (b != s && Ismbyte2(*b) && Ismbyte1(*(b-1))) {
 309                 /* The "{" is the 2nd byte of a MB character */
 310                 continue;
 311             }
 312 #endif /* DSPMBYTE */
 313             if ((len = globbrace(s, b, &bl)) < 0) {
 314                 xfree((ptr_t) nv);
 315                 stderror(ERR_MISSING, -len);
 316             }
 317             xfree((ptr_t) s);
 318             if (len == 1) {
 319                 *vl-- = *bl;
 320                 xfree((ptr_t) bl);
 321                 continue;
 322             }
 323             if (&el[len] >= &nv[size]) {
 324                 int     l, e;
 325                 l = (int) (&el[len] - &nv[size]);
 326                 size += GLOBSPACE > l ? GLOBSPACE : l;
 327                 l = (int) (vl - nv);
 328                 e = (int) (el - nv);
 329                 nv = (Char **) xrealloc((ptr_t) nv,
 330                                         (size_t) (size * sizeof(Char *)));
 331                 vl = nv + l;
 332                 el = nv + e;
 333             }
 334             /* nv vl   el     bl
 335              * |  |    |      |
 336              * -.--..--       x--
 337              *   |            len
 338              *   vp
 339              */
 340             vp = vl--;
 341             *vp = *bl;
 342             len--;
 343             for (bp = el; bp != vp; bp--)
 344                 bp[len] = *bp;
 345             el += len;
 346             /* nv vl    el bl
 347              * |  |     |  |
 348              * -.-x  ---    --
 349              *   |len
 350              *   vp
 351              */
 352             vp++;
 353             for (bp = bl + 1; *bp; *vp++ = *bp++)
 354                 continue;
 355             xfree((ptr_t) bl);
 356         }
 357
 358     }
 359     if (elp != NULL)
 360         *elp = el;
 361     *nvp = nv;
 362 }
 363
 364 static Char **
 365 globexpand(v)
 366     Char  **v;
 367 {
 368     Char   *s;
 369     Char  **nv, **vl, **el;
 370     int     size = GLOBSPACE;
 371
 372
 373     nv = vl = (Char **) xmalloc((size_t) (sizeof(Char *) * size));
 374     *vl = NULL;
 375
 376     /*
 377      * Step 1: expand backquotes.
 378      */
 379     while ((s = *v++) != '\0') {
 380         if (Strchr(s, '`')) {
 381             int     i;
 382
 383             (void) dobackp(s, 0);
 384             for (i = 0; i < pargc; i++) {
 385                 *vl++ = pargv[i];
 386                 if (vl == &nv[size]) {
 387                     size += GLOBSPACE;
 388                     nv = (Char **) xrealloc((ptr_t) nv,
 389                                             (size_t) (size * sizeof(Char *)));
 390                     vl = &nv[size - GLOBSPACE];
 391                 }
 392             }
 393             xfree((ptr_t) pargv);
 394             pargv = NULL;
 395         }
 396         else {
 397             *vl++ = Strsave(s);
 398             if (vl == &nv[size]) {
 399                 size += GLOBSPACE;
 400                 nv = (Char **) xrealloc((ptr_t) nv,
 401                                         (size_t) (size * sizeof(Char *)));
 402                 vl = &nv[size - GLOBSPACE];
 403             }
 404         }
 405     }
 406     *vl = NULL;
 407
 408     if (noglob)
 409         return (nv);
 410
 411     /*
 412      * Step 2: expand braces
 413      */
 414     el = vl;
 415     expbrace(&nv, &el, size);
 416
 417
 418     /*
 419      * Step 3: expand ~ =
 420      */
 421     vl = nv;
 422     for (s = *vl; s; s = *++vl)
 423         switch (*s) {
 424             Char gp[BUFSIZE], *ns;
 425         case '~':
 426             *vl = globtilde(nv, s);
 427             break;
 428         case '=':
 429             if ((ns = globequal(gp, s)) == NULL) {
 430                 if (!adrof(STRnonomatch)) {
 431                     /* Error */
 432                     blkfree(nv);
 433                     stderror(ERR_DEEP);
 434                 }
 435             }
 436             if (ns && ns != s) {
 437                 /* Expansion succeeded */
 438                 xfree((ptr_t) s);
 439                 *vl = Strsave(gp);
 440             }
 441             break;
 442         default:
 443             break;
 444         }
 445     vl = nv;
 446
 447     /*
 448      * Step 4: expand .. if the variable symlinks==expand is set
 449      */
 450     if (symlinks == SYM_EXPAND) {
 451         for (s = *vl; s; s = *++vl) {
 452             *vl = dnormalize(s, 1);
 453             xfree((ptr_t) s);
 454         }
 455     }
 456     vl = nv;
 457
 458     return (vl);
 459 }
 460
 461 static Char *
 462 handleone(str, vl, action)
 463     Char   *str, **vl;
 464     int     action;
 465 {
 466
 467     Char   **vlp = vl;
 468     int chars;
 469     Char **t, *p, *strp;
 470
 471     switch (action) {
 472     case G_ERROR:
 473         setname(short2str(str));
 474         blkfree(vl);
 475         stderror(ERR_NAME | ERR_AMBIG);
 476         break;
 477     case G_APPEND:
 478         chars = 0;
 479         for (t = vlp; (p = *t++) != '\0'; chars++)
 480             while (*p++)
 481                 chars++;
 482         str = (Char *)xmalloc((size_t)(chars * sizeof(Char)));
 483         for (t = vlp, strp = str; (p = *t++) != '\0'; chars++) {
 484             while (*p)
 485                  *strp++ = *p++ & TRIM;
 486             *strp++ = ' ';
 487         }
 488         *--strp = '\0';
 489         blkfree(vl);
 490         break;
 491     case G_IGNORE:
 492         str = Strsave(strip(*vlp));
 493         blkfree(vl);
 494         break;
 495     default:
 496         break;
 497     }
 498     return (str);
 499 }
 500
 501 static Char **
 502 libglob(vl)
 503     Char  **vl;
 504 {
 505     int     gflgs = GLOB_QUOTE | GLOB_NOMAGIC | GLOB_ALTNOT;
 506     glob_t  globv;
 507     char   *ptr;
 508     int     nonomatch = adrof(STRnonomatch) != 0, magic = 0, match = 0;
 509
 510     if (!vl || !vl[0])
 511         return(vl);
 512
 513     globv.gl_offs = 0;
 514     globv.gl_pathv = 0;
 515     globv.gl_pathc = 0;
 516
 517     if (nonomatch)
 518         gflgs |= GLOB_NOCHECK;
 519
 520     do {
 521         ptr = short2qstr(*vl);
 522         switch (glob(ptr, gflgs, 0, &globv)) {
 523         case GLOB_ABEND:
 524             globfree(&globv);
 525             setname(ptr);
 526             stderror(ERR_NAME | ERR_GLOB);
 527             /* NOTREACHED */
 528         case GLOB_NOSPACE:
 529             globfree(&globv);
 530             stderror(ERR_NOMEM);
 531             /* NOTREACHED */
 532         default:
 533             break;
 534         }
 535         if (globv.gl_flags & GLOB_MAGCHAR) {
 536             match |= (globv.gl_matchc != 0);
 537             magic = 1;
 538         }
 539         gflgs |= GLOB_APPEND;
 540     }
 541     while (*++vl);
 542     vl = (globv.gl_pathc == 0 || (magic && !match && !nonomatch)) ?
 543         NULL : blk2short(globv.gl_pathv);
 544     globfree(&globv);
 545     return (vl);
 546 }
 547
 548 Char   *
 549 globone(str, action)
 550     Char   *str;
 551     int     action;
 552 {
 553
 554     Char   *v[2], **vl, **vo;
 555     int gflg;
 556
 557     noglob = adrof(STRnoglob) != 0;
 558     gflag = 0;
 559     v[0] = str;
 560     v[1] = 0;
 561     tglob(v);
 562     gflg = gflag;
 563     if (gflg == G_NONE)
 564         return (strip(Strsave(str)));
 565
 566     if (gflg & G_CSH) {
 567         /*
 568          * Expand back-quote, tilde and brace
 569          */
 570         vo = globexpand(v);
 571         if (noglob || (gflg & G_GLOB) == 0) {
 572             if (vo[0] == NULL) {
 573                 xfree((ptr_t) vo);
 574                 return (Strsave(STRNULL));
 575             }
 576             if (vo[1] != NULL)
 577                 return (handleone(str, vo, action));
 578             else {
 579                 str = strip(vo[0]);
 580                 xfree((ptr_t) vo);
 581                 return (str);
 582             }
 583         }
 584     }
 585     else if (noglob || (gflg & G_GLOB) == 0)
 586         return (strip(Strsave(str)));
 587     else
 588         vo = v;
 589
 590     vl = libglob(vo);
 591     if ((gflg & G_CSH) && vl != vo)
 592         blkfree(vo);
 593     if (vl == NULL) {
 594         setname(short2str(str));
 595         stderror(ERR_NAME | ERR_NOMATCH);
 596     }
 597     if (vl[0] == NULL) {
 598         xfree((ptr_t) vl);
 599         return (Strsave(STRNULL));
 600     }
 601     if (vl[1])
 602         return (handleone(str, vl, action));
 603     else {
 604         str = strip(*vl);
 605         xfree((ptr_t) vl);
 606         return (str);
 607     }
 608 }
 609
 610 Char  **
 611 globall(v)
 612     Char  **v;
 613 {
 614     Char  **vl, **vo;
 615     int gflg = gflag;
 616
 617     if (!v || !v[0]) {
 618         gargv = saveblk(v);
 619         gargc = blklen(gargv);
 620         return (gargv);
 621     }
 622
 623     noglob = adrof(STRnoglob) != 0;
 624
 625     if (gflg & G_CSH)
 626         /*
 627          * Expand back-quote, tilde and brace
 628          */
 629         vl = vo = globexpand(v);
 630     else
 631         vl = vo = saveblk(v);
 632
 633     if (!noglob && (gflg & G_GLOB)) {
 634         vl = libglob(vo);
 635         if (vl != vo)
 636             blkfree(vo);
 637     }
 638     else
 639         trim(vl);
 640
 641     gargc = vl ? blklen(vl) : 0;
 642     return (gargv = vl);
 643 }
 644
 645 void
 646 ginit()
 647 {
 648     gargsiz = GLOBSPACE;
 649     gargv = (Char **) xmalloc((size_t) (sizeof(Char *) * gargsiz));
 650     gargv[0] = 0;
 651     gargc = 0;
 652 }
 653
 654 void
 655 rscan(t, f)
 656     register Char **t;
 657     void    (*f) __P((int));
 658 {
 659     register Char *p;
 660
 661     while ((p = *t++) != '\0')
 662         while (*p)
 663             (*f) (*p++);
 664 }
 665
 666 void
 667 trim(t)
 668     register Char **t;
 669 {
 670     register Char *p;
 671
 672     while ((p = *t++) != '\0')
 673         while (*p)
 674             *p++ &= TRIM;
 675 }
 676
 677 void
 678 tglob(t)
 679     register Char **t;
 680 {
 681     register Char *p, *c;
 682
 683     while ((p = *t++) != '\0') {
 684         if (*p == '~' || *p == '=')
 685             gflag |= G_CSH;
 686         else if (*p == '{' &&
 687                  (p[1] == '\0' || (p[1] == '}' && p[2] == '\0')))
 688             continue;
 689         /*
 690          * The following line used to be *(c = p++), but hp broke their
 691          * optimizer in 9.01, so we break the assignment into two pieces
 692          * The careful reader here will note that *most* compiler workarounds
 693          * in tcsh are either for apollo/DomainOS or hpux. Is it a coincidence?
 694          */
 695         while ( *(c = p) != '\0') {
 696             p++;
 697             if (*c == '`') {
 698                 gflag |= G_CSH;
 699 #ifdef notdef
 700                 /*
 701                  * We do want to expand echo `echo '*'`, so we don't\
 702                  * use this piece of code anymore.
 703                  */
 704                 while (*p && *p != '`')
 705                     if (*p++ == '\\') {
 706                         if (*p)         /* Quoted chars */
 707                             p++;
 708                         else
 709                             break;
 710                     }
 711                 if (*p)                 /* The matching ` */
 712                     p++;
 713                 else
 714                     break;
 715 #endif
 716             }
 717             else if (*c == '{')
 718                 gflag |= G_CSH;
 719             else if (isglob(*c))
 720                 gflag |= G_GLOB;
 721             else if (symlinks == SYM_EXPAND &&
 722                 *p && ISDOTDOT(c) && (c == *(t-1) || *(c-1) == '/') )
 723                 gflag |= G_CSH;
 724         }
 725     }
 726 }
 727
 728 /*
 729  * Command substitute cp.  If literal, then this is a substitution from a
 730  * << redirection, and so we should not crunch blanks and tabs, separating
 731  * words only at newlines.
 732  */
 733 Char  **
 734 dobackp(cp, literal)
 735     Char   *cp;
 736     bool    literal;
 737 {
 738     register Char *lp, *rp;
 739     Char   *ep, word[LONGBSIZE];
 740
 741     if (pargv) {
 742 #ifdef notdef
 743         abort();
 744 #endif
 745         blkfree(pargv);
 746     }
 747     pargsiz = GLOBSPACE;
 748     pargv = (Char **) xmalloc((size_t) (sizeof(Char *) * pargsiz));
 749     pargv[0] = NULL;
 750     pargcp = pargs = word;
 751     pargc = 0;
 752     pnleft = LONGBSIZE - 4;
 753     for (;;) {
 754 #if defined(DSPMBYTE)
 755         for (lp = cp;; lp++) { /* } */
 756             if (*lp == '`' &&
 757                 (lp-1 < cp || !Ismbyte2(*lp) || !Ismbyte1(*(lp-1)))) {
 758                 break;
 759             }
 760 #else /* DSPMBYTE */
 761         for (lp = cp; *lp != '`'; lp++) {
 762 #endif /* DSPMBYTE */
 763             if (*lp == 0) {
 764                 if (pargcp != pargs)
 765                     pword(LONGBSIZE);
 766                 return (pargv);
 767             }
 768             psave(*lp);
 769         }
 770         lp++;
 771         for (rp = lp; *rp && *rp != '`'; rp++)
 772             if (*rp == '\\') {
 773                 rp++;
 774                 if (!*rp)
 775                     goto oops;
 776             }
 777         if (!*rp)
 778     oops:  stderror(ERR_UNMATCHED, '`');
 779         ep = Strsave(lp);
 780         ep[rp - lp] = 0;
 781         backeval(ep, literal);
 782         cp = rp + 1;
 783     }
 784 }
 785
 786
 787 static void
 788 backeval(cp, literal)
 789     Char   *cp;
 790     bool    literal;
 791 {
 792     register int icnt, c;
 793     register Char *ip;
 794     struct command faket;
 795     bool    hadnl;
 796     int     pvec[2], quoted;
 797     Char   *fakecom[2], ibuf[BUFSIZE];
 798     char    tibuf[BUFSIZE];
 799
 800     hadnl = 0;
 801     icnt = 0;
 802     quoted = (literal || (cp[0] & QUOTE)) ? QUOTE : 0;
 803     faket.t_dtyp = NODE_COMMAND;
 804     faket.t_dflg = F_BACKQ;
 805     faket.t_dlef = 0;
 806     faket.t_drit = 0;
 807     faket.t_dspr = 0;
 808     faket.t_dcom = fakecom;
 809     fakecom[0] = STRfakecom1;
 810     fakecom[1] = 0;
 811
 812     /*
 813      * We do the psave job to temporarily change the current job so that the
 814      * following fork is considered a separate job.  This is so that when
 815      * backquotes are used in a builtin function that calls glob the "current
 816      * job" is not corrupted.  We only need one level of pushed jobs as long as
 817      * we are sure to fork here.
 818      */
 819     psavejob();
 820
 821     /*
 822      * It would be nicer if we could integrate this redirection more with the
 823      * routines in sh.sem.c by doing a fake execute on a builtin function that
 824      * was piped out.
 825      */
 826     mypipe(pvec);
 827     if (pfork(&faket, -1) == 0) {
 828         struct command *t;
 829
 830         (void) close(pvec[0]);
 831         (void) dmove(pvec[1], 1);
 832         (void) dmove(SHDIAG,  2);
 833         initdesc();
 834         closem();
 835         /*
 836          * Bugfix for nested backquotes by Michael Greim <greim@sbsvax.UUCP>,
 837          * posted to comp.bugs.4bsd 12 Sep. 1989.
 838          */
 839         if (pargv)              /* mg, 21.dec.88 */
 840             blkfree(pargv), pargv = 0, pargsiz = 0;
 841         /* mg, 21.dec.88 */
 842         arginp = cp;
 843         for (arginp = cp; *cp; cp++) {
 844             *cp &= TRIM;
 845             if (*cp == '\n' || *cp == '\r')
 846                 *cp = ' ';
 847         }
 848
 849         /*
 850          * In the child ``forget'' everything about current aliases or
 851          * eval vectors.
 852          */
 853         alvec = NULL;
 854         evalvec = NULL;
 855         alvecp = NULL;
 856         evalp = NULL;
 857         (void) lex(&paraml);
 858         if (seterr)
 859             stderror(ERR_OLD);
 860         alias(&paraml);
 861         t = syntax(paraml.next, &paraml, 0);
 862         if (seterr)
 863             stderror(ERR_OLD);
 864         if (t)
 865             t->t_dflg |= F_NOFORK;
 866 #ifdef SIGTSTP
 867         (void) sigignore(SIGTSTP);
 868 #endif
 869 #ifdef SIGTTIN
 870         (void) sigignore(SIGTTIN);
 871 #endif
 872 #ifdef SIGTTOU
 873         (void) sigignore(SIGTTOU);
 874 #endif
 875         execute(t, -1, NULL, NULL, TRUE);
 876         exitstat();
 877     }
 878     xfree((ptr_t) cp);
 879     (void) close(pvec[1]);
 880     c = 0;
 881     ip = NULL;
 882     do {
 883         int     cnt = 0;
 884
 885         for (;;) {
 886             if (icnt == 0) {
 887                 int     i;
 888
 889                 ip = ibuf;
 890                 do
 891                     icnt = read(pvec[0], tibuf, BUFSIZE);
 892                 while (icnt == -1 && errno == EINTR);
 893                 if (icnt <= 0) {
 894                     c = -1;
 895                     break;
 896                 }
 897                 for (i = 0; i < icnt; i++)
 898                     ip[i] = (unsigned char) tibuf[i];
 899             }
 900             if (hadnl)
 901                 break;
 902             --icnt;
 903             c = (*ip++ & TRIM);
 904             if (c == 0)
 905                 break;
 906 #ifdef WINNT_NATIVE
 907             if (c == '\r')
 908                 c = ' ';
 909 #endif /* WINNT_NATIVE */
 910             if (c == '\n') {
 911                 /*
 912                  * Continue around the loop one more time, so that we can eat
 913                  * the last newline without terminating this word.
 914                  */
 915                 hadnl = 1;
 916                 continue;
 917             }
 918             if (!quoted && (c == ' ' || c == '\t'))
 919                 break;
 920             cnt++;
 921             psave(c | quoted);
 922         }
 923         /*
 924          * Unless at end-of-file, we will form a new word here if there were
 925          * characters in the word, or in any case when we take text literally.
 926          * If we didn't make empty words here when literal was set then we
 927          * would lose blank lines.
 928          */
 929         if (c != -1 && (cnt || literal))
 930             pword(BUFSIZE);
 931         hadnl = 0;
 932     } while (c >= 0);
 933     (void) close(pvec[0]);
 934     pwait();
 935     prestjob();
 936 }
 937
 938 static void
 939 psave(c)
 940     int    c;
 941 {
 942     if (--pnleft <= 0)
 943         stderror(ERR_WTOOLONG);
 944     *pargcp++ = (Char) c;
 945 }
 946
 947 static void
 948 pword(bufsiz)
 949     int    bufsiz;
 950 {
 951     psave(0);
 952     if (pargc == pargsiz - 1) {
 953         pargsiz += GLOBSPACE;
 954         pargv = (Char **) xrealloc((ptr_t) pargv,
 955                                    (size_t) (pargsiz * sizeof(Char *)));
 956     }
 957     pargv[pargc++] = Strsave(pargs);
 958     pargv[pargc] = NULL;
 959     pargcp = pargs;
 960     pnleft = bufsiz - 4;
 961 }
 962
 963 int
 964 Gmatch(string, pattern)
 965     Char *string, *pattern;
 966 {
 967     return Gnmatch(string, pattern, NULL);
 968 }
 969
 970 int
 971 Gnmatch(string, pattern, endstr)
 972     Char *string, *pattern, **endstr;
 973 {
 974     Char **blk, **p, *tstring = string;
 975     int    gpol = 1, gres = 0;
 976
 977     if (*pattern == '^') {
 978         gpol = 0;
 979         pattern++;
 980     }
 981
 982     blk = (Char **) xmalloc((size_t) (GLOBSPACE * sizeof(Char *)));
 983     blk[0] = Strsave(pattern);
 984     blk[1] = NULL;
 985
 986     expbrace(&blk, NULL, GLOBSPACE);
 987
 988     if (endstr == NULL)
 989         /* Exact matches only */
 990         for (p = blk; *p; p++)
 991             gres |= pmatch(string, *p, &tstring) == 2 ? 1 : 0;
 992     else {
 993         /* partial matches */
 994         int minc = 0x7fffffff;
 995         for (p = blk; *p; p++)
 996             if (pmatch(string, *p, &tstring) != 0) {
 997                 int t = (int) (tstring - string);
 998                 gres |= 1;
 999                 if (minc == -1 || minc > t)
1000                     minc = t;
1001             }
1002         *endstr = string + minc;
1003     }
1004
1005     blkfree(blk);
1006     return(gres == gpol);
1007 }
1008
1009 /* pmatch():
1010  *      Return 2 on exact match,
1011  *      Return 1 on substring match.
1012  *      Return 0 on no match.
1013  *      *estr will point to the end of the longest exact or substring match.
1014  */
1015 static int
1016 pmatch(string, pattern, estr)
1017     register Char *string, *pattern, **estr;
1018 {
1019     register Char stringc, patternc;
1020     int     match, negate_range;
1021     Char    rangec, *oestr, *pestr;
1022
1023     for (;; ++string) {
1024         stringc = *string & TRIM;
1025         /*
1026          * apollo compiler bug: switch (patternc = *pattern++) dies
1027          */
1028         patternc = *pattern++;
1029         switch (patternc) {
1030         case 0:
1031             *estr = string;
1032             return (stringc == 0 ? 2 : 1);
1033         case '?':
1034             if (stringc == 0)
1035                 return (0);
1036             *estr = string;
1037             break;
1038         case '*':
1039             if (!*pattern) {
1040                 while (*string) string++;
1041                 *estr = string;
1042                 return (2);
1043             }
1044             oestr = *estr;
1045             pestr = NULL;
1046
1047             do {
1048                 switch(pmatch(string, pattern, estr)) {
1049                 case 0:
1050                     break;
1051                 case 1:
1052                     pestr = *estr;
1053                     break;
1054                 case 2:
1055                     return 2;
1056                 default:
1057                     abort();    /* Cannot happen */
1058                 }
1059                 *estr = string;
1060             }
1061             while (*string++);
1062
1063             if (pestr) {
1064                 *estr = pestr;
1065                 return 1;
1066             }
1067             else {
1068                 *estr = oestr;
1069                 return 0;
1070             }
1071
1072         case '[':
1073             match = 0;
1074             if ((negate_range = (*pattern == '^')) != 0)
1075                 pattern++;
1076             while ((rangec = *pattern++) != '\0') {
1077                 if (rangec == ']')
1078                     break;
1079                 if (match)
1080                     continue;
1081                 if (rangec == '-' && *(pattern-2) != '[' && *pattern  != ']') {
1082                     match = (globcharcoll(stringc, *pattern & TRIM) <= 0 &&
1083                     globcharcoll(*(pattern-2) & TRIM, stringc) <= 0);
1084                     pattern++;
1085                 }
1086                 else
1087                     match = (stringc == (rangec & TRIM));
1088             }
1089             if (rangec == 0)
1090                 stderror(ERR_NAME | ERR_MISSING, ']');
1091             if (match == negate_range)
1092                 return (0);
1093             *estr = string;
1094             break;
1095         default:
1096             if ((patternc & TRIM) != stringc)
1097                 return (0);
1098             *estr = string;
1099             break;
1100         }
1101     }
1102 }
1103
1104 void
1105 Gcat(s1, s2)
1106     Char   *s1, *s2;
1107 {
1108     register Char *p, *q;
1109     int     n;
1110
1111     for (p = s1; *p++;)
1112         continue;
1113     for (q = s2; *q++;)
1114         continue;
1115     n = (int) ((p - s1) + (q - s2) - 1);
1116     if (++gargc >= gargsiz) {
1117         gargsiz += GLOBSPACE;
1118         gargv = (Char **) xrealloc((ptr_t) gargv,
1119                                    (size_t) (gargsiz * sizeof(Char *)));
1120     }
1121     gargv[gargc] = 0;
1122     p = gargv[gargc - 1] = (Char *) xmalloc((size_t) (n * sizeof(Char)));
1123     for (q = s1; (*p++ = *q++) != '\0';)
1124         continue;
1125     for (p--, q = s2; (*p++ = *q++) != '\0';)
1126         continue;
1127 }
1128
1129 #if defined(FILEC) && defined(TIOCSTI)
1130 int
1131 sortscmp(a, b)
1132     register Char **a, **b;
1133 {
1134     if (!a)                     /* check for NULL */
1135         return (b ? 1 : 0);
1136     if (!b)
1137         return (-1);
1138
1139     if (!*a)                    /* check for NULL */
1140         return (*b ? 1 : 0);
1141     if (!*b)
1142         return (-1);
1143
1144     return (int) collate(*a, *b);
1145 }
1146
1147 #endif