lib/libc/gen/glob.c

   1 /*      $NetBSD: glob.c,v 1.28 2011/01/21 23:30:31 christos 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.28 2011/01/21 23:30:31 christos 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 u_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 *pattern, int flags, int (*errfunc)(const char *, int),
 184     glob_t *pglob)
 185 {
 186         const u_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 u_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         Char *pend;
 616         ptrdiff_t diff;
 617
 618         _DIAGASSERT(pathbuf != NULL);
 619         _DIAGASSERT(pathend != NULL);
 620         _DIAGASSERT(pattern != NULL);
 621         _DIAGASSERT(pglob != NULL);
 622
 623 #ifdef DEBUG
 624         qprintf("glob2", pathbuf);
 625 #endif
 626         /*
 627          * Loop over pattern segments until end of pattern or until
 628          * segment with meta character found.
 629          */
 630         for (anymeta = 0;;) {
 631                 if (*pattern == EOS) {          /* End of pattern? */
 632                         *pathend = EOS;
 633                         if (g_lstat(pathbuf, &sb, pglob))
 634                                 return 0;
 635
 636                         if ((pglob->gl_flags & GLOB_LIMIT) &&
 637                             limit->l_stat++ >= GLOB_LIMIT_STAT) {
 638                                 errno = 0;
 639                                 *pathend++ = SEP;
 640                                 *pathend = EOS;
 641 printf("stat limit\n");
 642                                 return GLOB_NOSPACE;
 643                         }
 644                         if (((pglob->gl_flags & GLOB_MARK) &&
 645                             pathend[-1] != SEP) && (S_ISDIR(sb.st_mode) ||
 646                             (S_ISLNK(sb.st_mode) &&
 647                             (g_stat(pathbuf, &sb, pglob) == 0) &&
 648                             S_ISDIR(sb.st_mode)))) {
 649                                 if (pathend >= pathlim)
 650                                         return GLOB_ABORTED;
 651                                 *pathend++ = SEP;
 652                                 *pathend = EOS;
 653                         }
 654                         ++pglob->gl_matchc;
 655                         return globextend(pathbuf, pglob, limit);
 656                 }
 657
 658                 /* Find end of next segment, copy tentatively to pathend. */
 659                 q = pathend;
 660                 p = pattern;
 661                 while (*p != EOS && *p != SEP) {
 662                         if (ismeta(*p))
 663                                 anymeta = 1;
 664                         if (q >= pathlim)
 665                                 return GLOB_ABORTED;
 666                         *q++ = *p++;
 667                 }
 668
 669                 /*
 670                  * No expansion, or path ends in slash-dot shash-dot-dot,
 671                  * do next segment.
 672                  */
 673                 if (pglob->gl_flags & GLOB_PERIOD) {
 674                         for (pend = pathend; pend > pathbuf && pend[-1] == '/';
 675                             pend--)
 676                                 continue;
 677                         diff = pend - pathbuf;
 678                 } else {
 679                         /* XXX: GCC */
 680                         diff = 0;
 681                         pend = pathend;
 682                 }
 683
 684                 if ((!anymeta) ||
 685                     ((pglob->gl_flags & GLOB_PERIOD) &&
 686                      (diff >= 1 && pend[-1] == DOT) &&
 687                      (diff >= 2 && (pend[-2] == SLASH || pend[-2] == DOT)) &&
 688                      (diff < 3 || pend[-3] == SLASH))) {
 689                         pathend = q;
 690                         pattern = p;
 691                         while (*pattern == SEP) {
 692                                 if (pathend >= pathlim)
 693                                         return GLOB_ABORTED;
 694                                 *pathend++ = *pattern++;
 695                         }
 696                 } else                  /* Need expansion, recurse. */
 697                         return glob3(pathbuf, pathend, pathlim, pattern, p,
 698                             pattern, pglob, limit);
 699         }
 700         /* NOTREACHED */
 701 }
 702
 703 static int
 704 glob3(Char *pathbuf, Char *pathend, Char *pathlim, const Char *pattern,
 705     const Char *restpattern, const Char *pglobstar, glob_t *pglob,
 706     struct glob_limit *limit)
 707 {
 708         struct dirent *dp;
 709         DIR *dirp;
 710         __gl_stat_t sbuf;
 711         int error;
 712         char buf[MAXPATHLEN];
 713         int globstar = 0;
 714         int chase_symlinks = 0;
 715         const Char *termstar = NULL;
 716
 717         /*
 718          * The readdirfunc declaration can't be prototyped, because it is
 719          * assigned, below, to two functions which are prototyped in glob.h
 720          * and dirent.h as taking pointers to differently typed opaque
 721          * structures.
 722          */
 723         struct dirent *(*readdirfunc)(void *);
 724
 725         _DIAGASSERT(pathbuf != NULL);
 726         _DIAGASSERT(pathend != NULL);
 727         _DIAGASSERT(pattern != NULL);
 728         _DIAGASSERT(restpattern != NULL);
 729         _DIAGASSERT(pglob != NULL);
 730
 731         *pathend = EOS;
 732         errno = 0;
 733
 734         while (pglobstar < restpattern) {
 735                 if ((pglobstar[0] & M_MASK) == M_ALL &&
 736                     (pglobstar[1] & M_MASK) == M_ALL) {
 737                         globstar = 1;
 738                         chase_symlinks = (pglobstar[2] & M_MASK) == M_ALL;
 739                         termstar = pglobstar + (2 + chase_symlinks);
 740                         break;
 741                 }
 742                 pglobstar++;
 743         }
 744
 745         if (globstar) {
 746                 error = pglobstar == pattern && termstar == restpattern ?
 747                     *restpattern == EOS ?
 748                     glob2(pathbuf, pathend, pathlim, restpattern - 1, pglob,
 749                     limit) :
 750                     glob2(pathbuf, pathend, pathlim, restpattern + 1, pglob,
 751                     limit) :
 752                     glob3(pathbuf, pathend, pathlim, pattern, restpattern,
 753                     termstar, pglob, limit);
 754                 if (error)
 755                         return error;
 756                 *pathend = EOS;
 757         }
 758
 759         if (*pathbuf && (g_lstat(pathbuf, &sbuf, pglob) ||
 760             !S_ISDIR(sbuf.st_mode)
 761 #ifdef S_IFLINK
 762              && ((globstar && !chase_symlinks) || !S_ISLNK(sbuf.st_mode))
 763 #endif
 764             ))
 765                 return 0;
 766
 767         if ((dirp = g_opendir(pathbuf, pglob)) == NULL) {
 768                 if (pglob->gl_errfunc) {
 769                         if (g_Ctoc(pathbuf, buf, sizeof(buf)))
 770                                 return GLOB_ABORTED;
 771                         if (pglob->gl_errfunc(buf, errno) ||
 772                             pglob->gl_flags & GLOB_ERR)
 773                                 return GLOB_ABORTED;
 774                 }
 775                 /*
 776                  * Posix/XOpen: glob should return when it encounters a
 777                  * directory that it cannot open or read
 778                  * XXX: Should we ignore ENOTDIR and ENOENT though?
 779                  * I think that Posix had in mind EPERM...
 780                  */
 781                 if (pglob->gl_flags & GLOB_ERR)
 782                         return GLOB_ABORTED;
 783
 784                 return 0;
 785         }
 786
 787         error = 0;
 788
 789         /* Search directory for matching names. */
 790         if (pglob->gl_flags & GLOB_ALTDIRFUNC)
 791                 readdirfunc = pglob->gl_readdir;
 792         else
 793                 readdirfunc = (struct dirent *(*)__P((void *))) readdir;
 794         while ((dp = (*readdirfunc)(dirp)) != NULL) {
 795                 u_char *sc;
 796                 Char *dc;
 797
 798                 if ((pglob->gl_flags & GLOB_LIMIT) &&
 799                     limit->l_readdir++ >= GLOB_LIMIT_READDIR) {
 800                         errno = 0;
 801                         *pathend++ = SEP;
 802                         *pathend = EOS;
 803                         return GLOB_NOSPACE;
 804                 }
 805
 806                 /*
 807                  * Initial DOT must be matched literally, unless we have
 808                  * GLOB_PERIOD set.
 809                  */
 810                 if ((pglob->gl_flags & GLOB_PERIOD) == 0)
 811                         if (dp->d_name[0] == DOT && *pattern != DOT)
 812                                 continue;
 813                 /*
 814                  * If GLOB_NO_DOTDIRS is set, . and .. vanish.
 815                  */
 816                 if ((pglob->gl_flags & GLOB_NO_DOTDIRS) &&
 817                     (dp->d_name[0] == DOT) &&
 818                     ((dp->d_name[1] == EOS) ||
 819                      ((dp->d_name[1] == DOT) && (dp->d_name[2] == EOS))))
 820                         continue;
 821                 /*
 822                  * The resulting string contains EOS, so we can
 823                  * use the pathlim character, if it is the nul
 824                  */
 825                 for (sc = (u_char *) dp->d_name, dc = pathend;
 826                      dc <= pathlim && (*dc++ = *sc++) != EOS;)
 827                         continue;
 828
 829                 /*
 830                  * Have we filled the buffer without seeing EOS?
 831                  */
 832                 if (dc > pathlim && *pathlim != EOS) {
 833                         /*
 834                          * Abort when requested by caller, otherwise
 835                          * reset pathend back to last SEP and continue
 836                          * with next dir entry.
 837                          */
 838                         if (pglob->gl_flags & GLOB_ERR) {
 839                                 error = GLOB_ABORTED;
 840                                 break;
 841                         }
 842                         else {
 843                                 *pathend = EOS;
 844                                 continue;
 845                         }
 846                 }
 847
 848                 if (globstar) {
 849 #ifdef S_IFLNK
 850                         if (!chase_symlinks &&
 851                             (g_lstat(pathbuf, &sbuf, pglob) ||
 852                             S_ISLNK(sbuf.st_mode)))
 853                                 continue;
 854 #endif
 855
 856                         if (!match(pathend, pattern, termstar))
 857                                 continue;
 858
 859                         if (--dc < pathlim - 2)
 860                                 *dc++ = SEP;
 861                         *dc = EOS;
 862                         error = glob2(pathbuf, dc, pathlim, pglobstar,
 863                             pglob, limit);
 864                         if (error)
 865                                 break;
 866                         *pathend = EOS;
 867                 } else {
 868                         if (!match(pathend, pattern, restpattern)) {
 869                                 *pathend = EOS;
 870                                 continue;
 871                         }
 872                         error = glob2(pathbuf, --dc, pathlim, restpattern,
 873                             pglob, limit);
 874                         if (error)
 875                                 break;
 876                 }
 877         }
 878         if (pglob->gl_flags & GLOB_ALTDIRFUNC)
 879                 (*pglob->gl_closedir)(dirp);
 880         else
 881                 closedir(dirp);
 882
 883         /*
 884          * Again Posix X/Open issue with regards to error handling.
 885          */
 886         if ((error || errno) && (pglob->gl_flags & GLOB_ERR))
 887                 return GLOB_ABORTED;
 888
 889         return error;
 890 }
 891
 892
 893 /*
 894  * Extend the gl_pathv member of a glob_t structure to accommodate a new item,
 895  * add the new item, and update gl_pathc.
 896  *
 897  * This assumes the BSD realloc, which only copies the block when its size
 898  * crosses a power-of-two boundary; for v7 realloc, this would cause quadratic
 899  * behavior.
 900  *
 901  * Return 0 if new item added, error code if memory couldn't be allocated.
 902  *
 903  * Invariant of the glob_t structure:
 904  *      Either gl_pathc is zero and gl_pathv is NULL; or gl_pathc > 0 and
 905  *      gl_pathv points to (gl_offs + gl_pathc + 1) items.
 906  */
 907 static int
 908 globextend(const Char *path, glob_t *pglob, struct glob_limit *limit)
 909 {
 910         char **pathv;
 911         size_t i, newsize, len;
 912         char *copy;
 913         const Char *p;
 914
 915         _DIAGASSERT(path != NULL);
 916         _DIAGASSERT(pglob != NULL);
 917
 918         newsize = sizeof(*pathv) * (2 + pglob->gl_pathc + pglob->gl_offs);
 919         if ((pglob->gl_flags & GLOB_LIMIT) &&
 920             newsize > GLOB_LIMIT_PATH * sizeof(*pathv))
 921                 goto nospace;
 922         pathv = pglob->gl_pathv ? realloc(pglob->gl_pathv, newsize) :
 923             malloc(newsize);
 924         if (pathv == NULL)
 925                 return GLOB_NOSPACE;
 926
 927         if (pglob->gl_pathv == NULL && pglob->gl_offs > 0) {
 928                 /* first time around -- clear initial gl_offs items */
 929                 pathv += pglob->gl_offs;
 930                 for (i = pglob->gl_offs + 1; --i > 0; )
 931                         *--pathv = NULL;
 932         }
 933         pglob->gl_pathv = pathv;
 934
 935         for (p = path; *p++;)
 936                 continue;
 937         len = (size_t)(p - path);
 938         limit->l_string += len;
 939         if ((copy = malloc(len)) != NULL) {
 940                 if (g_Ctoc(path, copy, len)) {
 941                         free(copy);
 942                         return GLOB_ABORTED;
 943                 }
 944                 pathv[pglob->gl_offs + pglob->gl_pathc++] = copy;
 945         }
 946         pathv[pglob->gl_offs + pglob->gl_pathc] = NULL;
 947
 948         if ((pglob->gl_flags & GLOB_LIMIT) &&
 949             (newsize + limit->l_string) >= GLOB_LIMIT_STRING)
 950                 goto nospace;
 951
 952         return copy == NULL ? GLOB_NOSPACE : 0;
 953 nospace:
 954         errno = 0;
 955         return GLOB_NOSPACE;
 956 }
 957
 958
 959 /*
 960  * pattern matching function for filenames.  Each occurrence of the *
 961  * pattern causes a recursion level.
 962  */
 963 static int
 964 match(const Char *name, const Char *pat, const Char *patend)
 965 {
 966         int ok, negate_range;
 967         Char c, k;
 968
 969         _DIAGASSERT(name != NULL);
 970         _DIAGASSERT(pat != NULL);
 971         _DIAGASSERT(patend != NULL);
 972
 973         while (pat < patend) {
 974                 c = *pat++;
 975                 switch (c & M_MASK) {
 976                 case M_ALL:
 977                         while (pat < patend && (*pat & M_MASK) == M_ALL)
 978                                 pat++;  /* eat consecutive '*' */
 979                         if (pat == patend)
 980                                 return 1;
 981                         for (; !match(name, pat, patend); name++)
 982                                 if (*name == EOS)
 983                                         return 0;
 984                         return 1;
 985                 case M_ONE:
 986                         if (*name++ == EOS)
 987                                 return 0;
 988                         break;
 989                 case M_SET:
 990                         ok = 0;
 991                         if ((k = *name++) == EOS)
 992                                 return 0;
 993                         if ((negate_range = ((*pat & M_MASK) == M_NOT)) != EOS)
 994                                 ++pat;
 995                         while (((c = *pat++) & M_MASK) != M_END)
 996                                 if ((*pat & M_MASK) == M_RNG) {
 997                                         if (c <= k && k <= pat[1])
 998                                                 ok = 1;
 999                                         pat += 2;
1000                                 } else if (c == k)
1001                                         ok = 1;
1002                         if (ok == negate_range)
1003                                 return 0;
1004                         break;
1005                 default:
1006                         if (*name++ != c)
1007                                 return 0;
1008                         break;
1009                 }
1010         }
1011         return *name == EOS;
1012 }
1013
1014 /* Free allocated data belonging to a glob_t structure. */
1015 void
1016 globfree(glob_t *pglob)
1017 {
1018         size_t i;
1019         char **pp;
1020
1021         _DIAGASSERT(pglob != NULL);
1022
1023         if (pglob->gl_pathv != NULL) {
1024                 pp = pglob->gl_pathv + pglob->gl_offs;
1025                 for (i = pglob->gl_pathc; i--; ++pp)
1026                         if (*pp)
1027                                 free(*pp);
1028                 free(pglob->gl_pathv);
1029                 pglob->gl_pathv = NULL;
1030                 pglob->gl_pathc = 0;
1031         }
1032 }
1033
1034 #ifndef __LIBC12_SOURCE__
1035 int
1036 glob_pattern_p(const char *pattern, int quote)
1037 {
1038         int range = 0;
1039
1040         for (; *pattern; pattern++)
1041                 switch (*pattern) {
1042                 case QUESTION:
1043                 case STAR:
1044                         return 1;
1045
1046                 case QUOTE:
1047                         if (quote && pattern[1] != EOS)
1048                               ++pattern;
1049                         break;
1050
1051                 case LBRACKET:
1052                         range = 1;
1053                         break;
1054
1055                 case RBRACKET:
1056                         if (range)
1057                               return 1;
1058                         break;
1059                 default:
1060                         break;
1061                 }
1062
1063           return 0;
1064 }
1065 #endif
1066
1067 static DIR *
1068 g_opendir(Char *str, glob_t *pglob)
1069 {
1070         char buf[MAXPATHLEN];
1071
1072         _DIAGASSERT(str != NULL);
1073         _DIAGASSERT(pglob != NULL);
1074
1075         if (!*str)
1076                 (void)strlcpy(buf, ".", sizeof(buf));
1077         else {
1078                 if (g_Ctoc(str, buf, sizeof(buf)))
1079                         return NULL;
1080         }
1081
1082         if (pglob->gl_flags & GLOB_ALTDIRFUNC)
1083                 return (*pglob->gl_opendir)(buf);
1084
1085         return opendir(buf);
1086 }
1087
1088 static int
1089 g_lstat(Char *fn, __gl_stat_t *sb, glob_t *pglob)
1090 {
1091         char buf[MAXPATHLEN];
1092
1093         _DIAGASSERT(fn != NULL);
1094         _DIAGASSERT(sb != NULL);
1095         _DIAGASSERT(pglob != NULL);
1096
1097         if (g_Ctoc(fn, buf, sizeof(buf)))
1098                 return -1;
1099         if (pglob->gl_flags & GLOB_ALTDIRFUNC)
1100                 return (*pglob->gl_lstat)(buf, sb);
1101         return lstat(buf, sb);
1102 }
1103
1104 static int
1105 g_stat(Char *fn, __gl_stat_t *sb, glob_t *pglob)
1106 {
1107         char buf[MAXPATHLEN];
1108
1109         _DIAGASSERT(fn != NULL);
1110         _DIAGASSERT(sb != NULL);
1111         _DIAGASSERT(pglob != NULL);
1112
1113         if (g_Ctoc(fn, buf, sizeof(buf)))
1114                 return -1;
1115         if (pglob->gl_flags & GLOB_ALTDIRFUNC)
1116                 return (*pglob->gl_stat)(buf, sb);
1117         return stat(buf, sb);
1118 }
1119
1120 static Char *
1121 g_strchr(const Char *str, int ch)
1122 {
1123
1124         _DIAGASSERT(str != NULL);
1125
1126         do {
1127                 if (*str == ch)
1128                         return __UNCONST(str);
1129         } while (*str++);
1130         return NULL;
1131 }
1132
1133 static int
1134 g_Ctoc(const Char *str, char *buf, size_t len)
1135 {
1136         char *dc;
1137
1138         _DIAGASSERT(str != NULL);
1139         _DIAGASSERT(buf != NULL);
1140
1141         if (len == 0)
1142                 return 1;
1143
1144         for (dc = buf; len && (*dc++ = *str++) != EOS; len--)
1145                 continue;
1146
1147         return len == 0;
1148 }
1149
1150 #ifdef DEBUG
1151 static void
1152 qprintf(const char *str, Char *s)
1153 {
1154         Char *p;
1155
1156         _DIAGASSERT(str != NULL);
1157         _DIAGASSERT(s != NULL);
1158
1159         (void)printf("%s:\n", str);
1160         for (p = s; *p; p++)
1161                 (void)printf("%c", CHAR(*p));
1162         (void)printf("\n");
1163         for (p = s; *p; p++)
1164                 (void)printf("%c", *p & M_PROTECT ? '"' : ' ');
1165         (void)printf("\n");
1166         for (p = s; *p; p++)
1167                 (void)printf("%c", ismeta(*p) ? '_' : ' ');
1168         (void)printf("\n");
1169 }
1170 #endif