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