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