contrib/tcsh/sh.glob.c

   1 /* $Header: /src/pub/tcsh/sh.glob.c,v 3.44 2000/01/14 22:57:28 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.44 2000/01/14 22:57:28 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             *vl = dnormalize(s, 1);
 456             xfree((ptr_t) s);
 457         }
 458     vl = nv;
 459
 460     return (vl);
 461 }
 462
 463 static Char *
 464 handleone(str, vl, action)
 465     Char   *str, **vl;
 466     int     action;
 467 {
 468
 469     Char   **vlp = vl;
 470     int chars;
 471     Char **t, *p, *strp;
 472
 473     switch (action) {
 474     case G_ERROR:
 475         setname(short2str(str));
 476         blkfree(vl);
 477         stderror(ERR_NAME | ERR_AMBIG);
 478         break;
 479     case G_APPEND:
 480         chars = 0;
 481         for (t = vlp; (p = *t++) != '\0'; chars++)
 482             while (*p++)
 483                 chars++;
 484         str = (Char *)xmalloc((size_t)(chars * sizeof(Char)));
 485         for (t = vlp, strp = str; (p = *t++) != '\0'; chars++) {
 486             while (*p)
 487                  *strp++ = *p++ & TRIM;
 488             *strp++ = ' ';
 489         }
 490         *--strp = '\0';
 491         blkfree(vl);
 492         break;
 493     case G_IGNORE:
 494         str = Strsave(strip(*vlp));
 495         blkfree(vl);
 496         break;
 497     default:
 498         break;
 499     }
 500     return (str);
 501 }
 502
 503 static Char **
 504 libglob(vl)
 505     Char  **vl;
 506 {
 507     int     gflgs = GLOB_QUOTE | GLOB_NOMAGIC | GLOB_ALTNOT;
 508     glob_t  globv;
 509     char   *ptr;
 510     int     nonomatch = adrof(STRnonomatch) != 0, magic = 0, match = 0;
 511
 512     if (!vl || !vl[0])
 513         return(vl);
 514
 515     globv.gl_offs = 0;
 516     globv.gl_pathv = 0;
 517     globv.gl_pathc = 0;
 518
 519     if (nonomatch)
 520         gflgs |= GLOB_NOCHECK;
 521
 522     do {
 523         ptr = short2qstr(*vl);
 524         switch (glob(ptr, gflgs, 0, &globv)) {
 525         case GLOB_ABEND:
 526             globfree(&globv);
 527             setname(ptr);
 528             stderror(ERR_NAME | ERR_GLOB);
 529             /* NOTREACHED */
 530         case GLOB_NOSPACE:
 531             globfree(&globv);
 532             stderror(ERR_NOMEM);
 533             /* NOTREACHED */
 534         default:
 535             break;
 536         }
 537         if (globv.gl_flags & GLOB_MAGCHAR) {
 538             match |= (globv.gl_matchc != 0);
 539             magic = 1;
 540         }
 541         gflgs |= GLOB_APPEND;
 542     }
 543     while (*++vl);
 544     vl = (globv.gl_pathc == 0 || (magic && !match && !nonomatch)) ?
 545         NULL : blk2short(globv.gl_pathv);
 546     globfree(&globv);
 547     return (vl);
 548 }
 549
 550 Char   *
 551 globone(str, action)
 552     Char   *str;
 553     int     action;
 554 {
 555
 556     Char   *v[2], **vl, **vo;
 557     int gflg;
 558
 559     noglob = adrof(STRnoglob) != 0;
 560     gflag = 0;
 561     v[0] = str;
 562     v[1] = 0;
 563     tglob(v);
 564     gflg = gflag;
 565     if (gflg == G_NONE)
 566         return (strip(Strsave(str)));
 567
 568     if (gflg & G_CSH) {
 569         /*
 570          * Expand back-quote, tilde and brace
 571          */
 572         vo = globexpand(v);
 573         if (noglob || (gflg & G_GLOB) == 0) {
 574             if (vo[0] == NULL) {
 575                 xfree((ptr_t) vo);
 576                 return (Strsave(STRNULL));
 577             }
 578             if (vo[1] != NULL)
 579                 return (handleone(str, vo, action));
 580             else {
 581                 str = strip(vo[0]);
 582                 xfree((ptr_t) vo);
 583                 return (str);
 584             }
 585         }
 586     }
 587     else if (noglob || (gflg & G_GLOB) == 0)
 588         return (strip(Strsave(str)));
 589     else
 590         vo = v;
 591
 592     vl = libglob(vo);
 593     if ((gflg & G_CSH) && vl != vo)
 594         blkfree(vo);
 595     if (vl == NULL) {
 596         setname(short2str(str));
 597         stderror(ERR_NAME | ERR_NOMATCH);
 598     }
 599     if (vl[0] == NULL) {
 600         xfree((ptr_t) vl);
 601         return (Strsave(STRNULL));
 602     }
 603     if (vl[1])
 604         return (handleone(str, vl, action));
 605     else {
 606         str = strip(*vl);
 607         xfree((ptr_t) vl);
 608         return (str);
 609     }
 610 }
 611
 612 Char  **
 613 globall(v)
 614     Char  **v;
 615 {
 616     Char  **vl, **vo;
 617     int gflg = gflag;
 618
 619     if (!v || !v[0]) {
 620         gargv = saveblk(v);
 621         gargc = blklen(gargv);
 622         return (gargv);
 623     }
 624
 625     noglob = adrof(STRnoglob) != 0;
 626
 627     if (gflg & G_CSH)
 628         /*
 629          * Expand back-quote, tilde and brace
 630          */
 631         vl = vo = globexpand(v);
 632     else
 633         vl = vo = saveblk(v);
 634
 635     if (!noglob && (gflg & G_GLOB)) {
 636         vl = libglob(vo);
 637         if (vl != vo)
 638             blkfree(vo);
 639     }
 640     else
 641         trim(vl);
 642
 643     gargc = vl ? blklen(vl) : 0;
 644     return (gargv = vl);
 645 }
 646
 647 void
 648 ginit()
 649 {
 650     gargsiz = GLOBSPACE;
 651     gargv = (Char **) xmalloc((size_t) (sizeof(Char *) * gargsiz));
 652     gargv[0] = 0;
 653     gargc = 0;
 654 }
 655
 656 void
 657 rscan(t, f)
 658     register Char **t;
 659     void    (*f) __P((int));
 660 {
 661     register Char *p;
 662
 663     while ((p = *t++) != '\0')
 664         while (*p)
 665             (*f) (*p++);
 666 }
 667
 668 void
 669 trim(t)
 670     register Char **t;
 671 {
 672     register Char *p;
 673
 674     while ((p = *t++) != '\0')
 675         while (*p)
 676             *p++ &= TRIM;
 677 }
 678
 679 void
 680 tglob(t)
 681     register Char **t;
 682 {
 683     register Char *p, *c;
 684
 685     while ((p = *t++) != '\0') {
 686         if (*p == '~' || *p == '=')
 687             gflag |= G_CSH;
 688         else if (*p == '{' &&
 689                  (p[1] == '\0' || (p[1] == '}' && p[2] == '\0')))
 690             continue;
 691         /*
 692          * The following line used to be *(c = p++), but hp broke their
 693          * optimizer in 9.01, so we break the assignment into two pieces
 694          * The careful reader here will note that *most* compiler workarounds
 695          * in tcsh are either for apollo/DomainOS or hpux. Is it a coincidence?
 696          */
 697         while ( *(c = p) != '\0') {
 698             p++;
 699             if (*c == '`') {
 700                 gflag |= G_CSH;
 701 #ifdef notdef
 702                 /*
 703                  * We do want to expand echo `echo '*'`, so we don't\
 704                  * use this piece of code anymore.
 705                  */
 706                 while (*p && *p != '`')
 707                     if (*p++ == '\\') {
 708                         if (*p)         /* Quoted chars */
 709                             p++;
 710                         else
 711                             break;
 712                     }
 713                 if (*p)                 /* The matching ` */
 714                     p++;
 715                 else
 716                     break;
 717 #endif
 718             }
 719             else if (*c == '{')
 720                 gflag |= G_CSH;
 721             else if (isglob(*c))
 722                 gflag |= G_GLOB;
 723             else if (symlinks == SYM_EXPAND &&
 724                 *p && ISDOTDOT(c) && (c == *(t-1) || *(c-1) == '/') )
 725                 gflag |= G_CSH;
 726         }
 727     }
 728 }
 729
 730 /*
 731  * Command substitute cp.  If literal, then this is a substitution from a
 732  * << redirection, and so we should not crunch blanks and tabs, separating
 733  * words only at newlines.
 734  */
 735 Char  **
 736 dobackp(cp, literal)
 737     Char   *cp;
 738     bool    literal;
 739 {
 740     register Char *lp, *rp;
 741     Char   *ep, word[LONGBSIZE];
 742
 743     if (pargv) {
 744 #ifdef notdef
 745         abort();
 746 #endif
 747         blkfree(pargv);
 748     }
 749     pargsiz = GLOBSPACE;
 750     pargv = (Char **) xmalloc((size_t) (sizeof(Char *) * pargsiz));
 751     pargv[0] = NULL;
 752     pargcp = pargs = word;
 753     pargc = 0;
 754     pnleft = LONGBSIZE - 4;
 755     for (;;) {
 756 #if defined(DSPMBYTE)
 757         for (lp = cp;; lp++) {
 758             if (*lp == '`' &&
 759                 (lp-1 < cp || !Ismbyte2(*lp) || !Ismbyte1(*(lp-1)))) {
 760                 break;
 761             }
 762 #else /* DSPMBYTE */
 763         for (lp = cp; *lp != '`'; lp++) {
 764 #endif /* DSPMBYTE */
 765             if (*lp == 0) {
 766                 if (pargcp != pargs)
 767                     pword(LONGBSIZE);
 768                 return (pargv);
 769             }
 770             psave(*lp);
 771         }
 772         lp++;
 773         for (rp = lp; *rp && *rp != '`'; rp++)
 774             if (*rp == '\\') {
 775                 rp++;
 776                 if (!*rp)
 777                     goto oops;
 778             }
 779         if (!*rp)
 780     oops:  stderror(ERR_UNMATCHED, '`');
 781         ep = Strsave(lp);
 782         ep[rp - lp] = 0;
 783         backeval(ep, literal);
 784         cp = rp + 1;
 785     }
 786 }
 787
 788
 789 static void
 790 backeval(cp, literal)
 791     Char   *cp;
 792     bool    literal;
 793 {
 794     register int icnt, c;
 795     register Char *ip;
 796     struct command faket;
 797     bool    hadnl;
 798     int     pvec[2], quoted;
 799     Char   *fakecom[2], ibuf[BUFSIZE];
 800     char    tibuf[BUFSIZE];
 801
 802     hadnl = 0;
 803     icnt = 0;
 804     quoted = (literal || (cp[0] & QUOTE)) ? QUOTE : 0;
 805     faket.t_dtyp = NODE_COMMAND;
 806     faket.t_dflg = F_BACKQ;
 807     faket.t_dlef = 0;
 808     faket.t_drit = 0;
 809     faket.t_dspr = 0;
 810     faket.t_dcom = fakecom;
 811     fakecom[0] = STRfakecom1;
 812     fakecom[1] = 0;
 813
 814     /*
 815      * We do the psave job to temporarily change the current job so that the
 816      * following fork is considered a separate job.  This is so that when
 817      * backquotes are used in a builtin function that calls glob the "current
 818      * job" is not corrupted.  We only need one level of pushed jobs as long as
 819      * we are sure to fork here.
 820      */
 821     psavejob();
 822
 823     /*
 824      * It would be nicer if we could integrate this redirection more with the
 825      * routines in sh.sem.c by doing a fake execute on a builtin function that
 826      * was piped out.
 827      */
 828     mypipe(pvec);
 829     if (pfork(&faket, -1) == 0) {
 830         struct command *t;
 831
 832         (void) close(pvec[0]);
 833         (void) dmove(pvec[1], 1);
 834         (void) dmove(SHDIAG,  2);
 835         initdesc();
 836         /*
 837          * Bugfix for nested backquotes by Michael Greim <greim@sbsvax.UUCP>,
 838          * posted to comp.bugs.4bsd 12 Sep. 1989.
 839          */
 840         if (pargv)              /* mg, 21.dec.88 */
 841             blkfree(pargv), pargv = 0, pargsiz = 0;
 842         /* mg, 21.dec.88 */
 843         arginp = cp;
 844         while (*cp)
 845             *cp++ &= TRIM;
 846
 847         /*
 848          * In the child ``forget'' everything about current aliases or
 849          * eval vectors.
 850          */
 851         alvec = NULL;
 852         evalvec = NULL;
 853         alvecp = NULL;
 854         evalp = NULL;
 855         (void) lex(&paraml);
 856         if (seterr)
 857             stderror(ERR_OLD);
 858         alias(&paraml);
 859         t = syntax(paraml.next, &paraml, 0);
 860         if (seterr)
 861             stderror(ERR_OLD);
 862         if (t)
 863             t->t_dflg |= F_NOFORK;
 864 #ifdef SIGTSTP
 865         (void) sigignore(SIGTSTP);
 866 #endif
 867 #ifdef SIGTTIN
 868         (void) sigignore(SIGTTIN);
 869 #endif
 870 #ifdef SIGTTOU
 871         (void) sigignore(SIGTTOU);
 872 #endif
 873         execute(t, -1, NULL, NULL);
 874         exitstat();
 875     }
 876     xfree((ptr_t) cp);
 877     (void) close(pvec[1]);
 878     c = 0;
 879     ip = NULL;
 880     do {
 881         int     cnt = 0;
 882
 883         for (;;) {
 884             if (icnt == 0) {
 885                 int     i;
 886
 887                 ip = ibuf;
 888                 do
 889                     icnt = read(pvec[0], tibuf, BUFSIZE);
 890                 while (icnt == -1 && errno == EINTR);
 891                 if (icnt <= 0) {
 892                     c = -1;
 893                     break;
 894                 }
 895                 for (i = 0; i < icnt; i++)
 896                     ip[i] = (unsigned char) tibuf[i];
 897             }
 898             if (hadnl)
 899                 break;
 900             --icnt;
 901             c = (*ip++ & TRIM);
 902             if (c == 0)
 903                 break;
 904 #ifdef WINNT
 905             if (c == '\r')
 906                 c = ' ';
 907 #endif /* WINNT */
 908             if (c == '\n') {
 909                 /*
 910                  * Continue around the loop one more time, so that we can eat
 911                  * the last newline without terminating this word.
 912                  */
 913                 hadnl = 1;
 914                 continue;
 915             }
 916             if (!quoted && (c == ' ' || c == '\t'))
 917                 break;
 918             cnt++;
 919             psave(c | quoted);
 920         }
 921         /*
 922          * Unless at end-of-file, we will form a new word here if there were
 923          * characters in the word, or in any case when we take text literally.
 924          * If we didn't make empty words here when literal was set then we
 925          * would lose blank lines.
 926          */
 927         if (c != -1 && (cnt || literal))
 928             pword(BUFSIZE);
 929         hadnl = 0;
 930     } while (c >= 0);
 931     (void) close(pvec[0]);
 932     pwait();
 933     prestjob();
 934 }
 935
 936 static void
 937 psave(c)
 938     int    c;
 939 {
 940     if (--pnleft <= 0)
 941         stderror(ERR_WTOOLONG);
 942     *pargcp++ = (Char) c;
 943 }
 944
 945 static void
 946 pword(bufsiz)
 947     int    bufsiz;
 948 {
 949     psave(0);
 950     if (pargc == pargsiz - 1) {
 951         pargsiz += GLOBSPACE;
 952         pargv = (Char **) xrealloc((ptr_t) pargv,
 953                                    (size_t) (pargsiz * sizeof(Char *)));
 954     }
 955     pargv[pargc++] = Strsave(pargs);
 956     pargv[pargc] = NULL;
 957     pargcp = pargs;
 958     pnleft = bufsiz - 4;
 959 }
 960
 961 int
 962 Gmatch(string, pattern)
 963     Char *string, *pattern;
 964 {
 965     return Gnmatch(string, pattern, NULL);
 966 }
 967
 968 int
 969 Gnmatch(string, pattern, endstr)
 970     Char *string, *pattern, **endstr;
 971 {
 972     Char **blk, **p, *tstring = string;
 973     int    gpol = 1, gres = 0;
 974
 975     if (*pattern == '^') {
 976         gpol = 0;
 977         pattern++;
 978     }
 979
 980     blk = (Char **) xmalloc((size_t) (GLOBSPACE * sizeof(Char *)));
 981     blk[0] = Strsave(pattern);
 982     blk[1] = NULL;
 983
 984     expbrace(&blk, NULL, GLOBSPACE);
 985
 986     if (endstr == NULL)
 987         /* Exact matches only */
 988         for (p = blk; *p; p++)
 989             gres |= pmatch(string, *p, &tstring) == 2 ? 1 : 0;
 990     else {
 991         /* partial matches */
 992         int minc = 0x7fffffff;
 993         for (p = blk; *p; p++)
 994             if (pmatch(string, *p, &tstring) != 0) {
 995                 int t = (int) (tstring - string);
 996                 gres |= 1;
 997                 if (minc == -1 || minc > t)
 998                     minc = t;
 999             }
1000         *endstr = string + minc;
1001     }
1002
1003     blkfree(blk);
1004     return(gres == gpol);
1005 }
1006
1007 /* pmatch():
1008  *      Return 2 on exact match,
1009  *      Return 1 on substring match.
1010  *      Return 0 on no match.
1011  *      *estr will point to the end of the longest exact or substring match.
1012  */
1013 static int
1014 pmatch(string, pattern, estr)
1015     register Char *string, *pattern, **estr;
1016 {
1017     register Char stringc, patternc;
1018     int     match, negate_range;
1019     Char    rangec, *oestr, *pestr;
1020
1021     for (;; ++string) {
1022         stringc = *string & TRIM;
1023         /*
1024          * apollo compiler bug: switch (patternc = *pattern++) dies
1025          */
1026         patternc = *pattern++;
1027         switch (patternc) {
1028         case 0:
1029             *estr = string;
1030             return (stringc == 0 ? 2 : 1);
1031         case '?':
1032             if (stringc == 0)
1033                 return (0);
1034             *estr = string;
1035             break;
1036         case '*':
1037             if (!*pattern) {
1038                 while (*string) string++;
1039                 *estr = string;
1040                 return (2);
1041             }
1042             oestr = *estr;
1043             pestr = NULL;
1044
1045             do {
1046                 switch(pmatch(string, pattern, estr)) {
1047                 case 0:
1048                     break;
1049                 case 1:
1050                     pestr = *estr;
1051                     break;
1052                 case 2:
1053                     return 2;
1054                 default:
1055                     abort();    /* Cannot happen */
1056                 }
1057                 *estr = string;
1058             }
1059             while (*string++);
1060
1061             if (pestr) {
1062                 *estr = pestr;
1063                 return 1;
1064             }
1065             else {
1066                 *estr = oestr;
1067                 return 0;
1068             }
1069
1070         case '[':
1071             match = 0;
1072             if ((negate_range = (*pattern == '^')) != 0)
1073                 pattern++;
1074             while ((rangec = *pattern++) != '\0') {
1075                 if (rangec == ']')
1076                     break;
1077                 if (match)
1078                     continue;
1079                 if (rangec == '-' && *(pattern-2) != '[' && *pattern  != ']') {
1080                     match = (globcharcoll(stringc, *pattern & TRIM) <= 0 &&
1081                     globcharcoll(*(pattern-2) & TRIM, stringc) <= 0);
1082                     pattern++;
1083                 }
1084                 else
1085                     match = (stringc == (rangec & TRIM));
1086             }
1087             if (rangec == 0)
1088                 stderror(ERR_NAME | ERR_MISSING, ']');
1089             if (match == negate_range)
1090                 return (0);
1091             *estr = string;
1092             break;
1093         default:
1094             if ((patternc & TRIM) != stringc)
1095                 return (0);
1096             *estr = string;
1097             break;
1098         }
1099     }
1100 }
1101
1102 void
1103 Gcat(s1, s2)
1104     Char   *s1, *s2;
1105 {
1106     register Char *p, *q;
1107     int     n;
1108
1109     for (p = s1; *p++;)
1110         continue;
1111     for (q = s2; *q++;)
1112         continue;
1113     n = (int) ((p - s1) + (q - s2) - 1);
1114     if (++gargc >= gargsiz) {
1115         gargsiz += GLOBSPACE;
1116         gargv = (Char **) xrealloc((ptr_t) gargv,
1117                                    (size_t) (gargsiz * sizeof(Char *)));
1118     }
1119     gargv[gargc] = 0;
1120     p = gargv[gargc - 1] = (Char *) xmalloc((size_t) (n * sizeof(Char)));
1121     for (q = s1; (*p++ = *q++) != '\0';)
1122         continue;
1123     for (p--, q = s2; (*p++ = *q++) != '\0';)
1124         continue;
1125 }
1126
1127 #ifdef FILEC
1128 int
1129 sortscmp(a, b)
1130     register Char **a, **b;
1131 {
1132     if (!a)                     /* check for NULL */
1133         return (b ? 1 : 0);
1134     if (!b)
1135         return (-1);
1136
1137     if (!*a)                    /* check for NULL */
1138         return (*b ? 1 : 0);
1139     if (!*b)
1140         return (-1);
1141
1142     return (int) collate(*a, *b);
1143 }
1144
1145 #endif