• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 /*	$OpenBSD: glob.c,v 1.38 2011/09/22 06:27:29 djm Exp $ */
2 /*
3  * Copyright (c) 1989, 1993
4  *	The Regents of the University of California.  All rights reserved.
5  *
6  * This code is derived from software contributed to Berkeley by
7  * Guido van Rossum.
8  *
9  * Redistribution and use in source and binary forms, with or without
10  * modification, are permitted provided that the following conditions
11  * are met:
12  * 1. Redistributions of source code must retain the above copyright
13  *    notice, this list of conditions and the following disclaimer.
14  * 2. Redistributions in binary form must reproduce the above copyright
15  *    notice, this list of conditions and the following disclaimer in the
16  *    documentation and/or other materials provided with the distribution.
17  * 3. Neither the name of the University nor the names of its contributors
18  *    may be used to endorse or promote products derived from this software
19  *    without specific prior written permission.
20  *
21  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
22  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
23  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
24  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
25  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
26  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
27  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
28  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
29  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
30  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
31  * SUCH DAMAGE.
32  */
33 
34 /* OPENBSD ORIGINAL: lib/libc/gen/glob.c */
35 
36 /*
37  * glob(3) -- a superset of the one defined in POSIX 1003.2.
38  *
39  * The [!...] convention to negate a range is supported (SysV, Posix, ksh).
40  *
41  * Optional extra services, controlled by flags not defined by POSIX:
42  *
43  * GLOB_QUOTE:
44  *	Escaping convention: \ inhibits any special meaning the following
45  *	character might have (except \ at end of string is retained).
46  * GLOB_MAGCHAR:
47  *	Set in gl_flags if pattern contained a globbing character.
48  * GLOB_NOMAGIC:
49  *	Same as GLOB_NOCHECK, but it will only append pattern if it did
50  *	not contain any magic characters.  [Used in csh style globbing]
51  * GLOB_ALTDIRFUNC:
52  *	Use alternately specified directory access functions.
53  * GLOB_TILDE:
54  *	expand ~user/foo to the /home/dir/of/user/foo
55  * GLOB_BRACE:
56  *	expand {1,2}{a,b} to 1a 1b 2a 2b
57  * gl_matchc:
58  *	Number of matches in the current invocation of glob.
59  */
60 
61 #include "includes.h"
62 #include "glob.h"
63 
64 #include <sys/types.h>
65 #include <sys/stat.h>
66 
67 #include <dirent.h>
68 #include <ctype.h>
69 #include <errno.h>
70 #include <limits.h>
71 #include <pwd.h>
72 #include <stdlib.h>
73 #include <string.h>
74 #include <unistd.h>
75 
76 #if !defined(HAVE_GLOB) || !defined(GLOB_HAS_ALTDIRFUNC) || \
77     !defined(GLOB_HAS_GL_MATCHC) || !defined(GLOB_HAS_GL_STATV) || \
78     !defined(HAVE_DECL_GLOB_NOMATCH) || HAVE_DECL_GLOB_NOMATCH == 0 || \
79     defined(BROKEN_GLOB)
80 
81 #include "charclass.h"
82 
83 #define	DOLLAR		'$'
84 #define	DOT		'.'
85 #define	EOS		'\0'
86 #define	LBRACKET	'['
87 #define	NOT		'!'
88 #define	QUESTION	'?'
89 #define	QUOTE		'\\'
90 #define	RANGE		'-'
91 #define	RBRACKET	']'
92 #define	SEP		'/'
93 #define	STAR		'*'
94 #define	TILDE		'~'
95 #define	UNDERSCORE	'_'
96 #define	LBRACE		'{'
97 #define	RBRACE		'}'
98 #define	SLASH		'/'
99 #define	COMMA		','
100 
101 #ifndef DEBUG
102 
103 #define	M_QUOTE		0x8000
104 #define	M_PROTECT	0x4000
105 #define	M_MASK		0xffff
106 #define	M_ASCII		0x00ff
107 
108 typedef u_short Char;
109 
110 #else
111 
112 #define	M_QUOTE		0x80
113 #define	M_PROTECT	0x40
114 #define	M_MASK		0xff
115 #define	M_ASCII		0x7f
116 
117 typedef char Char;
118 
119 #endif
120 
121 
122 #define	CHAR(c)		((Char)((c)&M_ASCII))
123 #define	META(c)		((Char)((c)|M_QUOTE))
124 #define	M_ALL		META('*')
125 #define	M_END		META(']')
126 #define	M_NOT		META('!')
127 #define	M_ONE		META('?')
128 #define	M_RNG		META('-')
129 #define	M_SET		META('[')
130 #define	M_CLASS		META(':')
131 #define	ismeta(c)	(((c)&M_QUOTE) != 0)
132 
133 #define	GLOB_LIMIT_MALLOC	65536
134 #define	GLOB_LIMIT_STAT		128
135 #define	GLOB_LIMIT_READDIR	16384
136 
137 /* Limit of recursion during matching attempts. */
138 #define GLOB_LIMIT_RECUR	64
139 
140 struct glob_lim {
141 	size_t	glim_malloc;
142 	size_t	glim_stat;
143 	size_t	glim_readdir;
144 };
145 
146 struct glob_path_stat {
147 	char		*gps_path;
148 	struct stat	*gps_stat;
149 };
150 
151 static int	 compare(const void *, const void *);
152 static int	 compare_gps(const void *, const void *);
153 static int	 g_Ctoc(const Char *, char *, u_int);
154 static int	 g_lstat(Char *, struct stat *, glob_t *);
155 static DIR	*g_opendir(Char *, glob_t *);
156 static Char	*g_strchr(const Char *, int);
157 static int	 g_strncmp(const Char *, const char *, size_t);
158 static int	 g_stat(Char *, struct stat *, glob_t *);
159 static int	 glob0(const Char *, glob_t *, struct glob_lim *);
160 static int	 glob1(Char *, Char *, glob_t *, struct glob_lim *);
161 static int	 glob2(Char *, Char *, Char *, Char *, Char *, Char *,
162 		    glob_t *, struct glob_lim *);
163 static int	 glob3(Char *, Char *, Char *, Char *, Char *,
164 		    Char *, Char *, glob_t *, struct glob_lim *);
165 static int	 globextend(const Char *, glob_t *, struct glob_lim *,
166 		    struct stat *);
167 static const Char *
168 		 globtilde(const Char *, Char *, size_t, glob_t *);
169 static int	 globexp1(const Char *, glob_t *, struct glob_lim *);
170 static int	 globexp2(const Char *, const Char *, glob_t *,
171 		    struct glob_lim *);
172 static int	 match(Char *, Char *, Char *, int);
173 #ifdef DEBUG
174 static void	 qprintf(const char *, Char *);
175 #endif
176 
177 int
glob(const char * pattern,int flags,int (* errfunc)(const char *,int),glob_t * pglob)178 glob(const char *pattern, int flags, int (*errfunc)(const char *, int),
179     glob_t *pglob)
180 {
181 	const u_char *patnext;
182 	int c;
183 	Char *bufnext, *bufend, patbuf[MAXPATHLEN];
184 	struct glob_lim limit = { 0, 0, 0 };
185 
186 	if (strnlen(pattern, PATH_MAX) == PATH_MAX)
187 		return(GLOB_NOMATCH);
188 
189 	patnext = (u_char *) pattern;
190 	if (!(flags & GLOB_APPEND)) {
191 		pglob->gl_pathc = 0;
192 		pglob->gl_pathv = NULL;
193 		pglob->gl_statv = NULL;
194 		if (!(flags & GLOB_DOOFFS))
195 			pglob->gl_offs = 0;
196 	}
197 	pglob->gl_flags = flags & ~GLOB_MAGCHAR;
198 	pglob->gl_errfunc = errfunc;
199 	pglob->gl_matchc = 0;
200 
201 	if (pglob->gl_offs < 0 || pglob->gl_pathc < 0 ||
202 	    pglob->gl_offs >= INT_MAX || pglob->gl_pathc >= INT_MAX ||
203 	    pglob->gl_pathc >= INT_MAX - pglob->gl_offs - 1)
204 		return GLOB_NOSPACE;
205 
206 	bufnext = patbuf;
207 	bufend = bufnext + MAXPATHLEN - 1;
208 	if (flags & GLOB_NOESCAPE)
209 		while (bufnext < bufend && (c = *patnext++) != EOS)
210 			*bufnext++ = c;
211 	else {
212 		/* Protect the quoted characters. */
213 		while (bufnext < bufend && (c = *patnext++) != EOS)
214 			if (c == QUOTE) {
215 				if ((c = *patnext++) == EOS) {
216 					c = QUOTE;
217 					--patnext;
218 				}
219 				*bufnext++ = c | M_PROTECT;
220 			} else
221 				*bufnext++ = c;
222 	}
223 	*bufnext = EOS;
224 
225 	if (flags & GLOB_BRACE)
226 		return globexp1(patbuf, pglob, &limit);
227 	else
228 		return glob0(patbuf, pglob, &limit);
229 }
230 
231 /*
232  * Expand recursively a glob {} pattern. When there is no more expansion
233  * invoke the standard globbing routine to glob the rest of the magic
234  * characters
235  */
236 static int
globexp1(const Char * pattern,glob_t * pglob,struct glob_lim * limitp)237 globexp1(const Char *pattern, glob_t *pglob, struct glob_lim *limitp)
238 {
239 	const Char* ptr = pattern;
240 
241 	/* Protect a single {}, for find(1), like csh */
242 	if (pattern[0] == LBRACE && pattern[1] == RBRACE && pattern[2] == EOS)
243 		return glob0(pattern, pglob, limitp);
244 
245 	if ((ptr = (const Char *) g_strchr(ptr, LBRACE)) != NULL)
246 		return globexp2(ptr, pattern, pglob, limitp);
247 
248 	return glob0(pattern, pglob, limitp);
249 }
250 
251 
252 /*
253  * Recursive brace globbing helper. Tries to expand a single brace.
254  * If it succeeds then it invokes globexp1 with the new pattern.
255  * If it fails then it tries to glob the rest of the pattern and returns.
256  */
257 static int
globexp2(const Char * ptr,const Char * pattern,glob_t * pglob,struct glob_lim * limitp)258 globexp2(const Char *ptr, const Char *pattern, glob_t *pglob,
259     struct glob_lim *limitp)
260 {
261 	int     i, rv;
262 	Char   *lm, *ls;
263 	const Char *pe, *pm, *pl;
264 	Char    patbuf[MAXPATHLEN];
265 
266 	/* copy part up to the brace */
267 	for (lm = patbuf, pm = pattern; pm != ptr; *lm++ = *pm++)
268 		;
269 	*lm = EOS;
270 	ls = lm;
271 
272 	/* Find the balanced brace */
273 	for (i = 0, pe = ++ptr; *pe; pe++)
274 		if (*pe == LBRACKET) {
275 			/* Ignore everything between [] */
276 			for (pm = pe++; *pe != RBRACKET && *pe != EOS; pe++)
277 				;
278 			if (*pe == EOS) {
279 				/*
280 				 * We could not find a matching RBRACKET.
281 				 * Ignore and just look for RBRACE
282 				 */
283 				pe = pm;
284 			}
285 		} else if (*pe == LBRACE)
286 			i++;
287 		else if (*pe == RBRACE) {
288 			if (i == 0)
289 				break;
290 			i--;
291 		}
292 
293 	/* Non matching braces; just glob the pattern */
294 	if (i != 0 || *pe == EOS)
295 		return glob0(patbuf, pglob, limitp);
296 
297 	for (i = 0, pl = pm = ptr; pm <= pe; pm++) {
298 		switch (*pm) {
299 		case LBRACKET:
300 			/* Ignore everything between [] */
301 			for (pl = pm++; *pm != RBRACKET && *pm != EOS; pm++)
302 				;
303 			if (*pm == EOS) {
304 				/*
305 				 * We could not find a matching RBRACKET.
306 				 * Ignore and just look for RBRACE
307 				 */
308 				pm = pl;
309 			}
310 			break;
311 
312 		case LBRACE:
313 			i++;
314 			break;
315 
316 		case RBRACE:
317 			if (i) {
318 				i--;
319 				break;
320 			}
321 			/* FALLTHROUGH */
322 		case COMMA:
323 			if (i && *pm == COMMA)
324 				break;
325 			else {
326 				/* Append the current string */
327 				for (lm = ls; (pl < pm); *lm++ = *pl++)
328 					;
329 
330 				/*
331 				 * Append the rest of the pattern after the
332 				 * closing brace
333 				 */
334 				for (pl = pe + 1; (*lm++ = *pl++) != EOS; )
335 					;
336 
337 				/* Expand the current pattern */
338 #ifdef DEBUG
339 				qprintf("globexp2:", patbuf);
340 #endif
341 				rv = globexp1(patbuf, pglob, limitp);
342 				if (rv && rv != GLOB_NOMATCH)
343 					return rv;
344 
345 				/* move after the comma, to the next string */
346 				pl = pm + 1;
347 			}
348 			break;
349 
350 		default:
351 			break;
352 		}
353 	}
354 	return 0;
355 }
356 
357 
358 
359 /*
360  * expand tilde from the passwd file.
361  */
362 static const Char *
globtilde(const Char * pattern,Char * patbuf,size_t patbuf_len,glob_t * pglob)363 globtilde(const Char *pattern, Char *patbuf, size_t patbuf_len, glob_t *pglob)
364 {
365 	struct passwd *pwd;
366 	char *h;
367 	const Char *p;
368 	Char *b, *eb;
369 
370 	if (*pattern != TILDE || !(pglob->gl_flags & GLOB_TILDE))
371 		return pattern;
372 
373 	/* Copy up to the end of the string or / */
374 	eb = &patbuf[patbuf_len - 1];
375 	for (p = pattern + 1, h = (char *) patbuf;
376 	    h < (char *)eb && *p && *p != SLASH; *h++ = *p++)
377 		;
378 
379 	*h = EOS;
380 
381 #if 0
382 	if (h == (char *)eb)
383 		return what;
384 #endif
385 
386 	if (((char *) patbuf)[0] == EOS) {
387 		/*
388 		 * handle a plain ~ or ~/ by expanding $HOME
389 		 * first and then trying the password file
390 		 */
391 #if 0
392 		if (issetugid() != 0 || (h = getenv("HOME")) == NULL) {
393 #endif
394 		if ((getuid() != geteuid()) || (h = getenv("HOME")) == NULL) {
395 			if ((pwd = getpwuid(getuid())) == NULL)
396 				return pattern;
397 			else
398 				h = pwd->pw_dir;
399 		}
400 	} else {
401 		/*
402 		 * Expand a ~user
403 		 */
404 		if ((pwd = getpwnam((char*) patbuf)) == NULL)
405 			return pattern;
406 		else
407 			h = pwd->pw_dir;
408 	}
409 
410 	/* Copy the home directory */
411 	for (b = patbuf; b < eb && *h; *b++ = *h++)
412 		;
413 
414 	/* Append the rest of the pattern */
415 	while (b < eb && (*b++ = *p++) != EOS)
416 		;
417 	*b = EOS;
418 
419 	return patbuf;
420 }
421 
422 static int
423 g_strncmp(const Char *s1, const char *s2, size_t n)
424 {
425 	int rv = 0;
426 
427 	while (n--) {
428 		rv = *(Char *)s1 - *(const unsigned char *)s2++;
429 		if (rv)
430 			break;
431 		if (*s1++ == '\0')
432 			break;
433 	}
434 	return rv;
435 }
436 
437 static int
438 g_charclass(const Char **patternp, Char **bufnextp)
439 {
440 	const Char *pattern = *patternp + 1;
441 	Char *bufnext = *bufnextp;
442 	const Char *colon;
443 	struct cclass *cc;
444 	size_t len;
445 
446 	if ((colon = g_strchr(pattern, ':')) == NULL || colon[1] != ']')
447 		return 1;	/* not a character class */
448 
449 	len = (size_t)(colon - pattern);
450 	for (cc = cclasses; cc->name != NULL; cc++) {
451 		if (!g_strncmp(pattern, cc->name, len) && cc->name[len] == '\0')
452 			break;
453 	}
454 	if (cc->name == NULL)
455 		return -1;	/* invalid character class */
456 	*bufnext++ = M_CLASS;
457 	*bufnext++ = (Char)(cc - &cclasses[0]);
458 	*bufnextp = bufnext;
459 	*patternp += len + 3;
460 
461 	return 0;
462 }
463 
464 /*
465  * The main glob() routine: compiles the pattern (optionally processing
466  * quotes), calls glob1() to do the real pattern matching, and finally
467  * sorts the list (unless unsorted operation is requested).  Returns 0
468  * if things went well, nonzero if errors occurred.  It is not an error
469  * to find no matches.
470  */
471 static int
472 glob0(const Char *pattern, glob_t *pglob, struct glob_lim *limitp)
473 {
474 	const Char *qpatnext;
475 	int c, err, oldpathc;
476 	Char *bufnext, patbuf[MAXPATHLEN];
477 
478 	qpatnext = globtilde(pattern, patbuf, MAXPATHLEN, pglob);
479 	oldpathc = pglob->gl_pathc;
480 	bufnext = patbuf;
481 
482 	/* We don't need to check for buffer overflow any more. */
483 	while ((c = *qpatnext++) != EOS) {
484 		switch (c) {
485 		case LBRACKET:
486 			c = *qpatnext;
487 			if (c == NOT)
488 				++qpatnext;
489 			if (*qpatnext == EOS ||
490 			    g_strchr(qpatnext+1, RBRACKET) == NULL) {
491 				*bufnext++ = LBRACKET;
492 				if (c == NOT)
493 					--qpatnext;
494 				break;
495 			}
496 			*bufnext++ = M_SET;
497 			if (c == NOT)
498 				*bufnext++ = M_NOT;
499 			c = *qpatnext++;
500 			do {
501 				if (c == LBRACKET && *qpatnext == ':') {
502 					do {
503 						err = g_charclass(&qpatnext,
504 						    &bufnext);
505 						if (err)
506 							break;
507 						c = *qpatnext++;
508 					} while (c == LBRACKET && *qpatnext == ':');
509 					if (err == -1 &&
510 					    !(pglob->gl_flags & GLOB_NOCHECK))
511 						return GLOB_NOMATCH;
512 					if (c == RBRACKET)
513 						break;
514 				}
515 				*bufnext++ = CHAR(c);
516 				if (*qpatnext == RANGE &&
517 				    (c = qpatnext[1]) != RBRACKET) {
518 					*bufnext++ = M_RNG;
519 					*bufnext++ = CHAR(c);
520 					qpatnext += 2;
521 				}
522 			} while ((c = *qpatnext++) != RBRACKET);
523 			pglob->gl_flags |= GLOB_MAGCHAR;
524 			*bufnext++ = M_END;
525 			break;
526 		case QUESTION:
527 			pglob->gl_flags |= GLOB_MAGCHAR;
528 			*bufnext++ = M_ONE;
529 			break;
530 		case STAR:
531 			pglob->gl_flags |= GLOB_MAGCHAR;
532 			/* collapse adjacent stars to one,
533 			 * to avoid exponential behavior
534 			 */
535 			if (bufnext == patbuf || bufnext[-1] != M_ALL)
536 				*bufnext++ = M_ALL;
537 			break;
538 		default:
539 			*bufnext++ = CHAR(c);
540 			break;
541 		}
542 	}
543 	*bufnext = EOS;
544 #ifdef DEBUG
545 	qprintf("glob0:", patbuf);
546 #endif
547 
548 	if ((err = glob1(patbuf, patbuf+MAXPATHLEN-1, pglob, limitp)) != 0)
549 		return(err);
550 
551 	/*
552 	 * If there was no match we are going to append the pattern
553 	 * if GLOB_NOCHECK was specified or if GLOB_NOMAGIC was specified
554 	 * and the pattern did not contain any magic characters
555 	 * GLOB_NOMAGIC is there just for compatibility with csh.
556 	 */
557 	if (pglob->gl_pathc == oldpathc) {
558 		if ((pglob->gl_flags & GLOB_NOCHECK) ||
559 		    ((pglob->gl_flags & GLOB_NOMAGIC) &&
560 		    !(pglob->gl_flags & GLOB_MAGCHAR)))
561 			return(globextend(pattern, pglob, limitp, NULL));
562 		else
563 			return(GLOB_NOMATCH);
564 	}
565 	if (!(pglob->gl_flags & GLOB_NOSORT)) {
566 		if ((pglob->gl_flags & GLOB_KEEPSTAT)) {
567 			/* Keep the paths and stat info synced during sort */
568 			struct glob_path_stat *path_stat;
569 			int i;
570 			int n = pglob->gl_pathc - oldpathc;
571 			int o = pglob->gl_offs + oldpathc;
572 
573 			if ((path_stat = calloc(n, sizeof(*path_stat))) == NULL)
574 				return GLOB_NOSPACE;
575 			for (i = 0; i < n; i++) {
576 				path_stat[i].gps_path = pglob->gl_pathv[o + i];
577 				path_stat[i].gps_stat = pglob->gl_statv[o + i];
578 			}
579 			qsort(path_stat, n, sizeof(*path_stat), compare_gps);
580 			for (i = 0; i < n; i++) {
581 				pglob->gl_pathv[o + i] = path_stat[i].gps_path;
582 				pglob->gl_statv[o + i] = path_stat[i].gps_stat;
583 			}
584 			free(path_stat);
585 		} else {
586 			qsort(pglob->gl_pathv + pglob->gl_offs + oldpathc,
587 			    pglob->gl_pathc - oldpathc, sizeof(char *),
588 			    compare);
589 		}
590 	}
591 	return(0);
592 }
593 
594 static int
595 compare(const void *p, const void *q)
596 {
597 	return(strcmp(*(char **)p, *(char **)q));
598 }
599 
600 static int
601 compare_gps(const void *_p, const void *_q)
602 {
603 	const struct glob_path_stat *p = (const struct glob_path_stat *)_p;
604 	const struct glob_path_stat *q = (const struct glob_path_stat *)_q;
605 
606 	return(strcmp(p->gps_path, q->gps_path));
607 }
608 
609 static int
610 glob1(Char *pattern, Char *pattern_last, glob_t *pglob, struct glob_lim *limitp)
611 {
612 	Char pathbuf[MAXPATHLEN];
613 
614 	/* A null pathname is invalid -- POSIX 1003.1 sect. 2.4. */
615 	if (*pattern == EOS)
616 		return(0);
617 	return(glob2(pathbuf, pathbuf+MAXPATHLEN-1,
618 	    pathbuf, pathbuf+MAXPATHLEN-1,
619 	    pattern, pattern_last, pglob, limitp));
620 }
621 
622 /*
623  * The functions glob2 and glob3 are mutually recursive; there is one level
624  * of recursion for each segment in the pattern that contains one or more
625  * meta characters.
626  */
627 static int
628 glob2(Char *pathbuf, Char *pathbuf_last, Char *pathend, Char *pathend_last,
629     Char *pattern, Char *pattern_last, glob_t *pglob, struct glob_lim *limitp)
630 {
631 	struct stat sb;
632 	Char *p, *q;
633 	int anymeta;
634 
635 	/*
636 	 * Loop over pattern segments until end of pattern or until
637 	 * segment with meta character found.
638 	 */
639 	for (anymeta = 0;;) {
640 		if (*pattern == EOS) {		/* End of pattern? */
641 			*pathend = EOS;
642 			if (g_lstat(pathbuf, &sb, pglob))
643 				return(0);
644 
645 			if ((pglob->gl_flags & GLOB_LIMIT) &&
646 			    limitp->glim_stat++ >= GLOB_LIMIT_STAT) {
647 				errno = 0;
648 				*pathend++ = SEP;
649 				*pathend = EOS;
650 				return(GLOB_NOSPACE);
651 			}
652 
653 			if (((pglob->gl_flags & GLOB_MARK) &&
654 			    pathend[-1] != SEP) && (S_ISDIR(sb.st_mode) ||
655 			    (S_ISLNK(sb.st_mode) &&
656 			    (g_stat(pathbuf, &sb, pglob) == 0) &&
657 			    S_ISDIR(sb.st_mode)))) {
658 				if (pathend+1 > pathend_last)
659 					return (1);
660 				*pathend++ = SEP;
661 				*pathend = EOS;
662 			}
663 			++pglob->gl_matchc;
664 			return(globextend(pathbuf, pglob, limitp, &sb));
665 		}
666 
667 		/* Find end of next segment, copy tentatively to pathend. */
668 		q = pathend;
669 		p = pattern;
670 		while (*p != EOS && *p != SEP) {
671 			if (ismeta(*p))
672 				anymeta = 1;
673 			if (q+1 > pathend_last)
674 				return (1);
675 			*q++ = *p++;
676 		}
677 
678 		if (!anymeta) {		/* No expansion, do next segment. */
679 			pathend = q;
680 			pattern = p;
681 			while (*pattern == SEP) {
682 				if (pathend+1 > pathend_last)
683 					return (1);
684 				*pathend++ = *pattern++;
685 			}
686 		} else
687 			/* Need expansion, recurse. */
688 			return(glob3(pathbuf, pathbuf_last, pathend,
689 			    pathend_last, pattern, p, pattern_last,
690 			    pglob, limitp));
691 	}
692 	/* NOTREACHED */
693 }
694 
695 static int
696 glob3(Char *pathbuf, Char *pathbuf_last, Char *pathend, Char *pathend_last,
697     Char *pattern, Char *restpattern, Char *restpattern_last, glob_t *pglob,
698     struct glob_lim *limitp)
699 {
700 	struct dirent *dp;
701 	DIR *dirp;
702 	int err;
703 	char buf[MAXPATHLEN];
704 
705 	/*
706 	 * The readdirfunc declaration can't be prototyped, because it is
707 	 * assigned, below, to two functions which are prototyped in glob.h
708 	 * and dirent.h as taking pointers to differently typed opaque
709 	 * structures.
710 	 */
711 	struct dirent *(*readdirfunc)(void *);
712 
713 	if (pathend > pathend_last)
714 		return (1);
715 	*pathend = EOS;
716 	errno = 0;
717 
718 	if ((dirp = g_opendir(pathbuf, pglob)) == NULL) {
719 		/* TODO: don't call for ENOENT or ENOTDIR? */
720 		if (pglob->gl_errfunc) {
721 			if (g_Ctoc(pathbuf, buf, sizeof(buf)))
722 				return(GLOB_ABORTED);
723 			if (pglob->gl_errfunc(buf, errno) ||
724 			    pglob->gl_flags & GLOB_ERR)
725 				return(GLOB_ABORTED);
726 		}
727 		return(0);
728 	}
729 
730 	err = 0;
731 
732 	/* Search directory for matching names. */
733 	if (pglob->gl_flags & GLOB_ALTDIRFUNC)
734 		readdirfunc = pglob->gl_readdir;
735 	else
736 		readdirfunc = (struct dirent *(*)(void *))readdir;
737 	while ((dp = (*readdirfunc)(dirp))) {
738 		u_char *sc;
739 		Char *dc;
740 
741 		if ((pglob->gl_flags & GLOB_LIMIT) &&
742 		    limitp->glim_readdir++ >= GLOB_LIMIT_READDIR) {
743 			errno = 0;
744 			*pathend++ = SEP;
745 			*pathend = EOS;
746 			err = GLOB_NOSPACE;
747 			break;
748 		}
749 
750 		/* Initial DOT must be matched literally. */
751 		if (dp->d_name[0] == DOT && *pattern != DOT)
752 			continue;
753 		dc = pathend;
754 		sc = (u_char *) dp->d_name;
755 		while (dc < pathend_last && (*dc++ = *sc++) != EOS)
756 			;
757 		if (dc >= pathend_last) {
758 			*dc = EOS;
759 			err = 1;
760 			break;
761 		}
762 
763 		if (!match(pathend, pattern, restpattern, GLOB_LIMIT_RECUR)) {
764 			*pathend = EOS;
765 			continue;
766 		}
767 		err = glob2(pathbuf, pathbuf_last, --dc, pathend_last,
768 		    restpattern, restpattern_last, pglob, limitp);
769 		if (err)
770 			break;
771 	}
772 
773 	if (pglob->gl_flags & GLOB_ALTDIRFUNC)
774 		(*pglob->gl_closedir)(dirp);
775 	else
776 		closedir(dirp);
777 	return(err);
778 }
779 
780 
781 /*
782  * Extend the gl_pathv member of a glob_t structure to accommodate a new item,
783  * add the new item, and update gl_pathc.
784  *
785  * This assumes the BSD realloc, which only copies the block when its size
786  * crosses a power-of-two boundary; for v7 realloc, this would cause quadratic
787  * behavior.
788  *
789  * Return 0 if new item added, error code if memory couldn't be allocated.
790  *
791  * Invariant of the glob_t structure:
792  *	Either gl_pathc is zero and gl_pathv is NULL; or gl_pathc > 0 and
793  *	gl_pathv points to (gl_offs + gl_pathc + 1) items.
794  */
795 static int
796 globextend(const Char *path, glob_t *pglob, struct glob_lim *limitp,
797     struct stat *sb)
798 {
799 	char **pathv;
800 	ssize_t i;
801 	size_t newn, len;
802 	char *copy = NULL;
803 	const Char *p;
804 	struct stat **statv;
805 
806 	newn = 2 + pglob->gl_pathc + pglob->gl_offs;
807 	if (pglob->gl_offs >= INT_MAX ||
808 	    pglob->gl_pathc >= INT_MAX ||
809 	    newn >= INT_MAX ||
810 	    SIZE_MAX / sizeof(*pathv) <= newn ||
811 	    SIZE_MAX / sizeof(*statv) <= newn) {
812  nospace:
813 		for (i = pglob->gl_offs; i < (ssize_t)(newn - 2); i++) {
814 			if (pglob->gl_pathv && pglob->gl_pathv[i])
815 				free(pglob->gl_pathv[i]);
816 			if ((pglob->gl_flags & GLOB_KEEPSTAT) != 0 &&
817 			    pglob->gl_pathv && pglob->gl_pathv[i])
818 				free(pglob->gl_statv[i]);
819 		}
820 		if (pglob->gl_pathv) {
821 			free(pglob->gl_pathv);
822 			pglob->gl_pathv = NULL;
823 		}
824 		if (pglob->gl_statv) {
825 			free(pglob->gl_statv);
826 			pglob->gl_statv = NULL;
827 		}
828 		return(GLOB_NOSPACE);
829 	}
830 
831 	pathv = realloc(pglob->gl_pathv, newn * sizeof(*pathv));
832 	if (pathv == NULL)
833 		goto nospace;
834 	if (pglob->gl_pathv == NULL && pglob->gl_offs > 0) {
835 		/* first time around -- clear initial gl_offs items */
836 		pathv += pglob->gl_offs;
837 		for (i = pglob->gl_offs; --i >= 0; )
838 			*--pathv = NULL;
839 	}
840 	pglob->gl_pathv = pathv;
841 
842 	if ((pglob->gl_flags & GLOB_KEEPSTAT) != 0) {
843 		statv = realloc(pglob->gl_statv, newn * sizeof(*statv));
844 		if (statv == NULL)
845 			goto nospace;
846 		if (pglob->gl_statv == NULL && pglob->gl_offs > 0) {
847 			/* first time around -- clear initial gl_offs items */
848 			statv += pglob->gl_offs;
849 			for (i = pglob->gl_offs; --i >= 0; )
850 				*--statv = NULL;
851 		}
852 		pglob->gl_statv = statv;
853 		if (sb == NULL)
854 			statv[pglob->gl_offs + pglob->gl_pathc] = NULL;
855 		else {
856 			limitp->glim_malloc += sizeof(**statv);
857 			if ((pglob->gl_flags & GLOB_LIMIT) &&
858 			    limitp->glim_malloc >= GLOB_LIMIT_MALLOC) {
859 				errno = 0;
860 				return(GLOB_NOSPACE);
861 			}
862 			if ((statv[pglob->gl_offs + pglob->gl_pathc] =
863 			    malloc(sizeof(**statv))) == NULL)
864 				goto copy_error;
865 			memcpy(statv[pglob->gl_offs + pglob->gl_pathc], sb,
866 			    sizeof(*sb));
867 		}
868 		statv[pglob->gl_offs + pglob->gl_pathc + 1] = NULL;
869 	}
870 
871 	for (p = path; *p++;)
872 		;
873 	len = (size_t)(p - path);
874 	limitp->glim_malloc += len;
875 	if ((copy = malloc(len)) != NULL) {
876 		if (g_Ctoc(path, copy, len)) {
877 			free(copy);
878 			return(GLOB_NOSPACE);
879 		}
880 		pathv[pglob->gl_offs + pglob->gl_pathc++] = copy;
881 	}
882 	pathv[pglob->gl_offs + pglob->gl_pathc] = NULL;
883 
884 	if ((pglob->gl_flags & GLOB_LIMIT) &&
885 	    (newn * sizeof(*pathv)) + limitp->glim_malloc >
886 	    GLOB_LIMIT_MALLOC) {
887 		errno = 0;
888 		return(GLOB_NOSPACE);
889 	}
890  copy_error:
891 	return(copy == NULL ? GLOB_NOSPACE : 0);
892 }
893 
894 
895 /*
896  * pattern matching function for filenames.  Each occurrence of the *
897  * pattern causes a recursion level.
898  */
899 static int
900 match(Char *name, Char *pat, Char *patend, int recur)
901 {
902 	int ok, negate_range;
903 	Char c, k;
904 
905 	if (recur-- == 0)
906 		return(GLOB_NOSPACE);
907 
908 	while (pat < patend) {
909 		c = *pat++;
910 		switch (c & M_MASK) {
911 		case M_ALL:
912 			while (pat < patend && (*pat & M_MASK) == M_ALL)
913 				pat++;	/* eat consecutive '*' */
914 			if (pat == patend)
915 				return(1);
916 			do {
917 			    if (match(name, pat, patend, recur))
918 				    return(1);
919 			} while (*name++ != EOS);
920 			return(0);
921 		case M_ONE:
922 			if (*name++ == EOS)
923 				return(0);
924 			break;
925 		case M_SET:
926 			ok = 0;
927 			if ((k = *name++) == EOS)
928 				return(0);
929 			if ((negate_range = ((*pat & M_MASK) == M_NOT)) != EOS)
930 				++pat;
931 			while (((c = *pat++) & M_MASK) != M_END) {
932 				if ((c & M_MASK) == M_CLASS) {
933 					Char idx = *pat & M_MASK;
934 					if (idx < NCCLASSES &&
935 					    cclasses[idx].isctype(k))
936 						ok = 1;
937 					++pat;
938 				}
939 				if ((*pat & M_MASK) == M_RNG) {
940 					if (c <= k && k <= pat[1])
941 						ok = 1;
942 					pat += 2;
943 				} else if (c == k)
944 					ok = 1;
945 			}
946 			if (ok == negate_range)
947 				return(0);
948 			break;
949 		default:
950 			if (*name++ != c)
951 				return(0);
952 			break;
953 		}
954 	}
955 	return(*name == EOS);
956 }
957 
958 /* Free allocated data belonging to a glob_t structure. */
959 void
960 globfree(glob_t *pglob)
961 {
962 	int i;
963 	char **pp;
964 
965 	if (pglob->gl_pathv != NULL) {
966 		pp = pglob->gl_pathv + pglob->gl_offs;
967 		for (i = pglob->gl_pathc; i--; ++pp)
968 			if (*pp)
969 				free(*pp);
970 		free(pglob->gl_pathv);
971 		pglob->gl_pathv = NULL;
972 	}
973 	if (pglob->gl_statv != NULL) {
974 		for (i = 0; i < pglob->gl_pathc; i++) {
975 			if (pglob->gl_statv[i] != NULL)
976 				free(pglob->gl_statv[i]);
977 		}
978 		free(pglob->gl_statv);
979 		pglob->gl_statv = NULL;
980 	}
981 }
982 
983 static DIR *
984 g_opendir(Char *str, glob_t *pglob)
985 {
986 	char buf[MAXPATHLEN];
987 
988 	if (!*str)
989 		strlcpy(buf, ".", sizeof buf);
990 	else {
991 		if (g_Ctoc(str, buf, sizeof(buf)))
992 			return(NULL);
993 	}
994 
995 	if (pglob->gl_flags & GLOB_ALTDIRFUNC)
996 		return((*pglob->gl_opendir)(buf));
997 
998 	return(opendir(buf));
999 }
1000 
1001 static int
1002 g_lstat(Char *fn, struct stat *sb, glob_t *pglob)
1003 {
1004 	char buf[MAXPATHLEN];
1005 
1006 	if (g_Ctoc(fn, buf, sizeof(buf)))
1007 		return(-1);
1008 	if (pglob->gl_flags & GLOB_ALTDIRFUNC)
1009 		return((*pglob->gl_lstat)(buf, sb));
1010 	return(lstat(buf, sb));
1011 }
1012 
1013 static int
1014 g_stat(Char *fn, struct stat *sb, glob_t *pglob)
1015 {
1016 	char buf[MAXPATHLEN];
1017 
1018 	if (g_Ctoc(fn, buf, sizeof(buf)))
1019 		return(-1);
1020 	if (pglob->gl_flags & GLOB_ALTDIRFUNC)
1021 		return((*pglob->gl_stat)(buf, sb));
1022 	return(stat(buf, sb));
1023 }
1024 
1025 static Char *
1026 g_strchr(const Char *str, int ch)
1027 {
1028 	do {
1029 		if (*str == ch)
1030 			return ((Char *)str);
1031 	} while (*str++);
1032 	return (NULL);
1033 }
1034 
1035 static int
1036 g_Ctoc(const Char *str, char *buf, u_int len)
1037 {
1038 
1039 	while (len--) {
1040 		if ((*buf++ = *str++) == EOS)
1041 			return (0);
1042 	}
1043 	return (1);
1044 }
1045 
1046 #ifdef DEBUG
1047 static void
1048 qprintf(const char *str, Char *s)
1049 {
1050 	Char *p;
1051 
1052 	(void)printf("%s:\n", str);
1053 	for (p = s; *p; p++)
1054 		(void)printf("%c", CHAR(*p));
1055 	(void)printf("\n");
1056 	for (p = s; *p; p++)
1057 		(void)printf("%c", *p & M_PROTECT ? '"' : ' ');
1058 	(void)printf("\n");
1059 	for (p = s; *p; p++)
1060 		(void)printf("%c", ismeta(*p) ? '_' : ' ');
1061 	(void)printf("\n");
1062 }
1063 #endif
1064 
1065 #endif /* !defined(HAVE_GLOB) || !defined(GLOB_HAS_ALTDIRFUNC) ||
1066           !defined(GLOB_HAS_GL_MATCHC) || !defined(GLOB_HAS_GL_STATV) */
1067