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