contrib/tcsh/sh.glob.c

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