2 * Copyright (c) 1989, 1993
3 * The Regents of the University of California. All rights reserved.
5 * This code is derived from software contributed to Berkeley by
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
11 * 1. Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 * 2. Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in the
15 * documentation and/or other materials provided with the distribution.
16 * 3. All advertising materials mentioning features or use of this software
17 * must display the following acknowledgement:
18 * This product includes software developed by the University of
19 * California, Berkeley and its contributors.
20 * 4. 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.
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
38 * glob(3) -- a superset of the one defined in POSIX 1003.2.
40 * The [!...] convention to negate a range is supported (SysV, Posix, ksh).
42 * Optional extra services, controlled by flags not defined by POSIX:
45 * Escaping convention: \ inhibits any special meaning the following
46 * character might have (except \ at end of string is retained).
48 * Set in gl_flags if pattern contained a globbing character.
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]
53 * Use alternately specified directory access functions.
55 * expand ~user/foo to the /home/dir/of/user/foo
57 * expand {1,2}{a,b} to 1a 1b 2a 2b
59 * Number of matches in the current invocation of glob.
66 #ifdef HAVE_SYS_PARAM_H
67 #include <sys/param.h>
69 #ifdef HAVE_SYS_TYPES_H
70 #include <sys/types.h>
72 #ifdef HAVE_SYS_STAT_H
98 #define ARG_MAX _POSIX_ARG_MAX
101 #define CHAR_DOLLAR '$'
103 #define CHAR_EOS '\0'
104 #define CHAR_LBRACKET '['
106 #define CHAR_QUESTION '?'
107 #define CHAR_QUOTE '\\'
108 #define CHAR_RANGE '-'
109 #define CHAR_RBRACKET ']'
111 #define CHAR_STAR '*'
112 #define CHAR_TILDE '~'
113 #define CHAR_UNDERSCORE '_'
114 #define CHAR_LBRACE '{'
115 #define CHAR_RBRACE '}'
116 #define CHAR_SLASH '/'
117 #define CHAR_COMMA ','
121 #define M_QUOTE 0x8000
122 #define M_PROTECT 0x4000
123 #define M_MASK 0xffff
124 #define M_ASCII 0x00ff
126 typedef u_short Char
;
131 #define M_PROTECT 0x40
140 #define CHAR(c) ((Char)((c)&M_ASCII))
141 #define META(c) ((Char)((c)|M_QUOTE))
142 #define M_ALL META('*')
143 #define M_END META(']')
144 #define M_NOT META('!')
145 #define M_ONE META('?')
146 #define M_RNG META('-')
147 #define M_SET META('[')
148 #define ismeta(c) (((c)&M_QUOTE) != 0)
151 static int compare (const void *, const void *);
152 static void g_Ctoc (const Char
*, char *);
153 static int g_lstat (Char
*, struct stat
*, glob_t
*);
154 static DIR *g_opendir (Char
*, glob_t
*);
155 static Char
*g_strchr (const Char
*, int);
157 static Char
*g_strcat (Char
*, const Char
*);
159 static int g_stat (Char
*, struct stat
*, glob_t
*);
160 static int glob0 (const Char
*, glob_t
*);
161 static int glob1 (Char
*, glob_t
*, size_t *);
162 static int glob2 (Char
*, Char
*, Char
*, glob_t
*, size_t *);
163 static int glob3 (Char
*, Char
*, Char
*, Char
*, glob_t
*, size_t *);
164 static int globextend (const Char
*, glob_t
*, size_t *);
165 static const Char
* globtilde (const Char
*, Char
*, glob_t
*);
166 static int globexp1 (const Char
*, glob_t
*);
167 static int globexp2 (const Char
*, const Char
*, glob_t
*, int *);
168 static int match (Char
*, Char
*, Char
*);
170 static void qprintf (const char *, Char
*);
174 glob(const char *pattern
,
176 int (*errfunc
)(const char *, int),
179 const u_char
*patnext
;
181 Char
*bufnext
, *bufend
, patbuf
[MaxPathLen
+1];
183 patnext
= (const u_char
*) pattern
;
184 if (!(flags
& GLOB_APPEND
)) {
186 pglob
->gl_pathv
= NULL
;
187 if (!(flags
& GLOB_DOOFFS
))
190 pglob
->gl_flags
= flags
& ~GLOB_MAGCHAR
;
191 pglob
->gl_errfunc
= errfunc
;
192 pglob
->gl_matchc
= 0;
195 bufend
= bufnext
+ MaxPathLen
;
196 if (flags
& GLOB_QUOTE
) {
197 /* Protect the quoted characters. */
198 while (bufnext
< bufend
&& (c
= *patnext
++) != CHAR_EOS
)
199 if (c
== CHAR_QUOTE
) {
200 if ((c
= *patnext
++) == CHAR_EOS
) {
204 *bufnext
++ = c
| M_PROTECT
;
210 while (bufnext
< bufend
&& (c
= *patnext
++) != CHAR_EOS
)
214 if (flags
& GLOB_BRACE
)
215 return globexp1(patbuf
, pglob
);
217 return glob0(patbuf
, pglob
);
221 * Expand recursively a glob {} pattern. When there is no more expansion
222 * invoke the standard globbing routine to glob the rest of the magic
225 static int globexp1(const Char
*pattern
, glob_t
*pglob
)
227 const Char
* ptr
= pattern
;
230 /* Protect a single {}, for find(1), like csh */
231 if (pattern
[0] == CHAR_LBRACE
&& pattern
[1] == CHAR_RBRACE
&& pattern
[2] == CHAR_EOS
)
232 return glob0(pattern
, pglob
);
234 while ((ptr
= (const Char
*) g_strchr(ptr
, CHAR_LBRACE
)) != NULL
)
235 if (!globexp2(ptr
, pattern
, pglob
, &rv
))
238 return glob0(pattern
, pglob
);
243 * Recursive brace globbing helper. Tries to expand a single brace.
244 * If it succeeds then it invokes globexp1 with the new pattern.
245 * If it fails then it tries to glob the rest of the pattern and returns.
247 static int globexp2(const Char
*ptr
, const Char
*pattern
,
248 glob_t
*pglob
, int *rv
)
252 const Char
*pe
, *pm
, *pl
;
253 Char patbuf
[MaxPathLen
+ 1];
255 /* copy part up to the brace */
256 for (lm
= patbuf
, pm
= pattern
; pm
!= ptr
; *lm
++ = *pm
++)
260 /* Find the balanced brace */
261 for (i
= 0, pe
= ++ptr
; *pe
; pe
++)
262 if (*pe
== CHAR_LBRACKET
) {
263 /* Ignore everything between [] */
264 for (pm
= pe
++; *pe
!= CHAR_RBRACKET
&& *pe
!= CHAR_EOS
; pe
++)
266 if (*pe
== CHAR_EOS
) {
268 * We could not find a matching CHAR_RBRACKET.
269 * Ignore and just look for CHAR_RBRACE
274 else if (*pe
== CHAR_LBRACE
)
276 else if (*pe
== CHAR_RBRACE
) {
282 /* Non matching braces; just glob the pattern */
283 if (i
!= 0 || *pe
== CHAR_EOS
) {
284 *rv
= glob0(patbuf
, pglob
);
288 for (i
= 0, pl
= pm
= ptr
; pm
<= pe
; pm
++)
291 /* Ignore everything between [] */
292 for (pl
= pm
++; *pm
!= CHAR_RBRACKET
&& *pm
!= CHAR_EOS
; pm
++)
294 if (*pm
== CHAR_EOS
) {
296 * We could not find a matching CHAR_RBRACKET.
297 * Ignore and just look for CHAR_RBRACE
314 if (i
&& *pm
== CHAR_COMMA
)
317 /* Append the current string */
318 for (lm
= ls
; (pl
< pm
); *lm
++ = *pl
++)
321 * Append the rest of the pattern after the
324 for (pl
= pe
+ 1; (*lm
++ = *pl
++) != CHAR_EOS
;)
327 /* Expand the current pattern */
329 qprintf("globexp2:", patbuf
);
331 *rv
= globexp1(patbuf
, pglob
);
333 /* move after the comma, to the next string */
348 * expand tilde from the passwd file.
351 globtilde(const Char
*pattern
, Char
*patbuf
, glob_t
*pglob
)
358 if (*pattern
!= CHAR_TILDE
|| !(pglob
->gl_flags
& GLOB_TILDE
))
361 /* Copy up to the end of the string or / */
362 for (p
= pattern
+ 1, h
= (char *) patbuf
; *p
&& *p
!= CHAR_SLASH
;
368 if (((char *) patbuf
)[0] == CHAR_EOS
) {
370 * handle a plain ~ or ~/ by expanding $HOME
371 * first and then trying the password file
373 if ((h
= getenv("HOME")) == NULL
) {
374 if ((pwd
= k_getpwuid(getuid())) == NULL
)
384 if ((pwd
= k_getpwnam((char*) patbuf
)) == NULL
)
390 /* Copy the home directory */
391 for (b
= patbuf
; *h
; *b
++ = *h
++)
394 /* Append the rest of the pattern */
395 while ((*b
++ = *p
++) != CHAR_EOS
)
403 * The main glob() routine: compiles the pattern (optionally processing
404 * quotes), calls glob1() to do the real pattern matching, and finally
405 * sorts the list (unless unsorted operation is requested). Returns 0
406 * if things went well, nonzero if errors occurred. It is not an error
407 * to find no matches.
410 glob0(const Char
*pattern
, glob_t
*pglob
)
412 const Char
*qpatnext
;
413 int c
, err
, oldpathc
;
414 Char
*bufnext
, patbuf
[MaxPathLen
+1];
417 qpatnext
= globtilde(pattern
, patbuf
, pglob
);
418 oldpathc
= pglob
->gl_pathc
;
421 /* We don't need to check for buffer overflow any more. */
422 while ((c
= *qpatnext
++) != CHAR_EOS
) {
428 if (*qpatnext
== CHAR_EOS
||
429 g_strchr(qpatnext
+1, CHAR_RBRACKET
) == NULL
) {
430 *bufnext
++ = CHAR_LBRACKET
;
440 *bufnext
++ = CHAR(c
);
441 if (*qpatnext
== CHAR_RANGE
&&
442 (c
= qpatnext
[1]) != CHAR_RBRACKET
) {
444 *bufnext
++ = CHAR(c
);
447 } while ((c
= *qpatnext
++) != CHAR_RBRACKET
);
448 pglob
->gl_flags
|= GLOB_MAGCHAR
;
452 pglob
->gl_flags
|= GLOB_MAGCHAR
;
456 pglob
->gl_flags
|= GLOB_MAGCHAR
;
457 /* collapse adjacent stars to one,
458 * to avoid exponential behavior
460 if (bufnext
== patbuf
|| bufnext
[-1] != M_ALL
)
464 *bufnext
++ = CHAR(c
);
470 qprintf("glob0:", patbuf
);
473 if ((err
= glob1(patbuf
, pglob
, &limit
)) != 0)
477 * If there was no match we are going to append the pattern
478 * if GLOB_NOCHECK was specified or if GLOB_NOMAGIC was specified
479 * and the pattern did not contain any magic characters
480 * GLOB_NOMAGIC is there just for compatibility with csh.
482 if (pglob
->gl_pathc
== oldpathc
&&
483 ((pglob
->gl_flags
& GLOB_NOCHECK
) ||
484 ((pglob
->gl_flags
& GLOB_NOMAGIC
) &&
485 !(pglob
->gl_flags
& GLOB_MAGCHAR
))))
486 return(globextend(pattern
, pglob
, &limit
));
487 else if (!(pglob
->gl_flags
& GLOB_NOSORT
))
488 qsort(pglob
->gl_pathv
+ pglob
->gl_offs
+ oldpathc
,
489 pglob
->gl_pathc
- oldpathc
, sizeof(char *), compare
);
494 compare(const void *p
, const void *q
)
496 return(strcmp(*(char **)p
, *(char **)q
));
500 glob1(Char
*pattern
, glob_t
*pglob
, size_t *limit
)
502 Char pathbuf
[MaxPathLen
+1];
504 /* A null pathname is invalid -- POSIX 1003.1 sect. 2.4. */
505 if (*pattern
== CHAR_EOS
)
507 return(glob2(pathbuf
, pathbuf
, pattern
, pglob
, limit
));
511 * The functions glob2 and glob3 are mutually recursive; there is one level
512 * of recursion for each segment in the pattern that contains one or more
517 #if defined(S_IFLNK) && defined(S_IFMT)
518 #define S_ISLNK(mode) (((mode) & S_IFMT) == S_IFLNK)
520 #define S_ISLNK(mode) 0
525 glob2(Char
*pathbuf
, Char
*pathend
, Char
*pattern
, glob_t
*pglob
,
533 * Loop over pattern segments until end of pattern or until
534 * segment with meta character found.
536 for (anymeta
= 0;;) {
537 if (*pattern
== CHAR_EOS
) { /* End of pattern? */
539 if (g_lstat(pathbuf
, &sb
, pglob
))
542 if (((pglob
->gl_flags
& GLOB_MARK
) &&
543 pathend
[-1] != CHAR_SEP
) && (S_ISDIR(sb
.st_mode
)
544 || (S_ISLNK(sb
.st_mode
) &&
545 (g_stat(pathbuf
, &sb
, pglob
) == 0) &&
546 S_ISDIR(sb
.st_mode
)))) {
547 *pathend
++ = CHAR_SEP
;
551 return(globextend(pathbuf
, pglob
, limit
));
554 /* Find end of next segment, copy tentatively to pathend. */
557 while (*p
!= CHAR_EOS
&& *p
!= CHAR_SEP
) {
563 if (!anymeta
) { /* No expansion, do next segment. */
566 while (*pattern
== CHAR_SEP
)
567 *pathend
++ = *pattern
++;
568 } else /* Need expansion, recurse. */
569 return(glob3(pathbuf
, pathend
, pattern
, p
, pglob
,
576 glob3(Char
*pathbuf
, Char
*pathend
, Char
*pattern
, Char
*restpattern
,
577 glob_t
*pglob
, size_t *limit
)
582 char buf
[MaxPathLen
];
585 * The readdirfunc declaration can't be prototyped, because it is
586 * assigned, below, to two functions which are prototyped in glob.h
587 * and dirent.h as taking pointers to differently typed opaque
590 struct dirent
*(*readdirfunc
)(void *);
595 if ((dirp
= g_opendir(pathbuf
, pglob
)) == NULL
) {
596 /* TODO: don't call for ENOENT or ENOTDIR? */
597 if (pglob
->gl_errfunc
) {
598 g_Ctoc(pathbuf
, buf
);
599 if (pglob
->gl_errfunc(buf
, errno
) ||
600 pglob
->gl_flags
& GLOB_ERR
)
608 /* Search directory for matching names. */
609 if (pglob
->gl_flags
& GLOB_ALTDIRFUNC
)
610 readdirfunc
= pglob
->gl_readdir
;
612 readdirfunc
= (struct dirent
*(*)(void *))readdir
;
613 while ((dp
= (*readdirfunc
)(dirp
))) {
617 /* Initial CHAR_DOT must be matched literally. */
618 if (dp
->d_name
[0] == CHAR_DOT
&& *pattern
!= CHAR_DOT
)
620 for (sc
= (u_char
*) dp
->d_name
, dc
= pathend
;
621 (*dc
++ = *sc
++) != CHAR_EOS
;)
623 if (!match(pathend
, pattern
, restpattern
)) {
627 err
= glob2(pathbuf
, --dc
, restpattern
, pglob
, limit
);
632 if (pglob
->gl_flags
& GLOB_ALTDIRFUNC
)
633 (*pglob
->gl_closedir
)(dirp
);
641 * Extend the gl_pathv member of a glob_t structure to accomodate a new item,
642 * add the new item, and update gl_pathc.
644 * This assumes the BSD realloc, which only copies the block when its size
645 * crosses a power-of-two boundary; for v7 realloc, this would cause quadratic
648 * Return 0 if new item added, error code if memory couldn't be allocated.
650 * Invariant of the glob_t structure:
651 * Either gl_pathc is zero and gl_pathv is NULL; or gl_pathc > 0 and
652 * gl_pathv points to (gl_offs + gl_pathc + 1) items.
655 globextend(const Char
*path
, glob_t
*pglob
, size_t *limit
)
663 newsize
= sizeof(*pathv
) * (2 + pglob
->gl_pathc
+ pglob
->gl_offs
);
664 pathv
= pglob
->gl_pathv
?
665 realloc(pglob
->gl_pathv
, newsize
) :
668 return(GLOB_NOSPACE
);
670 if (pglob
->gl_pathv
== NULL
&& pglob
->gl_offs
> 0) {
671 /* first time around -- clear initial gl_offs items */
672 pathv
+= pglob
->gl_offs
;
673 for (i
= pglob
->gl_offs
; --i
>= 0; )
676 pglob
->gl_pathv
= pathv
;
678 for (p
= path
; *p
++;)
680 len
= (size_t)(p
- path
);
682 if ((copy
= malloc(len
)) != NULL
) {
684 pathv
[pglob
->gl_offs
+ pglob
->gl_pathc
++] = copy
;
686 pathv
[pglob
->gl_offs
+ pglob
->gl_pathc
] = NULL
;
688 if ((pglob
->gl_flags
& GLOB_LIMIT
) && (newsize
+ *limit
) >= ARG_MAX
) {
690 return(GLOB_NOSPACE
);
693 return(copy
== NULL
? GLOB_NOSPACE
: 0);
698 * pattern matching function for filenames. Each occurrence of the *
699 * pattern causes a recursion level.
702 match(Char
*name
, Char
*pat
, Char
*patend
)
704 int ok
, negate_range
;
707 while (pat
< patend
) {
709 switch (c
& M_MASK
) {
714 if (match(name
, pat
, patend
))
716 while (*name
++ != CHAR_EOS
);
719 if (*name
++ == CHAR_EOS
)
724 if ((k
= *name
++) == CHAR_EOS
)
726 if ((negate_range
= ((*pat
& M_MASK
) == M_NOT
)) != CHAR_EOS
)
728 while (((c
= *pat
++) & M_MASK
) != M_END
)
729 if ((*pat
& M_MASK
) == M_RNG
) {
730 if (c
<= k
&& k
<= pat
[1])
735 if (ok
== negate_range
)
744 return(*name
== CHAR_EOS
);
747 /* Free allocated data belonging to a glob_t structure. */
749 globfree(glob_t
*pglob
)
754 if (pglob
->gl_pathv
!= NULL
) {
755 pp
= pglob
->gl_pathv
+ pglob
->gl_offs
;
756 for (i
= pglob
->gl_pathc
; i
--; ++pp
)
759 free(pglob
->gl_pathv
);
760 pglob
->gl_pathv
= NULL
;
765 g_opendir(Char
*str
, glob_t
*pglob
)
767 char buf
[MaxPathLen
];
770 strlcpy(buf
, ".", sizeof(buf
));
774 if (pglob
->gl_flags
& GLOB_ALTDIRFUNC
)
775 return((*pglob
->gl_opendir
)(buf
));
777 return(opendir(buf
));
781 g_lstat(Char
*fn
, struct stat
*sb
, glob_t
*pglob
)
783 char buf
[MaxPathLen
];
786 if (pglob
->gl_flags
& GLOB_ALTDIRFUNC
)
787 return((*pglob
->gl_lstat
)(buf
, sb
));
788 return(lstat(buf
, sb
));
792 g_stat(Char
*fn
, struct stat
*sb
, glob_t
*pglob
)
794 char buf
[MaxPathLen
];
797 if (pglob
->gl_flags
& GLOB_ALTDIRFUNC
)
798 return((*pglob
->gl_stat
)(buf
, sb
));
799 return(stat(buf
, sb
));
803 g_strchr(const Char
*str
, int ch
)
814 g_strcat(Char
*dst
, const Char
*src
)
821 while((*dst
++ = *src
++) != CHAR_EOS
)
829 g_Ctoc(const Char
*str
, char *buf
)
833 for (dc
= buf
; (*dc
++ = *str
++) != CHAR_EOS
;)
839 qprintf(const Char
*str
, Char
*s
)
843 printf("%s:\n", str
);
845 printf("%c", CHAR(*p
));
848 printf("%c", *p
& M_PROTECT
? '"' : ' ');
851 printf("%c", ismeta(*p
) ? '_' : ' ');