1/* Copyright (C) 1991,92,93,94,95,96,97,98,99 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 not,
15   write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
16   Boston, MA 02111-1307, 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/* Enable GNU extensions in glob.h.  */
28#ifndef _GNU_SOURCE
29# define _GNU_SOURCE	1
30#endif
31
32#include <errno.h>
33#include <sys/types.h>
34#include <sys/stat.h>
35
36/* Outcomment the following line for production quality code.  */
37/* #define NDEBUG 1 */
38#include <assert.h>
39
40#include <stdio.h>		/* Needed on stupid SunOS for assert.  */
41
42
43/* Comment out all this code if we are using the GNU C Library, and are not
44   actually compiling the library itself.  This code is part of the GNU C
45   Library, but also included in many other GNU distributions.  Compiling
46   and linking in this code is a waste when using the GNU C library
47   (especially if it is a shared library).  Rather than having every GNU
48   program understand `configure --with-gnu-libc' and omit the object files,
49   it is simpler to just do this in the source for each such file.  */
50
51#define GLOB_INTERFACE_VERSION 1
52#if !defined _LIBC && defined __GNU_LIBRARY__ && __GNU_LIBRARY__ > 1
53# include <gnu-versions.h>
54# if _GNU_GLOB_INTERFACE_VERSION == GLOB_INTERFACE_VERSION
55#  define ELIDE_CODE
56# endif
57#endif
58
59#ifndef ELIDE_CODE
60
61#if defined STDC_HEADERS || defined __GNU_LIBRARY__
62# include <stddef.h>
63#endif
64
65#if defined HAVE_UNISTD_H || defined _LIBC
66# include <unistd.h>
67# ifndef POSIX
68#  ifdef _POSIX_VERSION
69#   define POSIX
70#  endif
71# endif
72#endif
73
74#if !defined _AMIGA && !defined VMS && !defined WINDOWS32
75# include <pwd.h>
76#endif
77
78#if !defined __GNU_LIBRARY__ && !defined STDC_HEADERS
79extern int errno;
80#endif
81#ifndef __set_errno
82# define __set_errno(val) errno = (val)
83#endif
84
85#ifndef	NULL
86# define NULL	0
87#endif
88
89
90#if defined HAVE_DIRENT_H || defined __GNU_LIBRARY__
91# include <dirent.h>
92# define NAMLEN(dirent) strlen((dirent)->d_name)
93#else
94# define dirent direct
95# define NAMLEN(dirent) (dirent)->d_namlen
96# ifdef HAVE_SYS_NDIR_H
97#  include <sys/ndir.h>
98# endif
99# ifdef HAVE_SYS_DIR_H
100#  include <sys/dir.h>
101# endif
102# ifdef HAVE_NDIR_H
103#  include <ndir.h>
104# endif
105# ifdef HAVE_VMSDIR_H
106#  include "vmsdir.h"
107# endif /* HAVE_VMSDIR_H */
108#endif
109
110
111/* In GNU systems, <dirent.h> defines this macro for us.  */
112#ifdef _D_NAMLEN
113# undef NAMLEN
114# define NAMLEN(d) _D_NAMLEN(d)
115#endif
116
117/* When used in the GNU libc the symbol _DIRENT_HAVE_D_TYPE is available
118   if the `d_type' member for `struct dirent' is available.  */
119#ifdef _DIRENT_HAVE_D_TYPE
120# define HAVE_D_TYPE	1
121#endif
122
123
124#if (defined POSIX || defined WINDOWS32) && !defined __GNU_LIBRARY__
125/* Posix does not require that the d_ino field be present, and some
126   systems do not provide it. */
127# define REAL_DIR_ENTRY(dp) 1
128#else
129# define REAL_DIR_ENTRY(dp) (dp->d_ino != 0)
130#endif /* POSIX */
131
132#if defined STDC_HEADERS || defined __GNU_LIBRARY__
133# include <stdlib.h>
134# include <string.h>
135# define	ANSI_STRING
136#else	/* No standard headers.  */
137
138extern char *getenv ();
139
140# ifdef HAVE_STRING_H
141#  include <string.h>
142#  define ANSI_STRING
143# else
144#  include <strings.h>
145# endif
146# ifdef	HAVE_MEMORY_H
147#  include <memory.h>
148# endif
149
150extern char *malloc (), *realloc ();
151extern void free ();
152
153extern void qsort ();
154extern void abort (), exit ();
155
156#endif	/* Standard headers.  */
157
158#ifndef	ANSI_STRING
159
160# ifndef bzero
161extern void bzero ();
162# endif
163# ifndef bcopy
164extern void bcopy ();
165# endif
166
167# define memcpy(d, s, n)	bcopy ((s), (d), (n))
168# define strrchr	rindex
169/* memset is only used for zero here, but let's be paranoid.  */
170# define memset(s, better_be_zero, n) \
171  ((void) ((better_be_zero) == 0 ? (bzero((s), (n)), 0) : (abort(), 0)))
172#endif	/* Not ANSI_STRING.  */
173
174#if !defined HAVE_STRCOLL && !defined _LIBC
175# define strcoll	strcmp
176#endif
177
178#if !defined HAVE_MEMPCPY && __GLIBC__ - 0 == 2 && __GLIBC_MINOR__ >= 1
179# define HAVE_MEMPCPY	1
180# undef  mempcpy
181# define mempcpy(Dest, Src, Len) __mempcpy (Dest, Src, Len)
182#endif
183
184#ifndef	__GNU_LIBRARY__
185# ifdef	__GNUC__
186__inline
187# endif
188# ifndef __SASC
189#  ifdef WINDOWS32
190static void *
191#  else
192static char *
193# endif
194my_realloc (p, n)
195     char *p;
196     unsigned int n;
197{
198  /* These casts are the for sake of the broken Ultrix compiler,
199     which warns of illegal pointer combinations otherwise.  */
200  if (p == NULL)
201    return (char *) malloc (n);
202  return (char *) realloc (p, n);
203}
204# define	realloc	my_realloc
205# endif /* __SASC */
206#endif /* __GNU_LIBRARY__ */
207
208
209#if !defined __alloca && !defined __GNU_LIBRARY__
210
211# ifdef	__GNUC__
212#  undef alloca
213#  define alloca(n)	__builtin_alloca (n)
214# else	/* Not GCC.  */
215#  ifdef HAVE_ALLOCA_H
216#   include <alloca.h>
217#  else	/* Not HAVE_ALLOCA_H.  */
218#   ifndef _AIX
219#    ifdef WINDOWS32
220#     include <malloc.h>
221#    else
222extern char *alloca ();
223#    endif /* WINDOWS32 */
224#   endif /* Not _AIX.  */
225#  endif /* sparc or HAVE_ALLOCA_H.  */
226# endif	/* GCC.  */
227
228# define __alloca	alloca
229
230#endif
231
232#ifndef __GNU_LIBRARY__
233# define __stat stat
234# ifdef STAT_MACROS_BROKEN
235#  undef S_ISDIR
236# endif
237# ifndef S_ISDIR
238#  define S_ISDIR(mode) (((mode) & S_IFMT) == S_IFDIR)
239# endif
240#endif
241
242#ifdef _LIBC
243# undef strdup
244# define strdup(str) __strdup (str)
245# define sysconf(id) __sysconf (id)
246# define closedir(dir) __closedir (dir)
247# define opendir(name) __opendir (name)
248# define readdir(str) __readdir (str)
249# define getpwnam_r(name, bufp, buf, len, res) \
250   __getpwnam_r (name, bufp, buf, len, res)
251# ifndef __stat
252#  define __stat(fname, buf) __xstat (_STAT_VER, fname, buf)
253# endif
254#endif
255
256#if !(defined STDC_HEADERS || defined __GNU_LIBRARY__)
257# undef	size_t
258# define size_t	unsigned int
259#endif
260
261/* Some system header files erroneously define these.
262   We want our own definitions from <fnmatch.h> to take precedence.  */
263#ifndef __GNU_LIBRARY__
264# undef	FNM_PATHNAME
265# undef	FNM_NOESCAPE
266# undef	FNM_PERIOD
267#endif
268#include <fnmatch.h>
269
270/* Some system header files erroneously define these.
271   We want our own definitions from <glob.h> to take precedence.  */
272#ifndef __GNU_LIBRARY__
273# undef	GLOB_ERR
274# undef	GLOB_MARK
275# undef	GLOB_NOSORT
276# undef	GLOB_DOOFFS
277# undef	GLOB_NOCHECK
278# undef	GLOB_APPEND
279# undef	GLOB_NOESCAPE
280# undef	GLOB_PERIOD
281#endif
282#include <glob.h>
283
284#ifdef HAVE_GETLOGIN_R
285extern int getlogin_r __P ((char *, size_t));
286#else
287extern char *getlogin __P ((void));
288#endif
289
290static
291#if __GNUC__ - 0 >= 2
292inline
293#endif
294const char *next_brace_sub __P ((const char *begin));
295static int glob_in_dir __P ((const char *pattern, const char *directory,
296			     int flags,
297			     int (*errfunc) (const char *, int),
298			     glob_t *pglob));
299static int prefix_array __P ((const char *prefix, char **array, size_t n));
300static int collated_compare __P ((const __ptr_t, const __ptr_t));
301
302#ifdef VMS
303/* these compilers like prototypes */
304#if !defined _LIBC || !defined NO_GLOB_PATTERN_P
305int __glob_pattern_p (const char *pattern, int quote);
306#endif
307#endif
308
309/* Find the end of the sub-pattern in a brace expression.  We define
310   this as an inline function if the compiler permits.  */
311static
312#if __GNUC__ - 0 >= 2
313inline
314#endif
315const char *
316next_brace_sub (begin)
317     const char *begin;
318{
319  unsigned int depth = 0;
320  const char *cp = begin;
321
322  while (1)
323    {
324      if (depth == 0)
325	{
326	  if (*cp != ',' && *cp != '}' && *cp != '\0')
327	    {
328	      if (*cp == '{')
329		++depth;
330	      ++cp;
331	      continue;
332	    }
333	}
334      else
335	{
336	  while (*cp != '\0' && (*cp != '}' || depth > 0))
337	    {
338	      if (*cp == '}')
339		--depth;
340	      ++cp;
341	    }
342	  if (*cp == '\0')
343	    /* An incorrectly terminated brace expression.  */
344	    return NULL;
345
346	  continue;
347	}
348      break;
349    }
350
351  return cp;
352}
353
354/* Do glob searching for PATTERN, placing results in PGLOB.
355   The bits defined above may be set in FLAGS.
356   If a directory cannot be opened or read and ERRFUNC is not nil,
357   it is called with the pathname that caused the error, and the
358   `errno' value from the failing call; if it returns non-zero
359   `glob' returns GLOB_ABORTED; if it returns zero, the error is ignored.
360   If memory cannot be allocated for PGLOB, GLOB_NOSPACE is returned.
361   Otherwise, `glob' returns zero.  */
362int
363glob (pattern, flags, errfunc, pglob)
364     const char *pattern;
365     int flags;
366     int (*errfunc) __P ((const char *, int));
367     glob_t *pglob;
368{
369  const char *filename;
370  const char *dirname;
371  size_t dirlen;
372  int status;
373  int oldcount;
374
375  if (pattern == NULL || pglob == NULL || (flags & ~__GLOB_FLAGS) != 0)
376    {
377      __set_errno (EINVAL);
378      return -1;
379    }
380
381  if (flags & GLOB_BRACE)
382    {
383      const char *begin = strchr (pattern, '{');
384      if (begin != NULL)
385	{
386	  /* Allocate working buffer large enough for our work.  Note that
387	    we have at least an opening and closing brace.  */
388	  int firstc;
389	  char *alt_start;
390	  const char *p;
391	  const char *next;
392	  const char *rest;
393	  size_t rest_len;
394#ifdef __GNUC__
395	  char onealt[strlen (pattern) - 1];
396#else
397	  char *onealt = (char *) malloc (strlen (pattern) - 1);
398	  if (onealt == NULL)
399	    {
400	      if (!(flags & GLOB_APPEND))
401		globfree (pglob);
402	      return GLOB_NOSPACE;
403	    }
404#endif
405
406	  /* We know the prefix for all sub-patterns.  */
407#ifdef HAVE_MEMPCPY
408	  alt_start = mempcpy (onealt, pattern, begin - pattern);
409#else
410	  memcpy (onealt, pattern, begin - pattern);
411	  alt_start = &onealt[begin - pattern];
412#endif
413
414	  /* Find the first sub-pattern and at the same time find the
415	     rest after the closing brace.  */
416	  next = next_brace_sub (begin + 1);
417	  if (next == NULL)
418	    {
419	      /* It is an illegal expression.  */
420#ifndef __GNUC__
421	      free (onealt);
422#endif
423	      return glob (pattern, flags & ~GLOB_BRACE, errfunc, pglob);
424	    }
425
426	  /* Now find the end of the whole brace expression.  */
427	  rest = next;
428	  while (*rest != '}')
429	    {
430	      rest = next_brace_sub (rest + 1);
431	      if (rest == NULL)
432		{
433		  /* It is an illegal expression.  */
434#ifndef __GNUC__
435		  free (onealt);
436#endif
437		  return glob (pattern, flags & ~GLOB_BRACE, errfunc, pglob);
438		}
439	    }
440	  /* Please note that we now can be sure the brace expression
441	     is well-formed.  */
442	  rest_len = strlen (++rest) + 1;
443
444	  /* We have a brace expression.  BEGIN points to the opening {,
445	     NEXT points past the terminator of the first element, and END
446	     points past the final }.  We will accumulate result names from
447	     recursive runs for each brace alternative in the buffer using
448	     GLOB_APPEND.  */
449
450	  if (!(flags & GLOB_APPEND))
451	    {
452	      /* This call is to set a new vector, so clear out the
453		 vector so we can append to it.  */
454	      pglob->gl_pathc = 0;
455	      pglob->gl_pathv = NULL;
456	    }
457	  firstc = pglob->gl_pathc;
458
459	  p = begin + 1;
460	  while (1)
461	    {
462	      int result;
463
464	      /* Construct the new glob expression.  */
465#ifdef HAVE_MEMPCPY
466	      mempcpy (mempcpy (alt_start, p, next - p), rest, rest_len);
467#else
468	      memcpy (alt_start, p, next - p);
469	      memcpy (&alt_start[next - p], rest, rest_len);
470#endif
471
472	      result = glob (onealt,
473			     ((flags & ~(GLOB_NOCHECK|GLOB_NOMAGIC))
474			      | GLOB_APPEND), errfunc, pglob);
475
476	      /* If we got an error, return it.  */
477	      if (result && result != GLOB_NOMATCH)
478		{
479#ifndef __GNUC__
480		  free (onealt);
481#endif
482		  if (!(flags & GLOB_APPEND))
483		    globfree (pglob);
484		  return result;
485		}
486
487	      if (*next == '}')
488		/* We saw the last entry.  */
489		break;
490
491	      p = next + 1;
492	      next = next_brace_sub (p);
493	      assert (next != NULL);
494	    }
495
496#ifndef __GNUC__
497	  free (onealt);
498#endif
499
500	  if (pglob->gl_pathc != firstc)
501	    /* We found some entries.  */
502	    return 0;
503	  else if (!(flags & (GLOB_NOCHECK|GLOB_NOMAGIC)))
504	    return GLOB_NOMATCH;
505	}
506    }
507
508  /* Find the filename.  */
509  filename = strrchr (pattern, '/');
510#if defined __MSDOS__ || defined WINDOWS32
511  /* The case of "d:pattern".  Since `:' is not allowed in
512     file names, we can safely assume that wherever it
513     happens in pattern, it signals the filename part.  This
514     is so we could some day support patterns like "[a-z]:foo".  */
515  if (filename == NULL)
516    filename = strchr (pattern, ':');
517#endif /* __MSDOS__ || WINDOWS32 */
518  if (filename == NULL)
519    {
520      /* This can mean two things: a simple name or "~name".  The later
521	 case is nothing but a notation for a directory.  */
522      if ((flags & (GLOB_TILDE|GLOB_TILDE_CHECK)) && pattern[0] == '~')
523	{
524	  dirname = pattern;
525	  dirlen = strlen (pattern);
526
527	  /* Set FILENAME to NULL as a special flag.  This is ugly but
528	     other solutions would require much more code.  We test for
529	     this special case below.  */
530	  filename = NULL;
531	}
532      else
533	{
534	  filename = pattern;
535#ifdef _AMIGA
536	  dirname = "";
537#else
538	  dirname = ".";
539#endif
540	  dirlen = 0;
541	}
542    }
543  else if (filename == pattern)
544    {
545      /* "/pattern".  */
546      dirname = "/";
547      dirlen = 1;
548      ++filename;
549    }
550  else
551    {
552      char *newp;
553      dirlen = filename - pattern;
554#if defined __MSDOS__ || defined WINDOWS32
555      if (*filename == ':'
556	  || (filename > pattern + 1 && filename[-1] == ':'))
557	{
558	  char *drive_spec;
559
560	  ++dirlen;
561	  drive_spec = (char *) __alloca (dirlen + 1);
562#ifdef HAVE_MEMPCPY
563	  *((char *) mempcpy (drive_spec, pattern, dirlen)) = '\0';
564#else
565	  memcpy (drive_spec, pattern, dirlen);
566	  drive_spec[dirlen] = '\0';
567#endif
568	  /* For now, disallow wildcards in the drive spec, to
569	     prevent infinite recursion in glob.  */
570	  if (__glob_pattern_p (drive_spec, !(flags & GLOB_NOESCAPE)))
571	    return GLOB_NOMATCH;
572	  /* If this is "d:pattern", we need to copy `:' to DIRNAME
573	     as well.  If it's "d:/pattern", don't remove the slash
574	     from "d:/", since "d:" and "d:/" are not the same.*/
575	}
576#endif
577      newp = (char *) __alloca (dirlen + 1);
578#ifdef HAVE_MEMPCPY
579      *((char *) mempcpy (newp, pattern, dirlen)) = '\0';
580#else
581      memcpy (newp, pattern, dirlen);
582      newp[dirlen] = '\0';
583#endif
584      dirname = newp;
585      ++filename;
586
587      if (filename[0] == '\0'
588#if defined __MSDOS__ || defined WINDOWS32
589          && dirname[dirlen - 1] != ':'
590	  && (dirlen < 3 || dirname[dirlen - 2] != ':'
591	      || dirname[dirlen - 1] != '/')
592#endif
593	  && dirlen > 1)
594	/* "pattern/".  Expand "pattern", appending slashes.  */
595	{
596	  int val = glob (dirname, flags | GLOB_MARK, errfunc, pglob);
597	  if (val == 0)
598	    pglob->gl_flags = ((pglob->gl_flags & ~GLOB_MARK)
599			       | (flags & GLOB_MARK));
600	  return val;
601	}
602    }
603
604  if (!(flags & GLOB_APPEND))
605    {
606      pglob->gl_pathc = 0;
607      pglob->gl_pathv = NULL;
608    }
609
610  oldcount = pglob->gl_pathc;
611
612#ifndef VMS
613  if ((flags & (GLOB_TILDE|GLOB_TILDE_CHECK)) && dirname[0] == '~')
614    {
615      if (dirname[1] == '\0' || dirname[1] == '/')
616	{
617	  /* Look up home directory.  */
618#ifdef VMS
619/* This isn't obvious, RTLs of DECC and VAXC know about "HOME" */
620          const char *home_dir = getenv ("SYS$LOGIN");
621#else
622          const char *home_dir = getenv ("HOME");
623#endif
624# ifdef _AMIGA
625	  if (home_dir == NULL || home_dir[0] == '\0')
626	    home_dir = "SYS:";
627# else
628#  ifdef WINDOWS32
629	  if (home_dir == NULL || home_dir[0] == '\0')
630            home_dir = "c:/users/default"; /* poor default */
631#  else
632#   ifdef VMS
633/* Again, this isn't obvious, if "HOME" isn't known "SYS$LOGIN" should be set */
634	  if (home_dir == NULL || home_dir[0] == '\0')
635	    home_dir = "SYS$DISK:[]";
636#   else
637	  if (home_dir == NULL || home_dir[0] == '\0')
638	    {
639	      int success;
640	      char *name;
641#   if defined HAVE_GETLOGIN_R || defined _LIBC
642	      size_t buflen = sysconf (_SC_LOGIN_NAME_MAX) + 1;
643
644	      if (buflen == 0)
645		/* `sysconf' does not support _SC_LOGIN_NAME_MAX.  Try
646		   a moderate value.  */
647		buflen = 20;
648	      name = (char *) __alloca (buflen);
649
650	      success = getlogin_r (name, buflen) >= 0;
651#   else
652	      success = (name = getlogin ()) != NULL;
653#   endif
654	      if (success)
655		{
656		  struct passwd *p;
657#   if defined HAVE_GETPWNAM_R || defined _LIBC
658		  size_t pwbuflen = sysconf (_SC_GETPW_R_SIZE_MAX);
659		  char *pwtmpbuf;
660		  struct passwd pwbuf;
661		  int save = errno;
662
663		  if (pwbuflen == -1)
664		    /* `sysconf' does not support _SC_GETPW_R_SIZE_MAX.
665		       Try a moderate value.  */
666		    pwbuflen = 1024;
667		  pwtmpbuf = (char *) __alloca (pwbuflen);
668
669		  while (getpwnam_r (name, &pwbuf, pwtmpbuf, pwbuflen, &p)
670			 != 0)
671		    {
672		      if (errno != ERANGE)
673			{
674			  p = NULL;
675			  break;
676			}
677		      pwbuflen *= 2;
678		      pwtmpbuf = (char *) __alloca (pwbuflen);
679		      __set_errno (save);
680		    }
681#   else
682		  p = getpwnam (name);
683#   endif
684		  if (p != NULL)
685		    home_dir = p->pw_dir;
686		}
687	    }
688	  if (home_dir == NULL || home_dir[0] == '\0')
689	    {
690	      if (flags & GLOB_TILDE_CHECK)
691		return GLOB_NOMATCH;
692	      else
693		home_dir = "~"; /* No luck.  */
694	    }
695#   endif /* VMS */
696#  endif /* WINDOWS32 */
697# endif
698	  /* Now construct the full directory.  */
699	  if (dirname[1] == '\0')
700	    dirname = home_dir;
701	  else
702	    {
703	      char *newp;
704	      size_t home_len = strlen (home_dir);
705	      newp = (char *) __alloca (home_len + dirlen);
706# ifdef HAVE_MEMPCPY
707	      mempcpy (mempcpy (newp, home_dir, home_len),
708		       &dirname[1], dirlen);
709# else
710	      memcpy (newp, home_dir, home_len);
711	      memcpy (&newp[home_len], &dirname[1], dirlen);
712# endif
713	      dirname = newp;
714	    }
715	}
716# if !defined _AMIGA && !defined WINDOWS32 && !defined VMS
717      else
718	{
719	  char *end_name = strchr (dirname, '/');
720	  const char *user_name;
721	  const char *home_dir;
722
723	  if (end_name == NULL)
724	    user_name = dirname + 1;
725	  else
726	    {
727	      char *newp;
728	      newp = (char *) __alloca (end_name - dirname);
729# ifdef HAVE_MEMPCPY
730	      *((char *) mempcpy (newp, dirname + 1, end_name - dirname))
731		= '\0';
732# else
733	      memcpy (newp, dirname + 1, end_name - dirname);
734	      newp[end_name - dirname - 1] = '\0';
735# endif
736	      user_name = newp;
737	    }
738
739	  /* Look up specific user's home directory.  */
740	  {
741	    struct passwd *p;
742#  if defined HAVE_GETPWNAM_R || defined _LIBC
743	    size_t buflen = sysconf (_SC_GETPW_R_SIZE_MAX);
744	    char *pwtmpbuf;
745	    struct passwd pwbuf;
746	    int save = errno;
747
748	    if (buflen == -1)
749	      /* `sysconf' does not support _SC_GETPW_R_SIZE_MAX.  Try a
750		 moderate value.  */
751	      buflen = 1024;
752	    pwtmpbuf = (char *) __alloca (buflen);
753
754	    while (getpwnam_r (user_name, &pwbuf, pwtmpbuf, buflen, &p) != 0)
755	      {
756		if (errno != ERANGE)
757		  {
758		    p = NULL;
759		    break;
760		  }
761		buflen *= 2;
762		pwtmpbuf = __alloca (buflen);
763		__set_errno (save);
764	      }
765#  else
766	    p = getpwnam (user_name);
767#  endif
768	    if (p != NULL)
769	      home_dir = p->pw_dir;
770	    else
771	      home_dir = NULL;
772	  }
773	  /* If we found a home directory use this.  */
774	  if (home_dir != NULL)
775	    {
776	      char *newp;
777	      size_t home_len = strlen (home_dir);
778	      size_t rest_len = end_name == NULL ? 0 : strlen (end_name);
779	      newp = (char *) __alloca (home_len + rest_len + 1);
780#  ifdef HAVE_MEMPCPY
781	      *((char *) mempcpy (mempcpy (newp, home_dir, home_len),
782				  end_name, rest_len)) = '\0';
783#  else
784	      memcpy (newp, home_dir, home_len);
785	      memcpy (&newp[home_len], end_name, rest_len);
786	      newp[home_len + rest_len] = '\0';
787#  endif
788	      dirname = newp;
789	    }
790	  else
791	    if (flags & GLOB_TILDE_CHECK)
792	      /* We have to regard it as an error if we cannot find the
793		 home directory.  */
794	      return GLOB_NOMATCH;
795	}
796# endif	/* Not Amiga && not WINDOWS32 && not VMS.  */
797    }
798#endif	/* Not VMS.  */
799
800  /* Now test whether we looked for "~" or "~NAME".  In this case we
801     can give the answer now.  */
802  if (filename == NULL)
803    {
804      struct stat st;
805
806      /* Return the directory if we don't check for error or if it exists.  */
807      if ((flags & GLOB_NOCHECK)
808	  || (((flags & GLOB_ALTDIRFUNC)
809	       ? (*pglob->gl_stat) (dirname, &st)
810	       : __stat (dirname, &st)) == 0
811	      && S_ISDIR (st.st_mode)))
812	{
813	  pglob->gl_pathv
814	    = (char **) realloc (pglob->gl_pathv,
815				 (pglob->gl_pathc +
816				  ((flags & GLOB_DOOFFS) ?
817				   pglob->gl_offs : 0) +
818				  1 + 1) *
819				 sizeof (char *));
820	  if (pglob->gl_pathv == NULL)
821	    return GLOB_NOSPACE;
822
823	  if (flags & GLOB_DOOFFS)
824	    while (pglob->gl_pathc < pglob->gl_offs)
825	      pglob->gl_pathv[pglob->gl_pathc++] = NULL;
826
827#if defined HAVE_STRDUP || defined _LIBC
828	  pglob->gl_pathv[pglob->gl_pathc] = strdup (dirname);
829#else
830	  {
831	    size_t len = strlen (dirname) + 1;
832	    char *dircopy = malloc (len);
833	    if (dircopy != NULL)
834	      pglob->gl_pathv[pglob->gl_pathc] = memcpy (dircopy, dirname,
835							 len);
836	  }
837#endif
838	  if (pglob->gl_pathv[pglob->gl_pathc] == NULL)
839	    {
840	      free (pglob->gl_pathv);
841	      return GLOB_NOSPACE;
842	    }
843	  pglob->gl_pathv[++pglob->gl_pathc] = NULL;
844	  pglob->gl_flags = flags;
845
846	  return 0;
847	}
848
849      /* Not found.  */
850      return GLOB_NOMATCH;
851    }
852
853  if (__glob_pattern_p (dirname, !(flags & GLOB_NOESCAPE)))
854    {
855      /* The directory name contains metacharacters, so we
856	 have to glob for the directory, and then glob for
857	 the pattern in each directory found.  */
858      glob_t dirs;
859      register int i;
860
861      status = glob (dirname,
862		     ((flags & (GLOB_ERR | GLOB_NOCHECK | GLOB_NOESCAPE))
863		      | GLOB_NOSORT | GLOB_ONLYDIR),
864		     errfunc, &dirs);
865      if (status != 0)
866	return status;
867
868      /* We have successfully globbed the preceding directory name.
869	 For each name we found, call glob_in_dir on it and FILENAME,
870	 appending the results to PGLOB.  */
871      for (i = 0; i < dirs.gl_pathc; ++i)
872	{
873	  int old_pathc;
874
875#ifdef	SHELL
876	  {
877	    /* Make globbing interruptible in the bash shell. */
878	    extern int interrupt_state;
879
880	    if (interrupt_state)
881	      {
882		globfree (&dirs);
883		globfree (&files);
884		return GLOB_ABORTED;
885	      }
886	  }
887#endif /* SHELL.  */
888
889	  old_pathc = pglob->gl_pathc;
890	  status = glob_in_dir (filename, dirs.gl_pathv[i],
891				((flags | GLOB_APPEND)
892				 & ~(GLOB_NOCHECK | GLOB_ERR)),
893				errfunc, pglob);
894	  if (status == GLOB_NOMATCH)
895	    /* No matches in this directory.  Try the next.  */
896	    continue;
897
898	  if (status != 0)
899	    {
900	      globfree (&dirs);
901	      globfree (pglob);
902	      return status;
903	    }
904
905	  /* Stick the directory on the front of each name.  */
906	  if (prefix_array (dirs.gl_pathv[i],
907			    &pglob->gl_pathv[old_pathc],
908			    pglob->gl_pathc - old_pathc))
909	    {
910	      globfree (&dirs);
911	      globfree (pglob);
912	      return GLOB_NOSPACE;
913	    }
914	}
915
916      flags |= GLOB_MAGCHAR;
917
918      /* We have ignored the GLOB_NOCHECK flag in the `glob_in_dir' calls.
919	 But if we have not found any matching entry and thie GLOB_NOCHECK
920	 flag was set we must return the list consisting of the disrectory
921	 names followed by the filename.  */
922      if (pglob->gl_pathc == oldcount)
923	{
924	  /* No matches.  */
925	  if (flags & GLOB_NOCHECK)
926	    {
927	      size_t filename_len = strlen (filename) + 1;
928	      char **new_pathv;
929	      struct stat st;
930
931	      /* This is an pessimistic guess about the size.  */
932	      pglob->gl_pathv
933		= (char **) realloc (pglob->gl_pathv,
934				     (pglob->gl_pathc +
935				      ((flags & GLOB_DOOFFS) ?
936				       pglob->gl_offs : 0) +
937				      dirs.gl_pathc + 1) *
938				     sizeof (char *));
939	      if (pglob->gl_pathv == NULL)
940		{
941		  globfree (&dirs);
942		  return GLOB_NOSPACE;
943		}
944
945	      if (flags & GLOB_DOOFFS)
946		while (pglob->gl_pathc < pglob->gl_offs)
947		  pglob->gl_pathv[pglob->gl_pathc++] = NULL;
948
949	      for (i = 0; i < dirs.gl_pathc; ++i)
950		{
951		  const char *dir = dirs.gl_pathv[i];
952		  size_t dir_len = strlen (dir);
953
954		  /* First check whether this really is a directory.  */
955		  if (((flags & GLOB_ALTDIRFUNC)
956		       ? (*pglob->gl_stat) (dir, &st) : __stat (dir, &st)) != 0
957		      || !S_ISDIR (st.st_mode))
958		    /* No directory, ignore this entry.  */
959		    continue;
960
961		  pglob->gl_pathv[pglob->gl_pathc] = malloc (dir_len + 1
962							     + filename_len);
963		  if (pglob->gl_pathv[pglob->gl_pathc] == NULL)
964		    {
965		      globfree (&dirs);
966		      globfree (pglob);
967		      return GLOB_NOSPACE;
968		    }
969
970#ifdef HAVE_MEMPCPY
971		  mempcpy (mempcpy (mempcpy (pglob->gl_pathv[pglob->gl_pathc],
972					     dir, dir_len),
973				    "/", 1),
974			   filename, filename_len);
975#else
976		  memcpy (pglob->gl_pathv[pglob->gl_pathc], dir, dir_len);
977		  pglob->gl_pathv[pglob->gl_pathc][dir_len] = '/';
978		  memcpy (&pglob->gl_pathv[pglob->gl_pathc][dir_len + 1],
979			  filename, filename_len);
980#endif
981		  ++pglob->gl_pathc;
982		}
983
984	      pglob->gl_pathv[pglob->gl_pathc] = NULL;
985	      pglob->gl_flags = flags;
986
987	      /* Now we know how large the gl_pathv vector must be.  */
988	      new_pathv = (char **) realloc (pglob->gl_pathv,
989					     ((pglob->gl_pathc + 1)
990					      * sizeof (char *)));
991	      if (new_pathv != NULL)
992		pglob->gl_pathv = new_pathv;
993	    }
994	  else
995	    return GLOB_NOMATCH;
996	}
997
998      globfree (&dirs);
999    }
1000  else
1001    {
1002      status = glob_in_dir (filename, dirname, flags, errfunc, pglob);
1003      if (status != 0)
1004	return status;
1005
1006      if (dirlen > 0)
1007	{
1008	  /* Stick the directory on the front of each name.  */
1009	  int ignore = oldcount;
1010
1011	  if ((flags & GLOB_DOOFFS) && ignore < pglob->gl_offs)
1012	    ignore = pglob->gl_offs;
1013
1014	  if (prefix_array (dirname,
1015			    &pglob->gl_pathv[ignore],
1016			    pglob->gl_pathc - ignore))
1017	    {
1018	      globfree (pglob);
1019	      return GLOB_NOSPACE;
1020	    }
1021	}
1022    }
1023
1024  if (flags & GLOB_MARK)
1025    {
1026      /* Append slashes to directory names.  */
1027      int i;
1028      struct stat st;
1029      for (i = oldcount; i < pglob->gl_pathc; ++i)
1030	if (((flags & GLOB_ALTDIRFUNC)
1031	     ? (*pglob->gl_stat) (pglob->gl_pathv[i], &st)
1032	     : __stat (pglob->gl_pathv[i], &st)) == 0
1033	    && S_ISDIR (st.st_mode))
1034	  {
1035 	    size_t len = strlen (pglob->gl_pathv[i]) + 2;
1036	    char *new = realloc (pglob->gl_pathv[i], len);
1037 	    if (new == NULL)
1038	      {
1039		globfree (pglob);
1040		return GLOB_NOSPACE;
1041	      }
1042	    strcpy (&new[len - 2], "/");
1043	    pglob->gl_pathv[i] = new;
1044	  }
1045    }
1046
1047  if (!(flags & GLOB_NOSORT))
1048    {
1049      /* Sort the vector.  */
1050      int non_sort = oldcount;
1051
1052      if ((flags & GLOB_DOOFFS) && pglob->gl_offs > oldcount)
1053	non_sort = pglob->gl_offs;
1054
1055      qsort ((__ptr_t) &pglob->gl_pathv[non_sort],
1056	     pglob->gl_pathc - non_sort,
1057	     sizeof (char *), collated_compare);
1058    }
1059
1060  return 0;
1061}
1062
1063
1064/* Free storage allocated in PGLOB by a previous `glob' call.  */
1065void
1066globfree (pglob)
1067     register glob_t *pglob;
1068{
1069  if (pglob->gl_pathv != NULL)
1070    {
1071      register int i;
1072      for (i = 0; i < pglob->gl_pathc; ++i)
1073	if (pglob->gl_pathv[i] != NULL)
1074	  free ((__ptr_t) pglob->gl_pathv[i]);
1075      free ((__ptr_t) pglob->gl_pathv);
1076    }
1077}
1078
1079
1080/* Do a collated comparison of A and B.  */
1081static int
1082collated_compare (a, b)
1083     const __ptr_t a;
1084     const __ptr_t b;
1085{
1086  const char *const s1 = *(const char *const * const) a;
1087  const char *const s2 = *(const char *const * const) b;
1088
1089  if (s1 == s2)
1090    return 0;
1091  if (s1 == NULL)
1092    return 1;
1093  if (s2 == NULL)
1094    return -1;
1095  return strcoll (s1, s2);
1096}
1097
1098
1099/* Prepend DIRNAME to each of N members of ARRAY, replacing ARRAY's
1100   elements in place.  Return nonzero if out of memory, zero if successful.
1101   A slash is inserted between DIRNAME and each elt of ARRAY,
1102   unless DIRNAME is just "/".  Each old element of ARRAY is freed.  */
1103static int
1104prefix_array (dirname, array, n)
1105     const char *dirname;
1106     char **array;
1107     size_t n;
1108{
1109  register size_t i;
1110  size_t dirlen = strlen (dirname);
1111#if defined __MSDOS__ || defined WINDOWS32
1112  int sep_char = '/';
1113# define DIRSEP_CHAR sep_char
1114#else
1115# define DIRSEP_CHAR '/'
1116#endif
1117
1118  if (dirlen == 1 && dirname[0] == '/')
1119    /* DIRNAME is just "/", so normal prepending would get us "//foo".
1120       We want "/foo" instead, so don't prepend any chars from DIRNAME.  */
1121    dirlen = 0;
1122#if defined __MSDOS__ || defined WINDOWS32
1123  else if (dirlen > 1)
1124    {
1125      if (dirname[dirlen - 1] == '/' && dirname[dirlen - 2] == ':')
1126	/* DIRNAME is "d:/".  Don't prepend the slash from DIRNAME.  */
1127	--dirlen;
1128      else if (dirname[dirlen - 1] == ':')
1129	{
1130	  /* DIRNAME is "d:".  Use `:' instead of `/'.  */
1131	  --dirlen;
1132	  sep_char = ':';
1133	}
1134    }
1135#endif
1136
1137  for (i = 0; i < n; ++i)
1138    {
1139      size_t eltlen = strlen (array[i]) + 1;
1140      char *new = (char *) malloc (dirlen + 1 + eltlen);
1141      if (new == NULL)
1142	{
1143	  while (i > 0)
1144	    free ((__ptr_t) array[--i]);
1145	  return 1;
1146	}
1147
1148#ifdef HAVE_MEMPCPY
1149      {
1150	char *endp = (char *) mempcpy (new, dirname, dirlen);
1151	*endp++ = DIRSEP_CHAR;
1152	mempcpy (endp, array[i], eltlen);
1153      }
1154#else
1155      memcpy (new, dirname, dirlen);
1156      new[dirlen] = DIRSEP_CHAR;
1157      memcpy (&new[dirlen + 1], array[i], eltlen);
1158#endif
1159      free ((__ptr_t) array[i]);
1160      array[i] = new;
1161    }
1162
1163  return 0;
1164}
1165
1166
1167/* We must not compile this function twice.  */
1168#if !defined _LIBC || !defined NO_GLOB_PATTERN_P
1169/* Return nonzero if PATTERN contains any metacharacters.
1170   Metacharacters can be quoted with backslashes if QUOTE is nonzero.  */
1171int
1172__glob_pattern_p (pattern, quote)
1173     const char *pattern;
1174     int quote;
1175{
1176  register const char *p;
1177  int open = 0;
1178
1179  for (p = pattern; *p != '\0'; ++p)
1180    switch (*p)
1181      {
1182      case '?':
1183      case '*':
1184	return 1;
1185
1186      case '\\':
1187	if (quote && p[1] != '\0')
1188	  ++p;
1189	break;
1190
1191      case '[':
1192	open = 1;
1193	break;
1194
1195      case ']':
1196	if (open)
1197	  return 1;
1198	break;
1199      }
1200
1201  return 0;
1202}
1203# ifdef _LIBC
1204weak_alias (__glob_pattern_p, glob_pattern_p)
1205# endif
1206#endif
1207
1208
1209/* Like `glob', but PATTERN is a final pathname component,
1210   and matches are searched for in DIRECTORY.
1211   The GLOB_NOSORT bit in FLAGS is ignored.  No sorting is ever done.
1212   The GLOB_APPEND flag is assumed to be set (always appends).  */
1213static int
1214glob_in_dir (pattern, directory, flags, errfunc, pglob)
1215     const char *pattern;
1216     const char *directory;
1217     int flags;
1218     int (*errfunc) __P ((const char *, int));
1219     glob_t *pglob;
1220{
1221  __ptr_t stream = NULL;
1222
1223  struct globlink
1224    {
1225      struct globlink *next;
1226      char *name;
1227    };
1228  struct globlink *names = NULL;
1229  size_t nfound;
1230  int meta;
1231  int save;
1232
1233#ifdef VMS
1234  if (*directory == 0)
1235    directory = "[]";
1236#endif
1237  meta = __glob_pattern_p (pattern, !(flags & GLOB_NOESCAPE));
1238  if (meta == 0)
1239    {
1240      if (flags & (GLOB_NOCHECK|GLOB_NOMAGIC))
1241	/* We need not do any tests.  The PATTERN contains no meta
1242	   characters and we must not return an error therefore the
1243	   result will always contain exactly one name.  */
1244	flags |= GLOB_NOCHECK;
1245      else
1246	{
1247	  /* Since we use the normal file functions we can also use stat()
1248	     to verify the file is there.  */
1249	  struct stat st;
1250	  size_t patlen = strlen (pattern);
1251	  size_t dirlen = strlen (directory);
1252	  char *fullname = (char *) __alloca (dirlen + 1 + patlen + 1);
1253
1254# ifdef HAVE_MEMPCPY
1255	  mempcpy (mempcpy (mempcpy (fullname, directory, dirlen),
1256			    "/", 1),
1257		   pattern, patlen + 1);
1258# else
1259	  memcpy (fullname, directory, dirlen);
1260	  fullname[dirlen] = '/';
1261	  memcpy (&fullname[dirlen + 1], pattern, patlen + 1);
1262# endif
1263	  if (((flags & GLOB_ALTDIRFUNC)
1264	       ? (*pglob->gl_stat) (fullname, &st)
1265	       : __stat (fullname, &st)) == 0)
1266	    /* We found this file to be existing.  Now tell the rest
1267	       of the function to copy this name into the result.  */
1268	    flags |= GLOB_NOCHECK;
1269	}
1270
1271      nfound = 0;
1272    }
1273  else
1274    {
1275      if (pattern[0] == '\0')
1276	{
1277	  /* This is a special case for matching directories like in
1278	     "*a/".  */
1279	  names = (struct globlink *) __alloca (sizeof (struct globlink));
1280	  names->name = (char *) malloc (1);
1281	  if (names->name == NULL)
1282	    goto memory_error;
1283	  names->name[0] = '\0';
1284	  names->next = NULL;
1285	  nfound = 1;
1286	  meta = 0;
1287	}
1288      else
1289	{
1290	  stream = ((flags & GLOB_ALTDIRFUNC)
1291		    ? (*pglob->gl_opendir) (directory)
1292		    : (__ptr_t) opendir (directory));
1293	  if (stream == NULL)
1294	    {
1295	      if (errno != ENOTDIR
1296		  && ((errfunc != NULL && (*errfunc) (directory, errno))
1297		      || (flags & GLOB_ERR)))
1298		return GLOB_ABORTED;
1299	      nfound = 0;
1300	      meta = 0;
1301	    }
1302	  else
1303	    {
1304	      int fnm_flags = ((!(flags & GLOB_PERIOD) ? FNM_PERIOD : 0)
1305			       | ((flags & GLOB_NOESCAPE) ? FNM_NOESCAPE : 0)
1306#if defined _AMIGA || defined VMS
1307				   | FNM_CASEFOLD
1308#endif
1309				   );
1310	      nfound = 0;
1311	      flags |= GLOB_MAGCHAR;
1312
1313	      while (1)
1314		{
1315		  const char *name;
1316		  size_t len;
1317		  struct dirent *d = ((flags & GLOB_ALTDIRFUNC)
1318				      ? (*pglob->gl_readdir) (stream)
1319				      : readdir ((DIR *) stream));
1320		  if (d == NULL)
1321		    break;
1322		  if (! REAL_DIR_ENTRY (d))
1323		    continue;
1324
1325#ifdef HAVE_D_TYPE
1326		  /* If we shall match only directories use the information
1327		     provided by the dirent call if possible.  */
1328		  if ((flags & GLOB_ONLYDIR)
1329		      && d->d_type != DT_UNKNOWN && d->d_type != DT_DIR)
1330		    continue;
1331#endif
1332
1333		  name = d->d_name;
1334
1335		  if (fnmatch (pattern, name, fnm_flags) == 0)
1336		    {
1337		      struct globlink *new = (struct globlink *)
1338			__alloca (sizeof (struct globlink));
1339		      len = NAMLEN (d);
1340		      new->name = (char *) malloc (len + 1);
1341		      if (new->name == NULL)
1342			goto memory_error;
1343#ifdef HAVE_MEMPCPY
1344		      *((char *) mempcpy ((__ptr_t) new->name, name, len))
1345			= '\0';
1346#else
1347		      memcpy ((__ptr_t) new->name, name, len);
1348		      new->name[len] = '\0';
1349#endif
1350		      new->next = names;
1351		      names = new;
1352		      ++nfound;
1353		    }
1354		}
1355	    }
1356	}
1357    }
1358
1359  if (nfound == 0 && (flags & GLOB_NOCHECK))
1360    {
1361      size_t len = strlen (pattern);
1362      nfound = 1;
1363      names = (struct globlink *) __alloca (sizeof (struct globlink));
1364      names->next = NULL;
1365      names->name = (char *) malloc (len + 1);
1366      if (names->name == NULL)
1367	goto memory_error;
1368#ifdef HAVE_MEMPCPY
1369      *((char *) mempcpy (names->name, pattern, len)) = '\0';
1370#else
1371      memcpy (names->name, pattern, len);
1372      names->name[len] = '\0';
1373#endif
1374    }
1375
1376  if (nfound != 0)
1377    {
1378      pglob->gl_pathv
1379	= (char **) realloc (pglob->gl_pathv,
1380			     (pglob->gl_pathc +
1381			      ((flags & GLOB_DOOFFS) ? pglob->gl_offs : 0) +
1382			      nfound + 1) *
1383			     sizeof (char *));
1384      if (pglob->gl_pathv == NULL)
1385	goto memory_error;
1386
1387      if (flags & GLOB_DOOFFS)
1388	while (pglob->gl_pathc < pglob->gl_offs)
1389	  pglob->gl_pathv[pglob->gl_pathc++] = NULL;
1390
1391      for (; names != NULL; names = names->next)
1392	pglob->gl_pathv[pglob->gl_pathc++] = names->name;
1393      pglob->gl_pathv[pglob->gl_pathc] = NULL;
1394
1395      pglob->gl_flags = flags;
1396    }
1397
1398  save = errno;
1399  if (stream != NULL)
1400    {
1401      if (flags & GLOB_ALTDIRFUNC)
1402	(*pglob->gl_closedir) (stream);
1403      else
1404	closedir ((DIR *) stream);
1405    }
1406  __set_errno (save);
1407
1408  return nfound == 0 ? GLOB_NOMATCH : 0;
1409
1410 memory_error:
1411  {
1412    int save = errno;
1413    if (flags & GLOB_ALTDIRFUNC)
1414      (*pglob->gl_closedir) (stream);
1415    else
1416      closedir ((DIR *) stream);
1417    __set_errno (save);
1418  }
1419  while (names != NULL)
1420    {
1421      if (names->name != NULL)
1422	free ((__ptr_t) names->name);
1423      names = names->next;
1424    }
1425  return GLOB_NOSPACE;
1426}
1427
1428#endif	/* Not ELIDE_CODE.  */
1429