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
37 #if defined(LIBC_SCCS) && !defined(lint)
39 static char sccsid
[] = "@(#)glob.c 8.3 (Berkeley) 10/13/93";
41 static char rcsid
[] = "$OpenBSD: glob.c,v 1.8 1998/08/14 21:39:30 deraadt Exp $";
43 #endif /* LIBC_SCCS and not lint */
46 * glob(3) -- a superset of the one defined in POSIX 1003.2.
48 * The [!...] convention to negate a range is supported (SysV, Posix, ksh).
50 * Optional extra services, controlled by flags not defined by POSIX:
53 * Escaping convention: \ inhibits any special meaning the following
54 * character might have (except \ at end of string is retained).
56 * Set in gl_flags if pattern contained a globbing character.
58 * Same as GLOB_NOCHECK, but it will only append pattern if it did
59 * not contain any magic characters. [Used in csh style globbing]
61 * Use alternately specified directory access functions.
63 * expand ~user/foo to the /home/dir/of/user/foo
65 * expand {1,2}{a,b} to 1a 1b 2a 2b
67 * Number of matches in the current invocation of glob.
72 //#include <sys/param.h>
105 #define UNDERSCORE '_'
113 #define M_QUOTE 0x8000
114 #define M_PROTECT 0x4000
115 #define M_MASK 0xffff
116 #define M_ASCII 0x00ff
118 typedef u_short Char
;
123 #define M_PROTECT 0x40
132 #define CHAR(c) ((Char)((c)&M_ASCII))
133 #define META(c) ((Char)((c)|M_QUOTE))
134 #define M_ALL META('*')
135 #define M_END META(']')
136 #define M_NOT META('!')
137 #define M_ONE META('?')
138 #define M_RNG META('-')
139 #define M_SET META('[')
140 #define ismeta(c) (((c)&M_QUOTE) != 0)
143 static int compare (const void *, const void *);
144 static void g_Ctoc (const Char
*, char *);
145 static int g_lstat (Char
*, struct stat
*, glob_t
*);
146 static DIR *g_opendir (Char
*, glob_t
*);
147 static Char
*g_strchr (Char
*, int);
149 static Char
*g_strcat (Char
*, const Char
*);
151 static int g_stat (Char
*, struct stat
*, glob_t
*);
152 static int glob0 (const Char
*, glob_t
*);
153 static int glob1 (Char
*, glob_t
*);
154 static int glob2 (Char
*, Char
*, Char
*, glob_t
*);
155 static int glob3 (Char
*, Char
*, Char
*, Char
*, glob_t
*);
156 static int globextend (const Char
*, glob_t
*);
157 static const Char
* globtilde (const Char
*, Char
*, size_t, glob_t
*);
158 static int globexp1 (const Char
*, glob_t
*);
159 static int globexp2 (const Char
*, const Char
*, glob_t
*, int *);
160 static int match (Char
*, Char
*, Char
*);
162 static void qprintf (const char *, Char
*);
166 openbsd_glob(pattern
, flags
, errfunc
, pglob
)
168 int flags
, (*errfunc
) __P((const char *, int));
171 const u_char
*patnext
;
173 Char
*bufnext
, *bufend
, patbuf
[MAXPATHLEN
+1];
175 patnext
= (u_char
*) pattern
;
176 if (!(flags
& GLOB_APPEND
)) {
178 pglob
->gl_pathv
= NULL
;
179 if (!(flags
& GLOB_DOOFFS
))
182 pglob
->gl_flags
= flags
& ~GLOB_MAGCHAR
;
183 pglob
->gl_errfunc
= errfunc
;
184 pglob
->gl_matchc
= 0;
187 bufend
= bufnext
+ MAXPATHLEN
;
188 if (flags
& GLOB_NOESCAPE
)
189 while (bufnext
< bufend
&& (c
= *patnext
++) != EOS
)
192 /* Protect the quoted characters. */
193 while (bufnext
< bufend
&& (c
= *patnext
++) != EOS
)
195 if ((c
= *patnext
++) == EOS
) {
199 *bufnext
++ = c
| M_PROTECT
;
206 if (flags
& GLOB_BRACE
)
207 return globexp1(patbuf
, pglob
);
209 return glob0(patbuf
, pglob
);
213 * Expand recursively a glob {} pattern. When there is no more expansion
214 * invoke the standard globbing routine to glob the rest of the magic
217 static int globexp1(pattern
, pglob
)
221 const Char
* ptr
= pattern
;
224 /* Protect a single {}, for find(1), like csh */
225 if (pattern
[0] == LBRACE
&& pattern
[1] == RBRACE
&& pattern
[2] == EOS
)
226 return glob0(pattern
, pglob
);
228 while ((ptr
= (const Char
*) g_strchr((Char
*) ptr
, LBRACE
)) != NULL
)
229 if (!globexp2(ptr
, pattern
, pglob
, &rv
))
232 return glob0(pattern
, pglob
);
237 * Recursive brace globbing helper. Tries to expand a single brace.
238 * If it succeeds then it invokes globexp1 with the new pattern.
239 * If it fails then it tries to glob the rest of the pattern and returns.
241 static int globexp2(ptr
, pattern
, pglob
, rv
)
242 const Char
*ptr
, *pattern
;
248 const Char
*pe
, *pm
, *pl
;
249 Char patbuf
[MAXPATHLEN
+ 1];
251 /* copy part up to the brace */
252 for (lm
= patbuf
, pm
= pattern
; pm
!= ptr
; *lm
++ = *pm
++)
256 /* Find the balanced brace */
257 for (i
= 0, pe
= ++ptr
; *pe
; pe
++)
258 if (*pe
== LBRACKET
) {
259 /* Ignore everything between [] */
260 for (pm
= pe
++; *pe
!= RBRACKET
&& *pe
!= EOS
; pe
++)
264 * We could not find a matching RBRACKET.
265 * Ignore and just look for RBRACE
270 else if (*pe
== LBRACE
)
272 else if (*pe
== RBRACE
) {
278 /* Non matching braces; just glob the pattern */
279 if (i
!= 0 || *pe
== EOS
) {
280 *rv
= glob0(patbuf
, pglob
);
284 for (i
= 0, pl
= pm
= ptr
; pm
<= pe
; pm
++)
287 /* Ignore everything between [] */
288 for (pl
= pm
++; *pm
!= RBRACKET
&& *pm
!= EOS
; pm
++)
292 * We could not find a matching RBRACKET.
293 * Ignore and just look for RBRACE
310 if (i
&& *pm
== COMMA
)
313 /* Append the current string */
314 for (lm
= ls
; (pl
< pm
); *lm
++ = *pl
++)
317 * Append the rest of the pattern after the
320 for (pl
= pe
+ 1; (*lm
++ = *pl
++) != EOS
;)
323 /* Expand the current pattern */
325 qprintf("globexp2:", patbuf
);
327 *rv
= globexp1(patbuf
, pglob
);
329 /* move after the comma, to the next string */
344 * expand tilde from the passwd file.
347 globtilde(pattern
, patbuf
, patbuf_len
, pglob
)
358 if (*pattern
!= TILDE
|| !(pglob
->gl_flags
& GLOB_TILDE
))
361 /* Copy up to the end of the string or / */
362 eb
= &patbuf
[patbuf_len
- 1];
363 for (p
= pattern
+ 1, h
= (char *) patbuf
;
364 h
< (char *)eb
&& *p
&& *p
!= SLASH
; *h
++ = *p
++)
369 if (((char *) patbuf
)[0] == EOS
) {
371 * handle a plain ~ or ~/ by expanding $HOME
372 * first and then trying the password file
374 #ifdef HAVE_ISSETUGID
375 if (issetugid() != 0 || (h
= getenv("HOME")) == NULL
) {
377 if ((pwd
= getpwuid(getuid())) == NULL
)
381 #ifdef HAVE_ISSETUGID
389 if ((pwd
= getpwnam((char*) patbuf
)) == NULL
)
395 /* Copy the home directory */
396 for (b
= patbuf
; b
< eb
&& *h
; *b
++ = *h
++)
399 /* Append the rest of the pattern */
400 while (b
< eb
&& (*b
++ = *p
++) != EOS
)
409 * The main glob() routine: compiles the pattern (optionally processing
410 * quotes), calls glob1() to do the real pattern matching, and finally
411 * sorts the list (unless unsorted operation is requested). Returns 0
412 * if things went well, nonzero if errors occurred. It is not an error
413 * to find no matches.
416 glob0(pattern
, pglob
)
420 const Char
*qpatnext
;
421 int c
, err
, oldpathc
;
422 Char
*bufnext
, patbuf
[MAXPATHLEN
+1];
424 qpatnext
= globtilde(pattern
, patbuf
, sizeof(patbuf
) / sizeof(Char
),
426 oldpathc
= pglob
->gl_pathc
;
429 /* We don't need to check for buffer overflow any more. */
430 while ((c
= *qpatnext
++) != EOS
) {
436 if (*qpatnext
== EOS
||
437 g_strchr((Char
*) qpatnext
+1, RBRACKET
) == NULL
) {
438 *bufnext
++ = LBRACKET
;
448 *bufnext
++ = CHAR(c
);
449 if (*qpatnext
== RANGE
&&
450 (c
= qpatnext
[1]) != RBRACKET
) {
452 *bufnext
++ = CHAR(c
);
455 } while ((c
= *qpatnext
++) != RBRACKET
);
456 pglob
->gl_flags
|= GLOB_MAGCHAR
;
460 pglob
->gl_flags
|= GLOB_MAGCHAR
;
464 pglob
->gl_flags
|= GLOB_MAGCHAR
;
465 /* collapse adjacent stars to one,
466 * to avoid exponential behavior
468 if (bufnext
== patbuf
|| bufnext
[-1] != M_ALL
)
472 *bufnext
++ = CHAR(c
);
478 qprintf("glob0:", patbuf
);
481 if ((err
= glob1(patbuf
, pglob
)) != 0)
485 * If there was no match we are going to append the pattern
486 * if GLOB_NOCHECK was specified or if GLOB_NOMAGIC was specified
487 * and the pattern did not contain any magic characters
488 * GLOB_NOMAGIC is there just for compatibility with csh.
490 if (pglob
->gl_pathc
== oldpathc
) {
491 if ((pglob
->gl_flags
& GLOB_NOCHECK
) ||
492 ((pglob
->gl_flags
& GLOB_NOMAGIC
) &&
493 !(pglob
->gl_flags
& GLOB_MAGCHAR
)))
494 return(globextend(pattern
, pglob
));
496 return(GLOB_NOMATCH
);
498 if (!(pglob
->gl_flags
& GLOB_NOSORT
))
499 qsort(pglob
->gl_pathv
+ pglob
->gl_offs
+ oldpathc
,
500 pglob
->gl_pathc
- oldpathc
, sizeof(char *), compare
);
508 return(strcmp(*(char **)p
, *(char **)q
));
512 glob1(pattern
, pglob
)
516 Char pathbuf
[MAXPATHLEN
+1];
518 /* A null pathname is invalid -- POSIX 1003.1 sect. 2.4. */
521 return(glob2(pathbuf
, pathbuf
, pattern
, pglob
));
525 * The functions glob2 and glob3 are mutually recursive; there is one level
526 * of recursion for each segment in the pattern that contains one or more
530 glob2(pathbuf
, pathend
, pattern
, pglob
)
531 Char
*pathbuf
, *pathend
, *pattern
;
539 * Loop over pattern segments until end of pattern or until
540 * segment with meta character found.
542 for (anymeta
= 0;;) {
543 if (*pattern
== EOS
) { /* End of pattern? */
545 if (g_lstat(pathbuf
, &sb
, pglob
))
548 if (((pglob
->gl_flags
& GLOB_MARK
) &&
549 pathend
[-1] != SEP
) && (S_ISDIR(sb
.st_mode
)
550 || (S_ISLNK(sb
.st_mode
) &&
551 (g_stat(pathbuf
, &sb
, pglob
) == 0) &&
552 S_ISDIR(sb
.st_mode
)))) {
557 return(globextend(pathbuf
, pglob
));
560 /* Find end of next segment, copy tentatively to pathend. */
563 while (*p
!= EOS
&& *p
!= SEP
) {
569 if (!anymeta
) { /* No expansion, do next segment. */
572 while (*pattern
== SEP
)
573 *pathend
++ = *pattern
++;
574 } else /* Need expansion, recurse. */
575 return(glob3(pathbuf
, pathend
, pattern
, p
, pglob
));
581 glob3(pathbuf
, pathend
, pattern
, restpattern
, pglob
)
582 Char
*pathbuf
, *pathend
, *pattern
, *restpattern
;
585 register struct dirent
*dp
;
588 char buf
[MAXPATHLEN
];
591 * The readdirfunc declaration can't be prototyped, because it is
592 * assigned, below, to two functions which are prototyped in glob.h
593 * and dirent.h as taking pointers to differently typed opaque
596 struct dirent
*(*readdirfunc
)();
601 if ((dirp
= g_opendir(pathbuf
, pglob
)) == NULL
) {
602 /* TODO: don't call for ENOENT or ENOTDIR? */
603 if (pglob
->gl_errfunc
) {
604 g_Ctoc(pathbuf
, buf
);
605 if (pglob
->gl_errfunc(buf
, errno
) ||
606 pglob
->gl_flags
& GLOB_ERR
)
607 return (GLOB_ABORTED
);
614 /* Search directory for matching names. */
615 if (pglob
->gl_flags
& GLOB_ALTDIRFUNC
)
616 readdirfunc
= pglob
->gl_readdir
;
618 readdirfunc
= readdir
;
619 while ((dp
= (*readdirfunc
)(dirp
))) {
623 /* Initial DOT must be matched literally. */
624 if (dp
->d_name
[0] == DOT
&& *pattern
!= DOT
)
626 for (sc
= (u_char
*) dp
->d_name
, dc
= pathend
;
627 (*dc
++ = *sc
++) != EOS
;)
629 if (!match(pathend
, pattern
, restpattern
)) {
633 err
= glob2(pathbuf
, --dc
, restpattern
, pglob
);
638 if (pglob
->gl_flags
& GLOB_ALTDIRFUNC
)
639 (*pglob
->gl_closedir
)(dirp
);
647 * Extend the gl_pathv member of a glob_t structure to accomodate a new item,
648 * add the new item, and update gl_pathc.
650 * This assumes the BSD realloc, which only copies the block when its size
651 * crosses a power-of-two boundary; for v7 realloc, this would cause quadratic
654 * Return 0 if new item added, error code if memory couldn't be allocated.
656 * Invariant of the glob_t structure:
657 * Either gl_pathc is zero and gl_pathv is NULL; or gl_pathc > 0 and
658 * gl_pathv points to (gl_offs + gl_pathc + 1) items.
661 globextend(path
, pglob
)
665 register char **pathv
;
671 newsize
= sizeof(*pathv
) * (2 + pglob
->gl_pathc
+ pglob
->gl_offs
);
672 pathv
= pglob
->gl_pathv
?
673 realloc((char *)pglob
->gl_pathv
, newsize
) :
677 free(pglob
->gl_pathv
);
678 return(GLOB_NOSPACE
);
681 if (pglob
->gl_pathv
== NULL
&& pglob
->gl_offs
> 0) {
682 /* first time around -- clear initial gl_offs items */
683 pathv
+= pglob
->gl_offs
;
684 for (i
= pglob
->gl_offs
; --i
>= 0; )
687 pglob
->gl_pathv
= pathv
;
689 for (p
= path
; *p
++;)
691 if ((copy
= malloc(p
- path
)) != NULL
) {
693 pathv
[pglob
->gl_offs
+ pglob
->gl_pathc
++] = copy
;
695 pathv
[pglob
->gl_offs
+ pglob
->gl_pathc
] = NULL
;
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(name
, pat
, patend
)
706 register Char
*name
, *pat
, *patend
;
708 int ok
, negate_range
;
711 while (pat
< patend
) {
713 switch (c
& M_MASK
) {
718 if (match(name
, pat
, patend
))
720 while (*name
++ != EOS
);
728 if ((k
= *name
++) == EOS
)
730 if ((negate_range
= ((*pat
& M_MASK
) == M_NOT
)) != EOS
)
732 while (((c
= *pat
++) & M_MASK
) != M_END
)
733 if ((*pat
& M_MASK
) == M_RNG
) {
734 if (c
<= k
&& k
<= pat
[1])
739 if (ok
== negate_range
)
748 return(*name
== EOS
);
751 /* Free allocated data belonging to a glob_t structure. */
753 openbsd_globfree(pglob
)
759 if (pglob
->gl_pathv
!= NULL
) {
760 pp
= pglob
->gl_pathv
+ pglob
->gl_offs
;
761 for (i
= pglob
->gl_pathc
; i
--; ++pp
)
764 free(pglob
->gl_pathv
);
769 g_opendir(str
, pglob
)
773 char buf
[MAXPATHLEN
];
780 if (pglob
->gl_flags
& GLOB_ALTDIRFUNC
)
781 return((*pglob
->gl_opendir
)(buf
));
783 return(opendir(buf
));
787 g_lstat(fn
, sb
, pglob
)
792 char buf
[MAXPATHLEN
];
795 if (pglob
->gl_flags
& GLOB_ALTDIRFUNC
)
796 return((*pglob
->gl_lstat
)(buf
, sb
));
797 return(lstat(buf
, sb
));
801 g_stat(fn
, sb
, pglob
)
806 char buf
[MAXPATHLEN
];
809 if (pglob
->gl_flags
& GLOB_ALTDIRFUNC
)
810 return((*pglob
->gl_stat
)(buf
, sb
));
811 return(stat(buf
, sb
));
837 while((*dst
++ = *src
++) != EOS
)
846 register const Char
*str
;
851 for (dc
= buf
; (*dc
++ = *str
++) != EOS
;)
863 (void)printf("%s:\n", str
);
865 (void)printf("%c", CHAR(*p
));
868 (void)printf("%c", *p
& M_PROTECT
? '"' : ' ');
871 (void)printf("%c", ismeta(*p
) ? '_' : ' ');