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