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