StdLib/PosixLib/Glob/glob.c

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