gen/glob-fbsd.c

   1 /*
   2  * Copyright (c) 1989, 1993
   3  *      The Regents of the University of California.  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. All advertising materials mentioning features or use of this software
  17  *    must display the following acknowledgement:
  18  *      This product includes software developed by the University of
  19  *      California, Berkeley and its contributors.
  20  * 4. Neither the name of the University nor the names of its contributors
  21  *    may be used to endorse or promote products derived from this software
  22  *    without specific prior written permission.
  23  *
  24  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  25  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  26  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  27  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  28  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  29  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  30  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  31  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  32  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  33  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  34  * SUCH DAMAGE.
  35  */
  36
  37 #if defined(LIBC_SCCS) && !defined(lint)
  38 static char sccsid[] = "@(#)glob.c      8.3 (Berkeley) 10/13/93";
  39 #endif /* LIBC_SCCS and not lint */
  40 #include <sys/cdefs.h>
  41 __FBSDID("$FreeBSD: src/lib/libc/gen/glob.c,v 1.22 2004/07/29 03:48:52 tjr Exp $");
  42
  43 #include "xlocale_private.h"
  44
  45 /*
  46  * glob(3) -- a superset of the one defined in POSIX 1003.2.
  47  *
  48  * The [!...] convention to negate a range is supported (SysV, Posix, ksh).
  49  *
  50  * Optional extra services, controlled by flags not defined by POSIX:
  51  *
  52  * GLOB_QUOTE:
  53  *      Escaping convention: \ inhibits any special meaning the following
  54  *      character might have (except \ at end of string is retained).
  55  * GLOB_MAGCHAR:
  56  *      Set in gl_flags if pattern contained a globbing character.
  57  * GLOB_NOMAGIC:
  58  *      Same as GLOB_NOCHECK, but it will only append pattern if it did
  59  *      not contain any magic characters.  [Used in csh style globbing]
  60  * GLOB_ALTDIRFUNC:
  61  *      Use alternately specified directory access functions.
  62  * GLOB_TILDE:
  63  *      expand ~user/foo to the /home/dir/of/user/foo
  64  * GLOB_BRACE:
  65  *      expand {1,2}{a,b} to 1a 1b 2a 2b
  66  * gl_matchc:
  67  *      Number of matches in the current invocation of glob.
  68  */
  69
  70 /*
  71  * Some notes on multibyte character support:
  72  * 1. Patterns with illegal byte sequences match nothing - even if
  73  *    GLOB_NOCHECK is specified.
  74  * 2. Illegal byte sequences in filenames are handled by treating them as
  75  *    single-byte characters with a value of the first byte of the sequence
  76  *    cast to wchar_t.
  77  * 3. State-dependent encodings are not currently supported.
  78  */
  79
  80 #include <sys/param.h>
  81 #include <sys/stat.h>
  82
  83 #include <ctype.h>
  84 #include <dirent.h>
  85 #include <errno.h>
  86 #include <glob.h>
  87 #include <limits.h>
  88 #include <pwd.h>
  89 #include <stdint.h>
  90 #include <stdio.h>
  91 #include <stdlib.h>
  92 #include <string.h>
  93 #include <unistd.h>
  94 #include <wchar.h>
  95
  96 #include "collate.h"
  97
  98 #define DOLLAR          '$'
  99 #define DOT             '.'
 100 #define EOS             '\0'
 101 #define LBRACKET        '['
 102 #define NOT             '!'
 103 #define QUESTION        '?'
 104 #define QUOTE           '\\'
 105 #define RANGE           '-'
 106 #define RBRACKET        ']'
 107 #define SEP             '/'
 108 #define STAR            '*'
 109 #define TILDE           '~'
 110 #define UNDERSCORE      '_'
 111 #define LBRACE          '{'
 112 #define RBRACE          '}'
 113 #define SLASH           '/'
 114 #define COMMA           ','
 115
 116 #ifndef DEBUG
 117
 118 #define M_QUOTE         0x8000000000ULL
 119 #define M_PROTECT       0x4000000000ULL
 120 #define M_MASK          0xffffffffffULL
 121 #define M_CHAR          0x00ffffffffULL
 122
 123 typedef uint_fast64_t Char;
 124
 125 #else
 126
 127 #define M_QUOTE         0x80
 128 #define M_PROTECT       0x40
 129 #define M_MASK          0xff
 130 #define M_CHAR          0x7f
 131
 132 typedef char Char;
 133
 134 #endif
 135
 136
 137 #define CHAR(c)         ((Char)((c)&M_CHAR))
 138 #define META(c)         ((Char)((c)|M_QUOTE))
 139 #define M_ALL           META('*')
 140 #define M_END           META(']')
 141 #define M_NOT           META('!')
 142 #define M_ONE           META('?')
 143 #define M_RNG           META('-')
 144 #define M_SET           META('[')
 145 #define ismeta(c)       (((c)&M_QUOTE) != 0)
 146
 147
 148 #define compare         __gl_compare
 149 #define g_Ctoc          __gl_g_Ctoc
 150 #define g_strchr        __gl_g_strchr
 151 #define globextend      __gl_globextend
 152 #define globtilde       __gl_globtilde
 153 #define match           __gl_match
 154 __private_extern__ int compare(const void *, const void *);
 155 __private_extern__ int g_Ctoc(const Char *, char *, u_int, locale_t);
 156 __private_extern__ Char *g_strchr(Char *, wchar_t);
 157 __private_extern__ int globextend(const Char *, glob_t *, int *, locale_t);
 158 __private_extern__ const Char *
 159                  globtilde(const Char *, Char *, size_t, glob_t *);
 160 __private_extern__ int match(Char *, Char *, Char *, locale_t);
 161
 162
 163 static int       g_lstat(Char *, struct stat *, glob_t *, locale_t);
 164 static DIR      *g_opendir(Char *, glob_t *, locale_t);
 165 #ifdef notdef
 166 static Char     *g_strcat(Char *, const Char *);
 167 #endif
 168 static int       g_stat(Char *, struct stat *, glob_t *, locale_t);
 169 static int       glob0(const Char *, glob_t *, int *, locale_t);
 170 static int       glob1(Char *, glob_t *, int *, locale_t);
 171 static int       glob2(Char *, Char *, Char *, Char *, glob_t *, int *, locale_t);
 172 static int       glob3(Char *, Char *, Char *, Char *, Char *, glob_t *, int *, locale_t);
 173 static int       globexp1(const Char *, glob_t *, int *, locale_t);
 174 static int       globexp2(const Char *, const Char *, glob_t *, int *, int *, locale_t);
 175 #ifdef DEBUG
 176 static void      qprintf(const char *, Char *);
 177 #endif
 178
 179 static int
 180 __glob(pattern, pglob)
 181         const char *pattern;
 182         glob_t *pglob;
 183 {
 184         const u_char *patnext;
 185         int limit;
 186         Char *bufnext, *bufend, patbuf[MAXPATHLEN], prot;
 187         mbstate_t mbs;
 188         wchar_t wc;
 189         size_t clen;
 190         locale_t loc = __current_locale();
 191         int mb_cur_max = MB_CUR_MAX_L(loc);
 192
 193         patnext = (u_char *) pattern;
 194         if (!(pglob->gl_flags & GLOB_APPEND)) {
 195                 pglob->gl_pathc = 0;
 196                 pglob->gl_pathv = NULL;
 197                 if (!(pglob->gl_flags & GLOB_DOOFFS))
 198                         pglob->gl_offs = 0;
 199         }
 200         if (pglob->gl_flags & GLOB_LIMIT) {
 201                 limit = pglob->gl_matchc;
 202                 if (limit == 0)
 203                         limit = ARG_MAX;
 204         } else
 205                 limit = 0;
 206         pglob->gl_matchc = 0;
 207
 208         bufnext = patbuf;
 209         bufend = bufnext + MAXPATHLEN - 1;
 210         if (pglob->gl_flags & GLOB_NOESCAPE) {
 211                 memset(&mbs, 0, sizeof(mbs));
 212                 while (bufend - bufnext >= mb_cur_max) {
 213                         clen = mbrtowc_l(&wc, (const char *)patnext, MB_LEN_MAX, &mbs, loc);
 214                         if (clen == (size_t)-1 || clen == (size_t)-2)
 215                                 return (GLOB_NOMATCH);
 216                         else if (clen == 0)
 217                                 break;
 218                         *bufnext++ = wc;
 219                         patnext += clen;
 220                 }
 221         } else {
 222                 /* Protect the quoted characters. */
 223                 memset(&mbs, 0, sizeof(mbs));
 224                 while (bufend - bufnext >= mb_cur_max) {
 225                         if (*patnext == QUOTE) {
 226                                 if (*++patnext == EOS) {
 227                                         *bufnext++ = QUOTE | M_PROTECT;
 228                                         continue;
 229                                 }
 230                                 prot = M_PROTECT;
 231                         } else
 232                                 prot = 0;
 233                         clen = mbrtowc_l(&wc, (const char *)patnext, MB_LEN_MAX, &mbs, loc);
 234                         if (clen == (size_t)-1 || clen == (size_t)-2)
 235                                 return (GLOB_NOMATCH);
 236                         else if (clen == 0)
 237                                 break;
 238                         *bufnext++ = wc | prot;
 239                         patnext += clen;
 240                 }
 241         }
 242         *bufnext = EOS;
 243
 244         if (pglob->gl_flags & GLOB_BRACE)
 245             return globexp1(patbuf, pglob, &limit, loc);
 246         else
 247             return glob0(patbuf, pglob, &limit, loc);
 248 }
 249
 250 int
 251 glob(pattern, flags, errfunc, pglob)
 252         const char *pattern;
 253         int flags, (*errfunc)(const char *, int);
 254         glob_t *pglob;
 255 {
 256 #ifdef __BLOCKS__
 257         pglob->gl_flags = flags & ~(GLOB_MAGCHAR | _GLOB_ERR_BLOCK);
 258 #else /* !__BLOCKS__ */
 259         pglob->gl_flags = flags & ~GLOB_MAGCHAR;
 260 #endif /* __BLOCKS__ */
 261         pglob->gl_errfunc = errfunc;
 262         return __glob(pattern, pglob);
 263 }
 264
 265 #ifdef __BLOCKS__
 266 int
 267 glob_b(pattern, flags, errblk, pglob)
 268         const char *pattern;
 269         int flags, (^errblk)(const char *, int);
 270         glob_t *pglob;
 271 {
 272         pglob->gl_flags = flags & ~GLOB_MAGCHAR;
 273         pglob->gl_flags |= _GLOB_ERR_BLOCK;
 274         pglob->gl_errblk = errblk;
 275         return __glob(pattern, pglob);
 276 }
 277 #endif /* __BLOCKS__ */
 278
 279 /*
 280  * Expand recursively a glob {} pattern. When there is no more expansion
 281  * invoke the standard globbing routine to glob the rest of the magic
 282  * characters
 283  */
 284 static int
 285 globexp1(pattern, pglob, limit, loc)
 286         const Char *pattern;
 287         glob_t *pglob;
 288         int *limit;
 289         locale_t loc;
 290 {
 291         const Char* ptr = pattern;
 292         int rv;
 293
 294         /* Protect a single {}, for find(1), like csh */
 295         if (pattern[0] == LBRACE && pattern[1] == RBRACE && pattern[2] == EOS)
 296                 return glob0(pattern, pglob, limit, loc);
 297
 298         while ((ptr = (const Char *) g_strchr((Char *) ptr, LBRACE)) != NULL)
 299                 if (!globexp2(ptr, pattern, pglob, &rv, limit, loc))
 300                         return rv;
 301
 302         return glob0(pattern, pglob, limit, loc);
 303 }
 304
 305
 306 /*
 307  * Recursive brace globbing helper. Tries to expand a single brace.
 308  * If it succeeds then it invokes globexp1 with the new pattern.
 309  * If it fails then it tries to glob the rest of the pattern and returns.
 310  */
 311 static int
 312 globexp2(ptr, pattern, pglob, rv, limit, loc)
 313         const Char *ptr, *pattern;
 314         glob_t *pglob;
 315         int *rv, *limit;
 316         locale_t loc;
 317 {
 318         int     i;
 319         Char   *lm, *ls;
 320         const Char *pe, *pm, *pl;
 321         Char    patbuf[MAXPATHLEN];
 322
 323         /* copy part up to the brace */
 324         for (lm = patbuf, pm = pattern; pm != ptr; *lm++ = *pm++)
 325                 continue;
 326         *lm = EOS;
 327         ls = lm;
 328
 329         /* Find the balanced brace */
 330         for (i = 0, pe = ++ptr; *pe; pe++)
 331                 if (*pe == LBRACKET) {
 332                         /* Ignore everything between [] */
 333                         for (pm = pe++; *pe != RBRACKET && *pe != EOS; pe++)
 334                                 continue;
 335                         if (*pe == EOS) {
 336                                 /*
 337                                  * We could not find a matching RBRACKET.
 338                                  * Ignore and just look for RBRACE
 339                                  */
 340                                 pe = pm;
 341                         }
 342                 }
 343                 else if (*pe == LBRACE)
 344                         i++;
 345                 else if (*pe == RBRACE) {
 346                         if (i == 0)
 347                                 break;
 348                         i--;
 349                 }
 350
 351         /* Non matching braces; just glob the pattern */
 352         if (i != 0 || *pe == EOS) {
 353                 *rv = glob0(patbuf, pglob, limit, loc);
 354                 return 0;
 355         }
 356
 357         for (i = 0, pl = pm = ptr; pm <= pe; pm++)
 358                 switch (*pm) {
 359                 case LBRACKET:
 360                         /* Ignore everything between [] */
 361                         for (pl = pm++; *pm != RBRACKET && *pm != EOS; pm++)
 362                                 continue;
 363                         if (*pm == EOS) {
 364                                 /*
 365                                  * We could not find a matching RBRACKET.
 366                                  * Ignore and just look for RBRACE
 367                                  */
 368                                 pm = pl;
 369                         }
 370                         break;
 371
 372                 case LBRACE:
 373                         i++;
 374                         break;
 375
 376                 case RBRACE:
 377                         if (i) {
 378                             i--;
 379                             break;
 380                         }
 381                         /* FALLTHROUGH */
 382                 case COMMA:
 383                         if (i && *pm == COMMA)
 384                                 break;
 385                         else {
 386                                 /* Append the current string */
 387                                 for (lm = ls; (pl < pm); *lm++ = *pl++)
 388                                         continue;
 389                                 /*
 390                                  * Append the rest of the pattern after the
 391                                  * closing brace
 392                                  */
 393                                 for (pl = pe + 1; (*lm++ = *pl++) != EOS;)
 394                                         continue;
 395
 396                                 /* Expand the current pattern */
 397 #ifdef DEBUG
 398                                 qprintf("globexp2:", patbuf);
 399 #endif
 400                                 *rv = globexp1(patbuf, pglob, limit, loc);
 401
 402                                 /* move after the comma, to the next string */
 403                                 pl = pm + 1;
 404                         }
 405                         break;
 406
 407                 default:
 408                         break;
 409                 }
 410         *rv = 0;
 411         return 0;
 412 }
 413
 414
 415
 416 #ifndef BUILDING_VARIANT
 417 /*
 418  * expand tilde from the passwd file.
 419  */
 420 __private_extern__ const Char *
 421 globtilde(pattern, patbuf, patbuf_len, pglob)
 422         const Char *pattern;
 423         Char *patbuf;
 424         size_t patbuf_len;
 425         glob_t *pglob;
 426 {
 427         struct passwd *pwd;
 428         char *h;
 429         const Char *p;
 430         Char *b, *eb;
 431
 432         if (*pattern != TILDE || !(pglob->gl_flags & GLOB_TILDE))
 433                 return pattern;
 434
 435         /*
 436          * Copy up to the end of the string or /
 437          */
 438         eb = &patbuf[patbuf_len - 1];
 439         for (p = pattern + 1, h = (char *) patbuf;
 440             h < (char *)eb && *p && *p != SLASH; *h++ = *p++)
 441                 continue;
 442
 443         *h = EOS;
 444
 445         if (((char *) patbuf)[0] == EOS) {
 446                 /*
 447                  * handle a plain ~ or ~/ by expanding $HOME first (iff
 448                  * we're not running setuid or setgid) and then trying
 449                  * the password file
 450                  */
 451                 if (issetugid() != 0 ||
 452                     (h = getenv("HOME")) == NULL) {
 453                         if (((h = getlogin()) != NULL &&
 454                              (pwd = getpwnam(h)) != NULL) ||
 455                             (pwd = getpwuid(getuid())) != NULL)
 456                                 h = pwd->pw_dir;
 457                         else
 458                                 return pattern;
 459                 }
 460         }
 461         else {
 462                 /*
 463                  * Expand a ~user
 464                  */
 465                 if ((pwd = getpwnam((char*) patbuf)) == NULL)
 466                         return pattern;
 467                 else
 468                         h = pwd->pw_dir;
 469         }
 470
 471         /* Copy the home directory */
 472         for (b = patbuf; b < eb && *h; *b++ = *h++)
 473                 continue;
 474
 475         /* Append the rest of the pattern */
 476         while (b < eb && (*b++ = *p++) != EOS)
 477                 continue;
 478         *b = EOS;
 479
 480         return patbuf;
 481 }
 482 #endif /* BUILDING_VARIANT */
 483
 484
 485 /*
 486  * The main glob() routine: compiles the pattern (optionally processing
 487  * quotes), calls glob1() to do the real pattern matching, and finally
 488  * sorts the list (unless unsorted operation is requested).  Returns 0
 489  * if things went well, nonzero if errors occurred.
 490  */
 491 static int
 492 glob0(pattern, pglob, limit, loc)
 493         const Char *pattern;
 494         glob_t *pglob;
 495         int *limit;
 496         locale_t loc;
 497 {
 498         const Char *qpatnext;
 499         Char c;
 500         int err, oldpathc;
 501         Char *bufnext, patbuf[MAXPATHLEN];
 502
 503         qpatnext = globtilde(pattern, patbuf, MAXPATHLEN, pglob);
 504         oldpathc = pglob->gl_pathc;
 505         bufnext = patbuf;
 506
 507         /* We don't need to check for buffer overflow any more. */
 508         while ((c = *qpatnext++) != EOS) {
 509                 if (c & M_PROTECT) {
 510                         *bufnext++ = CHAR(c);
 511                         continue;
 512                 } /* else */
 513                 switch (c) {
 514                 case LBRACKET:
 515                         c = *qpatnext;
 516                         if (c == NOT)
 517                                 ++qpatnext;
 518                         if (*qpatnext == EOS ||
 519                             g_strchr((Char *) qpatnext+1, RBRACKET) == NULL) {
 520                                 *bufnext++ = LBRACKET;
 521                                 if (c == NOT)
 522                                         --qpatnext;
 523                                 break;
 524                         }
 525                         *bufnext++ = M_SET;
 526                         if (c == NOT)
 527                                 *bufnext++ = M_NOT;
 528                         c = *qpatnext++;
 529                         do {
 530                                 *bufnext++ = CHAR(c);
 531                                 if (*qpatnext == RANGE &&
 532                                     (c = qpatnext[1]) != RBRACKET) {
 533                                         *bufnext++ = M_RNG;
 534                                         *bufnext++ = CHAR(c);
 535                                         qpatnext += 2;
 536                                 }
 537                         } while ((c = *qpatnext++) != RBRACKET);
 538                         pglob->gl_flags |= GLOB_MAGCHAR;
 539                         *bufnext++ = M_END;
 540                         break;
 541                 case QUESTION:
 542                         pglob->gl_flags |= GLOB_MAGCHAR;
 543                         *bufnext++ = M_ONE;
 544                         break;
 545                 case STAR:
 546                         pglob->gl_flags |= GLOB_MAGCHAR;
 547                         /* collapse adjacent stars to one,
 548                          * to avoid exponential behavior
 549                          */
 550                         if (bufnext == patbuf || bufnext[-1] != M_ALL)
 551                             *bufnext++ = M_ALL;
 552                         break;
 553                 default:
 554                         *bufnext++ = CHAR(c);
 555                         break;
 556                 }
 557         }
 558         *bufnext = EOS;
 559 #ifdef DEBUG
 560         qprintf("glob0:", patbuf);
 561 #endif
 562
 563         if ((err = glob1(patbuf, pglob, limit, loc)) != 0)
 564                 return(err);
 565
 566         /*
 567          * If there was no match we are going to append the pattern
 568          * if GLOB_NOCHECK was specified or if GLOB_NOMAGIC was specified
 569          * and the pattern did not contain any magic characters
 570          * GLOB_NOMAGIC is there just for compatibility with csh.
 571          */
 572         if (pglob->gl_pathc == oldpathc) {
 573                 if (((pglob->gl_flags & GLOB_NOCHECK) ||
 574                     ((pglob->gl_flags & GLOB_NOMAGIC) &&
 575                         !(pglob->gl_flags & GLOB_MAGCHAR))))
 576                         return(globextend(pattern, pglob, limit, loc));
 577                 else
 578                         return(GLOB_NOMATCH);
 579         }
 580         if (!(pglob->gl_flags & GLOB_NOSORT))
 581                 qsort(pglob->gl_pathv + pglob->gl_offs + oldpathc,
 582                     pglob->gl_pathc - oldpathc, sizeof(char *), compare);
 583         return(0);
 584 }
 585
 586 #ifndef BUILDING_VARIANT
 587 __private_extern__ int
 588 compare(p, q)
 589         const void *p, *q;
 590 {
 591         return(strcoll(*(char **)p, *(char **)q));
 592 }
 593 #endif /* BUILDING_VARIANT */
 594
 595 static int
 596 glob1(pattern, pglob, limit, loc)
 597         Char *pattern;
 598         glob_t *pglob;
 599         int *limit;
 600         locale_t loc;
 601 {
 602         Char pathbuf[MAXPATHLEN];
 603
 604         /* A null pathname is invalid -- POSIX 1003.1 sect. 2.4. */
 605         if (*pattern == EOS)
 606                 return(0);
 607         return(glob2(pathbuf, pathbuf, pathbuf + MAXPATHLEN - 1,
 608             pattern, pglob, limit, loc));
 609 }
 610
 611 /*
 612  * The functions glob2 and glob3 are mutually recursive; there is one level
 613  * of recursion for each segment in the pattern that contains one or more
 614  * meta characters.
 615  */
 616 static int
 617 glob2(pathbuf, pathend, pathend_last, pattern, pglob, limit, loc)
 618         Char *pathbuf, *pathend, *pathend_last, *pattern;
 619         glob_t *pglob;
 620         int *limit;
 621         locale_t loc;
 622 {
 623         struct stat sb;
 624         Char *p, *q;
 625         int anymeta;
 626
 627         /*
 628          * Loop over pattern segments until end of pattern or until
 629          * segment with meta character found.
 630          */
 631         for (anymeta = 0;;) {
 632                 if (*pattern == EOS) {          /* End of pattern? */
 633                         *pathend = EOS;
 634                         if (g_lstat(pathbuf, &sb, pglob, loc))
 635                                 return(0);
 636
 637                         if (((pglob->gl_flags & GLOB_MARK) &&
 638                             pathend[-1] != SEP) && (S_ISDIR(sb.st_mode)
 639                             || (S_ISLNK(sb.st_mode) &&
 640                             (g_stat(pathbuf, &sb, pglob, loc) == 0) &&
 641                             S_ISDIR(sb.st_mode)))) {
 642                                 if (pathend + 1 > pathend_last)
 643                                         return (GLOB_ABORTED);
 644                                 *pathend++ = SEP;
 645                                 *pathend = EOS;
 646                         }
 647                         ++pglob->gl_matchc;
 648                         return(globextend(pathbuf, pglob, limit, loc));
 649                 }
 650
 651                 /* Find end of next segment, copy tentatively to pathend. */
 652                 q = pathend;
 653                 p = pattern;
 654                 while (*p != EOS && *p != SEP) {
 655                         if (ismeta(*p))
 656                                 anymeta = 1;
 657                         if (q + 1 > pathend_last)
 658                                 return (GLOB_ABORTED);
 659                         *q++ = *p++;
 660                 }
 661
 662                 if (!anymeta) {         /* No expansion, do next segment. */
 663                         pathend = q;
 664                         pattern = p;
 665                         while (*pattern == SEP) {
 666                                 if (pathend + 1 > pathend_last)
 667                                         return (GLOB_ABORTED);
 668                                 *pathend++ = *pattern++;
 669                         }
 670                 } else                  /* Need expansion, recurse. */
 671                         return(glob3(pathbuf, pathend, pathend_last, pattern, p,
 672                             pglob, limit, loc));
 673         }
 674         /* NOTREACHED */
 675 }
 676
 677 static int
 678 glob3(pathbuf, pathend, pathend_last, pattern, restpattern, pglob, limit, loc)
 679         Char *pathbuf, *pathend, *pathend_last, *pattern, *restpattern;
 680         glob_t *pglob;
 681         int *limit;
 682         locale_t loc;
 683 {
 684         struct dirent *dp;
 685         DIR *dirp;
 686         int err;
 687         char buf[MAXPATHLEN];
 688
 689         /*
 690          * The readdirfunc declaration can't be prototyped, because it is
 691          * assigned, below, to two functions which are prototyped in glob.h
 692          * and dirent.h as taking pointers to differently typed opaque
 693          * structures.
 694          */
 695         struct dirent *(*readdirfunc)();
 696
 697         if (pathend > pathend_last)
 698                 return (GLOB_ABORTED);
 699         *pathend = EOS;
 700         errno = 0;
 701
 702         if ((dirp = g_opendir(pathbuf, pglob, loc)) == NULL) {
 703                 /* TODO: don't call for ENOENT or ENOTDIR? */
 704                 if (pglob->gl_errfunc) {
 705                         if (g_Ctoc(pathbuf, buf, sizeof(buf), loc))
 706                                 return (GLOB_ABORTED);
 707 #ifdef __BLOCKS__
 708                         if (pglob->gl_flags & _GLOB_ERR_BLOCK) {
 709                                 if (pglob->gl_errblk(buf, errno))
 710                                         return (GLOB_ABORTED);
 711                         } else
 712 #endif /* __BLOCKS__ */
 713                         if (pglob->gl_errfunc(buf, errno))
 714                                 return (GLOB_ABORTED);
 715                 }
 716                 if (pglob->gl_flags & GLOB_ERR)
 717                         return (GLOB_ABORTED);
 718                 return(0);
 719         }
 720
 721         err = 0;
 722
 723         /* Search directory for matching names. */
 724         if (pglob->gl_flags & GLOB_ALTDIRFUNC)
 725                 readdirfunc = pglob->gl_readdir;
 726         else
 727                 readdirfunc = readdir;
 728         while ((dp = (*readdirfunc)(dirp))) {
 729                 u_char *sc;
 730                 Char *dc;
 731                 wchar_t wc;
 732                 size_t clen;
 733                 mbstate_t mbs;
 734
 735                 /* Initial DOT must be matched literally. */
 736                 if (dp->d_name[0] == DOT && *pattern != DOT)
 737                         continue;
 738                 memset(&mbs, 0, sizeof(mbs));
 739                 dc = pathend;
 740                 sc = (u_char *) dp->d_name;
 741                 while (dc < pathend_last) {
 742                         clen = mbrtowc_l(&wc, (const char *)sc, MB_LEN_MAX, &mbs, loc);
 743                         if (clen == (size_t)-1 || clen == (size_t)-2) {
 744                                 wc = *sc;
 745                                 clen = 1;
 746                                 memset(&mbs, 0, sizeof(mbs));
 747                         }
 748                         if ((*dc++ = wc) == EOS)
 749                                 break;
 750                         sc += clen;
 751                 }
 752                 if (!match(pathend, pattern, restpattern, loc)) {
 753                         *pathend = EOS;
 754                         continue;
 755                 }
 756                 err = glob2(pathbuf, --dc, pathend_last, restpattern,
 757                     pglob, limit, loc);
 758                 if (err)
 759                         break;
 760         }
 761
 762         if (pglob->gl_flags & GLOB_ALTDIRFUNC)
 763                 (*pglob->gl_closedir)(dirp);
 764         else
 765                 closedir(dirp);
 766         return(err);
 767 }
 768
 769
 770 #ifndef BUILDING_VARIANT
 771 /*
 772  * Extend the gl_pathv member of a glob_t structure to accomodate a new item,
 773  * add the new item, and update gl_pathc.
 774  *
 775  * This assumes the BSD realloc, which only copies the block when its size
 776  * crosses a power-of-two boundary; for v7 realloc, this would cause quadratic
 777  * behavior.
 778  *
 779  * Return 0 if new item added, error code if memory couldn't be allocated.
 780  *
 781  * Invariant of the glob_t structure:
 782  *      Either gl_pathc is zero and gl_pathv is NULL; or gl_pathc > 0 and
 783  *      gl_pathv points to (gl_offs + gl_pathc + 1) items.
 784  */
 785 __private_extern__ int
 786 globextend(path, pglob, limit, loc)
 787         const Char *path;
 788         glob_t *pglob;
 789         int *limit;
 790         locale_t loc;
 791 {
 792         char **pathv;
 793         int i;
 794         u_int newsize, len;
 795         char *copy;
 796         const Char *p;
 797
 798         if (*limit && pglob->gl_pathc > *limit) {
 799                 errno = 0;
 800                 return (GLOB_NOSPACE);
 801         }
 802
 803         newsize = sizeof(*pathv) * (2 + pglob->gl_pathc + pglob->gl_offs);
 804         pathv = pglob->gl_pathv ?
 805                     realloc((char *)pglob->gl_pathv, newsize) :
 806                     malloc(newsize);
 807         if (pathv == NULL) {
 808                 if (pglob->gl_pathv) {
 809                         free(pglob->gl_pathv);
 810                         pglob->gl_pathv = NULL;
 811                 }
 812                 return(GLOB_NOSPACE);
 813         }
 814
 815         if (pglob->gl_pathv == NULL && pglob->gl_offs > 0) {
 816                 /* first time around -- clear initial gl_offs items */
 817                 pathv += pglob->gl_offs;
 818                 for (i = pglob->gl_offs; --i >= 0; )
 819                         *--pathv = NULL;
 820         }
 821         pglob->gl_pathv = pathv;
 822
 823         for (p = path; *p++;)
 824                 continue;
 825         len = MB_CUR_MAX_L(loc) * (size_t)(p - path);   /* XXX overallocation */
 826         if ((copy = malloc(len)) != NULL) {
 827                 if (g_Ctoc(path, copy, len, loc)) {
 828                         free(copy);
 829                         return (GLOB_NOSPACE);
 830                 }
 831                 pathv[pglob->gl_offs + pglob->gl_pathc++] = copy;
 832         }
 833         pathv[pglob->gl_offs + pglob->gl_pathc] = NULL;
 834         return(copy == NULL ? GLOB_NOSPACE : 0);
 835 }
 836
 837 /*
 838  * pattern matching function for filenames.  Each occurrence of the *
 839  * pattern causes a recursion level.
 840  */
 841 __private_extern__ int
 842 match(name, pat, patend, loc)
 843         Char *name, *pat, *patend;
 844         locale_t loc;
 845 {
 846         int ok, negate_range;
 847         Char c, k;
 848
 849         while (pat < patend) {
 850                 c = *pat++;
 851                 switch (c & M_MASK) {
 852                 case M_ALL:
 853                         if (pat == patend)
 854                                 return(1);
 855                         do
 856                             if (match(name, pat, patend, loc))
 857                                     return(1);
 858                         while (*name++ != EOS);
 859                         return(0);
 860                 case M_ONE:
 861                         if (*name++ == EOS)
 862                                 return(0);
 863                         break;
 864                 case M_SET:
 865                         ok = 0;
 866                         if ((k = *name++) == EOS)
 867                                 return(0);
 868                         if ((negate_range = ((*pat & M_MASK) == M_NOT)) != EOS)
 869                                 ++pat;
 870                         while (((c = *pat++) & M_MASK) != M_END)
 871                                 if ((*pat & M_MASK) == M_RNG) {
 872                                         if (loc->__collate_load_error ?
 873                                             CHAR(c) <= CHAR(k) && CHAR(k) <= CHAR(pat[1]) :
 874                                                __collate_range_cmp(CHAR(c), CHAR(k), loc) <= 0
 875                                             && __collate_range_cmp(CHAR(k), CHAR(pat[1]), loc) <= 0
 876                                            )
 877                                                 ok = 1;
 878                                         pat += 2;
 879                                 } else if (c == k)
 880                                         ok = 1;
 881                         if (ok == negate_range)
 882                                 return(0);
 883                         break;
 884                 default:
 885                         if (*name++ != c)
 886                                 return(0);
 887                         break;
 888                 }
 889         }
 890         return(*name == EOS);
 891 }
 892
 893 /* Free allocated data belonging to a glob_t structure. */
 894 void
 895 globfree(pglob)
 896         glob_t *pglob;
 897 {
 898         int i;
 899         char **pp;
 900
 901         if (pglob->gl_pathv != NULL) {
 902                 pp = pglob->gl_pathv + pglob->gl_offs;
 903                 for (i = pglob->gl_pathc; i--; ++pp)
 904                         if (*pp)
 905                                 free(*pp);
 906                 free(pglob->gl_pathv);
 907                 pglob->gl_pathv = NULL;
 908         }
 909 }
 910 #endif /* !BUILDING_VARIANT */
 911
 912 static DIR *
 913 g_opendir(str, pglob, loc)
 914         Char *str;
 915         glob_t *pglob;
 916         locale_t loc;
 917 {
 918         char buf[MAXPATHLEN];
 919
 920         if (!*str)
 921                 strcpy(buf, ".");
 922         else {
 923                 if (g_Ctoc(str, buf, sizeof(buf), loc))
 924                         return (NULL);
 925         }
 926
 927         if (pglob->gl_flags & GLOB_ALTDIRFUNC)
 928                 return((*pglob->gl_opendir)(buf));
 929
 930         return(opendir(buf));
 931 }
 932
 933 static int
 934 g_lstat(fn, sb, pglob, loc)
 935         Char *fn;
 936         struct stat *sb;
 937         glob_t *pglob;
 938         locale_t loc;
 939 {
 940         char buf[MAXPATHLEN];
 941
 942         if (g_Ctoc(fn, buf, sizeof(buf), loc)) {
 943                 errno = ENAMETOOLONG;
 944                 return (-1);
 945         }
 946         if (pglob->gl_flags & GLOB_ALTDIRFUNC)
 947                 return((*pglob->gl_lstat)(buf, sb));
 948         return(lstat(buf, sb));
 949 }
 950
 951 static int
 952 g_stat(fn, sb, pglob, loc)
 953         Char *fn;
 954         struct stat *sb;
 955         glob_t *pglob;
 956         locale_t loc;
 957 {
 958         char buf[MAXPATHLEN];
 959
 960         if (g_Ctoc(fn, buf, sizeof(buf), loc)) {
 961                 errno = ENAMETOOLONG;
 962                 return (-1);
 963         }
 964         if (pglob->gl_flags & GLOB_ALTDIRFUNC)
 965                 return((*pglob->gl_stat)(buf, sb));
 966         return(stat(buf, sb));
 967 }
 968
 969 #ifndef BUILDING_VARIANT
 970 __private_extern__ Char *
 971 g_strchr(str, ch)
 972         Char *str;
 973         wchar_t ch;
 974 {
 975         do {
 976                 if (*str == ch)
 977                         return (str);
 978         } while (*str++);
 979         return (NULL);
 980 }
 981
 982 __private_extern__ int
 983 g_Ctoc(str, buf, len, loc)
 984         const Char *str;
 985         char *buf;
 986         u_int len;
 987         locale_t loc;
 988 {
 989         mbstate_t mbs;
 990         size_t clen;
 991         int mb_cur_max = MB_CUR_MAX_L(loc);
 992
 993         memset(&mbs, 0, sizeof(mbs));
 994         while (len >= mb_cur_max) {
 995                 clen = wcrtomb_l(buf, *str, &mbs, loc);
 996                 if (clen == (size_t)-1)
 997                         return (1);
 998                 if (*str == L'\0')
 999                         return (0);
1000                 str++;
1001                 buf += clen;
1002                 len -= clen;
1003         }
1004         return (1);
1005 }
1006
1007 #ifdef DEBUG
1008 static void
1009 qprintf(str, s)
1010         const char *str;
1011         Char *s;
1012 {
1013         Char *p;
1014
1015         (void)printf("%s:\n", str);
1016         for (p = s; *p; p++)
1017                 (void)printf("%c", CHAR(*p));
1018         (void)printf("\n");
1019         for (p = s; *p; p++)
1020                 (void)printf("%c", *p & M_PROTECT ? '"' : ' ');
1021         (void)printf("\n");
1022         for (p = s; *p; p++)
1023                 (void)printf("%c", ismeta(*p) ? '_' : ' ');
1024         (void)printf("\n");
1025 }
1026 #endif
1027 #endif /* !BUILDING_VARIANT */