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