contrib/tcsh/glob.c

   1 /*
   2  * Copyright (c) 1989 The Regents of the University of California.
   3  * All rights reserved.
   4  *
   5  * This code is derived from software contributed to Berkeley by
   6  * Guido van Rossum.
   7  *
   8  * Redistribution and use in source and binary forms, with or without
   9  * modification, are permitted provided that the following conditions
  10  * are met:
  11  * 1. Redistributions of source code must retain the above copyright
  12  *    notice, this list of conditions and the following disclaimer.
  13  * 2. Redistributions in binary form must reproduce the above copyright
  14  *    notice, this list of conditions and the following disclaimer in the
  15  *    documentation and/or other materials provided with the distribution.
  16  * 3. Neither the name of the University nor the names of its contributors
  17  *    may be used to endorse or promote products derived from this software
  18  *    without specific prior written permission.
  19  *
  20  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  21  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  22  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  23  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  24  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  25  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  26  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  27  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  28  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  29  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  30  * SUCH DAMAGE.
  31  */
  32 #if defined(LIBC_SCCS) && !defined(lint)
  33 static char sccsid[] = "@(#)glob.c      5.12 (Berkeley) 6/24/91";
  34 #endif /* LIBC_SCCS and not lint */
  35 /*
  36  * Glob: the interface is a superset of the one defined in POSIX 1003.2,
  37  * draft 9.
  38  *
  39  * The [!...] convention to negate a range is supported (SysV, Posix, ksh).
  40  *
  41  * Optional extra services, controlled by flags not defined by POSIX:
  42  *
  43  * GLOB_QUOTE:
  44  *      Escaping convention: \ inhibits any special meaning the following
  45  *      character might have (except \ at end of string is retained).
  46  * GLOB_MAGCHAR:
  47  *      Set in gl_flags if pattern contained a globbing character.
  48  * GLOB_ALTNOT:
  49  *      Use ^ instead of ! for "not".
  50  * gl_matchc:
  51  *      Number of matches in the current invocation of glob.
  52  */
  53
  54 #ifdef WINNT_NATIVE
  55         #pragma warning(disable:4244)
  56 #endif /* WINNT_NATIVE */
  57
  58 #define Char __Char
  59 #include "sh.h"
  60 #include "glob.h"
  61
  62 #ifndef HAVE_MBLEN
  63 #undef mblen
  64 #define mblen(_s,_n)    mbrlen((_s),(_n),NULL)
  65 #endif
  66
  67 #undef Char
  68 #undef QUOTE
  69 #undef TILDE
  70 #undef META
  71 #undef ismeta
  72 #undef Strchr
  73
  74 #ifndef S_ISDIR
  75 #define S_ISDIR(a)      (((a) & S_IFMT) == S_IFDIR)
  76 #endif
  77
  78 #if !defined(S_ISLNK) && defined(S_IFLNK)
  79 #define S_ISLNK(a)      (((a) & S_IFMT) == S_IFLNK)
  80 #endif
  81
  82 #if !defined(S_ISLNK) && !defined(lstat)
  83 #define lstat stat
  84 #endif
  85
  86 typedef unsigned short Char;
  87
  88 static  int      glob1          (Char *, glob_t *, int);
  89 static  int      glob2          (struct strbuf *, const Char *, glob_t *, int);
  90 static  int      glob3          (struct strbuf *, const Char *, const Char *,
  91                                  const Char *, glob_t *, int);
  92 static  void     globextend     (const char *, glob_t *);
  93 static  int      match          (const char *, const Char *, const Char *,
  94                                  int);
  95 static  int      compare        (const void *, const void *);
  96 static  DIR     *Opendir        (const char *);
  97 #ifdef S_IFLNK
  98 static  int      Lstat          (const char *, struct stat *);
  99 #endif
 100 static  int      Stat           (const char *, struct stat *sb);
 101 static  Char    *Strchr         (Char *, int);
 102 #ifdef DEBUG
 103 static  void     qprintf        (const char *, const Char *);
 104 #endif
 105
 106 #define DOLLAR          '$'
 107 #define DOT             '.'
 108 #define EOS             '\0'
 109 #define LBRACKET        '['
 110 #define NOT             '!'
 111 #define ALTNOT          '^'
 112 #define QUESTION        '?'
 113 #define QUOTE           '\\'
 114 #define RANGE           '-'
 115 #define RBRACKET        ']'
 116 #define SEP             '/'
 117 #define STAR            '*'
 118 #define TILDE           '~'
 119 #define UNDERSCORE      '_'
 120
 121 #define M_META          0x8000
 122 #define M_PROTECT       0x4000
 123 #define M_MASK          0xffff
 124 #define M_ASCII         0x00ff
 125
 126 #define LCHAR(c)        ((c)&M_ASCII)
 127 #define META(c)         ((c)|M_META)
 128 #define M_ALL           META('*')
 129 #define M_END           META(']')
 130 #define M_NOT           META('!')
 131 #define M_ALTNOT        META('^')
 132 #define M_ONE           META('?')
 133 #define M_RNG           META('-')
 134 #define M_SET           META('[')
 135 #define ismeta(c)       (((c)&M_META) != 0)
 136
 137 int
 138 globcharcoll(__Char c1, __Char c2, int cs)
 139 {
 140 #if defined(NLS) && defined(LC_COLLATE) && defined(HAVE_STRCOLL)
 141 # if defined(WIDE_STRINGS)
 142     wchar_t s1[2], s2[2];
 143
 144     if (c1 == c2)
 145         return (0);
 146     if (cs) {
 147         c1 = towlower(c1);
 148         c2 = towlower(c2);
 149     } else {
 150 #ifndef __FreeBSD__
 151         /* This should not be here, but I'll rather leave it in than engage in
 152            a LC_COLLATE flamewar about a shell I don't use... */
 153         if (iswlower(c1) && iswupper(c2))
 154             return (1);
 155         if (iswupper(c1) && iswlower(c2))
 156             return (-1);
 157 #endif
 158     }
 159     s1[0] = c1;
 160     s2[0] = c2;
 161     s1[1] = s2[1] = '\0';
 162     return wcscoll(s1, s2);
 163 # else /* not WIDE_STRINGS */
 164     char s1[2], s2[2];
 165
 166     if (c1 == c2)
 167         return (0);
 168     /*
 169      * From kevin lyda <kevin@suberic.net>:
 170      * strcoll does not guarantee case sorting, so we pre-process now:
 171      */
 172     if (cs) {
 173         c1 = islower(c1) ? c1 : tolower(c1);
 174         c2 = islower(c2) ? c2 : tolower(c2);
 175     } else {
 176         if (islower(c1) && isupper(c2))
 177             return (1);
 178         if (isupper(c1) && islower(c2))
 179             return (-1);
 180     }
 181     s1[0] = c1;
 182     s2[0] = c2;
 183     s1[1] = s2[1] = '\0';
 184     return strcoll(s1, s2);
 185 # endif
 186 #else
 187     return (c1 - c2);
 188 #endif
 189 }
 190
 191 /*
 192  * Need to dodge two kernel bugs:
 193  * opendir("") != opendir(".")
 194  * NAMEI_BUG: on plain files trailing slashes are ignored in some kernels.
 195  *            POSIX specifies that they should be ignored in directories.
 196  */
 197
 198 static DIR *
 199 Opendir(const char *str)
 200 {
 201 #if defined(hpux) || defined(__hpux)
 202     struct stat st;
 203 #endif
 204
 205     if (!*str)
 206         return (opendir("."));
 207 #if defined(hpux) || defined(__hpux)
 208     /*
 209      * Opendir on some device files hangs, so avoid it
 210      */
 211     if (stat(str, &st) == -1 || !S_ISDIR(st.st_mode))
 212         return NULL;
 213 #endif
 214     return opendir(str);
 215 }
 216
 217 #ifdef S_IFLNK
 218 static int
 219 Lstat(const char *fn, struct stat *sb)
 220 {
 221     int st;
 222
 223     st = lstat(fn, sb);
 224 # ifdef NAMEI_BUG
 225     if (*fn != 0 && strend(fn)[-1] == '/' && !S_ISDIR(sb->st_mode))
 226         st = -1;
 227 # endif /* NAMEI_BUG */
 228     return st;
 229 }
 230 #else
 231 #define Lstat Stat
 232 #endif /* S_IFLNK */
 233
 234 static int
 235 Stat(const char *fn, struct stat *sb)
 236 {
 237     int st;
 238
 239     st = stat(fn, sb);
 240 #ifdef NAMEI_BUG
 241     if (*fn != 0 && strend(fn)[-1] == '/' && !S_ISDIR(sb->st_mode))
 242         st = -1;
 243 #endif /* NAMEI_BUG */
 244     return st;
 245 }
 246
 247 static Char *
 248 Strchr(Char *str, int ch)
 249 {
 250     do
 251         if (*str == ch)
 252             return (str);
 253     while (*str++);
 254     return (NULL);
 255 }
 256
 257 #ifdef DEBUG
 258 static void
 259 qprintf(const char *pre, const Char *s)
 260 {
 261     const Char *p;
 262
 263     xprintf("%s", pre);
 264     for (p = s; *p; p++)
 265         xprintf("%c", *p & 0xff);
 266     xprintf("\n%s", pre);
 267     for (p = s; *p; p++)
 268         xprintf("%c", *p & M_PROTECT ? '"' : ' ');
 269     xprintf("\n%s", pre);
 270     for (p = s; *p; p++)
 271         xprintf("%c", *p & M_META ? '_' : ' ');
 272     xprintf("\n");
 273 }
 274 #endif /* DEBUG */
 275
 276 static int
 277 compare(const void *p, const void *q)
 278 {
 279 #if defined(NLS) && defined(HAVE_STRCOLL)
 280     return (strcoll(*(char *const *) p, *(char *const *) q));
 281 #else
 282     return (strcmp(*(char *const *) p, *(char *const *) q));
 283 #endif /* NLS && HAVE_STRCOLL */
 284 }
 285
 286 /*
 287  * The main glob() routine: compiles the pattern (optionally processing
 288  * quotes), calls glob1() to do the real pattern matching, and finally
 289  * sorts the list (unless unsorted operation is requested).  Returns 0
 290  * if things went well, nonzero if errors occurred.  It is not an error
 291  * to find no matches.
 292  */
 293 int
 294 glob(const char *pattern, int flags, int (*errfunc) (const char *, int),
 295      glob_t *pglob)
 296 {
 297     int     err, oldpathc;
 298     Char *bufnext, m_not;
 299     const unsigned char *patnext;
 300     int     c, not;
 301     Char *qpatnext, *patbuf;
 302     int     no_match;
 303
 304     patnext = (const unsigned char *) pattern;
 305     if (!(flags & GLOB_APPEND)) {
 306         pglob->gl_pathc = 0;
 307         pglob->gl_pathv = NULL;
 308         if (!(flags & GLOB_DOOFFS))
 309             pglob->gl_offs = 0;
 310     }
 311     pglob->gl_flags = flags & ~GLOB_MAGCHAR;
 312     pglob->gl_errfunc = errfunc;
 313     oldpathc = pglob->gl_pathc;
 314     pglob->gl_matchc = 0;
 315
 316     if (pglob->gl_flags & GLOB_ALTNOT) {
 317         not = ALTNOT;
 318         m_not = M_ALTNOT;
 319     }
 320     else {
 321         not = NOT;
 322         m_not = M_NOT;
 323     }
 324
 325     patbuf = xmalloc((strlen(pattern) + 1) * sizeof(*patbuf));
 326     bufnext = patbuf;
 327
 328     no_match = *patnext == not;
 329     if (no_match)
 330         patnext++;
 331
 332     if (flags & GLOB_QUOTE) {
 333         /* Protect the quoted characters */
 334         while ((c = *patnext++) != EOS) {
 335 #ifdef WIDE_STRINGS
 336             int len;
 337
 338             len = mblen((const char *)(patnext - 1), MB_LEN_MAX);
 339             if (len == -1)
 340                 TCSH_IGNORE(mblen(NULL, 0));
 341             else if (len > 1) {
 342                 *bufnext++ = (Char) c;
 343                 while (--len != 0)
 344                     *bufnext++ = (Char) (*patnext++ | M_PROTECT);
 345             } else
 346 #endif /* WIDE_STRINGS */
 347             if (c == QUOTE) {
 348                 if ((c = *patnext++) == EOS) {
 349                     c = QUOTE;
 350                     --patnext;
 351                 }
 352                 *bufnext++ = (Char) (c | M_PROTECT);
 353             }
 354             else
 355                 *bufnext++ = (Char) c;
 356         }
 357     }
 358     else
 359         while ((c = *patnext++) != EOS)
 360             *bufnext++ = (Char) c;
 361     *bufnext = EOS;
 362
 363     bufnext = patbuf;
 364     qpatnext = patbuf;
 365     while ((c = *qpatnext++) != EOS) {
 366         switch (c) {
 367         case LBRACKET:
 368             c = *qpatnext;
 369             if (c == not)
 370                 ++qpatnext;
 371             if (*qpatnext == EOS ||
 372                 Strchr(qpatnext + 1, RBRACKET) == NULL) {
 373                 *bufnext++ = LBRACKET;
 374                 if (c == not)
 375                     --qpatnext;
 376                 break;
 377             }
 378             pglob->gl_flags |= GLOB_MAGCHAR;
 379             *bufnext++ = M_SET;
 380             if (c == not)
 381                 *bufnext++ = m_not;
 382             c = *qpatnext++;
 383             do {
 384                 *bufnext++ = LCHAR(c);
 385                 if (*qpatnext == RANGE &&
 386                     (c = qpatnext[1]) != RBRACKET) {
 387                     *bufnext++ = M_RNG;
 388                     *bufnext++ = LCHAR(c);
 389                     qpatnext += 2;
 390                 }
 391             } while ((c = *qpatnext++) != RBRACKET);
 392             *bufnext++ = M_END;
 393             break;
 394         case QUESTION:
 395             pglob->gl_flags |= GLOB_MAGCHAR;
 396             *bufnext++ = M_ONE;
 397             break;
 398         case STAR:
 399             pglob->gl_flags |= GLOB_MAGCHAR;
 400             /* collapse adjacent stars to one [or three if globstar],
 401              * to avoid exponential behavior
 402              */
 403             if (bufnext == patbuf || bufnext[-1] != M_ALL ||
 404                ((flags & GLOB_STAR) != 0 &&
 405                  (bufnext - 1 == patbuf || bufnext[-2] != M_ALL ||
 406                  bufnext - 2 == patbuf || bufnext[-3] != M_ALL)))
 407                 *bufnext++ = M_ALL;
 408             break;
 409         default:
 410             *bufnext++ = LCHAR(c);
 411             break;
 412         }
 413     }
 414     *bufnext = EOS;
 415 #ifdef DEBUG
 416     qprintf("patbuf=", patbuf);
 417 #endif
 418
 419     if ((err = glob1(patbuf, pglob, no_match)) != 0) {
 420         xfree(patbuf);
 421         return (err);
 422     }
 423
 424     /*
 425      * If there was no match we are going to append the pattern
 426      * if GLOB_NOCHECK was specified or if GLOB_NOMAGIC was specified
 427      * and the pattern did not contain any magic characters
 428      * GLOB_NOMAGIC is there just for compatibility with csh.
 429      */
 430     if (pglob->gl_pathc == oldpathc &&
 431         ((flags & GLOB_NOCHECK) ||
 432          ((flags & GLOB_NOMAGIC) && !(pglob->gl_flags & GLOB_MAGCHAR)))) {
 433         if (!(flags & GLOB_QUOTE))
 434             globextend(pattern, pglob);
 435         else {
 436             char *copy, *dest;
 437             const char *src;
 438
 439             /* copy pattern, interpreting quotes */
 440             copy = xmalloc(strlen(pattern) + 1);
 441             dest = copy;
 442             src = pattern;
 443             while (*src != EOS) {
 444                 /* Don't interpret quotes. The spec does not say we should do */
 445                 if (*src == QUOTE) {
 446                     if (*++src == EOS)
 447                         --src;
 448                 }
 449                 *dest++ = *src++;
 450             }
 451             *dest = EOS;
 452             globextend(copy, pglob);
 453             xfree(copy);
 454         }
 455         xfree(patbuf);
 456         return 0;
 457     }
 458     else if (!(flags & GLOB_NOSORT) && (pglob->gl_pathc != oldpathc))
 459         qsort(pglob->gl_pathv + pglob->gl_offs + oldpathc,
 460               pglob->gl_pathc - oldpathc, sizeof(char *), compare);
 461     xfree(patbuf);
 462     return (0);
 463 }
 464
 465 static int
 466 glob1(Char *pattern, glob_t *pglob, int no_match)
 467 {
 468     struct strbuf pathbuf = strbuf_INIT;
 469     int err;
 470
 471     /*
 472      * a null pathname is invalid -- POSIX 1003.1 sect. 2.4.
 473      */
 474     if (*pattern == EOS)
 475         return (0);
 476     err = glob2(&pathbuf, pattern, pglob, no_match);
 477     xfree(pathbuf.s);
 478     return err;
 479 }
 480
 481 /*
 482  * functions glob2 and glob3 are mutually recursive; there is one level
 483  * of recursion for each segment in the pattern that contains one or
 484  * more meta characters.
 485  */
 486 static int
 487 glob2(struct strbuf *pathbuf, const Char *pattern, glob_t *pglob, int no_match)
 488 {
 489     struct stat sbuf;
 490     int anymeta;
 491     const Char *p;
 492     size_t orig_len;
 493
 494     /*
 495      * loop over pattern segments until end of pattern or until segment with
 496      * meta character found.
 497      */
 498     anymeta = 0;
 499     for (;;) {
 500         if (*pattern == EOS) {  /* end of pattern? */
 501             strbuf_terminate(pathbuf);
 502
 503             if (Lstat(pathbuf->s, &sbuf))
 504                 return (0);
 505
 506             if (((pglob->gl_flags & GLOB_MARK) &&
 507                  pathbuf->s[pathbuf->len - 1] != SEP) &&
 508                 (S_ISDIR(sbuf.st_mode)
 509 #ifdef S_IFLNK
 510                  || (S_ISLNK(sbuf.st_mode) &&
 511                      (Stat(pathbuf->s, &sbuf) == 0) &&
 512                      S_ISDIR(sbuf.st_mode))
 513 #endif
 514                  )) {
 515                 strbuf_append1(pathbuf, SEP);
 516                 strbuf_terminate(pathbuf);
 517             }
 518             ++pglob->gl_matchc;
 519             globextend(pathbuf->s, pglob);
 520             return 0;
 521         }
 522
 523         /* find end of next segment, tentatively copy to pathbuf */
 524         p = pattern;
 525         orig_len = pathbuf->len;
 526         while (*p != EOS && *p != SEP) {
 527             if (ismeta(*p))
 528                 anymeta = 1;
 529             strbuf_append1(pathbuf, *p++);
 530         }
 531
 532         if (!anymeta) {         /* no expansion, do next segment */
 533             pattern = p;
 534             while (*pattern == SEP)
 535                 strbuf_append1(pathbuf, *pattern++);
 536         }
 537         else {                  /* need expansion, recurse */
 538             pathbuf->len = orig_len;
 539             return (glob3(pathbuf, pattern, p, pattern, pglob, no_match));
 540         }
 541     }
 542     /* NOTREACHED */
 543 }
 544
 545 static size_t
 546 One_Char_mbtowc(__Char *pwc, const Char *s, size_t n)
 547 {
 548 #ifdef WIDE_STRINGS
 549     char buf[MB_LEN_MAX], *p;
 550
 551     if (n > MB_LEN_MAX)
 552         n = MB_LEN_MAX;
 553     p = buf;
 554     while (p < buf + n && (*p++ = LCHAR(*s++)) != 0)
 555         ;
 556     return one_mbtowc(pwc, buf, n);
 557 #else
 558     *pwc = *s & CHAR;
 559     return 1;
 560 #endif
 561 }
 562
 563 static int
 564 glob3(struct strbuf *pathbuf, const Char *pattern, const Char *restpattern,
 565       const Char *pglobstar, glob_t *pglob, int no_match)
 566 {
 567     DIR    *dirp;
 568     struct dirent *dp;
 569     struct stat sbuf;
 570     int     err;
 571     Char m_not = (pglob->gl_flags & GLOB_ALTNOT) ? M_ALTNOT : M_NOT;
 572     size_t orig_len;
 573     int globstar = 0;
 574     int chase_symlinks = 0;
 575     const Char *termstar = NULL;
 576
 577     strbuf_terminate(pathbuf);
 578     orig_len = pathbuf->len;
 579     errno = err = 0;
 580
 581     while (pglobstar < restpattern) {
 582         __Char wc;
 583         size_t width = One_Char_mbtowc(&wc, pglobstar, MB_LEN_MAX);
 584         if ((pglobstar[0] & M_MASK) == M_ALL &&
 585             (pglobstar[width] & M_MASK) == M_ALL) {
 586             globstar = 1;
 587             chase_symlinks = (pglobstar[2 * width] & M_MASK) == M_ALL;
 588             termstar = pglobstar + (2 + chase_symlinks) * width;
 589             break;
 590         }
 591         pglobstar += width;
 592     }
 593
 594     if (globstar) {
 595         err = pglobstar==pattern && termstar==restpattern ?
 596                 *restpattern == EOS ?
 597                 glob2(pathbuf, restpattern - 1, pglob, no_match) :
 598                 glob2(pathbuf, restpattern + 1, pglob, no_match) :
 599                 glob3(pathbuf, pattern, restpattern, termstar, pglob, no_match);
 600         if (err)
 601             return err;
 602         pathbuf->len = orig_len;
 603         strbuf_terminate(pathbuf);
 604     }
 605
 606     if (*pathbuf->s && (Lstat(pathbuf->s, &sbuf) || !S_ISDIR(sbuf.st_mode)
 607 #ifdef S_IFLINK
 608              && ((globstar && !chase_symlinks) || !S_ISLNK(sbuf.st_mode))
 609 #endif
 610         ))
 611         return 0;
 612
 613     if (!(dirp = Opendir(pathbuf->s))) {
 614         /* todo: don't call for ENOENT or ENOTDIR? */
 615         if ((pglob->gl_errfunc && (*pglob->gl_errfunc) (pathbuf->s, errno)) ||
 616             (pglob->gl_flags & GLOB_ERR))
 617             return (GLOB_ABEND);
 618         else
 619             return (0);
 620     }
 621
 622     /* search directory for matching names */
 623     while ((dp = readdir(dirp)) != NULL) {
 624         /* initial DOT must be matched literally */
 625         if (dp->d_name[0] == DOT && *pattern != DOT)
 626             if (!(pglob->gl_flags & GLOB_DOT) || !dp->d_name[1] ||
 627                 (dp->d_name[1] == DOT && !dp->d_name[2]))
 628                 continue; /*unless globdot and not . or .. */
 629         pathbuf->len = orig_len;
 630         strbuf_append(pathbuf, dp->d_name);
 631         strbuf_terminate(pathbuf);
 632
 633         if (globstar) {
 634 #ifdef S_IFLNK
 635             if (!chase_symlinks &&
 636                 (Lstat(pathbuf->s, &sbuf) || S_ISLNK(sbuf.st_mode)))
 637                     continue;
 638 #endif
 639             if (match(pathbuf->s + orig_len, pattern, termstar,
 640                 (int)m_not) == no_match)
 641                     continue;
 642             strbuf_append1(pathbuf, SEP);
 643             strbuf_terminate(pathbuf);
 644             if ((err = glob2(pathbuf, pglobstar, pglob, no_match)) != 0)
 645                 break;
 646         } else {
 647             if (match(pathbuf->s + orig_len, pattern, restpattern,
 648                 (int) m_not) == no_match)
 649                 continue;
 650             if ((err = glob2(pathbuf, restpattern, pglob, no_match)) != 0)
 651                 break;
 652         }
 653     }
 654     /* todo: check error from readdir? */
 655     closedir(dirp);
 656     return (err);
 657 }
 658
 659
 660 /*
 661  * Extend the gl_pathv member of a glob_t structure to accomodate a new item,
 662  * add the new item, and update gl_pathc.
 663  *
 664  * This assumes the BSD realloc, which only copies the block when its size
 665  * crosses a power-of-two boundary; for v7 realloc, this would cause quadratic
 666  * behavior.
 667  *
 668  * Return 0 if new item added, error code if memory couldn't be allocated.
 669  *
 670  * Invariant of the glob_t structure:
 671  *      Either gl_pathc is zero and gl_pathv is NULL; or gl_pathc > 0 and
 672  *       gl_pathv points to (gl_offs + gl_pathc + 1) items.
 673  */
 674 static void
 675 globextend(const char *path, glob_t *pglob)
 676 {
 677     char **pathv;
 678     int i;
 679     size_t newsize;
 680
 681     newsize = sizeof(*pathv) * (2 + pglob->gl_pathc + pglob->gl_offs);
 682     pathv = xrealloc(pglob->gl_pathv, newsize);
 683
 684     if (pglob->gl_pathv == NULL && pglob->gl_offs > 0) {
 685         /* first time around -- clear initial gl_offs items */
 686         pathv += pglob->gl_offs;
 687         for (i = pglob->gl_offs; --i >= 0;)
 688             *--pathv = NULL;
 689     }
 690     pglob->gl_pathv = pathv;
 691
 692     pathv[pglob->gl_offs + pglob->gl_pathc++] = strsave(path);
 693     pathv[pglob->gl_offs + pglob->gl_pathc] = NULL;
 694 }
 695
 696 /*
 697  * pattern matching function for filenames.
 698  */
 699 static  int
 700 match(const char *name, const Char *pat, const Char *patend, int m_not)
 701 {
 702     int ok, negate_range;
 703     const Char *patNext;
 704     const char *nameNext, *nameStart, *nameEnd;
 705     Char c;
 706
 707     patNext = pat;
 708     nameStart = nameNext = name;
 709     nameEnd = NULL;
 710
 711     while (pat < patend || *name) {
 712         size_t lwk, pwk;
 713         __Char wc, wk, wc1;
 714
 715         c = *pat; /* Only for M_MASK bits */
 716         if (*name == EOS)
 717                 nameEnd = name;
 718
 719         pwk = One_Char_mbtowc(&wc, pat, MB_LEN_MAX);
 720         lwk = one_mbtowc(&wk, name, MB_LEN_MAX);
 721         switch (c & M_MASK) {
 722         case M_ALL:
 723             while ((*(pat + pwk) & M_MASK) == M_ALL) {
 724                 pat += pwk;
 725                 pwk = One_Char_mbtowc(&wc, pat, MB_LEN_MAX);
 726             }
 727             patNext = pat;
 728             nameNext = name + lwk;
 729             pat += pwk;
 730             continue;
 731         case M_ONE:
 732             if (*name == EOS)
 733                 break;
 734             name += lwk;
 735             pat += pwk;
 736             continue;
 737         case M_SET:
 738             ok = 0;
 739             if (*name == EOS)
 740                 break;
 741             pat += pwk;
 742             pwk = One_Char_mbtowc(&wc, pat, MB_LEN_MAX);
 743             name += lwk;
 744             if ((negate_range = ((*pat & M_MASK) == m_not)) != 0) {
 745                 pat += pwk;
 746                 pwk = One_Char_mbtowc(&wc, pat, MB_LEN_MAX);
 747             }
 748             wc1 = wc;
 749             while ((*pat & M_MASK) != M_END) {
 750                 if ((*pat & M_MASK) == M_RNG) {
 751                     __Char wc2;
 752
 753                     pat += pwk;
 754                     pwk = One_Char_mbtowc(&wc2, pat, MB_LEN_MAX);
 755                     if (globcharcoll(wc1, wk, 0) <= 0 &&
 756                         globcharcoll(wk, wc2, 0) <= 0)
 757                         ok = 1;
 758                 } else if (wc == wk)
 759                     ok = 1;
 760                 pat += pwk;
 761                 wc1 = wc;
 762                 pwk = One_Char_mbtowc(&wc, pat, MB_LEN_MAX);
 763             }
 764             pat += pwk;
 765             pwk = One_Char_mbtowc(&wc, pat, MB_LEN_MAX);
 766             if (ok == negate_range)
 767                 break;
 768             continue;
 769         default:
 770             if (*name == EOS || samecase(wk) != samecase(wc))
 771                 break;
 772             name += lwk;
 773             pat += pwk;
 774             continue;
 775         }
 776         if (nameNext != nameStart
 777             && (nameEnd == NULL || nameNext <= nameEnd)) {
 778             pat = patNext;
 779             name = nameNext;
 780             continue;
 781         }
 782         return 0;
 783     }
 784     return 1;
 785 }
 786
 787 /* free allocated data belonging to a glob_t structure */
 788 void
 789 globfree(glob_t *pglob)
 790 {
 791     int i;
 792     char **pp;
 793
 794     if (pglob->gl_pathv != NULL) {
 795         pp = pglob->gl_pathv + pglob->gl_offs;
 796         for (i = pglob->gl_pathc; i--; ++pp)
 797             if (*pp)
 798                 xfree(*pp), *pp = NULL;
 799         xfree(pglob->gl_pathv), pglob->gl_pathv = NULL;
 800     }
 801 }