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