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
107typedef 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
116typedef 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
139struct glob_lim {
140	size_t	glim_malloc;
141	size_t	glim_stat;
142	size_t	glim_readdir;
143};
144
145struct glob_path_stat {
146	char		*gps_path;
147	struct stat	*gps_stat;
148};
149
150static int	 compare(const void *, const void *);
151static int	 compare_gps(const void *, const void *);
152static int	 g_Ctoc(const Char *, char *, u_int);
153static int	 g_lstat(Char *, struct stat *, glob_t *);
154static DIR	*g_opendir(Char *, glob_t *);
155static Char	*g_strchr(const Char *, int);
156static int	 g_strncmp(const Char *, const char *, size_t);
157static int	 g_stat(Char *, struct stat *, glob_t *);
158static int	 glob0(const Char *, glob_t *, struct glob_lim *);
159static int	 glob1(Char *, Char *, glob_t *, struct glob_lim *);
160static int	 glob2(Char *, Char *, Char *, Char *, Char *, Char *,
161		    glob_t *, struct glob_lim *);
162static int	 glob3(Char *, Char *, Char *, Char *, Char *,
163		    Char *, Char *, glob_t *, struct glob_lim *);
164static int	 globextend(const Char *, glob_t *, struct glob_lim *,
165		    struct stat *);
166static const Char *
167		 globtilde(const Char *, Char *, size_t, glob_t *);
168static int	 globexp1(const Char *, glob_t *, struct glob_lim *);
169static int	 globexp2(const Char *, const Char *, glob_t *,
170		    struct glob_lim *);
171static int	 match(Char *, Char *, Char *, int);
172#ifdef DEBUG
173static void	 qprintf(const char *, Char *);
174#endif
175
176int
177glob(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 */
235static int
236globexp1(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 */
256static int
257globexp2(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 */
361static const Char *
362globtilde(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
421static int
422g_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
436static int
437g_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 */
470static int
471glob0(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
593static int
594compare(const void *p, const void *q)
595{
596	return(strcmp(*(char **)p, *(char **)q));
597}
598
599static int
600compare_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
608static int
609glob1(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 */
626static int
627glob2(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
694static int
695glob3(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 */
794static int
795globextend(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 */
898static int
899match(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. */
958void
959globfree(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
982static DIR *
983g_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
1000static int
1001g_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
1012static int
1013g_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
1024static Char *
1025g_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
1034static int
1035g_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
1046static void
1047qprintf(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