lib/glob.c

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