lib/libc/gen/glob.c

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