Formerly ../hurd/hurdkill.c.~5~
[kopensolaris-gnu/glibc.git] / posix / glob.c
1 /* Copyright (C) 1991, 1992, 1993 Free Software Foundation, Inc.
2
3 This library is free software; you can redistribute it and/or
4 modify it under the terms of the GNU Library General Public License as
5 published by the Free Software Foundation; either version 2 of the
6 License, or (at your option) any later version.
7
8 This library is distributed in the hope that it will be useful,
9 but WITHOUT ANY WARRANTY; without even the implied warranty of
10 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
11 Library General Public License for more details.
12
13 You should have received a copy of the GNU Library General Public
14 License along with this library; see the file COPYING.LIB.  If
15 not, write to the Free Software Foundation, Inc., 675 Mass Ave,
16 Cambridge, MA 02139, USA.  */
17
18 /* AIX requires this to be the first thing in the file.  */
19 #if defined (_AIX) && !defined (__GNUC__)
20  #pragma alloca
21 #endif
22
23 #ifdef  HAVE_CONFIG_H
24 #include <config.h>
25 #endif
26
27 #include <errno.h>
28 #include <sys/types.h>
29
30
31 /* Comment out all this code if we are using the GNU C Library, and are not
32    actually compiling the library itself.  This code is part of the GNU C
33    Library, but also included in many other GNU distributions.  Compiling
34    and linking in this code is a waste when using the GNU C library
35    (especially if it is a shared library).  Rather than having every GNU
36    program understand `configure --with-gnu-libc' and omit the object files,
37    it is simpler to just do this in the source for each such file.  */
38
39 #if defined (_LIBC) || !defined (__GNU_LIBRARY__)
40
41
42 #ifdef  STDC_HEADERS
43 #include <stddef.h>
44 #endif
45
46 #ifdef  HAVE_UNISTD_H
47 #include <unistd.h>
48 #ifndef POSIX
49 #ifdef  _POSIX_VERSION
50 #define POSIX
51 #endif
52 #endif
53 #endif
54
55 #if !defined(__GNU_LIBRARY__) && !defined(STDC_HEADERS)
56 extern int errno;
57 #endif
58
59 #ifndef NULL
60 #define NULL    0
61 #endif
62
63 #if     defined (POSIX) || defined (DIRENT) || defined (__GNU_LIBRARY__)
64 #include <dirent.h>
65 #ifndef __GNU_LIBRARY__
66 #define D_NAMLEN(d) strlen((d)->d_name)
67 #else   /* GNU C library.  */
68 #define D_NAMLEN(d) ((d)->d_namlen)
69 #endif  /* Not GNU C library.  */
70 #else   /* Not POSIX or DIRENT.  */
71 #define direct dirent
72 #define D_NAMLEN(d) ((d)->d_namlen)
73 #ifdef  SYSNDIR
74 #include <sys/ndir.h>
75 #endif  /* SYSNDIR */
76 #ifdef  SYSDIR
77 #include <sys/dir.h>
78 #endif  /* SYSDIR */
79 #ifdef NDIR
80 #include <ndir.h>
81 #endif  /* NDIR */
82 #endif  /* POSIX or DIRENT or __GNU_LIBRARY__.  */
83
84 #if defined (POSIX) && !defined (__GNU_LIBRARY__)
85 /* Posix does not require that the d_ino field be present, and some
86    systems do not provide it. */
87 #define REAL_DIR_ENTRY(dp) 1
88 #else
89 #define REAL_DIR_ENTRY(dp) (dp->d_ino != 0)
90 #endif /* POSIX */
91
92 #if     (defined (STDC_HEADERS) || defined (__GNU_LIBRARY__))
93 #include <stdlib.h>
94 #include <string.h>
95 #define ANSI_STRING
96 #else   /* No standard headers.  */
97
98 #ifdef HAVE_STRING_H
99 #include <string.h>
100 #define ANSI_STRING
101 #else
102 #include <strings.h>
103 #endif
104 #ifdef  HAVE_MEMORY_H
105 #include <memory.h>
106 #endif
107
108 extern char *malloc (), *realloc ();
109 extern void free ();
110
111 extern void qsort ();
112 extern void abort (), exit ();
113
114 #endif  /* Standard headers.  */
115
116 #ifndef ANSI_STRING
117
118 #ifndef bzero
119 extern void bzero ();
120 #endif
121 #ifndef bcopy
122 extern void bcopy ();
123 #endif
124
125 #define memcpy(d, s, n) bcopy ((s), (d), (n))
126 #define strrchr rindex
127 /* memset is only used for zero here, but let's be paranoid.  */
128 #define memset(s, better_be_zero, n) \
129   ((void) ((better_be_zero) == 0 ? (bzero((s), (n)), 0) : (abort(), 0)))
130 #endif  /* Not ANSI_STRING.  */
131
132 #ifndef HAVE_STRCOLL
133 #define strcoll strcmp
134 #endif
135
136
137 #ifndef __GNU_LIBRARY__
138 #ifdef  __GNUC__
139 __inline
140 #endif
141 static char *
142 my_realloc (p, n)
143      char *p;
144      unsigned int n;
145 {
146   /* These casts are the for sake of the broken Ultrix compiler,
147      which warns of illegal pointer combinations otherwise.  */
148   if (p == NULL)
149     return (char *) malloc (n);
150   return (char *) realloc (p, n);
151 }
152 #define realloc my_realloc
153 #endif
154
155
156 #if     !defined(__alloca) && !defined(__GNU_LIBRARY__)
157
158 #ifdef  __GNUC__
159 #undef  alloca
160 #define alloca(n)       __builtin_alloca (n)
161 #else   /* Not GCC.  */
162 #if     defined (sparc) || defined (HAVE_ALLOCA_H)
163 #include <alloca.h>
164 #else   /* Not sparc or HAVE_ALLOCA_H.  */
165 #ifndef _AIX
166 extern char *alloca ();
167 #endif  /* Not _AIX.  */
168 #endif  /* sparc or HAVE_ALLOCA_H.  */
169 #endif  /* GCC.  */
170
171 #define __alloca        alloca
172
173 #endif
174
175 #ifndef STDC_HEADERS
176 #undef  size_t
177 #define size_t  unsigned int
178 #endif
179
180 /* Some system header files erroneously define these.
181    We want our own definitions from <fnmatch.h> to take precedence.  */
182 #undef  FNM_PATHNAME
183 #undef  FNM_NOESCAPE
184 #undef  FNM_PERIOD
185 #include <fnmatch.h>
186
187 /* Some system header files erroneously define these.
188    We want our own definitions from <glob.h> to take precedence.  */
189 #undef  GLOB_ERR
190 #undef  GLOB_MARK
191 #undef  GLOB_NOSORT
192 #undef  GLOB_DOOFFS
193 #undef  GLOB_NOCHECK
194 #undef  GLOB_APPEND
195 #undef  GLOB_NOESCAPE
196 #undef  GLOB_PERIOD
197 #include <glob.h>
198 \f
199 __ptr_t (*__glob_opendir_hook) __P ((const char *directory));
200 const char *(*__glob_readdir_hook) __P ((__ptr_t stream));
201 void (*__glob_closedir_hook) __P ((__ptr_t stream));
202
203 static int glob_pattern_p __P ((const char *pattern, int quote));
204 static int glob_in_dir __P ((const char *pattern, const char *directory,
205                              int flags,
206                              int (*errfunc) __P ((const char *, int)),
207                              glob_t *pglob));
208 static int prefix_array __P ((const char *prefix, char **array, size_t n));
209 static int collated_compare __P ((const __ptr_t, const __ptr_t));
210
211 /* Do glob searching for PATTERN, placing results in PGLOB.
212    The bits defined above may be set in FLAGS.
213    If a directory cannot be opened or read and ERRFUNC is not nil,
214    it is called with the pathname that caused the error, and the
215    `errno' value from the failing call; if it returns non-zero
216    `glob' returns GLOB_ABEND; if it returns zero, the error is ignored.
217    If memory cannot be allocated for PGLOB, GLOB_NOSPACE is returned.
218    Otherwise, `glob' returns zero.  */
219 int
220 glob (pattern, flags, errfunc, pglob)
221      const char *pattern;
222      int flags;
223      int (*errfunc) __P ((const char *, int));
224      glob_t *pglob;
225 {
226   const char *filename;
227   char *dirname;
228   size_t dirlen;
229   int status;
230   int oldcount;
231
232   if (pattern == NULL || pglob == NULL || (flags & ~__GLOB_FLAGS) != 0)
233     {
234       errno = EINVAL;
235       return -1;
236     }
237
238   /* Find the filename.  */
239   filename = strrchr (pattern, '/');
240   if (filename == NULL)
241     {
242       filename = pattern;
243       dirname = (char *) ".";
244       dirlen = 0;
245     }
246   else if (filename == pattern)
247     {
248       /* "/pattern".  */
249       dirname = (char *) "/";
250       dirlen = 1;
251       ++filename;
252     }
253   else
254     {
255       dirlen = filename - pattern;
256       dirname = (char *) __alloca (dirlen + 1);
257       memcpy (dirname, pattern, dirlen);
258       dirname[dirlen] = '\0';
259       ++filename;
260     }
261
262   if (filename[0] == '\0' && dirlen > 1)
263     /* "pattern/".  Expand "pattern", appending slashes.  */
264     {
265       int ret = glob (dirname, flags | GLOB_MARK, errfunc, pglob);
266       if (ret == 0)
267         pglob->gl_flags = (pglob->gl_flags & ~GLOB_MARK) | (flags & GLOB_MARK);
268       return ret;
269     }
270
271   if (!(flags & GLOB_APPEND))
272     {
273       pglob->gl_pathc = 0;
274       pglob->gl_pathv = NULL;
275     }
276
277   oldcount = pglob->gl_pathc;
278
279   if (glob_pattern_p (dirname, !(flags & GLOB_NOESCAPE)))
280     {
281       /* The directory name contains metacharacters, so we
282          have to glob for the directory, and then glob for
283          the pattern in each directory found.  */
284       glob_t dirs;
285       register int i;
286
287       status = glob (dirname,
288                      ((flags & (GLOB_ERR | GLOB_NOCHECK | GLOB_NOESCAPE)) |
289                       GLOB_NOSORT),
290                      errfunc, &dirs);
291       if (status != 0)
292         return status;
293
294       /* We have successfully globbed the preceding directory name.
295          For each name we found, call glob_in_dir on it and FILENAME,
296          appending the results to PGLOB.  */
297       for (i = 0; i < dirs.gl_pathc; ++i)
298         {
299           int oldcount;
300
301 #ifdef  SHELL
302           {
303             /* Make globbing interruptible in the bash shell. */
304             extern int interrupt_state;
305
306             if (interrupt_state)
307               {
308                 globfree (&dirs);
309                 globfree (&files);
310                 return GLOB_ABEND;
311               }
312           }
313 #endif /* SHELL.  */
314
315           oldcount = pglob->gl_pathc;
316           status = glob_in_dir (filename, dirs.gl_pathv[i],
317                                 (flags | GLOB_APPEND) & ~GLOB_NOCHECK,
318                                 errfunc, pglob);
319           if (status == GLOB_NOMATCH)
320             /* No matches in this directory.  Try the next.  */
321             continue;
322
323           if (status != 0)
324             {
325               globfree (&dirs);
326               globfree (pglob);
327               return status;
328             }
329
330           /* Stick the directory on the front of each name.  */
331           if (prefix_array (dirs.gl_pathv[i],
332                             &pglob->gl_pathv[oldcount],
333                             pglob->gl_pathc - oldcount))
334             {
335               globfree (&dirs);
336               globfree (pglob);
337               return GLOB_NOSPACE;
338             }
339         }
340
341       flags |= GLOB_MAGCHAR;
342
343       if (pglob->gl_pathc == oldcount)
344         /* No matches.  */
345         if (flags & GLOB_NOCHECK)
346           {
347             const size_t len = strlen (pattern) + 1;
348             char *patcopy = (char *) malloc (len);
349             if (patcopy == NULL)
350               return GLOB_NOSPACE;
351             memcpy (patcopy, pattern, len);
352
353             pglob->gl_pathv
354               = (char **) realloc (pglob->gl_pathv,
355                                    (pglob->gl_pathc +
356                                     ((flags & GLOB_DOOFFS) ?
357                                      pglob->gl_offs : 0) +
358                                     1 + 1) *
359                                    sizeof (char *));
360             if (pglob->gl_pathv == NULL)
361               {
362                 free (patcopy);
363                 return GLOB_NOSPACE;
364               }
365
366             if (flags & GLOB_DOOFFS)
367               while (pglob->gl_pathc < pglob->gl_offs)
368                 pglob->gl_pathv[pglob->gl_pathc++] = NULL;
369
370             pglob->gl_pathv[pglob->gl_pathc++] = patcopy;
371             pglob->gl_pathv[pglob->gl_pathc] = NULL;
372             pglob->gl_flags = flags;
373           }
374         else
375           return GLOB_NOMATCH;
376     }
377   else
378     {
379       status = glob_in_dir (filename, dirname, flags, errfunc, pglob);
380       if (status != 0)
381         return status;
382
383       if (dirlen > 0)
384         {
385           /* Stick the directory on the front of each name.  */
386           if (prefix_array (dirname,
387                             &pglob->gl_pathv[oldcount],
388                             pglob->gl_pathc - oldcount))
389             {
390               globfree (pglob);
391               return GLOB_NOSPACE;
392             }
393         }
394     }
395
396   if (!(flags & GLOB_NOSORT))
397     /* Sort the vector.  */
398     qsort ((__ptr_t) & pglob->gl_pathv[oldcount],
399            pglob->gl_pathc - oldcount,
400            sizeof (char *), collated_compare);
401
402   return 0;
403 }
404
405
406 /* Free storage allocated in PGLOB by a previous `glob' call.  */
407 void
408 globfree (pglob)
409      register glob_t *pglob;
410 {
411   if (pglob->gl_pathv != NULL)
412     {
413       register int i;
414       for (i = 0; i < pglob->gl_pathc; ++i)
415         if (pglob->gl_pathv[i] != NULL)
416           free ((__ptr_t) pglob->gl_pathv[i]);
417       free ((__ptr_t) pglob->gl_pathv);
418     }
419 }
420
421
422 /* Do a collated comparison of A and B.  */
423 static int
424 collated_compare (a, b)
425      const __ptr_t a;
426      const __ptr_t b;
427 {
428   const char *const s1 = *(const char *const * const) a;
429   const char *const s2 = *(const char *const * const) b;
430
431   if (s1 == s2)
432     return 0;
433   if (s1 == NULL)
434     return 1;
435   if (s2 == NULL)
436     return -1;
437   return strcoll (s1, s2);
438 }
439
440
441 /* Prepend DIRNAME to each of N members of ARRAY, replacing ARRAY's
442    elements in place.  Return nonzero if out of memory, zero if successful.
443    A slash is inserted between DIRNAME and each elt of ARRAY,
444    unless DIRNAME is just "/".  Each old element of ARRAY is freed.  */
445 static int
446 prefix_array (dirname, array, n)
447      const char *dirname;
448      char **array;
449      const size_t n;
450 {
451   register size_t i;
452   size_t dirlen = strlen (dirname);
453
454   if (dirlen == 1 && dirname[0] == '/')
455     /* DIRNAME is just "/", so normal prepending would get us "//foo".
456        We want "/foo" instead, so don't prepend any chars from DIRNAME.  */
457     dirlen = 0;
458
459   for (i = 0; i < n; ++i)
460     {
461       const size_t eltlen = strlen (array[i]) + 1;
462       char *new = (char *) malloc (dirlen + 1 + eltlen);
463       if (new == NULL)
464         {
465           while (i > 0)
466             free ((__ptr_t) array[--i]);
467           return 1;
468         }
469
470       memcpy (new, dirname, dirlen);
471       new[dirlen] = '/';
472       memcpy (&new[dirlen + 1], array[i], eltlen);
473       free ((__ptr_t) array[i]);
474       array[i] = new;
475     }
476
477   return 0;
478 }
479
480
481 /* Return nonzero if PATTERN contains any metacharacters.
482    Metacharacters can be quoted with backslashes if QUOTE is nonzero.  */
483 static int
484 glob_pattern_p (pattern, quote)
485      const char *pattern;
486      const int quote;
487 {
488   register const char *p;
489   int open = 0;
490
491   for (p = pattern; *p != '\0'; ++p)
492     switch (*p)
493       {
494       case '?':
495       case '*':
496         return 1;
497
498       case '\\':
499         if (quote)
500           ++p;
501         break;
502
503       case '[':
504         open = 1;
505         break;
506
507       case ']':
508         if (open)
509           return 1;
510         break;
511       }
512
513   return 0;
514 }
515
516
517 /* Like `glob', but PATTERN is a final pathname component,
518    and matches are searched for in DIRECTORY.
519    The GLOB_NOSORT bit in FLAGS is ignored.  No sorting is ever done.
520    The GLOB_APPEND flag is assumed to be set (always appends).  */
521 static int
522 glob_in_dir (pattern, directory, flags, errfunc, pglob)
523      const char *pattern;
524      const char *directory;
525      int flags;
526      int (*errfunc) __P ((const char *, int));
527      glob_t *pglob;
528 {
529   __ptr_t stream;
530
531   struct globlink
532     {
533       struct globlink *next;
534       char *name;
535     };
536   struct globlink *names = NULL;
537   size_t nfound = 0;
538
539   if (!glob_pattern_p (pattern, !(flags & GLOB_NOESCAPE)))
540     {
541       stream = NULL;
542       flags |= GLOB_NOCHECK;
543     }
544   else
545     {
546       flags |= GLOB_MAGCHAR;
547
548       stream = (__glob_opendir_hook ? (*__glob_opendir_hook) (directory)
549                 : (__ptr_t) opendir (directory));
550       if (stream == NULL)
551         {
552           if ((errfunc != NULL && (*errfunc) (directory, errno)) ||
553               (flags & GLOB_ERR))
554             return GLOB_ABEND;
555         }
556       else
557         while (1)
558           {
559             const char *name;
560             size_t len;
561
562             if (__glob_readdir_hook)
563               {
564                 name = (*__glob_readdir_hook) (stream);
565                 if (name == NULL)
566                   break;
567                 len = 0;
568               }
569             else
570               {
571                 struct dirent *d = readdir ((DIR *) stream);
572                 if (d == NULL)
573                   break;
574                 if (! REAL_DIR_ENTRY (d))
575                   continue;
576                 name = d->d_name;
577 #ifdef  HAVE_D_NAMLEN
578                 len = d->d_namlen;
579 #else
580                 len = 0;
581 #endif
582               }
583                 
584             if (fnmatch (pattern, name,
585                          (!(flags & GLOB_PERIOD) ? FNM_PERIOD : 0) |
586                          ((flags & GLOB_NOESCAPE) ? FNM_NOESCAPE : 0)) == 0)
587               {
588                 struct globlink *new
589                   = (struct globlink *) __alloca (sizeof (struct globlink));
590                 if (len == 0)
591                   len = strlen (name);
592                 new->name
593                   = (char *) malloc (len + ((flags & GLOB_MARK) ? 1 : 0) + 1);
594                 if (new->name == NULL)
595                   goto memory_error;
596                 memcpy ((__ptr_t) new->name, name, len);
597                 if (flags & GLOB_MARK)
598                   new->name[len++] = '/';
599                 new->name[len] = '\0';
600                 new->next = names;
601                 names = new;
602                 ++nfound;
603               }
604           }
605     }
606
607   if (nfound == 0 && (flags & GLOB_NOCHECK))
608     {
609       size_t len = strlen (pattern);
610       nfound = 1;
611       names = (struct globlink *) __alloca (sizeof (struct globlink));
612       names->next = NULL;
613       names->name = (char *) malloc (len + ((flags & GLOB_MARK) ? 1 : 0) + 1);
614       if (names->name == NULL)
615         goto memory_error;
616       memcpy (names->name, pattern, len);
617       if (flags & GLOB_MARK)
618         names->name[len++] = '/';
619       names->name[len] = '\0';
620     }
621
622   pglob->gl_pathv
623     = (char **) realloc (pglob->gl_pathv,
624                          (pglob->gl_pathc +
625                           ((flags & GLOB_DOOFFS) ? pglob->gl_offs : 0) +
626                           nfound + 1) *
627                          sizeof (char *));
628   if (pglob->gl_pathv == NULL)
629     goto memory_error;
630
631   if (flags & GLOB_DOOFFS)
632     while (pglob->gl_pathc < pglob->gl_offs)
633       pglob->gl_pathv[pglob->gl_pathc++] = NULL;
634
635   for (; names != NULL; names = names->next)
636     pglob->gl_pathv[pglob->gl_pathc++] = names->name;
637   pglob->gl_pathv[pglob->gl_pathc] = NULL;
638
639   pglob->gl_flags = flags;
640
641   if (stream != NULL)
642     {
643       int save = errno;
644       if (__glob_closedir_hook)
645         (*__glob_closedir_hook) (stream);
646       else
647         (void) closedir ((DIR *) stream);
648       errno = save;
649     }
650   return nfound == 0 ? GLOB_NOMATCH : 0;
651
652  memory_error:
653   {
654     int save = errno;
655     if (__glob_closedir_hook)
656       (*__glob_closedir_hook) (stream);
657     else
658       (void) closedir ((DIR *) stream);
659     errno = save;
660   }
661   while (names != NULL)
662     {
663       if (names->name != NULL)
664         free ((__ptr_t) names->name);
665       names = names->next;
666     }
667   return GLOB_NOSPACE;
668 }
669
670 #endif  /* _LIBC or not __GNU_LIBRARY__.  */