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