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