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