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 int
 180 glob(pattern, flags, errfunc, pglob)
 181         const char *pattern;
 182         int flags, (*errfunc)(const char *, int);
 183         glob_t *pglob;
 184 {
 185         const u_char *patnext;
 186         int limit;
 187         Char *bufnext, *bufend, patbuf[MAXPATHLEN], prot;
 188         mbstate_t mbs;
 189         wchar_t wc;
 190         size_t clen;
 191         locale_t loc = __current_locale();
 192         int mb_cur_max = MB_CUR_MAX_L(loc);
 193
 194         patnext = (u_char *) pattern;
 195         if (!(flags & GLOB_APPEND)) {
 196                 pglob->gl_pathc = 0;
 197                 pglob->gl_pathv = NULL;
 198                 if (!(flags & GLOB_DOOFFS))
 199                         pglob->gl_offs = 0;
 200         }
 201         if (flags & GLOB_LIMIT) {
 202                 limit = pglob->gl_matchc;
 203                 if (limit == 0)
 204                         limit = ARG_MAX;
 205         } else
 206                 limit = 0;
 207         pglob->gl_flags = flags & ~GLOB_MAGCHAR;
 208         pglob->gl_errfunc = errfunc;
 209         pglob->gl_matchc = 0;
 210
 211         bufnext = patbuf;
 212         bufend = bufnext + MAXPATHLEN - 1;
 213         if (flags & GLOB_NOESCAPE) {
 214                 memset(&mbs, 0, sizeof(mbs));
 215                 while (bufend - bufnext >= mb_cur_max) {
 216                         clen = mbrtowc_l(&wc, (const char *)patnext, MB_LEN_MAX, &mbs, loc);
 217                         if (clen == (size_t)-1 || clen == (size_t)-2)
 218                                 return (GLOB_NOMATCH);
 219                         else if (clen == 0)
 220                                 break;
 221                         *bufnext++ = wc;
 222                         patnext += clen;
 223                 }
 224         } else {
 225                 /* Protect the quoted characters. */
 226                 memset(&mbs, 0, sizeof(mbs));
 227                 while (bufend - bufnext >= mb_cur_max) {
 228                         if (*patnext == QUOTE) {
 229                                 if (*++patnext == EOS) {
 230                                         *bufnext++ = QUOTE | M_PROTECT;
 231                                         continue;
 232                                 }
 233                                 prot = M_PROTECT;
 234                         } else
 235                                 prot = 0;
 236                         clen = mbrtowc_l(&wc, (const char *)patnext, MB_LEN_MAX, &mbs, loc);
 237                         if (clen == (size_t)-1 || clen == (size_t)-2)
 238                                 return (GLOB_NOMATCH);
 239                         else if (clen == 0)
 240                                 break;
 241                         *bufnext++ = wc | prot;
 242                         patnext += clen;
 243                 }
 244         }
 245         *bufnext = EOS;
 246
 247         if (flags & GLOB_BRACE)
 248             return globexp1(patbuf, pglob, &limit, loc);
 249         else
 250             return glob0(patbuf, pglob, &limit, loc);
 251 }
 252
 253 /*
 254  * Expand recursively a glob {} pattern. When there is no more expansion
 255  * invoke the standard globbing routine to glob the rest of the magic
 256  * characters
 257  */
 258 static int
 259 globexp1(pattern, pglob, limit, loc)
 260         const Char *pattern;
 261         glob_t *pglob;
 262         int *limit;
 263         locale_t loc;
 264 {
 265         const Char* ptr = pattern;
 266         int rv;
 267
 268         /* Protect a single {}, for find(1), like csh */
 269         if (pattern[0] == LBRACE && pattern[1] == RBRACE && pattern[2] == EOS)
 270                 return glob0(pattern, pglob, limit, loc);
 271
 272         while ((ptr = (const Char *) g_strchr((Char *) ptr, LBRACE)) != NULL)
 273                 if (!globexp2(ptr, pattern, pglob, &rv, limit, loc))
 274                         return rv;
 275
 276         return glob0(pattern, pglob, limit, loc);
 277 }
 278
 279
 280 /*
 281  * Recursive brace globbing helper. Tries to expand a single brace.
 282  * If it succeeds then it invokes globexp1 with the new pattern.
 283  * If it fails then it tries to glob the rest of the pattern and returns.
 284  */
 285 static int
 286 globexp2(ptr, pattern, pglob, rv, limit, loc)
 287         const Char *ptr, *pattern;
 288         glob_t *pglob;
 289         int *rv, *limit;
 290         locale_t loc;
 291 {
 292         int     i;
 293         Char   *lm, *ls;
 294         const Char *pe, *pm, *pl;
 295         Char    patbuf[MAXPATHLEN];
 296
 297         /* copy part up to the brace */
 298         for (lm = patbuf, pm = pattern; pm != ptr; *lm++ = *pm++)
 299                 continue;
 300         *lm = EOS;
 301         ls = lm;
 302
 303         /* Find the balanced brace */
 304         for (i = 0, pe = ++ptr; *pe; pe++)
 305                 if (*pe == LBRACKET) {
 306                         /* Ignore everything between [] */
 307                         for (pm = pe++; *pe != RBRACKET && *pe != EOS; pe++)
 308                                 continue;
 309                         if (*pe == EOS) {
 310                                 /*
 311                                  * We could not find a matching RBRACKET.
 312                                  * Ignore and just look for RBRACE
 313                                  */
 314                                 pe = pm;
 315                         }
 316                 }
 317                 else if (*pe == LBRACE)
 318                         i++;
 319                 else if (*pe == RBRACE) {
 320                         if (i == 0)
 321                                 break;
 322                         i--;
 323                 }
 324
 325         /* Non matching braces; just glob the pattern */
 326         if (i != 0 || *pe == EOS) {
 327                 *rv = glob0(patbuf, pglob, limit, loc);
 328                 return 0;
 329         }
 330
 331         for (i = 0, pl = pm = ptr; pm <= pe; pm++)
 332                 switch (*pm) {
 333                 case LBRACKET:
 334                         /* Ignore everything between [] */
 335                         for (pl = pm++; *pm != RBRACKET && *pm != EOS; pm++)
 336                                 continue;
 337                         if (*pm == EOS) {
 338                                 /*
 339                                  * We could not find a matching RBRACKET.
 340                                  * Ignore and just look for RBRACE
 341                                  */
 342                                 pm = pl;
 343                         }
 344                         break;
 345
 346                 case LBRACE:
 347                         i++;
 348                         break;
 349
 350                 case RBRACE:
 351                         if (i) {
 352                             i--;
 353                             break;
 354                         }
 355                         /* FALLTHROUGH */
 356                 case COMMA:
 357                         if (i && *pm == COMMA)
 358                                 break;
 359                         else {
 360                                 /* Append the current string */
 361                                 for (lm = ls; (pl < pm); *lm++ = *pl++)
 362                                         continue;
 363                                 /*
 364                                  * Append the rest of the pattern after the
 365                                  * closing brace
 366                                  */
 367                                 for (pl = pe + 1; (*lm++ = *pl++) != EOS;)
 368                                         continue;
 369
 370                                 /* Expand the current pattern */
 371 #ifdef DEBUG
 372                                 qprintf("globexp2:", patbuf);
 373 #endif
 374                                 *rv = globexp1(patbuf, pglob, limit, loc);
 375
 376                                 /* move after the comma, to the next string */
 377                                 pl = pm + 1;
 378                         }
 379                         break;
 380
 381                 default:
 382                         break;
 383                 }
 384         *rv = 0;
 385         return 0;
 386 }
 387
 388
 389
 390 #ifndef BUILDING_VARIANT
 391 /*
 392  * expand tilde from the passwd file.
 393  */
 394 __private_extern__ const Char *
 395 globtilde(pattern, patbuf, patbuf_len, pglob)
 396         const Char *pattern;
 397         Char *patbuf;
 398         size_t patbuf_len;
 399         glob_t *pglob;
 400 {
 401         struct passwd *pwd;
 402         char *h;
 403         const Char *p;
 404         Char *b, *eb;
 405
 406         if (*pattern != TILDE || !(pglob->gl_flags & GLOB_TILDE))
 407                 return pattern;
 408
 409         /*
 410          * Copy up to the end of the string or /
 411          */
 412         eb = &patbuf[patbuf_len - 1];
 413         for (p = pattern + 1, h = (char *) patbuf;
 414             h < (char *)eb && *p && *p != SLASH; *h++ = *p++)
 415                 continue;
 416
 417         *h = EOS;
 418
 419         if (((char *) patbuf)[0] == EOS) {
 420                 /*
 421                  * handle a plain ~ or ~/ by expanding $HOME first (iff
 422                  * we're not running setuid or setgid) and then trying
 423                  * the password file
 424                  */
 425                 if (issetugid() != 0 ||
 426                     (h = getenv("HOME")) == NULL) {
 427                         if (((h = getlogin()) != NULL &&
 428                              (pwd = getpwnam(h)) != NULL) ||
 429                             (pwd = getpwuid(getuid())) != NULL)
 430                                 h = pwd->pw_dir;
 431                         else
 432                                 return pattern;
 433                 }
 434         }
 435         else {
 436                 /*
 437                  * Expand a ~user
 438                  */
 439                 if ((pwd = getpwnam((char*) patbuf)) == NULL)
 440                         return pattern;
 441                 else
 442                         h = pwd->pw_dir;
 443         }
 444
 445         /* Copy the home directory */
 446         for (b = patbuf; b < eb && *h; *b++ = *h++)
 447                 continue;
 448
 449         /* Append the rest of the pattern */
 450         while (b < eb && (*b++ = *p++) != EOS)
 451                 continue;
 452         *b = EOS;
 453
 454         return patbuf;
 455 }
 456 #endif /* BUILDING_VARIANT */
 457
 458
 459 /*
 460  * The main glob() routine: compiles the pattern (optionally processing
 461  * quotes), calls glob1() to do the real pattern matching, and finally
 462  * sorts the list (unless unsorted operation is requested).  Returns 0
 463  * if things went well, nonzero if errors occurred.
 464  */
 465 static int
 466 glob0(pattern, pglob, limit, loc)
 467         const Char *pattern;
 468         glob_t *pglob;
 469         int *limit;
 470         locale_t loc;
 471 {
 472         const Char *qpatnext;
 473         Char c;
 474         int err, oldpathc;
 475         Char *bufnext, patbuf[MAXPATHLEN];
 476
 477         qpatnext = globtilde(pattern, patbuf, MAXPATHLEN, pglob);
 478         oldpathc = pglob->gl_pathc;
 479         bufnext = patbuf;
 480
 481         /* We don't need to check for buffer overflow any more. */
 482         while ((c = *qpatnext++) != EOS) {
 483                 if (c & M_PROTECT) {
 484                         *bufnext++ = CHAR(c);
 485                         continue;
 486                 } /* else */
 487                 switch (c) {
 488                 case LBRACKET:
 489                         c = *qpatnext;
 490                         if (c == NOT)
 491                                 ++qpatnext;
 492                         if (*qpatnext == EOS ||
 493                             g_strchr((Char *) qpatnext+1, RBRACKET) == NULL) {
 494                                 *bufnext++ = LBRACKET;
 495                                 if (c == NOT)
 496                                         --qpatnext;
 497                                 break;
 498                         }
 499                         *bufnext++ = M_SET;
 500                         if (c == NOT)
 501                                 *bufnext++ = M_NOT;
 502                         c = *qpatnext++;
 503                         do {
 504                                 *bufnext++ = CHAR(c);
 505                                 if (*qpatnext == RANGE &&
 506                                     (c = qpatnext[1]) != RBRACKET) {
 507                                         *bufnext++ = M_RNG;
 508                                         *bufnext++ = CHAR(c);
 509                                         qpatnext += 2;
 510                                 }
 511                         } while ((c = *qpatnext++) != RBRACKET);
 512                         pglob->gl_flags |= GLOB_MAGCHAR;
 513                         *bufnext++ = M_END;
 514                         break;
 515                 case QUESTION:
 516                         pglob->gl_flags |= GLOB_MAGCHAR;
 517                         *bufnext++ = M_ONE;
 518                         break;
 519                 case STAR:
 520                         pglob->gl_flags |= GLOB_MAGCHAR;
 521                         /* collapse adjacent stars to one,
 522                          * to avoid exponential behavior
 523                          */
 524                         if (bufnext == patbuf || bufnext[-1] != M_ALL)
 525                             *bufnext++ = M_ALL;
 526                         break;
 527                 default:
 528                         *bufnext++ = CHAR(c);
 529                         break;
 530                 }
 531         }
 532         *bufnext = EOS;
 533 #ifdef DEBUG
 534         qprintf("glob0:", patbuf);
 535 #endif
 536
 537         if ((err = glob1(patbuf, pglob, limit, loc)) != 0)
 538                 return(err);
 539
 540         /*
 541          * If there was no match we are going to append the pattern
 542          * if GLOB_NOCHECK was specified or if GLOB_NOMAGIC was specified
 543          * and the pattern did not contain any magic characters
 544          * GLOB_NOMAGIC is there just for compatibility with csh.
 545          */
 546         if (pglob->gl_pathc == oldpathc) {
 547                 if (((pglob->gl_flags & GLOB_NOCHECK) ||
 548                     ((pglob->gl_flags & GLOB_NOMAGIC) &&
 549                         !(pglob->gl_flags & GLOB_MAGCHAR))))
 550                         return(globextend(pattern, pglob, limit, loc));
 551                 else
 552                         return(GLOB_NOMATCH);
 553         }
 554         if (!(pglob->gl_flags & GLOB_NOSORT))
 555                 qsort(pglob->gl_pathv + pglob->gl_offs + oldpathc,
 556                     pglob->gl_pathc - oldpathc, sizeof(char *), compare);
 557         return(0);
 558 }
 559
 560 #ifndef BUILDING_VARIANT
 561 __private_extern__ int
 562 compare(p, q)
 563         const void *p, *q;
 564 {
 565         return(strcoll(*(char **)p, *(char **)q));
 566 }
 567 #endif /* BUILDING_VARIANT */
 568
 569 static int
 570 glob1(pattern, pglob, limit, loc)
 571         Char *pattern;
 572         glob_t *pglob;
 573         int *limit;
 574         locale_t loc;
 575 {
 576         Char pathbuf[MAXPATHLEN];
 577
 578         /* A null pathname is invalid -- POSIX 1003.1 sect. 2.4. */
 579         if (*pattern == EOS)
 580                 return(0);
 581         return(glob2(pathbuf, pathbuf, pathbuf + MAXPATHLEN - 1,
 582             pattern, pglob, limit, loc));
 583 }
 584
 585 /*
 586  * The functions glob2 and glob3 are mutually recursive; there is one level
 587  * of recursion for each segment in the pattern that contains one or more
 588  * meta characters.
 589  */
 590 static int
 591 glob2(pathbuf, pathend, pathend_last, pattern, pglob, limit, loc)
 592         Char *pathbuf, *pathend, *pathend_last, *pattern;
 593         glob_t *pglob;
 594         int *limit;
 595         locale_t loc;
 596 {
 597         struct stat sb;
 598         Char *p, *q;
 599         int anymeta;
 600
 601         /*
 602          * Loop over pattern segments until end of pattern or until
 603          * segment with meta character found.
 604          */
 605         for (anymeta = 0;;) {
 606                 if (*pattern == EOS) {          /* End of pattern? */
 607                         *pathend = EOS;
 608                         if (g_lstat(pathbuf, &sb, pglob, loc))
 609                                 return(0);
 610
 611                         if (((pglob->gl_flags & GLOB_MARK) &&
 612                             pathend[-1] != SEP) && (S_ISDIR(sb.st_mode)
 613                             || (S_ISLNK(sb.st_mode) &&
 614                             (g_stat(pathbuf, &sb, pglob, loc) == 0) &&
 615                             S_ISDIR(sb.st_mode)))) {
 616                                 if (pathend + 1 > pathend_last)
 617                                         return (GLOB_ABORTED);
 618                                 *pathend++ = SEP;
 619                                 *pathend = EOS;
 620                         }
 621                         ++pglob->gl_matchc;
 622                         return(globextend(pathbuf, pglob, limit, loc));
 623                 }
 624
 625                 /* Find end of next segment, copy tentatively to pathend. */
 626                 q = pathend;
 627                 p = pattern;
 628                 while (*p != EOS && *p != SEP) {
 629                         if (ismeta(*p))
 630                                 anymeta = 1;
 631                         if (q + 1 > pathend_last)
 632                                 return (GLOB_ABORTED);
 633                         *q++ = *p++;
 634                 }
 635
 636                 if (!anymeta) {         /* No expansion, do next segment. */
 637                         pathend = q;
 638                         pattern = p;
 639                         while (*pattern == SEP) {
 640                                 if (pathend + 1 > pathend_last)
 641                                         return (GLOB_ABORTED);
 642                                 *pathend++ = *pattern++;
 643                         }
 644                 } else                  /* Need expansion, recurse. */
 645                         return(glob3(pathbuf, pathend, pathend_last, pattern, p,
 646                             pglob, limit, loc));
 647         }
 648         /* NOTREACHED */
 649 }
 650
 651 static int
 652 glob3(pathbuf, pathend, pathend_last, pattern, restpattern, pglob, limit, loc)
 653         Char *pathbuf, *pathend, *pathend_last, *pattern, *restpattern;
 654         glob_t *pglob;
 655         int *limit;
 656         locale_t loc;
 657 {
 658         struct dirent *dp;
 659         DIR *dirp;
 660         int err;
 661         char buf[MAXPATHLEN];
 662
 663         /*
 664          * The readdirfunc declaration can't be prototyped, because it is
 665          * assigned, below, to two functions which are prototyped in glob.h
 666          * and dirent.h as taking pointers to differently typed opaque
 667          * structures.
 668          */
 669         struct dirent *(*readdirfunc)();
 670
 671         if (pathend > pathend_last)
 672                 return (GLOB_ABORTED);
 673         *pathend = EOS;
 674         errno = 0;
 675
 676         if ((dirp = g_opendir(pathbuf, pglob, loc)) == NULL) {
 677                 /* TODO: don't call for ENOENT or ENOTDIR? */
 678                 if (pglob->gl_errfunc) {
 679                         if (g_Ctoc(pathbuf, buf, sizeof(buf), loc))
 680                                 return (GLOB_ABORTED);
 681                         if (pglob->gl_errfunc(buf, errno))
 682                                 return (GLOB_ABORTED);
 683                 }
 684                 if (pglob->gl_flags & GLOB_ERR)
 685                         return (GLOB_ABORTED);
 686                 return(0);
 687         }
 688
 689         err = 0;
 690
 691         /* Search directory for matching names. */
 692         if (pglob->gl_flags & GLOB_ALTDIRFUNC)
 693                 readdirfunc = pglob->gl_readdir;
 694         else
 695                 readdirfunc = readdir;
 696         while ((dp = (*readdirfunc)(dirp))) {
 697                 u_char *sc;
 698                 Char *dc;
 699                 wchar_t wc;
 700                 size_t clen;
 701                 mbstate_t mbs;
 702
 703                 /* Initial DOT must be matched literally. */
 704                 if (dp->d_name[0] == DOT && *pattern != DOT)
 705                         continue;
 706                 memset(&mbs, 0, sizeof(mbs));
 707                 dc = pathend;
 708                 sc = (u_char *) dp->d_name;
 709                 while (dc < pathend_last) {
 710                         clen = mbrtowc_l(&wc, (const char *)sc, MB_LEN_MAX, &mbs, loc);
 711                         if (clen == (size_t)-1 || clen == (size_t)-2) {
 712                                 wc = *sc;
 713                                 clen = 1;
 714                                 memset(&mbs, 0, sizeof(mbs));
 715                         }
 716                         if ((*dc++ = wc) == EOS)
 717                                 break;
 718                         sc += clen;
 719                 }
 720                 if (!match(pathend, pattern, restpattern, loc)) {
 721                         *pathend = EOS;
 722                         continue;
 723                 }
 724                 err = glob2(pathbuf, --dc, pathend_last, restpattern,
 725                     pglob, limit, loc);
 726                 if (err)
 727                         break;
 728         }
 729
 730         if (pglob->gl_flags & GLOB_ALTDIRFUNC)
 731                 (*pglob->gl_closedir)(dirp);
 732         else
 733                 closedir(dirp);
 734         return(err);
 735 }
 736
 737
 738 #ifndef BUILDING_VARIANT
 739 /*
 740  * Extend the gl_pathv member of a glob_t structure to accomodate a new item,
 741  * add the new item, and update gl_pathc.
 742  *
 743  * This assumes the BSD realloc, which only copies the block when its size
 744  * crosses a power-of-two boundary; for v7 realloc, this would cause quadratic
 745  * behavior.
 746  *
 747  * Return 0 if new item added, error code if memory couldn't be allocated.
 748  *
 749  * Invariant of the glob_t structure:
 750  *      Either gl_pathc is zero and gl_pathv is NULL; or gl_pathc > 0 and
 751  *      gl_pathv points to (gl_offs + gl_pathc + 1) items.
 752  */
 753 __private_extern__ int
 754 globextend(path, pglob, limit, loc)
 755         const Char *path;
 756         glob_t *pglob;
 757         int *limit;
 758         locale_t loc;
 759 {
 760         char **pathv;
 761         int i;
 762         u_int newsize, len;
 763         char *copy;
 764         const Char *p;
 765
 766         if (*limit && pglob->gl_pathc > *limit) {
 767                 errno = 0;
 768                 return (GLOB_NOSPACE);
 769         }
 770
 771         newsize = sizeof(*pathv) * (2 + pglob->gl_pathc + pglob->gl_offs);
 772         pathv = pglob->gl_pathv ?
 773                     realloc((char *)pglob->gl_pathv, newsize) :
 774                     malloc(newsize);
 775         if (pathv == NULL) {
 776                 if (pglob->gl_pathv) {
 777                         free(pglob->gl_pathv);
 778                         pglob->gl_pathv = NULL;
 779                 }
 780                 return(GLOB_NOSPACE);
 781         }
 782
 783         if (pglob->gl_pathv == NULL && pglob->gl_offs > 0) {
 784                 /* first time around -- clear initial gl_offs items */
 785                 pathv += pglob->gl_offs;
 786                 for (i = pglob->gl_offs; --i >= 0; )
 787                         *--pathv = NULL;
 788         }
 789         pglob->gl_pathv = pathv;
 790
 791         for (p = path; *p++;)
 792                 continue;
 793         len = MB_CUR_MAX_L(loc) * (size_t)(p - path);   /* XXX overallocation */
 794         if ((copy = malloc(len)) != NULL) {
 795                 if (g_Ctoc(path, copy, len, loc)) {
 796                         free(copy);
 797                         return (GLOB_NOSPACE);
 798                 }
 799                 pathv[pglob->gl_offs + pglob->gl_pathc++] = copy;
 800         }
 801         pathv[pglob->gl_offs + pglob->gl_pathc] = NULL;
 802         return(copy == NULL ? GLOB_NOSPACE : 0);
 803 }
 804
 805 /*
 806  * pattern matching function for filenames.  Each occurrence of the *
 807  * pattern causes a recursion level.
 808  */
 809 __private_extern__ int
 810 match(name, pat, patend, loc)
 811         Char *name, *pat, *patend;
 812         locale_t loc;
 813 {
 814         int ok, negate_range;
 815         Char c, k;
 816
 817         while (pat < patend) {
 818                 c = *pat++;
 819                 switch (c & M_MASK) {
 820                 case M_ALL:
 821                         if (pat == patend)
 822                                 return(1);
 823                         do
 824                             if (match(name, pat, patend, loc))
 825                                     return(1);
 826                         while (*name++ != EOS);
 827                         return(0);
 828                 case M_ONE:
 829                         if (*name++ == EOS)
 830                                 return(0);
 831                         break;
 832                 case M_SET:
 833                         ok = 0;
 834                         if ((k = *name++) == EOS)
 835                                 return(0);
 836                         if ((negate_range = ((*pat & M_MASK) == M_NOT)) != EOS)
 837                                 ++pat;
 838                         while (((c = *pat++) & M_MASK) != M_END)
 839                                 if ((*pat & M_MASK) == M_RNG) {
 840                                         if (loc->__collate_load_error ?
 841                                             CHAR(c) <= CHAR(k) && CHAR(k) <= CHAR(pat[1]) :
 842                                                __collate_range_cmp(CHAR(c), CHAR(k), loc) <= 0
 843                                             && __collate_range_cmp(CHAR(k), CHAR(pat[1]), loc) <= 0
 844                                            )
 845                                                 ok = 1;
 846                                         pat += 2;
 847                                 } else if (c == k)
 848                                         ok = 1;
 849                         if (ok == negate_range)
 850                                 return(0);
 851                         break;
 852                 default:
 853                         if (*name++ != c)
 854                                 return(0);
 855                         break;
 856                 }
 857         }
 858         return(*name == EOS);
 859 }
 860
 861 /* Free allocated data belonging to a glob_t structure. */
 862 void
 863 globfree(pglob)
 864         glob_t *pglob;
 865 {
 866         int i;
 867         char **pp;
 868
 869         if (pglob->gl_pathv != NULL) {
 870                 pp = pglob->gl_pathv + pglob->gl_offs;
 871                 for (i = pglob->gl_pathc; i--; ++pp)
 872                         if (*pp)
 873                                 free(*pp);
 874                 free(pglob->gl_pathv);
 875                 pglob->gl_pathv = NULL;
 876         }
 877 }
 878 #endif /* !BUILDING_VARIANT */
 879
 880 static DIR *
 881 g_opendir(str, pglob, loc)
 882         Char *str;
 883         glob_t *pglob;
 884         locale_t loc;
 885 {
 886         char buf[MAXPATHLEN];
 887
 888         if (!*str)
 889                 strcpy(buf, ".");
 890         else {
 891                 if (g_Ctoc(str, buf, sizeof(buf), loc))
 892                         return (NULL);
 893         }
 894
 895         if (pglob->gl_flags & GLOB_ALTDIRFUNC)
 896                 return((*pglob->gl_opendir)(buf));
 897
 898         return(opendir(buf));
 899 }
 900
 901 static int
 902 g_lstat(fn, sb, pglob, loc)
 903         Char *fn;
 904         struct stat *sb;
 905         glob_t *pglob;
 906         locale_t loc;
 907 {
 908         char buf[MAXPATHLEN];
 909
 910         if (g_Ctoc(fn, buf, sizeof(buf), loc)) {
 911                 errno = ENAMETOOLONG;
 912                 return (-1);
 913         }
 914         if (pglob->gl_flags & GLOB_ALTDIRFUNC)
 915                 return((*pglob->gl_lstat)(buf, sb));
 916         return(lstat(buf, sb));
 917 }
 918
 919 static int
 920 g_stat(fn, sb, pglob, loc)
 921         Char *fn;
 922         struct stat *sb;
 923         glob_t *pglob;
 924         locale_t loc;
 925 {
 926         char buf[MAXPATHLEN];
 927
 928         if (g_Ctoc(fn, buf, sizeof(buf), loc)) {
 929                 errno = ENAMETOOLONG;
 930                 return (-1);
 931         }
 932         if (pglob->gl_flags & GLOB_ALTDIRFUNC)
 933                 return((*pglob->gl_stat)(buf, sb));
 934         return(stat(buf, sb));
 935 }
 936
 937 #ifndef BUILDING_VARIANT
 938 __private_extern__ Char *
 939 g_strchr(str, ch)
 940         Char *str;
 941         wchar_t ch;
 942 {
 943         do {
 944                 if (*str == ch)
 945                         return (str);
 946         } while (*str++);
 947         return (NULL);
 948 }
 949
 950 __private_extern__ int
 951 g_Ctoc(str, buf, len, loc)
 952         const Char *str;
 953         char *buf;
 954         u_int len;
 955         locale_t loc;
 956 {
 957         mbstate_t mbs;
 958         size_t clen;
 959         int mb_cur_max = MB_CUR_MAX_L(loc);
 960
 961         memset(&mbs, 0, sizeof(mbs));
 962         while (len >= mb_cur_max) {
 963                 clen = wcrtomb_l(buf, *str, &mbs, loc);
 964                 if (clen == (size_t)-1)
 965                         return (1);
 966                 if (*str == L'\0')
 967                         return (0);
 968                 str++;
 969                 buf += clen;
 970                 len -= clen;
 971         }
 972         return (1);
 973 }
 974
 975 #ifdef DEBUG
 976 static void
 977 qprintf(str, s)
 978         const char *str;
 979         Char *s;
 980 {
 981         Char *p;
 982
 983         (void)printf("%s:\n", str);
 984         for (p = s; *p; p++)
 985                 (void)printf("%c", CHAR(*p));
 986         (void)printf("\n");
 987         for (p = s; *p; p++)
 988                 (void)printf("%c", *p & M_PROTECT ? '"' : ' ');
 989         (void)printf("\n");
 990         for (p = s; *p; p++)
 991                 (void)printf("%c", ismeta(*p) ? '_' : ' ');
 992         (void)printf("\n");
 993 }
 994 #endif
 995 #endif /* !BUILDING_VARIANT */