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