lib/glob.c

   1 /* Copyright (C) 1991-2002,2003,2004,2005,2006,2007 Free Software Foundation, Inc.
   2    This file is part of the GNU C Library.
   3
   4    The GNU C Library is free software; you can redistribute it and/or
   5    modify it under the terms of the GNU Lesser General Public
   6    License as published by the Free Software Foundation; either
   7    version 2.1 of the License, or (at your option) any later version.
   8
   9    The GNU C Library is distributed in the hope that it will be useful,
  10    but WITHOUT ANY WARRANTY; without even the implied warranty of
  11    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12    Lesser General Public License for more details.
  13
  14    You should have received a copy of the GNU Lesser General Public
  15    License along with the GNU C Library; if not, write to the Free
  16    Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
  17    02111-1307 USA.  */
  18
  19 #ifndef _LIBC
  20 # include <config.h>
  21 #endif
  22
  23 #include <glob.h>
  24
  25 #include <errno.h>
  26 #include <sys/types.h>
  27 #include <sys/stat.h>
  28 #include <stddef.h>
  29
  30 /* Outcomment the following line for production quality code.  */
  31 /* #define NDEBUG 1 */
  32 #include <assert.h>
  33
  34 #include <stdio.h>              /* Needed on stupid SunOS for assert.  */
  35
  36 #if !defined _LIBC || !defined GLOB_ONLY_P
  37
  38 #include <unistd.h>
  39 #if !defined POSIX && defined _POSIX_VERSION
  40 # define POSIX
  41 #endif
  42
  43 #include <pwd.h>
  44
  45 #include <errno.h>
  46 #ifndef __set_errno
  47 # define __set_errno(val) errno = (val)
  48 #endif
  49
  50 #include <dirent.h>
  51
  52
  53 /* In GNU systems, <dirent.h> defines this macro for us.  */
  54 #ifndef _D_EXACT_NAMLEN
  55 # define _D_EXACT_NAMLEN(dirent) strlen ((dirent)->d_name)
  56 #endif
  57
  58 /* When used in the GNU libc the symbol _DIRENT_HAVE_D_TYPE is available
  59    if the `d_type' member for `struct dirent' is available.
  60    HAVE_STRUCT_DIRENT_D_TYPE plays the same role in GNULIB.  */
  61 #if defined _DIRENT_HAVE_D_TYPE || defined HAVE_STRUCT_DIRENT_D_TYPE
  62 /* True if the directory entry D must be of type T.  */
  63 # define DIRENT_MUST_BE(d, t)   ((d)->d_type == (t))
  64
  65 /* True if the directory entry D might be a symbolic link.  */
  66 # define DIRENT_MIGHT_BE_SYMLINK(d) \
  67     ((d)->d_type == DT_UNKNOWN || (d)->d_type == DT_LNK)
  68
  69 /* True if the directory entry D might be a directory.  */
  70 # define DIRENT_MIGHT_BE_DIR(d)  \
  71     ((d)->d_type == DT_DIR || DIRENT_MIGHT_BE_SYMLINK (d))
  72
  73 #else /* !HAVE_D_TYPE */
  74 # define DIRENT_MUST_BE(d, t)           false
  75 # define DIRENT_MIGHT_BE_SYMLINK(d)     true
  76 # define DIRENT_MIGHT_BE_DIR(d)         true
  77 #endif /* HAVE_D_TYPE */
  78
  79 /* If the system has the `struct dirent64' type we use it internally.  */
  80 #if defined _LIBC && !defined COMPILE_GLOB64
  81 # if (defined POSIX || defined WINDOWS32) && !defined __GNU_LIBRARY__
  82 #  define CONVERT_D_INO(d64, d32)
  83 # else
  84 #  define CONVERT_D_INO(d64, d32) \
  85   (d64)->d_ino = (d32)->d_ino;
  86 # endif
  87
  88 # ifdef _DIRENT_HAVE_D_TYPE
  89 #  define CONVERT_D_TYPE(d64, d32) \
  90   (d64)->d_type = (d32)->d_type;
  91 # else
  92 #  define CONVERT_D_TYPE(d64, d32)
  93 # endif
  94
  95 # define CONVERT_DIRENT_DIRENT64(d64, d32) \
  96   memcpy ((d64)->d_name, (d32)->d_name, _D_EXACT_NAMLEN (d32) + 1);           \
  97   CONVERT_D_INO (d64, d32)                                                    \
  98   CONVERT_D_TYPE (d64, d32)
  99 #endif
 100
 101
 102 #if (defined POSIX || defined WINDOWS32) && !defined __GNU_LIBRARY__
 103 /* Posix does not require that the d_ino field be present, and some
 104    systems do not provide it. */
 105 # define REAL_DIR_ENTRY(dp) 1
 106 #else
 107 # define REAL_DIR_ENTRY(dp) (dp->d_ino != 0)
 108 #endif /* POSIX */
 109
 110 #include <stdlib.h>
 111 #include <string.h>
 112
 113 /* NAME_MAX is usually defined in <dirent.h> or <limits.h>.  */
 114 #include <limits.h>
 115 #ifndef NAME_MAX
 116 # define NAME_MAX (sizeof (((struct dirent *) 0)->d_name))
 117 #endif
 118
 119 #include <alloca.h>
 120
 121 #ifdef _LIBC
 122 # undef strdup
 123 # define strdup(str) __strdup (str)
 124 # define sysconf(id) __sysconf (id)
 125 # define closedir(dir) __closedir (dir)
 126 # define opendir(name) __opendir (name)
 127 # define readdir(str) __readdir64 (str)
 128 # define getpwnam_r(name, bufp, buf, len, res) \
 129    __getpwnam_r (name, bufp, buf, len, res)
 130 # ifndef __stat64
 131 #  define __stat64(fname, buf) __xstat64 (_STAT_VER, fname, buf)
 132 # endif
 133 # define struct_stat64          struct stat64
 134 #else /* !_LIBC */
 135 # include "getlogin_r.h"
 136 # define __stat64(fname, buf)   stat (fname, buf)
 137 # define struct_stat64          struct stat
 138 # define __stat(fname, buf)     stat (fname, buf)
 139 # define __alloca               alloca
 140 # define __readdir              readdir
 141 # define __readdir64            readdir64
 142 # define __glob_pattern_p       glob_pattern_p
 143 #endif /* _LIBC */
 144
 145 #include <stdbool.h>
 146 #include <fnmatch.h>
 147
 148 #ifdef _SC_GETPW_R_SIZE_MAX
 149 # define GETPW_R_SIZE_MAX()     sysconf (_SC_GETPW_R_SIZE_MAX)
 150 #else
 151 # define GETPW_R_SIZE_MAX()     (-1)
 152 #endif
 153 #ifdef _SC_LOGIN_NAME_MAX
 154 # define GET_LOGIN_NAME_MAX()   sysconf (_SC_LOGIN_NAME_MAX)
 155 #else
 156 # define GET_LOGIN_NAME_MAX()   (-1)
 157 #endif
 158 \f
 159 static const char *next_brace_sub (const char *begin, int flags) __THROW;
 160
 161 #endif /* !defined _LIBC || !defined GLOB_ONLY_P */
 162
 163 /* The results of opendir() in this file are not used with dirfd and fchdir,
 164    therefore save some unnecessary work in fchdir.c.  */
 165 #undef opendir
 166 #undef closedir
 167
 168 static int glob_in_dir (const char *pattern, const char *directory,
 169                         int flags, int (*errfunc) (const char *, int),
 170                         glob_t *pglob);
 171
 172 #if !defined _LIBC || !defined GLOB_ONLY_P
 173 static int prefix_array (const char *prefix, char **array, size_t n) __THROW;
 174 static int collated_compare (const void *, const void *) __THROW;
 175
 176
 177 /* Find the end of the sub-pattern in a brace expression.  */
 178 static const char *
 179 next_brace_sub (const char *cp, int flags)
 180 {
 181   unsigned int depth = 0;
 182   while (*cp != '\0')
 183     if ((flags & GLOB_NOESCAPE) == 0 && *cp == '\\')
 184       {
 185         if (*++cp == '\0')
 186           break;
 187         ++cp;
 188       }
 189     else
 190       {
 191         if ((*cp == '}' && depth-- == 0) || (*cp == ',' && depth == 0))
 192           break;
 193
 194         if (*cp++ == '{')
 195           depth++;
 196       }
 197
 198   return *cp != '\0' ? cp : NULL;
 199 }
 200
 201 #endif /* !defined _LIBC || !defined GLOB_ONLY_P */
 202
 203 /* Do glob searching for PATTERN, placing results in PGLOB.
 204    The bits defined above may be set in FLAGS.
 205    If a directory cannot be opened or read and ERRFUNC is not nil,
 206    it is called with the pathname that caused the error, and the
 207    `errno' value from the failing call; if it returns non-zero
 208    `glob' returns GLOB_ABORTED; if it returns zero, the error is ignored.
 209    If memory cannot be allocated for PGLOB, GLOB_NOSPACE is returned.
 210    Otherwise, `glob' returns zero.  */
 211 int
 212 #ifdef GLOB_ATTRIBUTE
 213 GLOB_ATTRIBUTE
 214 #endif
 215 glob (pattern, flags, errfunc, pglob)
 216      const char *pattern;
 217      int flags;
 218      int (*errfunc) (const char *, int);
 219      glob_t *pglob;
 220 {
 221   const char *filename;
 222   const char *dirname;
 223   size_t dirlen;
 224   int status;
 225   size_t oldcount;
 226
 227   if (pattern == NULL || pglob == NULL || (flags & ~__GLOB_FLAGS) != 0)
 228     {
 229       __set_errno (EINVAL);
 230       return -1;
 231     }
 232
 233   if (!(flags & GLOB_DOOFFS))
 234     /* Have to do this so `globfree' knows where to start freeing.  It
 235        also makes all the code that uses gl_offs simpler. */
 236     pglob->gl_offs = 0;
 237
 238   if (flags & GLOB_BRACE)
 239     {
 240       const char *begin;
 241
 242       if (flags & GLOB_NOESCAPE)
 243         begin = strchr (pattern, '{');
 244       else
 245         {
 246           begin = pattern;
 247           while (1)
 248             {
 249               if (*begin == '\0')
 250                 {
 251                   begin = NULL;
 252                   break;
 253                 }
 254
 255               if (*begin == '\\' && begin[1] != '\0')
 256                 ++begin;
 257               else if (*begin == '{')
 258                 break;
 259
 260               ++begin;
 261             }
 262         }
 263
 264       if (begin != NULL)
 265         {
 266           /* Allocate working buffer large enough for our work.  Note that
 267             we have at least an opening and closing brace.  */
 268           size_t firstc;
 269           char *alt_start;
 270           const char *p;
 271           const char *next;
 272           const char *rest;
 273           size_t rest_len;
 274 #ifdef __GNUC__
 275           char onealt[strlen (pattern) - 1];
 276 #else
 277           char *onealt = malloc (strlen (pattern) - 1);
 278           if (onealt == NULL)
 279             {
 280               if (!(flags & GLOB_APPEND))
 281                 {
 282                   pglob->gl_pathc = 0;
 283                   pglob->gl_pathv = NULL;
 284                 }
 285               return GLOB_NOSPACE;
 286             }
 287 #endif
 288
 289           /* We know the prefix for all sub-patterns.  */
 290           alt_start = mempcpy (onealt, pattern, begin - pattern);
 291
 292           /* Find the first sub-pattern and at the same time find the
 293              rest after the closing brace.  */
 294           next = next_brace_sub (begin + 1, flags);
 295           if (next == NULL)
 296             {
 297               /* It is an invalid expression.  */
 298 #ifndef __GNUC__
 299               free (onealt);
 300 #endif
 301               return glob (pattern, flags & ~GLOB_BRACE, errfunc, pglob);
 302             }
 303
 304           /* Now find the end of the whole brace expression.  */
 305           rest = next;
 306           while (*rest != '}')
 307             {
 308               rest = next_brace_sub (rest + 1, flags);
 309               if (rest == NULL)
 310                 {
 311                   /* It is an invalid expression.  */
 312 #ifndef __GNUC__
 313                   free (onealt);
 314 #endif
 315                   return glob (pattern, flags & ~GLOB_BRACE, errfunc, pglob);
 316                 }
 317             }
 318           /* Please note that we now can be sure the brace expression
 319              is well-formed.  */
 320           rest_len = strlen (++rest) + 1;
 321
 322           /* We have a brace expression.  BEGIN points to the opening {,
 323              NEXT points past the terminator of the first element, and END
 324              points past the final }.  We will accumulate result names from
 325              recursive runs for each brace alternative in the buffer using
 326              GLOB_APPEND.  */
 327
 328           if (!(flags & GLOB_APPEND))
 329             {
 330               /* This call is to set a new vector, so clear out the
 331                  vector so we can append to it.  */
 332               pglob->gl_pathc = 0;
 333               pglob->gl_pathv = NULL;
 334             }
 335           firstc = pglob->gl_pathc;
 336
 337           p = begin + 1;
 338           while (1)
 339             {
 340               int result;
 341
 342               /* Construct the new glob expression.  */
 343               mempcpy (mempcpy (alt_start, p, next - p), rest, rest_len);
 344
 345               result = glob (onealt,
 346                              ((flags & ~(GLOB_NOCHECK | GLOB_NOMAGIC))
 347                               | GLOB_APPEND), errfunc, pglob);
 348
 349               /* If we got an error, return it.  */
 350               if (result && result != GLOB_NOMATCH)
 351                 {
 352 #ifndef __GNUC__
 353                   free (onealt);
 354 #endif
 355                   if (!(flags & GLOB_APPEND))
 356                     {
 357                       globfree (pglob);
 358                       pglob->gl_pathc = 0;
 359                     }
 360                   return result;
 361                 }
 362
 363               if (*next == '}')
 364                 /* We saw the last entry.  */
 365                 break;
 366
 367               p = next + 1;
 368               next = next_brace_sub (p, flags);
 369               assert (next != NULL);
 370             }
 371
 372 #ifndef __GNUC__
 373           free (onealt);
 374 #endif
 375
 376           if (pglob->gl_pathc != firstc)
 377             /* We found some entries.  */
 378             return 0;
 379           else if (!(flags & (GLOB_NOCHECK|GLOB_NOMAGIC)))
 380             return GLOB_NOMATCH;
 381         }
 382     }
 383
 384   /* Find the filename.  */
 385   filename = strrchr (pattern, '/');
 386 #if defined __MSDOS__ || defined WINDOWS32
 387   /* The case of "d:pattern".  Since `:' is not allowed in
 388      file names, we can safely assume that wherever it
 389      happens in pattern, it signals the filename part.  This
 390      is so we could some day support patterns like "[a-z]:foo".  */
 391   if (filename == NULL)
 392     filename = strchr (pattern, ':');
 393 #endif /* __MSDOS__ || WINDOWS32 */
 394   if (filename == NULL)
 395     {
 396       /* This can mean two things: a simple name or "~name".  The latter
 397          case is nothing but a notation for a directory.  */
 398       if ((flags & (GLOB_TILDE|GLOB_TILDE_CHECK)) && pattern[0] == '~')
 399         {
 400           dirname = pattern;
 401           dirlen = strlen (pattern);
 402
 403           /* Set FILENAME to NULL as a special flag.  This is ugly but
 404              other solutions would require much more code.  We test for
 405              this special case below.  */
 406           filename = NULL;
 407         }
 408       else
 409         {
 410           filename = pattern;
 411 #ifdef _AMIGA
 412           dirname = "";
 413 #else
 414           dirname = ".";
 415 #endif
 416           dirlen = 0;
 417         }
 418     }
 419   else if (filename == pattern)
 420     {
 421       /* "/pattern".  */
 422       dirname = "/";
 423       dirlen = 1;
 424       ++filename;
 425     }
 426   else
 427     {
 428       char *newp;
 429       dirlen = filename - pattern;
 430 #if defined __MSDOS__ || defined WINDOWS32
 431       if (*filename == ':'
 432           || (filename > pattern + 1 && filename[-1] == ':'))
 433         {
 434           char *drive_spec;
 435
 436           ++dirlen;
 437           drive_spec = __alloca (dirlen + 1);
 438           *((char *) mempcpy (drive_spec, pattern, dirlen)) = '\0';
 439           /* For now, disallow wildcards in the drive spec, to
 440              prevent infinite recursion in glob.  */
 441           if (__glob_pattern_p (drive_spec, !(flags & GLOB_NOESCAPE)))
 442             return GLOB_NOMATCH;
 443           /* If this is "d:pattern", we need to copy `:' to DIRNAME
 444              as well.  If it's "d:/pattern", don't remove the slash
 445              from "d:/", since "d:" and "d:/" are not the same.*/
 446         }
 447 #endif
 448       newp = __alloca (dirlen + 1);
 449       *((char *) mempcpy (newp, pattern, dirlen)) = '\0';
 450       dirname = newp;
 451       ++filename;
 452
 453       if (filename[0] == '\0'
 454 #if defined __MSDOS__ || defined WINDOWS32
 455           && dirname[dirlen - 1] != ':'
 456           && (dirlen < 3 || dirname[dirlen - 2] != ':'
 457               || dirname[dirlen - 1] != '/')
 458 #endif
 459           && dirlen > 1)
 460         /* "pattern/".  Expand "pattern", appending slashes.  */
 461         {
 462           int val = glob (dirname, flags | GLOB_MARK, errfunc, pglob);
 463           if (val == 0)
 464             pglob->gl_flags = ((pglob->gl_flags & ~GLOB_MARK)
 465                                | (flags & GLOB_MARK));
 466           return val;
 467         }
 468     }
 469
 470   if (!(flags & GLOB_APPEND))
 471     {
 472       pglob->gl_pathc = 0;
 473       if (!(flags & GLOB_DOOFFS))
 474         pglob->gl_pathv = NULL;
 475       else
 476         {
 477           size_t i;
 478           pglob->gl_pathv = malloc ((pglob->gl_offs + 1) * sizeof (char *));
 479           if (pglob->gl_pathv == NULL)
 480             return GLOB_NOSPACE;
 481
 482           for (i = 0; i <= pglob->gl_offs; ++i)
 483             pglob->gl_pathv[i] = NULL;
 484         }
 485     }
 486
 487   oldcount = pglob->gl_pathc + pglob->gl_offs;
 488
 489   if ((flags & (GLOB_TILDE|GLOB_TILDE_CHECK)) && dirname[0] == '~')
 490     {
 491       if (dirname[1] == '\0' || dirname[1] == '/')
 492         {
 493           /* Look up home directory.  */
 494           const char *home_dir = getenv ("HOME");
 495 # ifdef _AMIGA
 496           if (home_dir == NULL || home_dir[0] == '\0')
 497             home_dir = "SYS:";
 498 # else
 499 #  ifdef WINDOWS32
 500           if (home_dir == NULL || home_dir[0] == '\0')
 501             home_dir = "c:/users/default"; /* poor default */
 502 #  else
 503           if (home_dir == NULL || home_dir[0] == '\0')
 504             {
 505               int success;
 506               char *name;
 507               size_t buflen = GET_LOGIN_NAME_MAX () + 1;
 508
 509               if (buflen == 0)
 510                 /* `sysconf' does not support _SC_LOGIN_NAME_MAX.  Try
 511                    a moderate value.  */
 512                 buflen = 20;
 513               name = __alloca (buflen);
 514
 515               success = getlogin_r (name, buflen) == 0;
 516               if (success)
 517                 {
 518                   struct passwd *p;
 519 #   if defined HAVE_GETPWNAM_R || defined _LIBC
 520                   long int pwbuflen = GETPW_R_SIZE_MAX ();
 521                   char *pwtmpbuf;
 522                   struct passwd pwbuf;
 523                   int save = errno;
 524
 525 #    ifndef _LIBC
 526                   if (pwbuflen == -1)
 527                     /* `sysconf' does not support _SC_GETPW_R_SIZE_MAX.
 528                        Try a moderate value.  */
 529                     pwbuflen = 1024;
 530 #    endif
 531                   pwtmpbuf = __alloca (pwbuflen);
 532
 533                   while (getpwnam_r (name, &pwbuf, pwtmpbuf, pwbuflen, &p)
 534                          != 0)
 535                     {
 536                       if (errno != ERANGE)
 537                         {
 538                           p = NULL;
 539                           break;
 540                         }
 541 #    ifdef _LIBC
 542                       pwtmpbuf = extend_alloca (pwtmpbuf, pwbuflen,
 543                                                 2 * pwbuflen);
 544 #    else
 545                       pwbuflen *= 2;
 546                       pwtmpbuf = __alloca (pwbuflen);
 547 #    endif
 548                       __set_errno (save);
 549                     }
 550 #   else
 551                   p = getpwnam (name);
 552 #   endif
 553                   if (p != NULL)
 554                     home_dir = p->pw_dir;
 555                 }
 556             }
 557           if (home_dir == NULL || home_dir[0] == '\0')
 558             {
 559               if (flags & GLOB_TILDE_CHECK)
 560                 return GLOB_NOMATCH;
 561               else
 562                 home_dir = "~"; /* No luck.  */
 563             }
 564 #  endif /* WINDOWS32 */
 565 # endif
 566           /* Now construct the full directory.  */
 567           if (dirname[1] == '\0')
 568             dirname = home_dir;
 569           else
 570             {
 571               char *newp;
 572               size_t home_len = strlen (home_dir);
 573               newp = __alloca (home_len + dirlen);
 574               mempcpy (mempcpy (newp, home_dir, home_len),
 575                        &dirname[1], dirlen);
 576               dirname = newp;
 577             }
 578         }
 579 # if !defined _AMIGA && !defined WINDOWS32
 580       else
 581         {
 582           char *end_name = strchr (dirname, '/');
 583           const char *user_name;
 584           const char *home_dir;
 585
 586           if (end_name == NULL)
 587             user_name = dirname + 1;
 588           else
 589             {
 590               char *newp;
 591               newp = __alloca (end_name - dirname);
 592               *((char *) mempcpy (newp, dirname + 1, end_name - dirname))
 593                 = '\0';
 594               user_name = newp;
 595             }
 596
 597           /* Look up specific user's home directory.  */
 598           {
 599             struct passwd *p;
 600 #  if defined HAVE_GETPWNAM_R || defined _LIBC
 601             long int buflen = GETPW_R_SIZE_MAX ();
 602             char *pwtmpbuf;
 603             struct passwd pwbuf;
 604             int save = errno;
 605
 606 #   ifndef _LIBC
 607             if (buflen == -1)
 608               /* `sysconf' does not support _SC_GETPW_R_SIZE_MAX.  Try a
 609                  moderate value.  */
 610               buflen = 1024;
 611 #   endif
 612             pwtmpbuf = __alloca (buflen);
 613
 614             while (getpwnam_r (user_name, &pwbuf, pwtmpbuf, buflen, &p) != 0)
 615               {
 616                 if (errno != ERANGE)
 617                   {
 618                     p = NULL;
 619                     break;
 620                   }
 621 #   ifdef _LIBC
 622                 pwtmpbuf = extend_alloca (pwtmpbuf, buflen, 2 * buflen);
 623 #   else
 624                 buflen *= 2;
 625                 pwtmpbuf = __alloca (buflen);
 626 #   endif
 627                 __set_errno (save);
 628               }
 629 #  else
 630             p = getpwnam (user_name);
 631 #  endif
 632             if (p != NULL)
 633               home_dir = p->pw_dir;
 634             else
 635               home_dir = NULL;
 636           }
 637           /* If we found a home directory use this.  */
 638           if (home_dir != NULL)
 639             {
 640               char *newp;
 641               size_t home_len = strlen (home_dir);
 642               size_t rest_len = end_name == NULL ? 0 : strlen (end_name);
 643               newp = __alloca (home_len + rest_len + 1);
 644               *((char *) mempcpy (mempcpy (newp, home_dir, home_len),
 645                                   end_name, rest_len)) = '\0';
 646               dirname = newp;
 647             }
 648           else
 649             if (flags & GLOB_TILDE_CHECK)
 650               /* We have to regard it as an error if we cannot find the
 651                  home directory.  */
 652               return GLOB_NOMATCH;
 653         }
 654 # endif /* Not Amiga && not WINDOWS32.  */
 655     }
 656
 657   /* Now test whether we looked for "~" or "~NAME".  In this case we
 658      can give the answer now.  */
 659   if (filename == NULL)
 660     {
 661       struct stat st;
 662       struct_stat64 st64;
 663
 664       /* Return the directory if we don't check for error or if it exists.  */
 665       if ((flags & GLOB_NOCHECK)
 666           || (((flags & GLOB_ALTDIRFUNC)
 667                ? ((*pglob->gl_stat) (dirname, &st) == 0
 668                   && S_ISDIR (st.st_mode))
 669                : (__stat64 (dirname, &st64) == 0 && S_ISDIR (st64.st_mode)))))
 670         {
 671           int newcount = pglob->gl_pathc + pglob->gl_offs;
 672           char **new_gl_pathv;
 673
 674           new_gl_pathv
 675             = realloc (pglob->gl_pathv, (newcount + 1 + 1) * sizeof (char *));
 676           if (new_gl_pathv == NULL)
 677             {
 678             nospace:
 679               free (pglob->gl_pathv);
 680               pglob->gl_pathv = NULL;
 681               pglob->gl_pathc = 0;
 682               return GLOB_NOSPACE;
 683             }
 684           pglob->gl_pathv = new_gl_pathv;
 685
 686            pglob->gl_pathv[newcount] = strdup (dirname);
 687           if (pglob->gl_pathv[newcount] == NULL)
 688             goto nospace;
 689           pglob->gl_pathv[++newcount] = NULL;
 690           ++pglob->gl_pathc;
 691           pglob->gl_flags = flags;
 692
 693           return 0;
 694         }
 695
 696       /* Not found.  */
 697       return GLOB_NOMATCH;
 698     }
 699
 700   if (__glob_pattern_p (dirname, !(flags & GLOB_NOESCAPE)))
 701     {
 702       /* The directory name contains metacharacters, so we
 703          have to glob for the directory, and then glob for
 704          the pattern in each directory found.  */
 705       glob_t dirs;
 706       size_t i;
 707
 708       if ((flags & GLOB_ALTDIRFUNC) != 0)
 709         {
 710           /* Use the alternative access functions also in the recursive
 711              call.  */
 712           dirs.gl_opendir = pglob->gl_opendir;
 713           dirs.gl_readdir = pglob->gl_readdir;
 714           dirs.gl_closedir = pglob->gl_closedir;
 715           dirs.gl_stat = pglob->gl_stat;
 716           dirs.gl_lstat = pglob->gl_lstat;
 717         }
 718
 719       status = glob (dirname,
 720                      ((flags & (GLOB_ERR | GLOB_NOCHECK | GLOB_NOESCAPE
 721                                 | GLOB_ALTDIRFUNC))
 722                       | GLOB_NOSORT | GLOB_ONLYDIR),
 723                      errfunc, &dirs);
 724       if (status != 0)
 725         return status;
 726
 727       /* We have successfully globbed the preceding directory name.
 728          For each name we found, call glob_in_dir on it and FILENAME,
 729          appending the results to PGLOB.  */
 730       for (i = 0; i < dirs.gl_pathc; ++i)
 731         {
 732           int old_pathc;
 733
 734 #ifdef  SHELL
 735           {
 736             /* Make globbing interruptible in the bash shell. */
 737             extern int interrupt_state;
 738
 739             if (interrupt_state)
 740               {
 741                 globfree (&dirs);
 742                 return GLOB_ABORTED;
 743               }
 744           }
 745 #endif /* SHELL.  */
 746
 747           old_pathc = pglob->gl_pathc;
 748           status = glob_in_dir (filename, dirs.gl_pathv[i],
 749                                 ((flags | GLOB_APPEND)
 750                                  & ~(GLOB_NOCHECK | GLOB_NOMAGIC)),
 751                                 errfunc, pglob);
 752           if (status == GLOB_NOMATCH)
 753             /* No matches in this directory.  Try the next.  */
 754             continue;
 755
 756           if (status != 0)
 757             {
 758               globfree (&dirs);
 759               globfree (pglob);
 760               pglob->gl_pathc = 0;
 761               return status;
 762             }
 763
 764           /* Stick the directory on the front of each name.  */
 765           if (prefix_array (dirs.gl_pathv[i],
 766                             &pglob->gl_pathv[old_pathc + pglob->gl_offs],
 767                             pglob->gl_pathc - old_pathc))
 768             {
 769               globfree (&dirs);
 770               globfree (pglob);
 771               pglob->gl_pathc = 0;
 772               return GLOB_NOSPACE;
 773             }
 774         }
 775
 776       flags |= GLOB_MAGCHAR;
 777
 778       /* We have ignored the GLOB_NOCHECK flag in the `glob_in_dir' calls.
 779          But if we have not found any matching entry and the GLOB_NOCHECK
 780          flag was set we must return the input pattern itself.  */
 781       if (pglob->gl_pathc + pglob->gl_offs == oldcount)
 782         {
 783           /* No matches.  */
 784           if (flags & GLOB_NOCHECK)
 785             {
 786               int newcount = pglob->gl_pathc + pglob->gl_offs;
 787               char **new_gl_pathv;
 788
 789               new_gl_pathv = realloc (pglob->gl_pathv,
 790                                       (newcount + 2) * sizeof (char *));
 791               if (new_gl_pathv == NULL)
 792                 {
 793                   globfree (&dirs);
 794                   return GLOB_NOSPACE;
 795                 }
 796               pglob->gl_pathv = new_gl_pathv;
 797
 798               pglob->gl_pathv[newcount] = strdup (pattern);
 799               if (pglob->gl_pathv[newcount] == NULL)
 800                 {
 801                   globfree (&dirs);
 802                   globfree (pglob);
 803                   pglob->gl_pathc = 0;
 804                   return GLOB_NOSPACE;
 805                 }
 806
 807               ++pglob->gl_pathc;
 808               ++newcount;
 809
 810               pglob->gl_pathv[newcount] = NULL;
 811               pglob->gl_flags = flags;
 812             }
 813           else
 814             {
 815               globfree (&dirs);
 816               return GLOB_NOMATCH;
 817             }
 818         }
 819
 820       globfree (&dirs);
 821     }
 822   else
 823     {
 824       int old_pathc = pglob->gl_pathc;
 825
 826       status = glob_in_dir (filename, dirname, flags, errfunc, pglob);
 827       if (status != 0)
 828         return status;
 829
 830       if (dirlen > 0)
 831         {
 832           /* Stick the directory on the front of each name.  */
 833           if (prefix_array (dirname,
 834                             &pglob->gl_pathv[old_pathc + pglob->gl_offs],
 835                             pglob->gl_pathc - old_pathc))
 836             {
 837               globfree (pglob);
 838               pglob->gl_pathc = 0;
 839               return GLOB_NOSPACE;
 840             }
 841         }
 842     }
 843
 844   if (!(flags & GLOB_NOSORT))
 845     {
 846       /* Sort the vector.  */
 847       qsort (&pglob->gl_pathv[oldcount],
 848              pglob->gl_pathc + pglob->gl_offs - oldcount,
 849              sizeof (char *), collated_compare);
 850     }
 851
 852   return 0;
 853 }
 854 #if defined _LIBC && !defined glob
 855 libc_hidden_def (glob)
 856 #endif
 857
 858
 859 #if !defined _LIBC || !defined GLOB_ONLY_P
 860
 861 /* Free storage allocated in PGLOB by a previous `glob' call.  */
 862 void
 863 globfree (pglob)
 864      register glob_t *pglob;
 865 {
 866   if (pglob->gl_pathv != NULL)
 867     {
 868       size_t i;
 869       for (i = 0; i < pglob->gl_pathc; ++i)
 870         if (pglob->gl_pathv[pglob->gl_offs + i] != NULL)
 871           free (pglob->gl_pathv[pglob->gl_offs + i]);
 872       free (pglob->gl_pathv);
 873       pglob->gl_pathv = NULL;
 874     }
 875 }
 876 #if defined _LIBC && !defined globfree
 877 libc_hidden_def (globfree)
 878 #endif
 879
 880
 881 /* Do a collated comparison of A and B.  */
 882 static int
 883 collated_compare (const void *a, const void *b)
 884 {
 885   char *const *ps1 = a; char *s1 = *ps1;
 886   char *const *ps2 = b; char *s2 = *ps2;
 887
 888   if (s1 == s2)
 889     return 0;
 890   if (s1 == NULL)
 891     return 1;
 892   if (s2 == NULL)
 893     return -1;
 894   return strcoll (s1, s2);
 895 }
 896
 897
 898 /* Prepend DIRNAME to each of N members of ARRAY, replacing ARRAY's
 899    elements in place.  Return nonzero if out of memory, zero if successful.
 900    A slash is inserted between DIRNAME and each elt of ARRAY,
 901    unless DIRNAME is just "/".  Each old element of ARRAY is freed.  */
 902 static int
 903 prefix_array (const char *dirname, char **array, size_t n)
 904 {
 905   register size_t i;
 906   size_t dirlen = strlen (dirname);
 907 #if defined __MSDOS__ || defined WINDOWS32
 908   int sep_char = '/';
 909 # define DIRSEP_CHAR sep_char
 910 #else
 911 # define DIRSEP_CHAR '/'
 912 #endif
 913
 914   if (dirlen == 1 && dirname[0] == '/')
 915     /* DIRNAME is just "/", so normal prepending would get us "//foo".
 916        We want "/foo" instead, so don't prepend any chars from DIRNAME.  */
 917     dirlen = 0;
 918 #if defined __MSDOS__ || defined WINDOWS32
 919   else if (dirlen > 1)
 920     {
 921       if (dirname[dirlen - 1] == '/' && dirname[dirlen - 2] == ':')
 922         /* DIRNAME is "d:/".  Don't prepend the slash from DIRNAME.  */
 923         --dirlen;
 924       else if (dirname[dirlen - 1] == ':')
 925         {
 926           /* DIRNAME is "d:".  Use `:' instead of `/'.  */
 927           --dirlen;
 928           sep_char = ':';
 929         }
 930     }
 931 #endif
 932
 933   for (i = 0; i < n; ++i)
 934     {
 935       size_t eltlen = strlen (array[i]) + 1;
 936       char *new = malloc (dirlen + 1 + eltlen);
 937       if (new == NULL)
 938         {
 939           while (i > 0)
 940             free (array[--i]);
 941           return 1;
 942         }
 943
 944       {
 945         char *endp = mempcpy (new, dirname, dirlen);
 946         *endp++ = DIRSEP_CHAR;
 947         mempcpy (endp, array[i], eltlen);
 948       }
 949       free (array[i]);
 950       array[i] = new;
 951     }
 952
 953   return 0;
 954 }
 955
 956
 957 /* We must not compile this function twice.  */
 958 #if !defined _LIBC || !defined NO_GLOB_PATTERN_P
 959 /* Return nonzero if PATTERN contains any metacharacters.
 960    Metacharacters can be quoted with backslashes if QUOTE is nonzero.  */
 961 int
 962 __glob_pattern_p (pattern, quote)
 963      const char *pattern;
 964      int quote;
 965 {
 966   register const char *p;
 967   int open = 0;
 968
 969   for (p = pattern; *p != '\0'; ++p)
 970     switch (*p)
 971       {
 972       case '?':
 973       case '*':
 974         return 1;
 975
 976       case '\\':
 977         if (quote && p[1] != '\0')
 978           ++p;
 979         break;
 980
 981       case '[':
 982         open = 1;
 983         break;
 984
 985       case ']':
 986         if (open)
 987           return 1;
 988         break;
 989       }
 990
 991   return 0;
 992 }
 993 # ifdef _LIBC
 994 weak_alias (__glob_pattern_p, glob_pattern_p)
 995 # endif
 996 #endif
 997
 998 #endif /* !GLOB_ONLY_P */
 999
