xref: /freebsd/lib/libc/gen/glob.c (revision daab0b01edd8f0175b355f02e5f1481b2f7898f9)
158f0484fSRodney W. Grimes /*
258f0484fSRodney W. Grimes  * Copyright (c) 1989, 1993
358f0484fSRodney W. Grimes  *	The Regents of the University of California.  All rights reserved.
458f0484fSRodney W. Grimes  *
558f0484fSRodney W. Grimes  * This code is derived from software contributed to Berkeley by
658f0484fSRodney W. Grimes  * Guido van Rossum.
758f0484fSRodney W. Grimes  *
83c87aa1dSDavid Chisnall  * Copyright (c) 2011 The FreeBSD Foundation
93c87aa1dSDavid Chisnall  * All rights reserved.
103c87aa1dSDavid Chisnall  * Portions of this software were developed by David Chisnall
113c87aa1dSDavid Chisnall  * under sponsorship from the FreeBSD Foundation.
123c87aa1dSDavid Chisnall  *
1358f0484fSRodney W. Grimes  * Redistribution and use in source and binary forms, with or without
1458f0484fSRodney W. Grimes  * modification, are permitted provided that the following conditions
1558f0484fSRodney W. Grimes  * are met:
1658f0484fSRodney W. Grimes  * 1. Redistributions of source code must retain the above copyright
1758f0484fSRodney W. Grimes  *    notice, this list of conditions and the following disclaimer.
1858f0484fSRodney W. Grimes  * 2. Redistributions in binary form must reproduce the above copyright
1958f0484fSRodney W. Grimes  *    notice, this list of conditions and the following disclaimer in the
2058f0484fSRodney W. Grimes  *    documentation and/or other materials provided with the distribution.
2158f0484fSRodney W. Grimes  * 4. Neither the name of the University nor the names of its contributors
2258f0484fSRodney W. Grimes  *    may be used to endorse or promote products derived from this software
2358f0484fSRodney W. Grimes  *    without specific prior written permission.
2458f0484fSRodney W. Grimes  *
2558f0484fSRodney W. Grimes  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
2658f0484fSRodney W. Grimes  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
2758f0484fSRodney W. Grimes  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
2858f0484fSRodney W. Grimes  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
2958f0484fSRodney W. Grimes  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
3058f0484fSRodney W. Grimes  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
3158f0484fSRodney W. Grimes  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
3258f0484fSRodney W. Grimes  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
3358f0484fSRodney W. Grimes  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
3458f0484fSRodney W. Grimes  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
3558f0484fSRodney W. Grimes  * SUCH DAMAGE.
3658f0484fSRodney W. Grimes  */
3758f0484fSRodney W. Grimes 
3858f0484fSRodney W. Grimes #if defined(LIBC_SCCS) && !defined(lint)
3958f0484fSRodney W. Grimes static char sccsid[] = "@(#)glob.c	8.3 (Berkeley) 10/13/93";
4058f0484fSRodney W. Grimes #endif /* LIBC_SCCS and not lint */
41b231cb39SDavid E. O'Brien #include <sys/cdefs.h>
42b231cb39SDavid E. O'Brien __FBSDID("$FreeBSD$");
4358f0484fSRodney W. Grimes 
4458f0484fSRodney W. Grimes /*
4558f0484fSRodney W. Grimes  * glob(3) -- a superset of the one defined in POSIX 1003.2.
4658f0484fSRodney W. Grimes  *
4758f0484fSRodney W. Grimes  * The [!...] convention to negate a range is supported (SysV, Posix, ksh).
4858f0484fSRodney W. Grimes  *
4958f0484fSRodney W. Grimes  * Optional extra services, controlled by flags not defined by POSIX:
5058f0484fSRodney W. Grimes  *
5158f0484fSRodney W. Grimes  * GLOB_QUOTE:
5258f0484fSRodney W. Grimes  *	Escaping convention: \ inhibits any special meaning the following
5358f0484fSRodney W. Grimes  *	character might have (except \ at end of string is retained).
5458f0484fSRodney W. Grimes  * GLOB_MAGCHAR:
5558f0484fSRodney W. Grimes  *	Set in gl_flags if pattern contained a globbing character.
5658f0484fSRodney W. Grimes  * GLOB_NOMAGIC:
5758f0484fSRodney W. Grimes  *	Same as GLOB_NOCHECK, but it will only append pattern if it did
5858f0484fSRodney W. Grimes  *	not contain any magic characters.  [Used in csh style globbing]
5958f0484fSRodney W. Grimes  * GLOB_ALTDIRFUNC:
6058f0484fSRodney W. Grimes  *	Use alternately specified directory access functions.
6158f0484fSRodney W. Grimes  * GLOB_TILDE:
6258f0484fSRodney W. Grimes  *	expand ~user/foo to the /home/dir/of/user/foo
6358f0484fSRodney W. Grimes  * GLOB_BRACE:
6458f0484fSRodney W. Grimes  *	expand {1,2}{a,b} to 1a 1b 2a 2b
6558f0484fSRodney W. Grimes  * gl_matchc:
6658f0484fSRodney W. Grimes  *	Number of matches in the current invocation of glob.
6758f0484fSRodney W. Grimes  */
6858f0484fSRodney W. Grimes 
69e9346e01STim J. Robbins /*
70e9346e01STim J. Robbins  * Some notes on multibyte character support:
71e9346e01STim J. Robbins  * 1. Patterns with illegal byte sequences match nothing - even if
72e9346e01STim J. Robbins  *    GLOB_NOCHECK is specified.
73e9346e01STim J. Robbins  * 2. Illegal byte sequences in filenames are handled by treating them as
74e9346e01STim J. Robbins  *    single-byte characters with a value of the first byte of the sequence
75e9346e01STim J. Robbins  *    cast to wchar_t.
76e9346e01STim J. Robbins  * 3. State-dependent encodings are not currently supported.
77e9346e01STim J. Robbins  */
78e9346e01STim J. Robbins 
7958f0484fSRodney W. Grimes #include <sys/param.h>
8058f0484fSRodney W. Grimes #include <sys/stat.h>
8158f0484fSRodney W. Grimes 
8258f0484fSRodney W. Grimes #include <ctype.h>
8358f0484fSRodney W. Grimes #include <dirent.h>
8458f0484fSRodney W. Grimes #include <errno.h>
8558f0484fSRodney W. Grimes #include <glob.h>
86e9346e01STim J. Robbins #include <limits.h>
8758f0484fSRodney W. Grimes #include <pwd.h>
88e9346e01STim J. Robbins #include <stdint.h>
8958f0484fSRodney W. Grimes #include <stdio.h>
9058f0484fSRodney W. Grimes #include <stdlib.h>
9158f0484fSRodney W. Grimes #include <string.h>
9258f0484fSRodney W. Grimes #include <unistd.h>
93e9346e01STim J. Robbins #include <wchar.h>
9458f0484fSRodney W. Grimes 
95edcfa072SAndrey A. Chernov #include "collate.h"
96edcfa072SAndrey A. Chernov 
97*daab0b01SMarcel Moolenaar /*
98*daab0b01SMarcel Moolenaar  * glob(3) expansion limits. Stop the expansion if any of these limits
99*daab0b01SMarcel Moolenaar  * is reached. This caps the runtime in the face of DoS attacks. See
100*daab0b01SMarcel Moolenaar  * also CVE-2010-2632
101*daab0b01SMarcel Moolenaar  */
102*daab0b01SMarcel Moolenaar #define	GLOB_LIMIT_BRACE	128	/* number of brace calls */
103*daab0b01SMarcel Moolenaar #define	GLOB_LIMIT_PATH		65536	/* number of path elements */
104*daab0b01SMarcel Moolenaar #define	GLOB_LIMIT_READDIR	16384	/* number of readdirs */
105*daab0b01SMarcel Moolenaar #define	GLOB_LIMIT_STAT		1024	/* number of stat system calls */
106*daab0b01SMarcel Moolenaar #define	GLOB_LIMIT_STRING	ARG_MAX	/* maximum total size for paths */
107*daab0b01SMarcel Moolenaar 
108*daab0b01SMarcel Moolenaar struct glob_limit {
109*daab0b01SMarcel Moolenaar 	size_t	l_brace_cnt;
110*daab0b01SMarcel Moolenaar 	size_t	l_path_lim;
111*daab0b01SMarcel Moolenaar 	size_t	l_readdir_cnt;
112*daab0b01SMarcel Moolenaar 	size_t	l_stat_cnt;
113*daab0b01SMarcel Moolenaar 	size_t	l_string_cnt;
114*daab0b01SMarcel Moolenaar };
115*daab0b01SMarcel Moolenaar 
11658f0484fSRodney W. Grimes #define	DOLLAR		'$'
11758f0484fSRodney W. Grimes #define	DOT		'.'
11858f0484fSRodney W. Grimes #define	EOS		'\0'
11958f0484fSRodney W. Grimes #define	LBRACKET	'['
12058f0484fSRodney W. Grimes #define	NOT		'!'
12158f0484fSRodney W. Grimes #define	QUESTION	'?'
12258f0484fSRodney W. Grimes #define	QUOTE		'\\'
12358f0484fSRodney W. Grimes #define	RANGE		'-'
12458f0484fSRodney W. Grimes #define	RBRACKET	']'
12558f0484fSRodney W. Grimes #define	SEP		'/'
12658f0484fSRodney W. Grimes #define	STAR		'*'
12758f0484fSRodney W. Grimes #define	TILDE		'~'
12858f0484fSRodney W. Grimes #define	UNDERSCORE	'_'
12958f0484fSRodney W. Grimes #define	LBRACE		'{'
13058f0484fSRodney W. Grimes #define	RBRACE		'}'
13158f0484fSRodney W. Grimes #define	SLASH		'/'
13258f0484fSRodney W. Grimes #define	COMMA		','
13358f0484fSRodney W. Grimes 
13458f0484fSRodney W. Grimes #ifndef DEBUG
13558f0484fSRodney W. Grimes 
136e9346e01STim J. Robbins #define	M_QUOTE		0x8000000000ULL
137e9346e01STim J. Robbins #define	M_PROTECT	0x4000000000ULL
138e9346e01STim J. Robbins #define	M_MASK		0xffffffffffULL
139e9346e01STim J. Robbins #define	M_CHAR		0x00ffffffffULL
14058f0484fSRodney W. Grimes 
141e9346e01STim J. Robbins typedef uint_fast64_t Char;
14258f0484fSRodney W. Grimes 
14358f0484fSRodney W. Grimes #else
14458f0484fSRodney W. Grimes 
14558f0484fSRodney W. Grimes #define	M_QUOTE		0x80
14658f0484fSRodney W. Grimes #define	M_PROTECT	0x40
14758f0484fSRodney W. Grimes #define	M_MASK		0xff
148e9346e01STim J. Robbins #define	M_CHAR		0x7f
14958f0484fSRodney W. Grimes 
15058f0484fSRodney W. Grimes typedef char Char;
15158f0484fSRodney W. Grimes 
15258f0484fSRodney W. Grimes #endif
15358f0484fSRodney W. Grimes 
15458f0484fSRodney W. Grimes 
155e9346e01STim J. Robbins #define	CHAR(c)		((Char)((c)&M_CHAR))
15658f0484fSRodney W. Grimes #define	META(c)		((Char)((c)|M_QUOTE))
15758f0484fSRodney W. Grimes #define	M_ALL		META('*')
15858f0484fSRodney W. Grimes #define	M_END		META(']')
15958f0484fSRodney W. Grimes #define	M_NOT		META('!')
16058f0484fSRodney W. Grimes #define	M_ONE		META('?')
16158f0484fSRodney W. Grimes #define	M_RNG		META('-')
16258f0484fSRodney W. Grimes #define	M_SET		META('[')
16358f0484fSRodney W. Grimes #define	ismeta(c)	(((c)&M_QUOTE) != 0)
16458f0484fSRodney W. Grimes 
16558f0484fSRodney W. Grimes 
166b231cb39SDavid E. O'Brien static int	 compare(const void *, const void *);
1674b767fa6SAndrey A. Chernov static int	 g_Ctoc(const Char *, char *, size_t);
168b231cb39SDavid E. O'Brien static int	 g_lstat(Char *, struct stat *, glob_t *);
169b231cb39SDavid E. O'Brien static DIR	*g_opendir(Char *, glob_t *);
17034a08754SMike Makonnen static const Char *g_strchr(const Char *, wchar_t);
17158f0484fSRodney W. Grimes #ifdef notdef
172b231cb39SDavid E. O'Brien static Char	*g_strcat(Char *, const Char *);
17358f0484fSRodney W. Grimes #endif
174b231cb39SDavid E. O'Brien static int	 g_stat(Char *, struct stat *, glob_t *);
175*daab0b01SMarcel Moolenaar static int	 glob0(const Char *, glob_t *, struct glob_limit *);
176*daab0b01SMarcel Moolenaar static int	 glob1(Char *, glob_t *, struct glob_limit *);
177*daab0b01SMarcel Moolenaar static int	 glob2(Char *, Char *, Char *, Char *, glob_t *,
178*daab0b01SMarcel Moolenaar     struct glob_limit *);
179*daab0b01SMarcel Moolenaar static int	 glob3(Char *, Char *, Char *, Char *, Char *, glob_t *,
180*daab0b01SMarcel Moolenaar     struct glob_limit *);
181*daab0b01SMarcel Moolenaar static int	 globextend(const Char *, glob_t *, struct glob_limit *);
182487dbd92SPeter Wemm static const Char *
183b231cb39SDavid E. O'Brien 		 globtilde(const Char *, Char *, size_t, glob_t *);
184*daab0b01SMarcel Moolenaar static int	 globexp1(const Char *, glob_t *, struct glob_limit *);
185*daab0b01SMarcel Moolenaar static int	 globexp2(const Char *, const Char *, glob_t *, int *,
186*daab0b01SMarcel Moolenaar     struct glob_limit *);
187b231cb39SDavid E. O'Brien static int	 match(Char *, Char *, Char *);
18858f0484fSRodney W. Grimes #ifdef DEBUG
189b231cb39SDavid E. O'Brien static void	 qprintf(const char *, Char *);
19058f0484fSRodney W. Grimes #endif
19158f0484fSRodney W. Grimes 
19258f0484fSRodney W. Grimes int
1930d6d372cSEitan Adler glob(const char * __restrict pattern, int flags,
1940d6d372cSEitan Adler 	 int (*errfunc)(const char *, int), glob_t * __restrict pglob)
19558f0484fSRodney W. Grimes {
196*daab0b01SMarcel Moolenaar 	struct glob_limit limit = { 0, 0, 0, 0, 0 };
1971cec70adSXin LI 	const char *patnext;
198e9346e01STim J. Robbins 	Char *bufnext, *bufend, patbuf[MAXPATHLEN], prot;
199e9346e01STim J. Robbins 	mbstate_t mbs;
200e9346e01STim J. Robbins 	wchar_t wc;
201e9346e01STim J. Robbins 	size_t clen;
20258f0484fSRodney W. Grimes 
2031cec70adSXin LI 	patnext = pattern;
20458f0484fSRodney W. Grimes 	if (!(flags & GLOB_APPEND)) {
20558f0484fSRodney W. Grimes 		pglob->gl_pathc = 0;
20658f0484fSRodney W. Grimes 		pglob->gl_pathv = NULL;
20758f0484fSRodney W. Grimes 		if (!(flags & GLOB_DOOFFS))
20858f0484fSRodney W. Grimes 			pglob->gl_offs = 0;
20958f0484fSRodney W. Grimes 	}
21075dc5f1aSMike Heffner 	if (flags & GLOB_LIMIT) {
211*daab0b01SMarcel Moolenaar 		limit.l_path_lim = pglob->gl_matchc;
212*daab0b01SMarcel Moolenaar 		if (limit.l_path_lim == 0)
213*daab0b01SMarcel Moolenaar 			limit.l_path_lim = GLOB_LIMIT_PATH;
214*daab0b01SMarcel Moolenaar 	}
21558f0484fSRodney W. Grimes 	pglob->gl_flags = flags & ~GLOB_MAGCHAR;
21658f0484fSRodney W. Grimes 	pglob->gl_errfunc = errfunc;
21758f0484fSRodney W. Grimes 	pglob->gl_matchc = 0;
21858f0484fSRodney W. Grimes 
21958f0484fSRodney W. Grimes 	bufnext = patbuf;
220487dbd92SPeter Wemm 	bufend = bufnext + MAXPATHLEN - 1;
221e9346e01STim J. Robbins 	if (flags & GLOB_NOESCAPE) {
222e9346e01STim J. Robbins 		memset(&mbs, 0, sizeof(mbs));
223e9346e01STim J. Robbins 		while (bufend - bufnext >= MB_CUR_MAX) {
224e9346e01STim J. Robbins 			clen = mbrtowc(&wc, patnext, MB_LEN_MAX, &mbs);
225e9346e01STim J. Robbins 			if (clen == (size_t)-1 || clen == (size_t)-2)
226e9346e01STim J. Robbins 				return (GLOB_NOMATCH);
227e9346e01STim J. Robbins 			else if (clen == 0)
228e9346e01STim J. Robbins 				break;
229e9346e01STim J. Robbins 			*bufnext++ = wc;
230e9346e01STim J. Robbins 			patnext += clen;
231e9346e01STim J. Robbins 		}
232e9346e01STim J. Robbins 	} else {
23358f0484fSRodney W. Grimes 		/* Protect the quoted characters. */
234e9346e01STim J. Robbins 		memset(&mbs, 0, sizeof(mbs));
235e9346e01STim J. Robbins 		while (bufend - bufnext >= MB_CUR_MAX) {
236e9346e01STim J. Robbins 			if (*patnext == QUOTE) {
237e9346e01STim J. Robbins 				if (*++patnext == EOS) {
238e9346e01STim J. Robbins 					*bufnext++ = QUOTE | M_PROTECT;
239e9346e01STim J. Robbins 					continue;
24058f0484fSRodney W. Grimes 				}
241e9346e01STim J. Robbins 				prot = M_PROTECT;
242e9346e01STim J. Robbins 			} else
243e9346e01STim J. Robbins 				prot = 0;
244e9346e01STim J. Robbins 			clen = mbrtowc(&wc, patnext, MB_LEN_MAX, &mbs);
245e9346e01STim J. Robbins 			if (clen == (size_t)-1 || clen == (size_t)-2)
246e9346e01STim J. Robbins 				return (GLOB_NOMATCH);
247e9346e01STim J. Robbins 			else if (clen == 0)
248e9346e01STim J. Robbins 				break;
249e9346e01STim J. Robbins 			*bufnext++ = wc | prot;
250e9346e01STim J. Robbins 			patnext += clen;
25158f0484fSRodney W. Grimes 		}
25258f0484fSRodney W. Grimes 	}
25358f0484fSRodney W. Grimes 	*bufnext = EOS;
25458f0484fSRodney W. Grimes 
25558f0484fSRodney W. Grimes 	if (flags & GLOB_BRACE)
25685529174SEitan Adler 	    return (globexp1(patbuf, pglob, &limit));
25758f0484fSRodney W. Grimes 	else
25885529174SEitan Adler 	    return (glob0(patbuf, pglob, &limit));
25958f0484fSRodney W. Grimes }
26058f0484fSRodney W. Grimes 
26158f0484fSRodney W. Grimes /*
26258f0484fSRodney W. Grimes  * Expand recursively a glob {} pattern. When there is no more expansion
26358f0484fSRodney W. Grimes  * invoke the standard globbing routine to glob the rest of the magic
26458f0484fSRodney W. Grimes  * characters
26558f0484fSRodney W. Grimes  */
266487dbd92SPeter Wemm static int
267*daab0b01SMarcel Moolenaar globexp1(const Char *pattern, glob_t *pglob, struct glob_limit *limit)
26858f0484fSRodney W. Grimes {
26958f0484fSRodney W. Grimes 	const Char* ptr = pattern;
27058f0484fSRodney W. Grimes 	int rv;
27158f0484fSRodney W. Grimes 
272*daab0b01SMarcel Moolenaar 	if ((pglob->gl_flags & GLOB_LIMIT) &&
273*daab0b01SMarcel Moolenaar 	    limit->l_brace_cnt++ >= GLOB_LIMIT_BRACE) {
274*daab0b01SMarcel Moolenaar 		errno = 0;
275*daab0b01SMarcel Moolenaar 		return (GLOB_NOSPACE);
276*daab0b01SMarcel Moolenaar 	}
277*daab0b01SMarcel Moolenaar 
27858f0484fSRodney W. Grimes 	/* Protect a single {}, for find(1), like csh */
27958f0484fSRodney W. Grimes 	if (pattern[0] == LBRACE && pattern[1] == RBRACE && pattern[2] == EOS)
280bae8632fSJonathan Lemon 		return glob0(pattern, pglob, limit);
28158f0484fSRodney W. Grimes 
28234a08754SMike Makonnen 	while ((ptr = g_strchr(ptr, LBRACE)) != NULL)
283bae8632fSJonathan Lemon 		if (!globexp2(ptr, pattern, pglob, &rv, limit))
28458f0484fSRodney W. Grimes 			return rv;
28558f0484fSRodney W. Grimes 
286bae8632fSJonathan Lemon 	return glob0(pattern, pglob, limit);
28758f0484fSRodney W. Grimes }
28858f0484fSRodney W. Grimes 
28958f0484fSRodney W. Grimes 
29058f0484fSRodney W. Grimes /*
29158f0484fSRodney W. Grimes  * Recursive brace globbing helper. Tries to expand a single brace.
29258f0484fSRodney W. Grimes  * If it succeeds then it invokes globexp1 with the new pattern.
29358f0484fSRodney W. Grimes  * If it fails then it tries to glob the rest of the pattern and returns.
29458f0484fSRodney W. Grimes  */
295487dbd92SPeter Wemm static int
296*daab0b01SMarcel Moolenaar globexp2(const Char *ptr, const Char *pattern, glob_t *pglob, int *rv,
297*daab0b01SMarcel Moolenaar     struct glob_limit *limit)
29858f0484fSRodney W. Grimes {
29958f0484fSRodney W. Grimes 	int     i;
30058f0484fSRodney W. Grimes 	Char   *lm, *ls;
301369316a8SAndrey A. Chernov 	const Char *pe, *pm, *pm1, *pl;
302487dbd92SPeter Wemm 	Char    patbuf[MAXPATHLEN];
30358f0484fSRodney W. Grimes 
30458f0484fSRodney W. Grimes 	/* copy part up to the brace */
30558f0484fSRodney W. Grimes 	for (lm = patbuf, pm = pattern; pm != ptr; *lm++ = *pm++)
30658f0484fSRodney W. Grimes 		continue;
307487dbd92SPeter Wemm 	*lm = EOS;
30858f0484fSRodney W. Grimes 	ls = lm;
30958f0484fSRodney W. Grimes 
31058f0484fSRodney W. Grimes 	/* Find the balanced brace */
31158f0484fSRodney W. Grimes 	for (i = 0, pe = ++ptr; *pe; pe++)
31258f0484fSRodney W. Grimes 		if (*pe == LBRACKET) {
31358f0484fSRodney W. Grimes 			/* Ignore everything between [] */
31458f0484fSRodney W. Grimes 			for (pm = pe++; *pe != RBRACKET && *pe != EOS; pe++)
31558f0484fSRodney W. Grimes 				continue;
31658f0484fSRodney W. Grimes 			if (*pe == EOS) {
31758f0484fSRodney W. Grimes 				/*
31858f0484fSRodney W. Grimes 				 * We could not find a matching RBRACKET.
31958f0484fSRodney W. Grimes 				 * Ignore and just look for RBRACE
32058f0484fSRodney W. Grimes 				 */
32158f0484fSRodney W. Grimes 				pe = pm;
32258f0484fSRodney W. Grimes 			}
32358f0484fSRodney W. Grimes 		}
32458f0484fSRodney W. Grimes 		else if (*pe == LBRACE)
32558f0484fSRodney W. Grimes 			i++;
32658f0484fSRodney W. Grimes 		else if (*pe == RBRACE) {
32758f0484fSRodney W. Grimes 			if (i == 0)
32858f0484fSRodney W. Grimes 				break;
32958f0484fSRodney W. Grimes 			i--;
33058f0484fSRodney W. Grimes 		}
33158f0484fSRodney W. Grimes 
33258f0484fSRodney W. Grimes 	/* Non matching braces; just glob the pattern */
33358f0484fSRodney W. Grimes 	if (i != 0 || *pe == EOS) {
334bae8632fSJonathan Lemon 		*rv = glob0(patbuf, pglob, limit);
33585529174SEitan Adler 		return (0);
33658f0484fSRodney W. Grimes 	}
33758f0484fSRodney W. Grimes 
33858f0484fSRodney W. Grimes 	for (i = 0, pl = pm = ptr; pm <= pe; pm++)
33958f0484fSRodney W. Grimes 		switch (*pm) {
34058f0484fSRodney W. Grimes 		case LBRACKET:
34158f0484fSRodney W. Grimes 			/* Ignore everything between [] */
342369316a8SAndrey A. Chernov 			for (pm1 = pm++; *pm != RBRACKET && *pm != EOS; pm++)
34358f0484fSRodney W. Grimes 				continue;
34458f0484fSRodney W. Grimes 			if (*pm == EOS) {
34558f0484fSRodney W. Grimes 				/*
34658f0484fSRodney W. Grimes 				 * We could not find a matching RBRACKET.
34758f0484fSRodney W. Grimes 				 * Ignore and just look for RBRACE
34858f0484fSRodney W. Grimes 				 */
349369316a8SAndrey A. Chernov 				pm = pm1;
35058f0484fSRodney W. Grimes 			}
35158f0484fSRodney W. Grimes 			break;
35258f0484fSRodney W. Grimes 
35358f0484fSRodney W. Grimes 		case LBRACE:
35458f0484fSRodney W. Grimes 			i++;
35558f0484fSRodney W. Grimes 			break;
35658f0484fSRodney W. Grimes 
35758f0484fSRodney W. Grimes 		case RBRACE:
35858f0484fSRodney W. Grimes 			if (i) {
35958f0484fSRodney W. Grimes 			    i--;
36058f0484fSRodney W. Grimes 			    break;
36158f0484fSRodney W. Grimes 			}
36258f0484fSRodney W. Grimes 			/* FALLTHROUGH */
36358f0484fSRodney W. Grimes 		case COMMA:
36458f0484fSRodney W. Grimes 			if (i && *pm == COMMA)
36558f0484fSRodney W. Grimes 				break;
36658f0484fSRodney W. Grimes 			else {
36758f0484fSRodney W. Grimes 				/* Append the current string */
36858f0484fSRodney W. Grimes 				for (lm = ls; (pl < pm); *lm++ = *pl++)
36958f0484fSRodney W. Grimes 					continue;
37058f0484fSRodney W. Grimes 				/*
37158f0484fSRodney W. Grimes 				 * Append the rest of the pattern after the
37258f0484fSRodney W. Grimes 				 * closing brace
37358f0484fSRodney W. Grimes 				 */
37458f0484fSRodney W. Grimes 				for (pl = pe + 1; (*lm++ = *pl++) != EOS;)
37558f0484fSRodney W. Grimes 					continue;
37658f0484fSRodney W. Grimes 
37758f0484fSRodney W. Grimes 				/* Expand the current pattern */
37858f0484fSRodney W. Grimes #ifdef DEBUG
37958f0484fSRodney W. Grimes 				qprintf("globexp2:", patbuf);
38058f0484fSRodney W. Grimes #endif
381bae8632fSJonathan Lemon 				*rv = globexp1(patbuf, pglob, limit);
38258f0484fSRodney W. Grimes 
38358f0484fSRodney W. Grimes 				/* move after the comma, to the next string */
38458f0484fSRodney W. Grimes 				pl = pm + 1;
38558f0484fSRodney W. Grimes 			}
38658f0484fSRodney W. Grimes 			break;
38758f0484fSRodney W. Grimes 
38858f0484fSRodney W. Grimes 		default:
38958f0484fSRodney W. Grimes 			break;
39058f0484fSRodney W. Grimes 		}
39158f0484fSRodney W. Grimes 	*rv = 0;
39285529174SEitan Adler 	return (0);
39358f0484fSRodney W. Grimes }
39458f0484fSRodney W. Grimes 
39558f0484fSRodney W. Grimes 
39658f0484fSRodney W. Grimes 
39758f0484fSRodney W. Grimes /*
39858f0484fSRodney W. Grimes  * expand tilde from the passwd file.
39958f0484fSRodney W. Grimes  */
40058f0484fSRodney W. Grimes static const Char *
4011cec70adSXin LI globtilde(const Char *pattern, Char *patbuf, size_t patbuf_len, glob_t *pglob)
40258f0484fSRodney W. Grimes {
40358f0484fSRodney W. Grimes 	struct passwd *pwd;
40458f0484fSRodney W. Grimes 	char *h;
40558f0484fSRodney W. Grimes 	const Char *p;
40662f187a4SWarner Losh 	Char *b, *eb;
40758f0484fSRodney W. Grimes 
40858f0484fSRodney W. Grimes 	if (*pattern != TILDE || !(pglob->gl_flags & GLOB_TILDE))
40985529174SEitan Adler 		return (pattern);
41058f0484fSRodney W. Grimes 
41162f187a4SWarner Losh 	/*
41262f187a4SWarner Losh 	 * Copy up to the end of the string or /
41362f187a4SWarner Losh 	 */
41462f187a4SWarner Losh 	eb = &patbuf[patbuf_len - 1];
41562f187a4SWarner Losh 	for (p = pattern + 1, h = (char *) patbuf;
41662f187a4SWarner Losh 	    h < (char *)eb && *p && *p != SLASH; *h++ = *p++)
41758f0484fSRodney W. Grimes 		continue;
41858f0484fSRodney W. Grimes 
41958f0484fSRodney W. Grimes 	*h = EOS;
42058f0484fSRodney W. Grimes 
42158f0484fSRodney W. Grimes 	if (((char *) patbuf)[0] == EOS) {
42258f0484fSRodney W. Grimes 		/*
4233fa69daeSWarner Losh 		 * handle a plain ~ or ~/ by expanding $HOME first (iff
4243fa69daeSWarner Losh 		 * we're not running setuid or setgid) and then trying
4253fa69daeSWarner Losh 		 * the password file
42658f0484fSRodney W. Grimes 		 */
4274539e95aSTim J. Robbins 		if (issetugid() != 0 ||
4289fcbcd02SJohn Birrell 		    (h = getenv("HOME")) == NULL) {
429eb8eee5aSAndrey A. Chernov 			if (((h = getlogin()) != NULL &&
430eb8eee5aSAndrey A. Chernov 			     (pwd = getpwnam(h)) != NULL) ||
431eb8eee5aSAndrey A. Chernov 			    (pwd = getpwuid(getuid())) != NULL)
43258f0484fSRodney W. Grimes 				h = pwd->pw_dir;
433eb8eee5aSAndrey A. Chernov 			else
43485529174SEitan Adler 				return (pattern);
43558f0484fSRodney W. Grimes 		}
43658f0484fSRodney W. Grimes 	}
43758f0484fSRodney W. Grimes 	else {
43858f0484fSRodney W. Grimes 		/*
43958f0484fSRodney W. Grimes 		 * Expand a ~user
44058f0484fSRodney W. Grimes 		 */
44158f0484fSRodney W. Grimes 		if ((pwd = getpwnam((char*) patbuf)) == NULL)
44285529174SEitan Adler 			return (pattern);
44358f0484fSRodney W. Grimes 		else
44458f0484fSRodney W. Grimes 			h = pwd->pw_dir;
44558f0484fSRodney W. Grimes 	}
44658f0484fSRodney W. Grimes 
44758f0484fSRodney W. Grimes 	/* Copy the home directory */
44862f187a4SWarner Losh 	for (b = patbuf; b < eb && *h; *b++ = *h++)
44958f0484fSRodney W. Grimes 		continue;
45058f0484fSRodney W. Grimes 
45158f0484fSRodney W. Grimes 	/* Append the rest of the pattern */
45262f187a4SWarner Losh 	while (b < eb && (*b++ = *p++) != EOS)
45358f0484fSRodney W. Grimes 		continue;
45462f187a4SWarner Losh 	*b = EOS;
45558f0484fSRodney W. Grimes 
45685529174SEitan Adler 	return (patbuf);
45758f0484fSRodney W. Grimes }
45858f0484fSRodney W. Grimes 
45958f0484fSRodney W. Grimes 
46058f0484fSRodney W. Grimes /*
46158f0484fSRodney W. Grimes  * The main glob() routine: compiles the pattern (optionally processing
46258f0484fSRodney W. Grimes  * quotes), calls glob1() to do the real pattern matching, and finally
46358f0484fSRodney W. Grimes  * sorts the list (unless unsorted operation is requested).  Returns 0
4644a59c3abSMike Heffner  * if things went well, nonzero if errors occurred.
46558f0484fSRodney W. Grimes  */
46658f0484fSRodney W. Grimes static int
467*daab0b01SMarcel Moolenaar glob0(const Char *pattern, glob_t *pglob, struct glob_limit *limit)
46858f0484fSRodney W. Grimes {
46958f0484fSRodney W. Grimes 	const Char *qpatnext;
4705b3fab81SGordon Tetlow 	int err;
4714b767fa6SAndrey A. Chernov 	size_t oldpathc;
4725b3fab81SGordon Tetlow 	Char *bufnext, c, patbuf[MAXPATHLEN];
47358f0484fSRodney W. Grimes 
474487dbd92SPeter Wemm 	qpatnext = globtilde(pattern, patbuf, MAXPATHLEN, pglob);
47558f0484fSRodney W. Grimes 	oldpathc = pglob->gl_pathc;
47658f0484fSRodney W. Grimes 	bufnext = patbuf;
47758f0484fSRodney W. Grimes 
47858f0484fSRodney W. Grimes 	/* We don't need to check for buffer overflow any more. */
47958f0484fSRodney W. Grimes 	while ((c = *qpatnext++) != EOS) {
48058f0484fSRodney W. Grimes 		switch (c) {
48158f0484fSRodney W. Grimes 		case LBRACKET:
48258f0484fSRodney W. Grimes 			c = *qpatnext;
48358f0484fSRodney W. Grimes 			if (c == NOT)
48458f0484fSRodney W. Grimes 				++qpatnext;
48558f0484fSRodney W. Grimes 			if (*qpatnext == EOS ||
48634a08754SMike Makonnen 			    g_strchr(qpatnext+1, RBRACKET) == NULL) {
48758f0484fSRodney W. Grimes 				*bufnext++ = LBRACKET;
48858f0484fSRodney W. Grimes 				if (c == NOT)
48958f0484fSRodney W. Grimes 					--qpatnext;
49058f0484fSRodney W. Grimes 				break;
49158f0484fSRodney W. Grimes 			}
49258f0484fSRodney W. Grimes 			*bufnext++ = M_SET;
49358f0484fSRodney W. Grimes 			if (c == NOT)
49458f0484fSRodney W. Grimes 				*bufnext++ = M_NOT;
49558f0484fSRodney W. Grimes 			c = *qpatnext++;
49658f0484fSRodney W. Grimes 			do {
49758f0484fSRodney W. Grimes 				*bufnext++ = CHAR(c);
49858f0484fSRodney W. Grimes 				if (*qpatnext == RANGE &&
49958f0484fSRodney W. Grimes 				    (c = qpatnext[1]) != RBRACKET) {
50058f0484fSRodney W. Grimes 					*bufnext++ = M_RNG;
50158f0484fSRodney W. Grimes 					*bufnext++ = CHAR(c);
50258f0484fSRodney W. Grimes 					qpatnext += 2;
50358f0484fSRodney W. Grimes 				}
50458f0484fSRodney W. Grimes 			} while ((c = *qpatnext++) != RBRACKET);
50558f0484fSRodney W. Grimes 			pglob->gl_flags |= GLOB_MAGCHAR;
50658f0484fSRodney W. Grimes 			*bufnext++ = M_END;
50758f0484fSRodney W. Grimes 			break;
50858f0484fSRodney W. Grimes 		case QUESTION:
50958f0484fSRodney W. Grimes 			pglob->gl_flags |= GLOB_MAGCHAR;
51058f0484fSRodney W. Grimes 			*bufnext++ = M_ONE;
51158f0484fSRodney W. Grimes 			break;
51258f0484fSRodney W. Grimes 		case STAR:
51358f0484fSRodney W. Grimes 			pglob->gl_flags |= GLOB_MAGCHAR;
51458f0484fSRodney W. Grimes 			/* collapse adjacent stars to one,
51558f0484fSRodney W. Grimes 			 * to avoid exponential behavior
51658f0484fSRodney W. Grimes 			 */
51758f0484fSRodney W. Grimes 			if (bufnext == patbuf || bufnext[-1] != M_ALL)
51858f0484fSRodney W. Grimes 			    *bufnext++ = M_ALL;
51958f0484fSRodney W. Grimes 			break;
52058f0484fSRodney W. Grimes 		default:
52158f0484fSRodney W. Grimes 			*bufnext++ = CHAR(c);
52258f0484fSRodney W. Grimes 			break;
52358f0484fSRodney W. Grimes 		}
52458f0484fSRodney W. Grimes 	}
52558f0484fSRodney W. Grimes 	*bufnext = EOS;
52658f0484fSRodney W. Grimes #ifdef DEBUG
52758f0484fSRodney W. Grimes 	qprintf("glob0:", patbuf);
52858f0484fSRodney W. Grimes #endif
52958f0484fSRodney W. Grimes 
530bae8632fSJonathan Lemon 	if ((err = glob1(patbuf, pglob, limit)) != 0)
53158f0484fSRodney W. Grimes 		return(err);
53258f0484fSRodney W. Grimes 
53358f0484fSRodney W. Grimes 	/*
53458f0484fSRodney W. Grimes 	 * If there was no match we are going to append the pattern
53558f0484fSRodney W. Grimes 	 * if GLOB_NOCHECK was specified or if GLOB_NOMAGIC was specified
53658f0484fSRodney W. Grimes 	 * and the pattern did not contain any magic characters
53758f0484fSRodney W. Grimes 	 * GLOB_NOMAGIC is there just for compatibility with csh.
53858f0484fSRodney W. Grimes 	 */
5394a59c3abSMike Heffner 	if (pglob->gl_pathc == oldpathc) {
5404a59c3abSMike Heffner 		if (((pglob->gl_flags & GLOB_NOCHECK) ||
54158f0484fSRodney W. Grimes 		    ((pglob->gl_flags & GLOB_NOMAGIC) &&
54258f0484fSRodney W. Grimes 			!(pglob->gl_flags & GLOB_MAGCHAR))))
543bae8632fSJonathan Lemon 			return (globextend(pattern, pglob, limit));
5444a59c3abSMike Heffner 		else
5454a59c3abSMike Heffner 			return (GLOB_NOMATCH);
5464a59c3abSMike Heffner 	}
5474a59c3abSMike Heffner 	if (!(pglob->gl_flags & GLOB_NOSORT))
54858f0484fSRodney W. Grimes 		qsort(pglob->gl_pathv + pglob->gl_offs + oldpathc,
54958f0484fSRodney W. Grimes 		    pglob->gl_pathc - oldpathc, sizeof(char *), compare);
55058f0484fSRodney W. Grimes 	return (0);
55158f0484fSRodney W. Grimes }
55258f0484fSRodney W. Grimes 
55358f0484fSRodney W. Grimes static int
5541cec70adSXin LI compare(const void *p, const void *q)
55558f0484fSRodney W. Grimes {
55658f0484fSRodney W. Grimes 	return (strcmp(*(char **)p, *(char **)q));
55758f0484fSRodney W. Grimes }
55858f0484fSRodney W. Grimes 
55958f0484fSRodney W. Grimes static int
560*daab0b01SMarcel Moolenaar glob1(Char *pattern, glob_t *pglob, struct glob_limit *limit)
56158f0484fSRodney W. Grimes {
562487dbd92SPeter Wemm 	Char pathbuf[MAXPATHLEN];
56358f0484fSRodney W. Grimes 
56458f0484fSRodney W. Grimes 	/* A null pathname is invalid -- POSIX 1003.1 sect. 2.4. */
56558f0484fSRodney W. Grimes 	if (*pattern == EOS)
56658f0484fSRodney W. Grimes 		return (0);
567487dbd92SPeter Wemm 	return (glob2(pathbuf, pathbuf, pathbuf + MAXPATHLEN - 1,
568487dbd92SPeter Wemm 	    pattern, pglob, limit));
56958f0484fSRodney W. Grimes }
57058f0484fSRodney W. Grimes 
57158f0484fSRodney W. Grimes /*
57258f0484fSRodney W. Grimes  * The functions glob2 and glob3 are mutually recursive; there is one level
57358f0484fSRodney W. Grimes  * of recursion for each segment in the pattern that contains one or more
57458f0484fSRodney W. Grimes  * meta characters.
57558f0484fSRodney W. Grimes  */
57658f0484fSRodney W. Grimes static int
5771cec70adSXin LI glob2(Char *pathbuf, Char *pathend, Char *pathend_last, Char *pattern,
578*daab0b01SMarcel Moolenaar       glob_t *pglob, struct glob_limit *limit)
57958f0484fSRodney W. Grimes {
58058f0484fSRodney W. Grimes 	struct stat sb;
58158f0484fSRodney W. Grimes 	Char *p, *q;
58258f0484fSRodney W. Grimes 	int anymeta;
58358f0484fSRodney W. Grimes 
58458f0484fSRodney W. Grimes 	/*
58558f0484fSRodney W. Grimes 	 * Loop over pattern segments until end of pattern or until
58658f0484fSRodney W. Grimes 	 * segment with meta character found.
58758f0484fSRodney W. Grimes 	 */
58858f0484fSRodney W. Grimes 	for (anymeta = 0;;) {
58958f0484fSRodney W. Grimes 		if (*pattern == EOS) {		/* End of pattern? */
59058f0484fSRodney W. Grimes 			*pathend = EOS;
59158f0484fSRodney W. Grimes 			if (g_lstat(pathbuf, &sb, pglob))
59258f0484fSRodney W. Grimes 				return (0);
59358f0484fSRodney W. Grimes 
594*daab0b01SMarcel Moolenaar 			if ((pglob->gl_flags & GLOB_LIMIT) &&
595*daab0b01SMarcel Moolenaar 			    limit->l_stat_cnt++ >= GLOB_LIMIT_STAT) {
596*daab0b01SMarcel Moolenaar 				errno = 0;
597*daab0b01SMarcel Moolenaar 				if (pathend + 1 > pathend_last)
598*daab0b01SMarcel Moolenaar 					return (GLOB_ABORTED);
599*daab0b01SMarcel Moolenaar 				*pathend++ = SEP;
600*daab0b01SMarcel Moolenaar 				*pathend = EOS;
601*daab0b01SMarcel Moolenaar 				return (GLOB_NOSPACE);
602*daab0b01SMarcel Moolenaar 			}
60358f0484fSRodney W. Grimes 			if (((pglob->gl_flags & GLOB_MARK) &&
60458f0484fSRodney W. Grimes 			    pathend[-1] != SEP) && (S_ISDIR(sb.st_mode)
60558f0484fSRodney W. Grimes 			    || (S_ISLNK(sb.st_mode) &&
60658f0484fSRodney W. Grimes 			    (g_stat(pathbuf, &sb, pglob) == 0) &&
60758f0484fSRodney W. Grimes 			    S_ISDIR(sb.st_mode)))) {
608487dbd92SPeter Wemm 				if (pathend + 1 > pathend_last)
6094a59c3abSMike Heffner 					return (GLOB_ABORTED);
61058f0484fSRodney W. Grimes 				*pathend++ = SEP;
61158f0484fSRodney W. Grimes 				*pathend = EOS;
61258f0484fSRodney W. Grimes 			}
61358f0484fSRodney W. Grimes 			++pglob->gl_matchc;
614bae8632fSJonathan Lemon 			return (globextend(pathbuf, pglob, limit));
61558f0484fSRodney W. Grimes 		}
61658f0484fSRodney W. Grimes 
61758f0484fSRodney W. Grimes 		/* Find end of next segment, copy tentatively to pathend. */
61858f0484fSRodney W. Grimes 		q = pathend;
61958f0484fSRodney W. Grimes 		p = pattern;
62058f0484fSRodney W. Grimes 		while (*p != EOS && *p != SEP) {
62158f0484fSRodney W. Grimes 			if (ismeta(*p))
62258f0484fSRodney W. Grimes 				anymeta = 1;
623487dbd92SPeter Wemm 			if (q + 1 > pathend_last)
6244a59c3abSMike Heffner 				return (GLOB_ABORTED);
62558f0484fSRodney W. Grimes 			*q++ = *p++;
62658f0484fSRodney W. Grimes 		}
62758f0484fSRodney W. Grimes 
62858f0484fSRodney W. Grimes 		if (!anymeta) {		/* No expansion, do next segment. */
62958f0484fSRodney W. Grimes 			pathend = q;
63058f0484fSRodney W. Grimes 			pattern = p;
631487dbd92SPeter Wemm 			while (*pattern == SEP) {
632487dbd92SPeter Wemm 				if (pathend + 1 > pathend_last)
6334a59c3abSMike Heffner 					return (GLOB_ABORTED);
63458f0484fSRodney W. Grimes 				*pathend++ = *pattern++;
635487dbd92SPeter Wemm 			}
63658f0484fSRodney W. Grimes 		} else			/* Need expansion, recurse. */
63785529174SEitan Adler 			return (glob3(pathbuf, pathend, pathend_last, pattern,
63885529174SEitan Adler 			    p, pglob, limit));
63958f0484fSRodney W. Grimes 	}
64058f0484fSRodney W. Grimes 	/* NOTREACHED */
64158f0484fSRodney W. Grimes }
64258f0484fSRodney W. Grimes 
64358f0484fSRodney W. Grimes static int
6441cec70adSXin LI glob3(Char *pathbuf, Char *pathend, Char *pathend_last,
6451cec70adSXin LI       Char *pattern, Char *restpattern,
646*daab0b01SMarcel Moolenaar       glob_t *pglob, struct glob_limit *limit)
64758f0484fSRodney W. Grimes {
648b231cb39SDavid E. O'Brien 	struct dirent *dp;
64958f0484fSRodney W. Grimes 	DIR *dirp;
65058f0484fSRodney W. Grimes 	int err;
65158f0484fSRodney W. Grimes 	char buf[MAXPATHLEN];
65258f0484fSRodney W. Grimes 
65358f0484fSRodney W. Grimes 	/*
65458f0484fSRodney W. Grimes 	 * The readdirfunc declaration can't be prototyped, because it is
65558f0484fSRodney W. Grimes 	 * assigned, below, to two functions which are prototyped in glob.h
65658f0484fSRodney W. Grimes 	 * and dirent.h as taking pointers to differently typed opaque
65758f0484fSRodney W. Grimes 	 * structures.
65858f0484fSRodney W. Grimes 	 */
65958f0484fSRodney W. Grimes 	struct dirent *(*readdirfunc)();
66058f0484fSRodney W. Grimes 
661487dbd92SPeter Wemm 	if (pathend > pathend_last)
6624a59c3abSMike Heffner 		return (GLOB_ABORTED);
66358f0484fSRodney W. Grimes 	*pathend = EOS;
66458f0484fSRodney W. Grimes 	errno = 0;
66558f0484fSRodney W. Grimes 
66658f0484fSRodney W. Grimes 	if ((dirp = g_opendir(pathbuf, pglob)) == NULL) {
66758f0484fSRodney W. Grimes 		/* TODO: don't call for ENOENT or ENOTDIR? */
66858f0484fSRodney W. Grimes 		if (pglob->gl_errfunc) {
66927d52f69SPeter Wemm 			if (g_Ctoc(pathbuf, buf, sizeof(buf)))
6704a59c3abSMike Heffner 				return (GLOB_ABORTED);
67158f0484fSRodney W. Grimes 			if (pglob->gl_errfunc(buf, errno) ||
67258f0484fSRodney W. Grimes 			    pglob->gl_flags & GLOB_ERR)
6734a59c3abSMike Heffner 				return (GLOB_ABORTED);
67458f0484fSRodney W. Grimes 		}
67558f0484fSRodney W. Grimes 		return (0);
67658f0484fSRodney W. Grimes 	}
67758f0484fSRodney W. Grimes 
67858f0484fSRodney W. Grimes 	err = 0;
67958f0484fSRodney W. Grimes 
68058f0484fSRodney W. Grimes 	/* Search directory for matching names. */
68158f0484fSRodney W. Grimes 	if (pglob->gl_flags & GLOB_ALTDIRFUNC)
68258f0484fSRodney W. Grimes 		readdirfunc = pglob->gl_readdir;
68358f0484fSRodney W. Grimes 	else
68458f0484fSRodney W. Grimes 		readdirfunc = readdir;
68558f0484fSRodney W. Grimes 	while ((dp = (*readdirfunc)(dirp))) {
6861cec70adSXin LI 		char *sc;
687b231cb39SDavid E. O'Brien 		Char *dc;
688e9346e01STim J. Robbins 		wchar_t wc;
689e9346e01STim J. Robbins 		size_t clen;
690e9346e01STim J. Robbins 		mbstate_t mbs;
69158f0484fSRodney W. Grimes 
692*daab0b01SMarcel Moolenaar 		if ((pglob->gl_flags & GLOB_LIMIT) &&
693*daab0b01SMarcel Moolenaar 		    limit->l_readdir_cnt++ >= GLOB_LIMIT_READDIR) {
694*daab0b01SMarcel Moolenaar 			errno = 0;
695*daab0b01SMarcel Moolenaar 			if (pathend + 1 > pathend_last)
696*daab0b01SMarcel Moolenaar 				err = GLOB_ABORTED;
697*daab0b01SMarcel Moolenaar 			else {
698*daab0b01SMarcel Moolenaar 				*pathend++ = SEP;
699*daab0b01SMarcel Moolenaar 				*pathend = EOS;
700*daab0b01SMarcel Moolenaar 				err = GLOB_NOSPACE;
701*daab0b01SMarcel Moolenaar 			}
702*daab0b01SMarcel Moolenaar 			break;
703*daab0b01SMarcel Moolenaar 		}
704*daab0b01SMarcel Moolenaar 
70558f0484fSRodney W. Grimes 		/* Initial DOT must be matched literally. */
70658f0484fSRodney W. Grimes 		if (dp->d_name[0] == DOT && *pattern != DOT)
70758f0484fSRodney W. Grimes 			continue;
708e9346e01STim J. Robbins 		memset(&mbs, 0, sizeof(mbs));
709487dbd92SPeter Wemm 		dc = pathend;
7101cec70adSXin LI 		sc = dp->d_name;
711e9346e01STim J. Robbins 		while (dc < pathend_last) {
712e9346e01STim J. Robbins 			clen = mbrtowc(&wc, sc, MB_LEN_MAX, &mbs);
713e9346e01STim J. Robbins 			if (clen == (size_t)-1 || clen == (size_t)-2) {
714e9346e01STim J. Robbins 				wc = *sc;
715e9346e01STim J. Robbins 				clen = 1;
716e9346e01STim J. Robbins 				memset(&mbs, 0, sizeof(mbs));
717e9346e01STim J. Robbins 			}
718e9346e01STim J. Robbins 			if ((*dc++ = wc) == EOS)
719e9346e01STim J. Robbins 				break;
720e9346e01STim J. Robbins 			sc += clen;
721e9346e01STim J. Robbins 		}
72258f0484fSRodney W. Grimes 		if (!match(pathend, pattern, restpattern)) {
72358f0484fSRodney W. Grimes 			*pathend = EOS;
72458f0484fSRodney W. Grimes 			continue;
72558f0484fSRodney W. Grimes 		}
726487dbd92SPeter Wemm 		err = glob2(pathbuf, --dc, pathend_last, restpattern,
727487dbd92SPeter Wemm 		    pglob, limit);
72858f0484fSRodney W. Grimes 		if (err)
72958f0484fSRodney W. Grimes 			break;
73058f0484fSRodney W. Grimes 	}
73158f0484fSRodney W. Grimes 
73258f0484fSRodney W. Grimes 	if (pglob->gl_flags & GLOB_ALTDIRFUNC)
73358f0484fSRodney W. Grimes 		(*pglob->gl_closedir)(dirp);
73458f0484fSRodney W. Grimes 	else
73558f0484fSRodney W. Grimes 		closedir(dirp);
73658f0484fSRodney W. Grimes 	return (err);
73758f0484fSRodney W. Grimes }
73858f0484fSRodney W. Grimes 
73958f0484fSRodney W. Grimes 
74058f0484fSRodney W. Grimes /*
74158f0484fSRodney W. Grimes  * Extend the gl_pathv member of a glob_t structure to accomodate a new item,
74258f0484fSRodney W. Grimes  * add the new item, and update gl_pathc.
74358f0484fSRodney W. Grimes  *
74458f0484fSRodney W. Grimes  * This assumes the BSD realloc, which only copies the block when its size
74558f0484fSRodney W. Grimes  * crosses a power-of-two boundary; for v7 realloc, this would cause quadratic
74658f0484fSRodney W. Grimes  * behavior.
74758f0484fSRodney W. Grimes  *
74858f0484fSRodney W. Grimes  * Return 0 if new item added, error code if memory couldn't be allocated.
74958f0484fSRodney W. Grimes  *
75058f0484fSRodney W. Grimes  * Invariant of the glob_t structure:
75158f0484fSRodney W. Grimes  *	Either gl_pathc is zero and gl_pathv is NULL; or gl_pathc > 0 and
75258f0484fSRodney W. Grimes  *	gl_pathv points to (gl_offs + gl_pathc + 1) items.
75358f0484fSRodney W. Grimes  */
75458f0484fSRodney W. Grimes static int
755*daab0b01SMarcel Moolenaar globextend(const Char *path, glob_t *pglob, struct glob_limit *limit)
75658f0484fSRodney W. Grimes {
757b231cb39SDavid E. O'Brien 	char **pathv;
7584b767fa6SAndrey A. Chernov 	size_t i, newsize, len;
75958f0484fSRodney W. Grimes 	char *copy;
76058f0484fSRodney W. Grimes 	const Char *p;
76158f0484fSRodney W. Grimes 
762*daab0b01SMarcel Moolenaar 	if ((pglob->gl_flags & GLOB_LIMIT) &&
763*daab0b01SMarcel Moolenaar 	    pglob->gl_matchc > limit->l_path_lim) {
76475dc5f1aSMike Heffner 		errno = 0;
76575dc5f1aSMike Heffner 		return (GLOB_NOSPACE);
76675dc5f1aSMike Heffner 	}
767813c96dbSJonathan Lemon 
76858f0484fSRodney W. Grimes 	newsize = sizeof(*pathv) * (2 + pglob->gl_pathc + pglob->gl_offs);
76943cc14e0SMarcel Moolenaar 	/* realloc(NULL, newsize) is equivalent to malloc(newsize). */
77043cc14e0SMarcel Moolenaar 	pathv = realloc((void *)pglob->gl_pathv, newsize);
771b628fac5SMarcel Moolenaar 	if (pathv == NULL)
77258f0484fSRodney W. Grimes 		return (GLOB_NOSPACE);
77358f0484fSRodney W. Grimes 
77458f0484fSRodney W. Grimes 	if (pglob->gl_pathv == NULL && pglob->gl_offs > 0) {
77558f0484fSRodney W. Grimes 		/* first time around -- clear initial gl_offs items */
77658f0484fSRodney W. Grimes 		pathv += pglob->gl_offs;
7774b767fa6SAndrey A. Chernov 		for (i = pglob->gl_offs + 1; --i > 0; )
77858f0484fSRodney W. Grimes 			*--pathv = NULL;
77958f0484fSRodney W. Grimes 	}
78058f0484fSRodney W. Grimes 	pglob->gl_pathv = pathv;
78158f0484fSRodney W. Grimes 
78258f0484fSRodney W. Grimes 	for (p = path; *p++;)
78358f0484fSRodney W. Grimes 		continue;
784e9346e01STim J. Robbins 	len = MB_CUR_MAX * (size_t)(p - path);	/* XXX overallocation */
785*daab0b01SMarcel Moolenaar 	limit->l_string_cnt += len;
786*daab0b01SMarcel Moolenaar 	if ((pglob->gl_flags & GLOB_LIMIT) &&
787*daab0b01SMarcel Moolenaar 	    limit->l_string_cnt >= GLOB_LIMIT_STRING) {
788*daab0b01SMarcel Moolenaar 		errno = 0;
789*daab0b01SMarcel Moolenaar 		return (GLOB_NOSPACE);
790*daab0b01SMarcel Moolenaar 	}
79127d52f69SPeter Wemm 	if ((copy = malloc(len)) != NULL) {
79227d52f69SPeter Wemm 		if (g_Ctoc(path, copy, len)) {
79376e2bc01SPeter Wemm 			free(copy);
79476e2bc01SPeter Wemm 			return (GLOB_NOSPACE);
79576e2bc01SPeter Wemm 		}
79658f0484fSRodney W. Grimes 		pathv[pglob->gl_offs + pglob->gl_pathc++] = copy;
79758f0484fSRodney W. Grimes 	}
79858f0484fSRodney W. Grimes 	pathv[pglob->gl_offs + pglob->gl_pathc] = NULL;
79958f0484fSRodney W. Grimes 	return (copy == NULL ? GLOB_NOSPACE : 0);
80058f0484fSRodney W. Grimes }
80158f0484fSRodney W. Grimes 
80258f0484fSRodney W. Grimes /*
80358f0484fSRodney W. Grimes  * pattern matching function for filenames.  Each occurrence of the *
80458f0484fSRodney W. Grimes  * pattern causes a recursion level.
80558f0484fSRodney W. Grimes  */
80658f0484fSRodney W. Grimes static int
8071cec70adSXin LI match(Char *name, Char *pat, Char *patend)
80858f0484fSRodney W. Grimes {
80958f0484fSRodney W. Grimes 	int ok, negate_range;
81058f0484fSRodney W. Grimes 	Char c, k;
8113c87aa1dSDavid Chisnall 	struct xlocale_collate *table =
8123c87aa1dSDavid Chisnall 		(struct xlocale_collate*)__get_locale()->components[XLC_COLLATE];
81358f0484fSRodney W. Grimes 
81458f0484fSRodney W. Grimes 	while (pat < patend) {
81558f0484fSRodney W. Grimes 		c = *pat++;
81658f0484fSRodney W. Grimes 		switch (c & M_MASK) {
81758f0484fSRodney W. Grimes 		case M_ALL:
81858f0484fSRodney W. Grimes 			if (pat == patend)
81958f0484fSRodney W. Grimes 				return (1);
82058f0484fSRodney W. Grimes 			do
82158f0484fSRodney W. Grimes 			    if (match(name, pat, patend))
82258f0484fSRodney W. Grimes 				    return (1);
82358f0484fSRodney W. Grimes 			while (*name++ != EOS);
82458f0484fSRodney W. Grimes 			return (0);
82558f0484fSRodney W. Grimes 		case M_ONE:
82658f0484fSRodney W. Grimes 			if (*name++ == EOS)
82758f0484fSRodney W. Grimes 				return (0);
82858f0484fSRodney W. Grimes 			break;
82958f0484fSRodney W. Grimes 		case M_SET:
83058f0484fSRodney W. Grimes 			ok = 0;
83158f0484fSRodney W. Grimes 			if ((k = *name++) == EOS)
83258f0484fSRodney W. Grimes 				return (0);
83358f0484fSRodney W. Grimes 			if ((negate_range = ((*pat & M_MASK) == M_NOT)) != EOS)
83458f0484fSRodney W. Grimes 				++pat;
83558f0484fSRodney W. Grimes 			while (((c = *pat++) & M_MASK) != M_END)
83658f0484fSRodney W. Grimes 				if ((*pat & M_MASK) == M_RNG) {
8373c87aa1dSDavid Chisnall 					if (table->__collate_load_error ?
83821d58869SAndrey A. Chernov 					    CHAR(c) <= CHAR(k) && CHAR(k) <= CHAR(pat[1]) :
8393c87aa1dSDavid Chisnall 					       __collate_range_cmp(table, CHAR(c), CHAR(k)) <= 0
8403c87aa1dSDavid Chisnall 					    && __collate_range_cmp(table, CHAR(k), CHAR(pat[1])) <= 0
841b92a8919SAndrey A. Chernov 					   )
84258f0484fSRodney W. Grimes 						ok = 1;
84358f0484fSRodney W. Grimes 					pat += 2;
84458f0484fSRodney W. Grimes 				} else if (c == k)
84558f0484fSRodney W. Grimes 					ok = 1;
84658f0484fSRodney W. Grimes 			if (ok == negate_range)
84758f0484fSRodney W. Grimes 				return (0);
84858f0484fSRodney W. Grimes 			break;
84958f0484fSRodney W. Grimes 		default:
85058f0484fSRodney W. Grimes 			if (*name++ != c)
85158f0484fSRodney W. Grimes 				return (0);
85258f0484fSRodney W. Grimes 			break;
85358f0484fSRodney W. Grimes 		}
85458f0484fSRodney W. Grimes 	}
85558f0484fSRodney W. Grimes 	return (*name == EOS);
85658f0484fSRodney W. Grimes }
85758f0484fSRodney W. Grimes 
85858f0484fSRodney W. Grimes /* Free allocated data belonging to a glob_t structure. */
85958f0484fSRodney W. Grimes void
8601cec70adSXin LI globfree(glob_t *pglob)
86158f0484fSRodney W. Grimes {
8624b767fa6SAndrey A. Chernov 	size_t i;
863b231cb39SDavid E. O'Brien 	char **pp;
86458f0484fSRodney W. Grimes 
86558f0484fSRodney W. Grimes 	if (pglob->gl_pathv != NULL) {
86658f0484fSRodney W. Grimes 		pp = pglob->gl_pathv + pglob->gl_offs;
86758f0484fSRodney W. Grimes 		for (i = pglob->gl_pathc; i--; ++pp)
86858f0484fSRodney W. Grimes 			if (*pp)
86958f0484fSRodney W. Grimes 				free(*pp);
87058f0484fSRodney W. Grimes 		free(pglob->gl_pathv);
87176e2bc01SPeter Wemm 		pglob->gl_pathv = NULL;
87258f0484fSRodney W. Grimes 	}
87358f0484fSRodney W. Grimes }
87458f0484fSRodney W. Grimes 
87558f0484fSRodney W. Grimes static DIR *
8761cec70adSXin LI g_opendir(Char *str, glob_t *pglob)
87758f0484fSRodney W. Grimes {
87858f0484fSRodney W. Grimes 	char buf[MAXPATHLEN];
87958f0484fSRodney W. Grimes 
88058f0484fSRodney W. Grimes 	if (!*str)
88158f0484fSRodney W. Grimes 		strcpy(buf, ".");
88276e2bc01SPeter Wemm 	else {
88327d52f69SPeter Wemm 		if (g_Ctoc(str, buf, sizeof(buf)))
88476e2bc01SPeter Wemm 			return (NULL);
88576e2bc01SPeter Wemm 	}
88658f0484fSRodney W. Grimes 
88758f0484fSRodney W. Grimes 	if (pglob->gl_flags & GLOB_ALTDIRFUNC)
88858f0484fSRodney W. Grimes 		return ((*pglob->gl_opendir)(buf));
88958f0484fSRodney W. Grimes 
89058f0484fSRodney W. Grimes 	return (opendir(buf));
89158f0484fSRodney W. Grimes }
89258f0484fSRodney W. Grimes 
89358f0484fSRodney W. Grimes static int
8941cec70adSXin LI g_lstat(Char *fn, struct stat *sb, glob_t *pglob)
89558f0484fSRodney W. Grimes {
89658f0484fSRodney W. Grimes 	char buf[MAXPATHLEN];
89758f0484fSRodney W. Grimes 
89827d52f69SPeter Wemm 	if (g_Ctoc(fn, buf, sizeof(buf))) {
89976e2bc01SPeter Wemm 		errno = ENAMETOOLONG;
90076e2bc01SPeter Wemm 		return (-1);
90176e2bc01SPeter Wemm 	}
90258f0484fSRodney W. Grimes 	if (pglob->gl_flags & GLOB_ALTDIRFUNC)
90358f0484fSRodney W. Grimes 		return((*pglob->gl_lstat)(buf, sb));
90458f0484fSRodney W. Grimes 	return (lstat(buf, sb));
90558f0484fSRodney W. Grimes }
90658f0484fSRodney W. Grimes 
90758f0484fSRodney W. Grimes static int
9081cec70adSXin LI g_stat(Char *fn, struct stat *sb, glob_t *pglob)
90958f0484fSRodney W. Grimes {
91058f0484fSRodney W. Grimes 	char buf[MAXPATHLEN];
91158f0484fSRodney W. Grimes 
91227d52f69SPeter Wemm 	if (g_Ctoc(fn, buf, sizeof(buf))) {
91376e2bc01SPeter Wemm 		errno = ENAMETOOLONG;
91476e2bc01SPeter Wemm 		return (-1);
91576e2bc01SPeter Wemm 	}
91658f0484fSRodney W. Grimes 	if (pglob->gl_flags & GLOB_ALTDIRFUNC)
91758f0484fSRodney W. Grimes 		return ((*pglob->gl_stat)(buf, sb));
91858f0484fSRodney W. Grimes 	return (stat(buf, sb));
91958f0484fSRodney W. Grimes }
92058f0484fSRodney W. Grimes 
92134a08754SMike Makonnen static const Char *
92234a08754SMike Makonnen g_strchr(const Char *str, wchar_t ch)
92358f0484fSRodney W. Grimes {
9241cec70adSXin LI 
92558f0484fSRodney W. Grimes 	do {
92658f0484fSRodney W. Grimes 		if (*str == ch)
92758f0484fSRodney W. Grimes 			return (str);
92858f0484fSRodney W. Grimes 	} while (*str++);
92958f0484fSRodney W. Grimes 	return (NULL);
93058f0484fSRodney W. Grimes }
93158f0484fSRodney W. Grimes 
93276e2bc01SPeter Wemm static int
9331cec70adSXin LI g_Ctoc(const Char *str, char *buf, size_t len)
93458f0484fSRodney W. Grimes {
935e9346e01STim J. Robbins 	mbstate_t mbs;
936e9346e01STim J. Robbins 	size_t clen;
93758f0484fSRodney W. Grimes 
938e9346e01STim J. Robbins 	memset(&mbs, 0, sizeof(mbs));
939e9346e01STim J. Robbins 	while (len >= MB_CUR_MAX) {
940e9346e01STim J. Robbins 		clen = wcrtomb(buf, *str, &mbs);
941e9346e01STim J. Robbins 		if (clen == (size_t)-1)
942e9346e01STim J. Robbins 			return (1);
943e9346e01STim J. Robbins 		if (*str == L'\0')
94476e2bc01SPeter Wemm 			return (0);
945e9346e01STim J. Robbins 		str++;
946e9346e01STim J. Robbins 		buf += clen;
947e9346e01STim J. Robbins 		len -= clen;
94858f0484fSRodney W. Grimes 	}
94927d52f69SPeter Wemm 	return (1);
95027d52f69SPeter Wemm }
95158f0484fSRodney W. Grimes 
95258f0484fSRodney W. Grimes #ifdef DEBUG
95358f0484fSRodney W. Grimes static void
9541cec70adSXin LI qprintf(const char *str, Char *s)
95558f0484fSRodney W. Grimes {
956b231cb39SDavid E. O'Brien 	Char *p;
95758f0484fSRodney W. Grimes 
95858f0484fSRodney W. Grimes 	(void)printf("%s:\n", str);
95958f0484fSRodney W. Grimes 	for (p = s; *p; p++)
96058f0484fSRodney W. Grimes 		(void)printf("%c", CHAR(*p));
96158f0484fSRodney W. Grimes 	(void)printf("\n");
96258f0484fSRodney W. Grimes 	for (p = s; *p; p++)
96358f0484fSRodney W. Grimes 		(void)printf("%c", *p & M_PROTECT ? '"' : ' ');
96458f0484fSRodney W. Grimes 	(void)printf("\n");
96558f0484fSRodney W. Grimes 	for (p = s; *p; p++)
96658f0484fSRodney W. Grimes 		(void)printf("%c", ismeta(*p) ? '_' : ' ');
96758f0484fSRodney W. Grimes 	(void)printf("\n");
96858f0484fSRodney W. Grimes }
96958f0484fSRodney W. Grimes #endif
970