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