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