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