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