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