GCC Code Coverage Report
Directory: ./ Exec Total Coverage
File: lib/libc/gen/glob.c Lines: 0 401 0.0 %
Date: 2017-11-13 Branches: 0 401 0.0 %

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