1/*	$OpenBSD: glob.c,v 1.49 2020/04/21 08:25:22 dtucker 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#include "glob.h"
63
64#include <sys/types.h>
65#include <sys/stat.h>
66
67#include <dirent.h>
68#include <ctype.h>
69#include <errno.h>
70#include <limits.h>
71#include <pwd.h>
72#include <stdlib.h>
73#ifdef HAVE_STDINT_H
74#include <stdint.h>
75#endif
76#include <string.h>
77#include <unistd.h>
78
79#if !defined(HAVE_GLOB) || !defined(GLOB_HAS_ALTDIRFUNC) || \
80    !defined(GLOB_HAS_GL_MATCHC) || !defined(GLOB_HAS_GL_STATV) || \
81    !defined(HAVE_DECL_GLOB_NOMATCH) || HAVE_DECL_GLOB_NOMATCH == 0 || \
82    defined(BROKEN_GLOB)
83
84#include "charclass.h"
85
86#ifdef TILDE
87# undef TILDE
88#endif
89
90#define	DOLLAR		'$'
91#define	DOT		'.'
92#define	EOS		'\0'
93#define	LBRACKET	'['
94#define	NOT		'!'
95#define	QUESTION	'?'
96#define	QUOTE		'\\'
97#define	RANGE		'-'
98#define	RBRACKET	']'
99#define	SEP		'/'
100#define	STAR		'*'
101#define	TILDE		'~'
102#define	UNDERSCORE	'_'
103#define	LBRACE		'{'
104#define	RBRACE		'}'
105#define	SLASH		'/'
106#define	COMMA		','
107
108#ifndef DEBUG
109
110#define	M_QUOTE		0x8000
111#define	M_PROTECT	0x4000
112#define	M_MASK		0xffff
113#define	M_ASCII		0x00ff
114
115typedef u_short Char;
116
117#else
118
119#define	M_QUOTE		0x80
120#define	M_PROTECT	0x40
121#define	M_MASK		0xff
122#define	M_ASCII		0x7f
123
124typedef char Char;
125
126#endif
127
128
129#define	CHAR(c)		((Char)((c)&M_ASCII))
130#define	META(c)		((Char)((c)|M_QUOTE))
131#define	M_ALL		META('*')
132#define	M_END		META(']')
133#define	M_NOT		META('!')
134#define	M_ONE		META('?')
135#define	M_RNG		META('-')
136#define	M_SET		META('[')
137#define	M_CLASS		META(':')
138#define	ismeta(c)	(((c)&M_QUOTE) != 0)
139
140#define	GLOB_LIMIT_MALLOC	65536
141#define	GLOB_LIMIT_STAT		2048
142#define	GLOB_LIMIT_READDIR	16384
143
144struct glob_lim {
145	size_t	glim_malloc;
146	size_t	glim_stat;
147	size_t	glim_readdir;
148};
149
150struct glob_path_stat {
151	char		*gps_path;
152	struct stat	*gps_stat;
153};
154
155static int	 compare(const void *, const void *);
156static int	 compare_gps(const void *, const void *);
157static int	 g_Ctoc(const Char *, char *, size_t);
158static int	 g_lstat(Char *, struct stat *, glob_t *);
159static DIR	*g_opendir(Char *, glob_t *);
160static Char	*g_strchr(const Char *, int);
161static int	 g_strncmp(const Char *, const char *, size_t);
162static int	 g_stat(Char *, struct stat *, glob_t *);
163static int	 glob0(const Char *, glob_t *, struct glob_lim *);
164static int	 glob1(Char *, Char *, glob_t *, struct glob_lim *);
165static int	 glob2(Char *, Char *, Char *, Char *, Char *, Char *,
166		    glob_t *, struct glob_lim *);
167static int	 glob3(Char *, Char *, Char *, Char *, Char *,
168		    Char *, Char *, glob_t *, struct glob_lim *);
169static int	 globextend(const Char *, glob_t *, struct glob_lim *,
170		    struct stat *);
171static const Char *
172		 globtilde(const Char *, Char *, size_t, glob_t *);
173static int	 globexp1(const Char *, glob_t *, struct glob_lim *);
174static int	 globexp2(const Char *, const Char *, glob_t *,
175		    struct glob_lim *);
176static int	 match(Char *, Char *, Char *);
177#ifdef DEBUG
178static void	 qprintf(const char *, Char *);
179#endif
180
181int
182glob(const char *pattern, int flags, int (*errfunc)(const char *, int),
183    glob_t *pglob)
184{
185	const u_char *patnext;
186	int c;
187	Char *bufnext, *bufend, patbuf[PATH_MAX];
188	struct glob_lim limit = { 0, 0, 0 };
189
190	patnext = (u_char *) pattern;
191	if (!(flags & GLOB_APPEND)) {
192		pglob->gl_pathc = 0;
193		pglob->gl_pathv = NULL;
194		pglob->gl_statv = NULL;
195		if (!(flags & GLOB_DOOFFS))
196			pglob->gl_offs = 0;
197	}
198	pglob->gl_flags = flags & ~GLOB_MAGCHAR;
199	pglob->gl_errfunc = errfunc;
200	pglob->gl_matchc = 0;
201
202	if (strnlen(pattern, PATH_MAX) == PATH_MAX)
203		return(GLOB_NOMATCH);
204
205	if (pglob->gl_offs >= SSIZE_MAX || pglob->gl_pathc >= SSIZE_MAX ||
206	    pglob->gl_pathc >= SSIZE_MAX - pglob->gl_offs - 1)
207		return GLOB_NOSPACE;
208
209	bufnext = patbuf;
210	bufend = bufnext + PATH_MAX - 1;
211	if (flags & GLOB_NOESCAPE)
212		while (bufnext < bufend && (c = *patnext++) != EOS)
213			*bufnext++ = c;
214	else {
215		/* Protect the quoted characters. */
216		while (bufnext < bufend && (c = *patnext++) != EOS)
217			if (c == QUOTE) {
218				if ((c = *patnext++) == EOS) {
219					c = QUOTE;
220					--patnext;
221				}
222				*bufnext++ = c | M_PROTECT;
223			} else
224				*bufnext++ = c;
225	}
226	*bufnext = EOS;
227
228	if (flags & GLOB_BRACE)
229		return globexp1(patbuf, pglob, &limit);
230	else
231		return glob0(patbuf, pglob, &limit);
232}
233
234/*
235 * Expand recursively a glob {} pattern. When there is no more expansion
236 * invoke the standard globbing routine to glob the rest of the magic
237 * characters
238 */
239static int
240globexp1(const Char *pattern, glob_t *pglob, struct glob_lim *limitp)
241{
242	const Char* ptr = pattern;
243
244	/* Protect a single {}, for find(1), like csh */
245	if (pattern[0] == LBRACE && pattern[1] == RBRACE && pattern[2] == EOS)
246		return glob0(pattern, pglob, limitp);
247
248	if ((ptr = (const Char *) g_strchr(ptr, LBRACE)) != NULL)
249		return globexp2(ptr, pattern, pglob, limitp);
250
251	return glob0(pattern, pglob, limitp);
252}
253
254
255/*
256 * Recursive brace globbing helper. Tries to expand a single brace.
257 * If it succeeds then it invokes globexp1 with the new pattern.
258 * If it fails then it tries to glob the rest of the pattern and returns.
259 */
260static int
261globexp2(const Char *ptr, const Char *pattern, glob_t *pglob,
262    struct glob_lim *limitp)
263{
264	int     i, rv;
265	Char   *lm, *ls;
266	const Char *pe, *pm, *pl;
267	Char    patbuf[PATH_MAX];
268
269	/* copy part up to the brace */
270	for (lm = patbuf, pm = pattern; pm != ptr; *lm++ = *pm++)
271		;
272	*lm = EOS;
273	ls = lm;
274
275	/* Find the balanced brace */
276	for (i = 0, pe = ++ptr; *pe; pe++)
277		if (*pe == LBRACKET) {
278			/* Ignore everything between [] */
279			for (pm = pe++; *pe != RBRACKET && *pe != EOS; pe++)
280				;
281			if (*pe == EOS) {
282				/*
283				 * We could not find a matching RBRACKET.
284				 * Ignore and just look for RBRACE
285				 */
286				pe = pm;
287			}
288		} else if (*pe == LBRACE)
289			i++;
290		else if (*pe == RBRACE) {
291			if (i == 0)
292				break;
293			i--;
294		}
295
296	/* Non matching braces; just glob the pattern */
297	if (i != 0 || *pe == EOS)
298		return glob0(patbuf, pglob, limitp);
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				;
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					;
332
333				/*
334				 * Append the rest of the pattern after the
335				 * closing brace
336				 */
337				for (pl = pe + 1; (*lm++ = *pl++) != EOS; )
338					;
339
340				/* Expand the current pattern */
341#ifdef DEBUG
342				qprintf("globexp2:", patbuf);
343#endif
344				rv = globexp1(patbuf, pglob, limitp);
345				if (rv && rv != GLOB_NOMATCH)
346					return rv;
347
348				/* move after the comma, to the next string */
349				pl = pm + 1;
350			}
351			break;
352
353		default:
354			break;
355		}
356	}
357	return 0;
358}
359
360
361
362/*
363 * expand tilde from the passwd file.
364 */
365static const Char *
366globtilde(const Char *pattern, Char *patbuf, size_t patbuf_len, glob_t *pglob)
367{
368	struct passwd *pwd;
369	char *h;
370	const Char *p;
371	Char *b, *eb;
372
373	if (*pattern != TILDE || !(pglob->gl_flags & GLOB_TILDE))
374		return pattern;
375
376	/* Copy up to the end of the string or / */
377	eb = &patbuf[patbuf_len - 1];
378	for (p = pattern + 1, h = (char *) patbuf;
379	    h < (char *)eb && *p && *p != SLASH; *h++ = *p++)
380		;
381
382	*h = EOS;
383
384#if 0
385	if (h == (char *)eb)
386		return what;
387#endif
388
389	if (((char *) patbuf)[0] == EOS) {
390		/*
391		 * handle a plain ~ or ~/ by expanding $HOME
392		 * first and then trying the password file
393		 */
394#if 0
395		if (issetugid() != 0 || (h = getenv("HOME")) == NULL) {
396#endif
397		if ((getuid() != geteuid()) || (h = getenv("HOME")) == NULL) {
398			if ((pwd = getpwuid(getuid())) == NULL)
399				return pattern;
400			else
401				h = pwd->pw_dir;
402		}
403	} else {
404		/*
405		 * Expand a ~user
406		 */
407		if ((pwd = getpwnam((char*) patbuf)) == NULL)
408			return pattern;
409		else
410			h = pwd->pw_dir;
411	}
412
413	/* Copy the home directory */
414	for (b = patbuf; b < eb && *h; *b++ = *h++)
415		;
416
417	/* Append the rest of the pattern */
418	while (b < eb && (*b++ = *p++) != EOS)
419		;
420	*b = EOS;
421
422	return patbuf;
423}
424
425static int
426g_strncmp(const Char *s1, const char *s2, size_t n)
427{
428	int rv = 0;
429
430	while (n--) {
431		rv = *(Char *)s1 - *(const unsigned char *)s2++;
432		if (rv)
433			break;
434		if (*s1++ == '\0')
435			break;
436	}
437	return rv;
438}
439
440static int
441g_charclass(const Char **patternp, Char **bufnextp)
442{
443	const Char *pattern = *patternp + 1;
444	Char *bufnext = *bufnextp;
445	const Char *colon;
446	struct cclass *cc;
447	size_t len;
448
449	if ((colon = g_strchr(pattern, ':')) == NULL || colon[1] != ']')
450		return 1;	/* not a character class */
451
452	len = (size_t)(colon - pattern);
453	for (cc = cclasses; cc->name != NULL; cc++) {
454		if (!g_strncmp(pattern, cc->name, len) && cc->name[len] == '\0')
455			break;
456	}
457	if (cc->name == NULL)
458		return -1;	/* invalid character class */
459	*bufnext++ = M_CLASS;
460	*bufnext++ = (Char)(cc - &cclasses[0]);
461	*bufnextp = bufnext;
462	*patternp += len + 3;
463
464	return 0;
465}
466
467/*
468 * The main glob() routine: compiles the pattern (optionally processing
469 * quotes), calls glob1() to do the real pattern matching, and finally
470 * sorts the list (unless unsorted operation is requested).  Returns 0
471 * if things went well, nonzero if errors occurred.  It is not an error
472 * to find no matches.
473 */
474static int
475glob0(const Char *pattern, glob_t *pglob, struct glob_lim *limitp)
476{
477	const Char *qpatnext;
478	int c, err;
479	size_t oldpathc;
480	Char *bufnext, patbuf[PATH_MAX];
481
482	qpatnext = globtilde(pattern, patbuf, PATH_MAX, pglob);
483	oldpathc = pglob->gl_pathc;
484	bufnext = patbuf;
485
486	/* We don't need to check for buffer overflow any more. */
487	while ((c = *qpatnext++) != EOS) {
488		switch (c) {
489		case LBRACKET:
490			c = *qpatnext;
491			if (c == NOT)
492				++qpatnext;
493			if (*qpatnext == EOS ||
494			    g_strchr(qpatnext+1, RBRACKET) == NULL) {
495				*bufnext++ = LBRACKET;
496				if (c == NOT)
497					--qpatnext;
498				break;
499			}
500			*bufnext++ = M_SET;
501			if (c == NOT)
502				*bufnext++ = M_NOT;
503			c = *qpatnext++;
504			do {
505				if (c == LBRACKET && *qpatnext == ':') {
506					do {
507						err = g_charclass(&qpatnext,
508						    &bufnext);
509						if (err)
510							break;
511						c = *qpatnext++;
512					} while (c == LBRACKET && *qpatnext == ':');
513					if (err == -1 &&
514					    !(pglob->gl_flags & GLOB_NOCHECK))
515						return GLOB_NOMATCH;
516					if (c == RBRACKET)
517						break;
518				}
519				*bufnext++ = CHAR(c);
520				if (*qpatnext == RANGE &&
521				    (c = qpatnext[1]) != RBRACKET) {
522					*bufnext++ = M_RNG;
523					*bufnext++ = CHAR(c);
524					qpatnext += 2;
525				}
526			} while ((c = *qpatnext++) != RBRACKET);
527			pglob->gl_flags |= GLOB_MAGCHAR;
528			*bufnext++ = M_END;
529			break;
530		case QUESTION:
531			pglob->gl_flags |= GLOB_MAGCHAR;
532			*bufnext++ = M_ONE;
533			break;
534		case STAR:
535			pglob->gl_flags |= GLOB_MAGCHAR;
536			/* collapse adjacent stars to one,
537			 * to avoid exponential behavior
538			 */
539			if (bufnext == patbuf || bufnext[-1] != M_ALL)
540				*bufnext++ = M_ALL;
541			break;
542		default:
543			*bufnext++ = CHAR(c);
544			break;
545		}
546	}
547	*bufnext = EOS;
548#ifdef DEBUG
549	qprintf("glob0:", patbuf);
550#endif
551
552	if ((err = glob1(patbuf, patbuf+PATH_MAX-1, pglob, limitp)) != 0)
553		return(err);
554
555	/*
556	 * If there was no match we are going to append the pattern
557	 * if GLOB_NOCHECK was specified or if GLOB_NOMAGIC was specified
558	 * and the pattern did not contain any magic characters
559	 * GLOB_NOMAGIC is there just for compatibility with csh.
560	 */
561	if (pglob->gl_pathc == oldpathc) {
562		if ((pglob->gl_flags & GLOB_NOCHECK) ||
563		    ((pglob->gl_flags & GLOB_NOMAGIC) &&
564		    !(pglob->gl_flags & GLOB_MAGCHAR)))
565			return(globextend(pattern, pglob, limitp, NULL));
566		else
567			return(GLOB_NOMATCH);
568	}
569	if (!(pglob->gl_flags & GLOB_NOSORT)) {
570		if ((pglob->gl_flags & GLOB_KEEPSTAT)) {
571			/* Keep the paths and stat info synced during sort */
572			struct glob_path_stat *path_stat;
573			size_t i;
574			size_t n = pglob->gl_pathc - oldpathc;
575			size_t o = pglob->gl_offs + oldpathc;
576
577			if ((path_stat = calloc(n, sizeof(*path_stat))) == NULL)
578				return GLOB_NOSPACE;
579			for (i = 0; i < n; i++) {
580				path_stat[i].gps_path = pglob->gl_pathv[o + i];
581				path_stat[i].gps_stat = pglob->gl_statv[o + i];
582			}
583			qsort(path_stat, n, sizeof(*path_stat), compare_gps);
584			for (i = 0; i < n; i++) {
585				pglob->gl_pathv[o + i] = path_stat[i].gps_path;
586				pglob->gl_statv[o + i] = path_stat[i].gps_stat;
587			}
588			free(path_stat);
589		} else {
590			qsort(pglob->gl_pathv + pglob->gl_offs + oldpathc,
591			    pglob->gl_pathc - oldpathc, sizeof(char *),
592			    compare);
593		}
594	}
595	return(0);
596}
597
598static int
599compare(const void *p, const void *q)
600{
601	return(strcmp(*(char **)p, *(char **)q));
602}
603
604static int
605compare_gps(const void *_p, const void *_q)
606{
607	const struct glob_path_stat *p = (const struct glob_path_stat *)_p;
608	const struct glob_path_stat *q = (const struct glob_path_stat *)_q;
609
610	return(strcmp(p->gps_path, q->gps_path));
611}
612
613static int
614glob1(Char *pattern, Char *pattern_last, glob_t *pglob, struct glob_lim *limitp)
615{
616	Char pathbuf[PATH_MAX];
617
618	/* A null pathname is invalid -- POSIX 1003.1 sect. 2.4. */
619	if (*pattern == EOS)
620		return(0);
621	return(glob2(pathbuf, pathbuf+PATH_MAX-1,
622	    pathbuf, pathbuf+PATH_MAX-1,
623	    pattern, pattern_last, pglob, limitp));
624}
625
626/*
627 * The functions glob2 and glob3 are mutually recursive; there is one level
628 * of recursion for each segment in the pattern that contains one or more
629 * meta characters.
630 */
631static int
632glob2(Char *pathbuf, Char *pathbuf_last, Char *pathend, Char *pathend_last,
633    Char *pattern, Char *pattern_last, glob_t *pglob, struct glob_lim *limitp)
634{
635	struct stat sb;
636	Char *p, *q;
637	int anymeta;
638
639	/*
640	 * Loop over pattern segments until end of pattern or until
641	 * segment with meta character found.
642	 */
643	for (anymeta = 0;;) {
644		if (*pattern == EOS) {		/* End of pattern? */
645			*pathend = EOS;
646
647			if ((pglob->gl_flags & GLOB_LIMIT) &&
648			    limitp->glim_stat++ >= GLOB_LIMIT_STAT) {
649				errno = 0;
650				*pathend++ = SEP;
651				*pathend = EOS;
652				return(GLOB_NOSPACE);
653			}
654			if (g_lstat(pathbuf, &sb, pglob))
655				return(0);
656
657			if (((pglob->gl_flags & GLOB_MARK) &&
658			    pathend[-1] != SEP) && (S_ISDIR(sb.st_mode) ||
659			    (S_ISLNK(sb.st_mode) &&
660			    (g_stat(pathbuf, &sb, pglob) == 0) &&
661			    S_ISDIR(sb.st_mode)))) {
662				if (pathend+1 > pathend_last)
663					return (1);
664				*pathend++ = SEP;
665				*pathend = EOS;
666			}
667			++pglob->gl_matchc;
668			return(globextend(pathbuf, pglob, limitp, &sb));
669		}
670
671		/* Find end of next segment, copy tentatively to pathend. */
672		q = pathend;
673		p = pattern;
674		while (*p != EOS && *p != SEP) {
675			if (ismeta(*p))
676				anymeta = 1;
677			if (q+1 > pathend_last)
678				return (1);
679			*q++ = *p++;
680		}
681
682		if (!anymeta) {		/* No expansion, do next segment. */
683			pathend = q;
684			pattern = p;
685			while (*pattern == SEP) {
686				if (pathend+1 > pathend_last)
687					return (1);
688				*pathend++ = *pattern++;
689			}
690		} else
691			/* Need expansion, recurse. */
692			return(glob3(pathbuf, pathbuf_last, pathend,
693			    pathend_last, pattern, p, pattern_last,
694			    pglob, limitp));
695	}
696	/* NOTREACHED */
697}
698
699static int
700glob3(Char *pathbuf, Char *pathbuf_last, Char *pathend, Char *pathend_last,
701    Char *pattern, Char *restpattern, Char *restpattern_last, glob_t *pglob,
702    struct glob_lim *limitp)
703{
704	struct dirent *dp;
705	DIR *dirp;
706	int err;
707	char buf[PATH_MAX];
708
709	/*
710	 * The readdirfunc declaration can't be prototyped, because it is
711	 * assigned, below, to two functions which are prototyped in glob.h
712	 * and dirent.h as taking pointers to differently typed opaque
713	 * structures.
714	 */
715	struct dirent *(*readdirfunc)(void *);
716
717	if (pathend > pathend_last)
718		return (1);
719	*pathend = EOS;
720	errno = 0;
721
722	if ((dirp = g_opendir(pathbuf, pglob)) == NULL) {
723		/* TODO: don't call for ENOENT or ENOTDIR? */
724		if (pglob->gl_errfunc) {
725			if (g_Ctoc(pathbuf, buf, sizeof(buf)))
726				return(GLOB_ABORTED);
727			if (pglob->gl_errfunc(buf, errno) ||
728			    pglob->gl_flags & GLOB_ERR)
729				return(GLOB_ABORTED);
730		}
731		return(0);
732	}
733
734	err = 0;
735
736	/* Search directory for matching names. */
737	if (pglob->gl_flags & GLOB_ALTDIRFUNC)
738		readdirfunc = pglob->gl_readdir;
739	else
740		readdirfunc = (struct dirent *(*)(void *))readdir;
741	while ((dp = (*readdirfunc)(dirp))) {
742		u_char *sc;
743		Char *dc;
744
745		if ((pglob->gl_flags & GLOB_LIMIT) &&
746		    limitp->glim_readdir++ >= GLOB_LIMIT_READDIR) {
747			errno = 0;
748			*pathend++ = SEP;
749			*pathend = EOS;
750			err = GLOB_NOSPACE;
751			break;
752		}
753
754		/* Initial DOT must be matched literally. */
755		if (dp->d_name[0] == DOT && *pattern != DOT)
756			continue;
757		dc = pathend;
758		sc = (u_char *) dp->d_name;
759		while (dc < pathend_last && (*dc++ = *sc++) != EOS)
760			;
761		if (dc >= pathend_last) {
762			*dc = EOS;
763			err = 1;
764			break;
765		}
766
767		if (!match(pathend, pattern, restpattern)) {
768			*pathend = EOS;
769			continue;
770		}
771		err = glob2(pathbuf, pathbuf_last, --dc, pathend_last,
772		    restpattern, restpattern_last, pglob, limitp);
773		if (err)
774			break;
775	}
776
777	if (pglob->gl_flags & GLOB_ALTDIRFUNC)
778		(*pglob->gl_closedir)(dirp);
779	else
780		closedir(dirp);
781	return(err);
782}
783
784
785/*
786 * Extend the gl_pathv member of a glob_t structure to accommodate a new item,
787 * add the new item, and update gl_pathc.
788 *
789 * This assumes the BSD realloc, which only copies the block when its size
790 * crosses a power-of-two boundary; for v7 realloc, this would cause quadratic
791 * behavior.
792 *
793 * Return 0 if new item added, error code if memory couldn't be allocated.
794 *
795 * Invariant of the glob_t structure:
796 *	Either gl_pathc is zero and gl_pathv is NULL; or gl_pathc > 0 and
797 *	gl_pathv points to (gl_offs + gl_pathc + 1) items.
798 */
799static int
800globextend(const Char *path, glob_t *pglob, struct glob_lim *limitp,
801    struct stat *sb)
802{
803	char **pathv;
804	size_t i, newn, len;
805	char *copy = NULL;
806	const Char *p;
807	struct stat **statv;
808
809	newn = 2 + pglob->gl_pathc + pglob->gl_offs;
810	if (pglob->gl_offs >= SSIZE_MAX ||
811	    pglob->gl_pathc >= SSIZE_MAX ||
812	    newn >= SSIZE_MAX ||
813	    SIZE_MAX / sizeof(*pathv) <= newn ||
814	    SIZE_MAX / sizeof(*statv) <= newn) {
815 nospace:
816		for (i = pglob->gl_offs; i < newn - 2; i++) {
817			if (pglob->gl_pathv && pglob->gl_pathv[i])
818				free(pglob->gl_pathv[i]);
819			if ((pglob->gl_flags & GLOB_KEEPSTAT) != 0 &&
820			    pglob->gl_pathv && pglob->gl_pathv[i])
821				free(pglob->gl_statv[i]);
822		}
823		free(pglob->gl_pathv);
824		pglob->gl_pathv = NULL;
825		free(pglob->gl_statv);
826		pglob->gl_statv = NULL;
827		return(GLOB_NOSPACE);
828	}
829
830	pathv = reallocarray(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; i--)
837			*--pathv = NULL;
838	}
839	pglob->gl_pathv = pathv;
840
841	if ((pglob->gl_flags & GLOB_KEEPSTAT) != 0) {
842		statv = reallocarray(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; i--)
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 an iteration.
897 *
898 * Note, this function differs from the original as per the discussion
899 * here: https://research.swtch.com/glob
900 *
901 * Basically we removed the recursion and made it use the algorithm
902 * from Russ Cox to not go quadratic on cases like a file called
903 * ("a" x 100) . "x" matched against a pattern like "a*a*a*a*a*a*a*y".
904 */
905static int
906match(Char *name, Char *pat, Char *patend)
907{
908	int ok, negate_range;
909	Char c, k;
910	Char *nextp = NULL;
911	Char *nextn = NULL;
912
913loop:
914	while (pat < patend) {
915		c = *pat++;
916		switch (c & M_MASK) {
917		case M_ALL:
918			while (pat < patend && (*pat & M_MASK) == M_ALL)
919				pat++;	/* eat consecutive '*' */
920			if (pat == patend)
921				return(1);
922			if (*name == EOS)
923				return(0);
924			nextn = name + 1;
925			nextp = pat - 1;
926			break;
927		case M_ONE:
928			if (*name++ == EOS)
929				goto fail;
930			break;
931		case M_SET:
932			ok = 0;
933			if ((k = *name++) == EOS)
934				goto fail;
935			if ((negate_range = ((*pat & M_MASK) == M_NOT)) != EOS)
936				++pat;
937			while (((c = *pat++) & M_MASK) != M_END) {
938				if ((c & M_MASK) == M_CLASS) {
939					Char idx = *pat & M_MASK;
940					if (idx < NCCLASSES &&
941					    cclasses[idx].isctype(k))
942						ok = 1;
943					++pat;
944				}
945				if ((*pat & M_MASK) == M_RNG) {
946					if (c <= k && k <= pat[1])
947						ok = 1;
948					pat += 2;
949				} else if (c == k)
950					ok = 1;
951			}
952			if (ok == negate_range)
953				goto fail;
954			break;
955		default:
956			if (*name++ != c)
957				goto fail;
958			break;
959		}
960	}
961	if (*name == EOS)
962		return(1);
963
964fail:
965	if (nextn) {
966		pat = nextp;
967		name = nextn;
968		goto loop;
969	}
970	return(0);
971}
972
973/* Free allocated data belonging to a glob_t structure. */
974void
975globfree(glob_t *pglob)
976{
977	size_t i;
978	char **pp;
979
980	if (pglob->gl_pathv != NULL) {
981		pp = pglob->gl_pathv + pglob->gl_offs;
982		for (i = pglob->gl_pathc; i--; ++pp)
983			free(*pp);
984		free(pglob->gl_pathv);
985		pglob->gl_pathv = NULL;
986	}
987	if (pglob->gl_statv != NULL) {
988		for (i = 0; i < pglob->gl_pathc; i++) {
989			free(pglob->gl_statv[i]);
990		}
991		free(pglob->gl_statv);
992		pglob->gl_statv = NULL;
993	}
994}
995
996static DIR *
997g_opendir(Char *str, glob_t *pglob)
998{
999	char buf[PATH_MAX];
1000
1001	if (!*str)
1002		strlcpy(buf, ".", sizeof buf);
1003	else {
1004		if (g_Ctoc(str, buf, sizeof(buf)))
1005			return(NULL);
1006	}
1007
1008	if (pglob->gl_flags & GLOB_ALTDIRFUNC)
1009		return((*pglob->gl_opendir)(buf));
1010
1011	return(opendir(buf));
1012}
1013
1014static int
1015g_lstat(Char *fn, struct stat *sb, glob_t *pglob)
1016{
1017	char buf[PATH_MAX];
1018
1019	if (g_Ctoc(fn, buf, sizeof(buf)))
1020		return(-1);
1021	if (pglob->gl_flags & GLOB_ALTDIRFUNC)
1022		return((*pglob->gl_lstat)(buf, sb));
1023	return(lstat(buf, sb));
1024}
1025
1026static int
1027g_stat(Char *fn, struct stat *sb, glob_t *pglob)
1028{
1029	char buf[PATH_MAX];
1030
1031	if (g_Ctoc(fn, buf, sizeof(buf)))
1032		return(-1);
1033	if (pglob->gl_flags & GLOB_ALTDIRFUNC)
1034		return((*pglob->gl_stat)(buf, sb));
1035	return(stat(buf, sb));
1036}
1037
1038static Char *
1039g_strchr(const Char *str, int ch)
1040{
1041	do {
1042		if (*str == ch)
1043			return ((Char *)str);
1044	} while (*str++);
1045	return (NULL);
1046}
1047
1048static int
1049g_Ctoc(const Char *str, char *buf, size_t len)
1050{
1051
1052	while (len--) {
1053		if ((*buf++ = *str++) == EOS)
1054			return (0);
1055	}
1056	return (1);
1057}
1058
1059#ifdef DEBUG
1060static void
1061qprintf(const char *str, Char *s)
1062{
1063	Char *p;
1064
1065	(void)printf("%s:\n", str);
1066	for (p = s; *p; p++)
1067		(void)printf("%c", CHAR(*p));
1068	(void)printf("\n");
1069	for (p = s; *p; p++)
1070		(void)printf("%c", *p & M_PROTECT ? '"' : ' ');
1071	(void)printf("\n");
1072	for (p = s; *p; p++)
1073		(void)printf("%c", ismeta(*p) ? '_' : ' ');
1074	(void)printf("\n");
1075}
1076#endif
1077
1078#endif /* !defined(HAVE_GLOB) || !defined(GLOB_HAS_ALTDIRFUNC) ||
1079          !defined(GLOB_HAS_GL_MATCHC) || !defined(GLOB_HAS_GL_STATV) */
1080