lib/glob.c

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