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