1 /* $OpenBSD: glob.c,v 1.25 2005/08/08 08:05:34 espie Exp $ */
3 * Copyright (c) 1989, 1993
4 * The Regents of the University of California. All rights reserved.
6 * This code is derived from software contributed to Berkeley by
9 * Redistribution and use in source and binary forms, with or without
10 * modification, are permitted provided that the following conditions
12 * 1. Redistributions of source code must retain the above copyright
13 * notice, this list of conditions and the following disclaimer.
14 * 2. Redistributions in binary form must reproduce the above copyright
15 * notice, this list of conditions and the following disclaimer in the
16 * documentation and/or other materials provided with the distribution.
17 * 3. Neither the name of the University nor the names of its contributors
18 * may be used to endorse or promote products derived from this software
19 * without specific prior written permission.
21 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
22 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
23 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
24 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
25 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
26 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
27 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
28 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
29 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
30 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
35 * glob(3) -- a superset of the one defined in POSIX 1003.2.
37 * The [!...] convention to negate a range is supported (SysV, Posix, ksh).
39 * Optional extra services, controlled by flags not defined by POSIX:
42 * Escaping convention: \ inhibits any special meaning the following
43 * character might have (except \ at end of string is retained).
45 * Set in gl_flags if pattern contained a globbing character.
47 * Same as GLOB_NOCHECK, but it will only append pattern if it did
48 * not contain any magic characters. [Used in csh style globbing]
50 * Use alternately specified directory access functions.
52 * expand ~user/foo to the /home/dir/of/user/foo
54 * expand {1,2}{a,b} to 1a 1b 2a 2b
56 * Number of matches in the current invocation of glob.
60 #include <sys/param.h>
85 #define UNDERSCORE '_'
93 #define M_QUOTE 0x8000
94 #define M_PROTECT 0x4000
96 #define M_ASCII 0x00ff
103 #define M_PROTECT 0x40
112 #define CHAR(c) ((Char)((c)&M_ASCII))
113 #define META(c) ((Char)((c)|M_QUOTE))
114 #define M_ALL META('*')
115 #define M_END META(']')
116 #define M_NOT META('!')
117 #define M_ONE META('?')
118 #define M_RNG META('-')
119 #define M_SET META('[')
120 #define ismeta(c) (((c)&M_QUOTE) != 0)
123 static int compare(const void *, const void *);
124 static int g_Ctoc(const Char
*, char *, u_int
);
125 static int g_lstat(Char
*, struct stat
*, glob_t
*);
126 static DIR *g_opendir(Char
*, glob_t
*);
127 static const Char
*g_strchr(const Char
*, int);
128 static int g_stat(Char
*, struct stat
*, glob_t
*);
129 static int glob0(const Char
*, glob_t
*);
130 static int glob1(Char
*, Char
*, glob_t
*, size_t *);
131 static int glob2(Char
*, Char
*, Char
*, Char
*, Char
*, Char
*,
133 static int glob3(Char
*, Char
*, Char
*, Char
*, Char
*, Char
*,
134 Char
*, Char
*, glob_t
*, size_t *);
135 static int globextend(const Char
*, glob_t
*, size_t *);
137 globtilde(const Char
*, Char
*, size_t, glob_t
*);
138 static int globexp1(const Char
*, glob_t
*);
139 static int globexp2(const Char
*, const Char
*, glob_t
*, int *);
140 static int match(Char
*, Char
*, Char
*);
142 static void qprintf(const char *, Char
*);
146 glob(const char *pattern
, int flags
, int (*errfunc
)(const char *, int),
149 const u_char
*patnext
;
151 Char
*bufnext
, *bufend
, patbuf
[MAXPATHLEN
];
153 patnext
= (const u_char
*) pattern
;
154 if (!(flags
& GLOB_APPEND
)) {
156 pglob
->gl_pathv
= NULL
;
157 if (!(flags
& GLOB_DOOFFS
))
160 pglob
->gl_flags
= flags
& ~GLOB_MAGCHAR
;
161 pglob
->gl_errfunc
= errfunc
;
162 pglob
->gl_matchc
= 0;
165 bufend
= bufnext
+ MAXPATHLEN
- 1;
166 if (flags
& GLOB_NOESCAPE
)
167 while (bufnext
< bufend
&& (c
= *patnext
++) != EOS
)
170 /* Protect the quoted characters. */
171 while (bufnext
< bufend
&& (c
= *patnext
++) != EOS
)
173 if ((c
= *patnext
++) == EOS
) {
177 *bufnext
++ = c
| M_PROTECT
;
183 if (flags
& GLOB_BRACE
)
184 return globexp1(patbuf
, pglob
);
186 return glob0(patbuf
, pglob
);
190 * Expand recursively a glob {} pattern. When there is no more expansion
191 * invoke the standard globbing routine to glob the rest of the magic
195 globexp1(const Char
*pattern
, glob_t
*pglob
)
197 const Char
* ptr
= pattern
;
200 /* Protect a single {}, for find(1), like csh */
201 if (pattern
[0] == LBRACE
&& pattern
[1] == RBRACE
&& pattern
[2] == EOS
)
202 return glob0(pattern
, pglob
);
204 while ((ptr
= g_strchr(ptr
, LBRACE
)) != NULL
)
205 if (!globexp2(ptr
, pattern
, pglob
, &rv
))
208 return glob0(pattern
, pglob
);
213 * Recursive brace globbing helper. Tries to expand a single brace.
214 * If it succeeds then it invokes globexp1 with the new pattern.
215 * If it fails then it tries to glob the rest of the pattern and returns.
218 globexp2(const Char
*ptr
, const Char
*pattern
, glob_t
*pglob
, int *rv
)
222 const Char
*pe
, *pm
, *pl
;
223 Char patbuf
[MAXPATHLEN
];
225 /* copy part up to the brace */
226 for (lm
= patbuf
, pm
= pattern
; pm
!= ptr
; *lm
++ = *pm
++)
231 /* Find the balanced brace */
232 for (i
= 0, pe
= ++ptr
; *pe
; pe
++)
233 if (*pe
== LBRACKET
) {
234 /* Ignore everything between [] */
235 for (pm
= pe
++; *pe
!= RBRACKET
&& *pe
!= EOS
; pe
++)
239 * We could not find a matching RBRACKET.
240 * Ignore and just look for RBRACE
244 } else if (*pe
== LBRACE
)
246 else if (*pe
== RBRACE
) {
252 /* Non matching braces; just glob the pattern */
253 if (i
!= 0 || *pe
== EOS
) {
254 *rv
= glob0(patbuf
, pglob
);
258 for (i
= 0, pl
= pm
= ptr
; pm
<= pe
; pm
++) {
261 /* Ignore everything between [] */
262 for (pl
= pm
++; *pm
!= RBRACKET
&& *pm
!= EOS
; pm
++)
266 * We could not find a matching RBRACKET.
267 * Ignore and just look for RBRACE
284 if (i
&& *pm
== COMMA
)
287 /* Append the current string */
288 for (lm
= ls
; (pl
< pm
); *lm
++ = *pl
++)
292 * Append the rest of the pattern after the
295 for (pl
= pe
+ 1; (*lm
++ = *pl
++) != EOS
; )
298 /* Expand the current pattern */
300 qprintf("globexp2:", patbuf
);
302 *rv
= globexp1(patbuf
, pglob
);
304 /* move after the comma, to the next string */
320 * expand tilde from the passwd file.
323 globtilde(const Char
*pattern
, Char
*patbuf
, size_t patbuf_len
, glob_t
*pglob
)
330 if (*pattern
!= TILDE
|| !(pglob
->gl_flags
& GLOB_TILDE
))
333 /* Copy up to the end of the string or / */
334 eb
= &patbuf
[patbuf_len
- 1];
335 for (p
= pattern
+ 1, h
= (char *) patbuf
;
336 h
< (char *)eb
&& *p
&& *p
!= SLASH
; *h
++ = *p
++)
346 if (((char *) patbuf
)[0] == EOS
) {
348 * handle a plain ~ or ~/ by expanding $HOME
349 * first and then trying the password file
351 if (issetugid() != 0 || (h
= getenv("HOME")) == NULL
) {
352 if ((pwd
= getpwuid(getuid())) == NULL
)
361 if ((pwd
= getpwnam((char*) patbuf
)) == NULL
)
367 /* Copy the home directory */
368 for (b
= patbuf
; b
< eb
&& *h
; *b
++ = *h
++)
371 /* Append the rest of the pattern */
372 while (b
< eb
&& (*b
++ = *p
++) != EOS
)
381 * The main glob() routine: compiles the pattern (optionally processing
382 * quotes), calls glob1() to do the real pattern matching, and finally
383 * sorts the list (unless unsorted operation is requested). Returns 0
384 * if things went well, nonzero if errors occurred. It is not an error
385 * to find no matches.
388 glob0(const Char
*pattern
, glob_t
*pglob
)
390 const Char
*qpatnext
;
391 int c
, err
, oldpathc
;
392 Char
*bufnext
, patbuf
[MAXPATHLEN
];
395 qpatnext
= globtilde(pattern
, patbuf
, MAXPATHLEN
, pglob
);
396 oldpathc
= pglob
->gl_pathc
;
399 /* We don't need to check for buffer overflow any more. */
400 while ((c
= *qpatnext
++) != EOS
) {
406 if (*qpatnext
== EOS
||
407 g_strchr(qpatnext
+1, RBRACKET
) == NULL
) {
408 *bufnext
++ = LBRACKET
;
418 *bufnext
++ = CHAR(c
);
419 if (*qpatnext
== RANGE
&&
420 (c
= qpatnext
[1]) != RBRACKET
) {
422 *bufnext
++ = CHAR(c
);
425 } while ((c
= *qpatnext
++) != RBRACKET
);
426 pglob
->gl_flags
|= GLOB_MAGCHAR
;
430 pglob
->gl_flags
|= GLOB_MAGCHAR
;
434 pglob
->gl_flags
|= GLOB_MAGCHAR
;
435 /* collapse adjacent stars to one,
436 * to avoid exponential behavior
438 if (bufnext
== patbuf
|| bufnext
[-1] != M_ALL
)
442 *bufnext
++ = CHAR(c
);
448 qprintf("glob0:", patbuf
);
451 if ((err
= glob1(patbuf
, patbuf
+MAXPATHLEN
-1, pglob
, &limit
)) != 0)
455 * If there was no match we are going to append the pattern
456 * if GLOB_NOCHECK was specified or if GLOB_NOMAGIC was specified
457 * and the pattern did not contain any magic characters
458 * GLOB_NOMAGIC is there just for compatibility with csh.
460 if (pglob
->gl_pathc
== oldpathc
) {
461 if ((pglob
->gl_flags
& GLOB_NOCHECK
) ||
462 ((pglob
->gl_flags
& GLOB_NOMAGIC
) &&
463 !(pglob
->gl_flags
& GLOB_MAGCHAR
)))
464 return(globextend(pattern
, pglob
, &limit
));
466 return(GLOB_NOMATCH
);
468 if (!(pglob
->gl_flags
& GLOB_NOSORT
))
469 qsort(pglob
->gl_pathv
+ pglob
->gl_offs
+ oldpathc
,
470 pglob
->gl_pathc
- oldpathc
, sizeof(char *), compare
);
475 compare(const void *p
, const void *q
)
477 return(strcmp(*(char *const *)p
, *(char *const *)q
));
481 glob1(Char
*pattern
, Char
*pattern_last
, glob_t
*pglob
, size_t *limitp
)
483 Char pathbuf
[MAXPATHLEN
];
485 /* A null pathname is invalid -- POSIX 1003.1 sect. 2.4. */
488 return(glob2(pathbuf
, pathbuf
+MAXPATHLEN
-1,
489 pathbuf
, pathbuf
+MAXPATHLEN
-1,
490 pattern
, pattern_last
, pglob
, limitp
));
494 * The functions glob2 and glob3 are mutually recursive; there is one level
495 * of recursion for each segment in the pattern that contains one or more
499 glob2(Char
*pathbuf
, Char
*pathbuf_last
, Char
*pathend
, Char
*pathend_last
,
500 Char
*pattern
, Char
*pattern_last
, glob_t
*pglob
, size_t *limitp
)
507 * Loop over pattern segments until end of pattern or until
508 * segment with meta character found.
510 for (anymeta
= 0;;) {
511 if (*pattern
== EOS
) { /* End of pattern? */
513 if (g_lstat(pathbuf
, &sb
, pglob
))
516 if (((pglob
->gl_flags
& GLOB_MARK
) &&
517 pathend
[-1] != SEP
) && (S_ISDIR(sb
.st_mode
) ||
518 (S_ISLNK(sb
.st_mode
) &&
519 (g_stat(pathbuf
, &sb
, pglob
) == 0) &&
520 S_ISDIR(sb
.st_mode
)))) {
521 if (pathend
+1 > pathend_last
)
527 return(globextend(pathbuf
, pglob
, limitp
));
530 /* Find end of next segment, copy tentatively to pathend. */
533 while (*p
!= EOS
&& *p
!= SEP
) {
536 if (q
+1 > pathend_last
)
541 if (!anymeta
) { /* No expansion, do next segment. */
544 while (*pattern
== SEP
) {
545 if (pathend
+1 > pathend_last
)
547 *pathend
++ = *pattern
++;
550 /* Need expansion, recurse. */
551 return(glob3(pathbuf
, pathbuf_last
, pathend
,
552 pathend_last
, pattern
, pattern_last
,
553 p
, pattern_last
, pglob
, limitp
));
559 glob3(Char
*pathbuf
, Char
*pathbuf_last
, Char
*pathend
, Char
*pathend_last
,
560 Char
*pattern
, Char
*pattern_last
__attribute__((unused
)), Char
*restpattern
,
561 Char
*restpattern_last
, glob_t
*pglob
, size_t *limitp
)
566 char buf
[MAXPATHLEN
];
569 * The readdirfunc declaration can't be prototyped, because it is
570 * assigned, below, to two functions which are prototyped in glob.h
571 * and dirent.h as taking pointers to differently typed opaque
574 struct dirent
*(*readdirfunc
)(void *);
576 if (pathend
> pathend_last
)
581 if ((dirp
= g_opendir(pathbuf
, pglob
)) == NULL
) {
582 /* TODO: don't call for ENOENT or ENOTDIR? */
583 if (pglob
->gl_errfunc
) {
584 if (g_Ctoc(pathbuf
, buf
, sizeof(buf
)))
585 return(GLOB_ABORTED
);
586 if (pglob
->gl_errfunc(buf
, errno
) ||
587 pglob
->gl_flags
& GLOB_ERR
)
588 return(GLOB_ABORTED
);
595 /* Search directory for matching names. */
596 if (pglob
->gl_flags
& GLOB_ALTDIRFUNC
)
597 readdirfunc
= pglob
->gl_readdir
;
599 readdirfunc
= (struct dirent
*(*)(void *))readdir
;
600 while ((dp
= (*readdirfunc
)(dirp
))) {
604 /* Initial DOT must be matched literally. */
605 if (dp
->d_name
[0] == DOT
&& *pattern
!= DOT
)
608 sc
= (u_char
*) dp
->d_name
;
609 while (dc
< pathend_last
&& (*dc
++ = *sc
++) != EOS
)
611 if (dc
>= pathend_last
) {
617 if (!match(pathend
, pattern
, restpattern
)) {
621 err
= glob2(pathbuf
, pathbuf_last
, --dc
, pathend_last
,
622 restpattern
, restpattern_last
, pglob
, limitp
);
627 if (pglob
->gl_flags
& GLOB_ALTDIRFUNC
)
628 (*pglob
->gl_closedir
)(dirp
);
636 * Extend the gl_pathv member of a glob_t structure to accommodate a new item,
637 * add the new item, and update gl_pathc.
639 * This assumes the BSD realloc, which only copies the block when its size
640 * crosses a power-of-two boundary; for v7 realloc, this would cause quadratic
643 * Return 0 if new item added, error code if memory couldn't be allocated.
645 * Invariant of the glob_t structure:
646 * Either gl_pathc is zero and gl_pathv is NULL; or gl_pathc > 0 and
647 * gl_pathv points to (gl_offs + gl_pathc + 1) items.
650 globextend(const Char
*path
, glob_t
*pglob
, size_t *limitp
)
658 newsize
= sizeof(*pathv
) * (2 + pglob
->gl_pathc
+ pglob
->gl_offs
);
659 pathv
= pglob
->gl_pathv
? realloc((char *)pglob
->gl_pathv
, newsize
) :
662 if (pglob
->gl_pathv
) {
663 free(pglob
->gl_pathv
);
664 pglob
->gl_pathv
= NULL
;
666 return(GLOB_NOSPACE
);
669 if (pglob
->gl_pathv
== NULL
&& pglob
->gl_offs
> 0) {
670 /* first time around -- clear initial gl_offs items */
671 pathv
+= pglob
->gl_offs
;
672 for (i
= pglob
->gl_offs
; --i
>= 0; )
675 pglob
->gl_pathv
= pathv
;
677 for (p
= path
; *p
++;)
679 len
= (size_t)(p
- path
);
681 if ((copy
= malloc(len
)) != NULL
) {
682 if (g_Ctoc(path
, copy
, len
)) {
684 return(GLOB_NOSPACE
);
686 pathv
[pglob
->gl_offs
+ pglob
->gl_pathc
++] = copy
;
688 pathv
[pglob
->gl_offs
+ pglob
->gl_pathc
] = NULL
;
690 if ((pglob
->gl_flags
& GLOB_LIMIT
) &&
691 newsize
+ *limitp
>= ARG_MAX
) {
693 return(GLOB_NOSPACE
);
696 return(copy
== NULL
? GLOB_NOSPACE
: 0);
701 * pattern matching function for filenames. Each occurrence of the *
702 * pattern causes a recursion level.
705 match(Char
*name
, Char
*pat
, Char
*patend
)
707 int ok
, negate_range
;
710 while (pat
< patend
) {
712 switch (c
& M_MASK
) {
717 if (match(name
, pat
, patend
))
719 } while (*name
++ != EOS
);
727 if ((k
= *name
++) == EOS
)
729 if ((negate_range
= ((*pat
& M_MASK
) == M_NOT
)) != EOS
)
731 while (((c
= *pat
++) & M_MASK
) != M_END
)
732 if ((*pat
& M_MASK
) == M_RNG
) {
733 if (c
<= k
&& k
<= pat
[1])
738 if (ok
== negate_range
)
747 return(*name
== EOS
);
750 /* Free allocated data belonging to a glob_t structure. */
752 globfree(glob_t
*pglob
)
757 if (pglob
->gl_pathv
!= NULL
) {
758 pp
= pglob
->gl_pathv
+ pglob
->gl_offs
;
759 for (i
= pglob
->gl_pathc
; i
--; ++pp
)
762 free(pglob
->gl_pathv
);
763 pglob
->gl_pathv
= NULL
;
768 g_opendir(Char
*str
, glob_t
*pglob
)
770 char buf
[MAXPATHLEN
];
773 strlcpy(buf
, ".", sizeof buf
);
775 if (g_Ctoc(str
, buf
, sizeof(buf
)))
779 if (pglob
->gl_flags
& GLOB_ALTDIRFUNC
)
780 return((*pglob
->gl_opendir
)(buf
));
782 return(opendir(buf
));
786 g_lstat(Char
*fn
, struct stat
*sb
, glob_t
*pglob
)
788 char buf
[MAXPATHLEN
];
790 if (g_Ctoc(fn
, buf
, sizeof(buf
)))
792 if (pglob
->gl_flags
& GLOB_ALTDIRFUNC
)
793 return((*pglob
->gl_lstat
)(buf
, sb
));
794 return(lstat(buf
, sb
));
798 g_stat(Char
*fn
, struct stat
*sb
, glob_t
*pglob
)
800 char buf
[MAXPATHLEN
];
802 if (g_Ctoc(fn
, buf
, sizeof(buf
)))
804 if (pglob
->gl_flags
& GLOB_ALTDIRFUNC
)
805 return((*pglob
->gl_stat
)(buf
, sb
));
806 return(stat(buf
, sb
));
810 g_strchr(const Char
*str
, int ch
)
820 g_Ctoc(const Char
*str
, char *buf
, u_int len
)
824 if ((*buf
++ = *str
++) == EOS
)
832 qprintf(const char *str
, Char
*s
)
836 (void)printf("%s:\n", str
);
838 (void)printf("%c", CHAR(*p
));
841 (void)printf("%c", *p
& M_PROTECT
? '"' : ' ');
844 (void)printf("%c", ismeta(*p
) ? '_' : ' ');