1000
1001 /* We put this in a separate function mainly to allow the memory
1002    allocated with alloca to be recycled.  */
1003 #if !defined _LIBC || !defined GLOB_ONLY_P
1004 static bool
1005 is_dir_p (const char *dir, size_t dirlen, const char *fname,
1006           glob_t *pglob, int flags)
1007 {
1008   size_t fnamelen = strlen (fname);
1009   char *fullname = __alloca (dirlen + 1 + fnamelen + 1);
1010   struct stat st;
1011   struct_stat64 st64;
1012
1013   mempcpy (mempcpy (mempcpy (fullname, dir, dirlen), "/", 1),
1014            fname, fnamelen + 1);
1015
1016   return ((flags & GLOB_ALTDIRFUNC)
1017           ? (*pglob->gl_stat) (fullname, &st) == 0 && S_ISDIR (st.st_mode)
1018           : __stat64 (fullname, &st64) == 0 && S_ISDIR (st64.st_mode));
1019 }
1020 #endif
1021
1022
1023 /* Like `glob', but PATTERN is a final pathname component,
1024    and matches are searched for in DIRECTORY.
1025    The GLOB_NOSORT bit in FLAGS is ignored.  No sorting is ever done.
1026    The GLOB_APPEND flag is assumed to be set (always appends).  */
1027 static int
1028 glob_in_dir (const char *pattern, const char *directory, int flags,
1029              int (*errfunc) (const char *, int),
1030              glob_t *pglob)
1031 {
1032   size_t dirlen = strlen (directory);
1033   void *stream = NULL;
1034   struct globlink
1035     {
1036       struct globlink *next;
1037       char *name;
1038     };
1039   struct globlink *names = NULL;
1040   size_t nfound;
1041   int meta;
1042   int save;
1043
1044   meta = __glob_pattern_p (pattern, !(flags & GLOB_NOESCAPE));
1045   if (meta == 0 && (flags & (GLOB_NOCHECK|GLOB_NOMAGIC)))
1046     {
1047       /* We need not do any tests.  The PATTERN contains no meta
1048          characters and we must not return an error therefore the
1049          result will always contain exactly one name.  */
1050       flags |= GLOB_NOCHECK;
1051       nfound = 0;
1052     }
1053   else if (meta == 0 &&
1054            ((flags & GLOB_NOESCAPE) || strchr (pattern, '\\') == NULL))
1055     {
1056       /* Since we use the normal file functions we can also use stat()
1057          to verify the file is there.  */
1058       struct stat st;
1059       struct_stat64 st64;
1060       size_t patlen = strlen (pattern);
1061       char *fullname = __alloca (dirlen + 1 + patlen + 1);
1062
1063       mempcpy (mempcpy (mempcpy (fullname, directory, dirlen),
1064                         "/", 1),
1065                pattern, patlen + 1);
1066       if (((flags & GLOB_ALTDIRFUNC)
1067            ? (*pglob->gl_stat) (fullname, &st)
1068            : __stat64 (fullname, &st64)) == 0)
1069         /* We found this file to be existing.  Now tell the rest
1070            of the function to copy this name into the result.  */
1071         flags |= GLOB_NOCHECK;
1072
1073       nfound = 0;
1074     }
1075   else
1076     {
1077       if (pattern[0] == '\0')
1078         {
1079           /* This is a special case for matching directories like in
1080              "*a/".  */
1081           names = __alloca (sizeof (struct globlink));
1082           names->name = malloc (1);
1083           if (names->name == NULL)
1084             goto memory_error;
1085           names->name[0] = '\0';
1086           names->next = NULL;
1087           nfound = 1;
1088           meta = 0;
1089         }
1090       else
1091         {
1092           stream = ((flags & GLOB_ALTDIRFUNC)
1093                     ? (*pglob->gl_opendir) (directory)
1094                     : opendir (directory));
1095           if (stream == NULL)
1096             {
1097               if (errno != ENOTDIR
1098                   && ((errfunc != NULL && (*errfunc) (directory, errno))
1099                       || (flags & GLOB_ERR)))
1100                 return GLOB_ABORTED;
1101               nfound = 0;
1102               meta = 0;
1103             }
1104           else
1105             {
1106               int fnm_flags = ((!(flags & GLOB_PERIOD) ? FNM_PERIOD : 0)
1107                                | ((flags & GLOB_NOESCAPE) ? FNM_NOESCAPE : 0)
1108 #if defined _AMIGA || defined __VMS
1109                                | FNM_CASEFOLD
1110 #endif
1111                                );
1112               nfound = 0;
1113               flags |= GLOB_MAGCHAR;
1114
1115               while (1)
1116                 {
1117                   const char *name;
1118                   size_t len;
1119 #if defined _LIBC && !defined COMPILE_GLOB64
1120                   struct dirent64 *d;
1121                   union
1122                     {
1123                       struct dirent64 d64;
1124                       char room [offsetof (struct dirent64, d_name[0])
1125                                  + NAME_MAX + 1];
1126                     }
1127                   d64buf;
1128
1129                   if (flags & GLOB_ALTDIRFUNC)
1130                     {
1131                       struct dirent *d32 = (*pglob->gl_readdir) (stream);
1132                       if (d32 != NULL)
1133                         {
1134                           CONVERT_DIRENT_DIRENT64 (&d64buf.d64, d32);
1135                           d = &d64buf.d64;
1136                         }
1137                       else
1138                         d = NULL;
1139                     }
1140                   else
1141                     d = __readdir64 (stream);
1142 #else
1143                   struct dirent *d = ((flags & GLOB_ALTDIRFUNC)
1144                                       ? ((*pglob->gl_readdir) (stream))
1145                                       : __readdir (stream));
1146 #endif
1147                   if (d == NULL)
1148                     break;
1149                   if (! REAL_DIR_ENTRY (d))
1150                     continue;
1151
1152                   /* If we shall match only directories use the information
1153                      provided by the dirent call if possible.  */
1154                   if ((flags & GLOB_ONLYDIR) && !DIRENT_MIGHT_BE_DIR (d))
1155                     continue;
1156
1157                   name = d->d_name;
1158
1159                   if (fnmatch (pattern, name, fnm_flags) == 0)
1160                     {
1161                       /* ISDIR will often be incorrectly set to false
1162                          when not in GLOB_ONLYDIR || GLOB_MARK mode, but we
1163                          don't care.  It won't be used and we save the
1164                          expensive call to stat.  */
1165                       int need_dir_test =
1166                         (GLOB_MARK | (DIRENT_MIGHT_BE_SYMLINK (d)
1167                                       ? GLOB_ONLYDIR : 0));
1168                       bool isdir = (DIRENT_MUST_BE (d, DT_DIR)
1169                                     || ((flags & need_dir_test)
1170                                         && is_dir_p (directory, dirlen, name,
1171                                                      pglob, flags)));
1172
1173                       /* In GLOB_ONLYDIR mode, skip non-dirs.  */
1174                       if ((flags & GLOB_ONLYDIR) && !isdir)
1175                           continue;
1176
1177                         {
1178                           struct globlink *new =
1179                             __alloca (sizeof (struct globlink));
1180                           char *p;
1181                           len = _D_EXACT_NAMLEN (d);
1182                           new->name =
1183                             malloc (len + 1 + ((flags & GLOB_MARK) && isdir));
1184                           if (new->name == NULL)
1185                             goto memory_error;
1186                           p = mempcpy (new->name, name, len);
1187                           if ((flags & GLOB_MARK) && isdir)
1188                               *p++ = '/';
1189                           *p = '\0';
1190                           new->next = names;
1191                           names = new;
1192                           ++nfound;
1193                         }
1194                     }
1195                 }
1196             }
1197         }
1198     }
1199
1200   if (nfound == 0 && (flags & GLOB_NOCHECK))
1201     {
1202       size_t len = strlen (pattern);
1203       nfound = 1;
1204       names = __alloca (sizeof (struct globlink));
1205       names->next = NULL;
1206       names->name = malloc (len + 1);
1207       if (names->name == NULL)
1208         goto memory_error;
1209       *((char *) mempcpy (names->name, pattern, len)) = '\0';
1210     }
1211
1212   if (nfound != 0)
1213     {
1214       char **new_gl_pathv;
1215
1216       new_gl_pathv
1217         = realloc (pglob->gl_pathv,
1218                    (pglob->gl_pathc + pglob->gl_offs + nfound + 1)
1219                    * sizeof (char *));
1220       if (new_gl_pathv == NULL)
1221         goto memory_error;
1222       pglob->gl_pathv = new_gl_pathv;
1223
1224       for (; names != NULL; names = names->next)
1225         pglob->gl_pathv[pglob->gl_offs + pglob->gl_pathc++] = names->name;
1226       pglob->gl_pathv[pglob->gl_offs + pglob->gl_pathc] = NULL;
1227
1228       pglob->gl_flags = flags;
1229     }
1230
1231   save = errno;
1232   if (stream != NULL)
1233     {
1234       if (flags & GLOB_ALTDIRFUNC)
1235         (*pglob->gl_closedir) (stream);
1236       else
1237         closedir (stream);
1238     }
1239   __set_errno (save);
1240
1241   return nfound == 0 ? GLOB_NOMATCH : 0;
1242
1243  memory_error:
1244   {
1245     int save = errno;
1246     if (flags & GLOB_ALTDIRFUNC)
1247       (*pglob->gl_closedir) (stream);
1248     else
1249       closedir (stream);
1250     __set_errno (save);
1251   }
1252   while (names != NULL)
1253     {
1254       if (names->name != NULL)
1255         free (names->name);
1256       names = names->next;
1257     }
1258   return GLOB_NOSPACE;
1259 }