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