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