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