2 * Copyright (c) 1999 Apple Computer, Inc. All rights reserved.
4 * @APPLE_LICENSE_HEADER_START@
6 * Copyright (c) 1999-2003 Apple Computer, Inc. All Rights Reserved.
8 * This file contains Original Code and/or Modifications of Original Code
9 * as defined in and that are subject to the Apple Public Source License
10 * Version 2.0 (the 'License'). You may not use this file except in
11 * compliance with the License. Please obtain a copy of the License at
12 * http://www.opensource.apple.com/apsl/ and read it before using this
15 * The Original Code and all software distributed under the License are
16 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
17 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
18 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
19 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
20 * Please see the License for the specific language governing rights and
21 * limitations under the License.
23 * @APPLE_LICENSE_HEADER_END@
26 * Copyright (c) 1995 NeXT Computer, Inc. All Rights Reserved
28 * Copyright (c) 1989, 1993
29 * The Regents of the University of California. All rights reserved.
31 * This code is derived from software contributed to Berkeley by
34 * The NEXTSTEP Software License Agreement specifies the terms
35 * and conditions for redistribution.
37 * @(#)glob.c 8.3 (Berkeley) 10/13/93
41 * glob(3) -- a superset of the one defined in POSIX 1003.2.
43 * The [!...] convention to negate a range is supported (SysV, Posix, ksh).
45 * Optional extra services, controlled by flags not defined by POSIX:
48 * Escaping convention: \ inhibits any special meaning the following
49 * character might have (except \ at end of string is retained).
51 * Set in gl_flags if pattern contained a globbing character.
53 * Same as GLOB_NOCHECK, but it will only append pattern if it did
54 * not contain any magic characters. [Used in csh style globbing]
56 * Use alternately specified directory access functions.
58 * expand ~user/foo to the /home/dir/of/user/foo
60 * expand {1,2}{a,b} to 1a 1b 2a 2b
62 * Number of matches in the current invocation of glob.
65 #include <sys/param.h>
90 #define UNDERSCORE '_'
98 #define M_QUOTE 0x8000
99 #define M_PROTECT 0x4000
100 #define M_MASK 0xffff
101 #define M_ASCII 0x00ff
103 typedef u_short Char
;
108 #define M_PROTECT 0x40
117 #define CHAR(c) ((Char)((c)&M_ASCII))
118 #define META(c) ((Char)((c)|M_QUOTE))
119 #define M_ALL META('*')
120 #define M_END META(']')
121 #define M_NOT META('!')
122 #define M_ONE META('?')
123 #define M_RNG META('-')
124 #define M_SET META('[')
125 #define ismeta(c) (((c)&M_QUOTE) != 0)
128 static int compare
__P((const void *, const void *));
129 static int g_Ctoc
__P((const Char
*, char *, u_int
));
130 static int g_lstat
__P((Char
*, struct stat
*, glob_t
*));
131 static DIR *g_opendir
__P((Char
*, glob_t
*));
132 static Char
*g_strchr
__P((Char
*, int));
134 static Char
*g_strcat
__P((Char
*, const Char
*));
136 static int g_stat
__P((Char
*, struct stat
*, glob_t
*));
137 static int glob0
__P((const Char
*, glob_t
*, int *));
138 static int glob1
__P((Char
*, glob_t
*, int *));
139 static int glob2
__P((Char
*, Char
*, Char
*, Char
*, glob_t
*, int *));
140 static int glob3
__P((Char
*, Char
*, Char
*, Char
*, Char
*, glob_t
*, int *));
141 static int globextend
__P((const Char
*, glob_t
*, int *));
143 globtilde
__P((const Char
*, Char
*, size_t, glob_t
*));
144 static int globexp1
__P((const Char
*, glob_t
*, int *));
145 static int globexp2
__P((const Char
*, const Char
*, glob_t
*, int *, int *));
146 static int match
__P((Char
*, Char
*, Char
*));
148 static void qprintf
__P((const char *, Char
*));
152 glob(pattern
, flags
, errfunc
, pglob
)
154 int flags
, (*errfunc
) __P((const char *, int));
157 const u_char
*patnext
;
159 Char
*bufnext
, *bufend
, patbuf
[MAXPATHLEN
];
161 patnext
= (u_char
*) pattern
;
162 if (!(flags
& GLOB_APPEND
)) {
164 pglob
->gl_pathv
= NULL
;
165 if (!(flags
& GLOB_DOOFFS
))
168 #if !defined(GLOB_MAXPATH)
169 #define GLOB_MAXPATH 0x1000
171 if (flags
& GLOB_MAXPATH
)
172 limit
= pglob
->gl_matchc
;
175 pglob
->gl_flags
= flags
& ~GLOB_MAGCHAR
;
176 pglob
->gl_errfunc
= errfunc
;
177 pglob
->gl_matchc
= 0;
180 bufend
= bufnext
+ MAXPATHLEN
- 1;
181 if (flags
& GLOB_QUOTE
) {
182 /* Protect the quoted characters. */
183 while (bufnext
< bufend
&& (c
= *patnext
++) != EOS
)
185 if ((c
= *patnext
++) == EOS
) {
189 *bufnext
++ = c
| M_PROTECT
;
195 while (bufnext
< bufend
&& (c
= *patnext
++) != EOS
)
199 if (flags
& GLOB_BRACE
)
200 return globexp1(patbuf
, pglob
, &limit
);
202 return glob0(patbuf
, pglob
, &limit
);
206 * Expand recursively a glob {} pattern. When there is no more expansion
207 * invoke the standard globbing routine to glob the rest of the magic
211 globexp1(pattern
, pglob
, limit
)
216 const Char
* ptr
= pattern
;
219 /* Protect a single {}, for find(1), like csh */
220 if (pattern
[0] == LBRACE
&& pattern
[1] == RBRACE
&& pattern
[2] == EOS
)
221 return glob0(pattern
, pglob
, limit
);
223 while ((ptr
= (const Char
*) g_strchr((Char
*) ptr
, LBRACE
)) != NULL
)
224 if (!globexp2(ptr
, pattern
, pglob
, &rv
, limit
))
227 return glob0(pattern
, pglob
, limit
);
232 * Recursive brace globbing helper. Tries to expand a single brace.
233 * If it succeeds then it invokes globexp1 with the new pattern.
234 * If it fails then it tries to glob the rest of the pattern and returns.
237 globexp2(ptr
, pattern
, pglob
, rv
, limit
)
238 const Char
*ptr
, *pattern
;
244 const Char
*pe
, *pm
, *pl
;
245 Char patbuf
[MAXPATHLEN
];
247 /* copy part up to the brace */
248 for (lm
= patbuf
, pm
= pattern
; pm
!= ptr
; *lm
++ = *pm
++)
253 /* Find the balanced brace */
254 for (i
= 0, pe
= ++ptr
; *pe
; pe
++)
255 if (*pe
== LBRACKET
) {
256 /* Ignore everything between [] */
257 for (pm
= pe
++; *pe
!= RBRACKET
&& *pe
!= EOS
; pe
++)
261 * We could not find a matching RBRACKET.
262 * Ignore and just look for RBRACE
267 else if (*pe
== LBRACE
)
269 else if (*pe
== RBRACE
) {
275 /* Non matching braces; just glob the pattern */
276 if (i
!= 0 || *pe
== EOS
) {
277 *rv
= glob0(patbuf
, pglob
, limit
);
281 for (i
= 0, pl
= pm
= ptr
; pm
<= pe
; pm
++)
284 /* Ignore everything between [] */
285 for (pl
= pm
++; *pm
!= RBRACKET
&& *pm
!= EOS
; pm
++)
289 * We could not find a matching RBRACKET.
290 * Ignore and just look for RBRACE
307 if (i
&& *pm
== COMMA
)
310 /* Append the current string */
311 for (lm
= ls
; (pl
< pm
); *lm
++ = *pl
++)
314 * Append the rest of the pattern after the
317 for (pl
= pe
+ 1; (*lm
++ = *pl
++) != EOS
;)
320 /* Expand the current pattern */
322 qprintf("globexp2:", patbuf
);
324 *rv
= globexp1(patbuf
, pglob
, limit
);
326 /* move after the comma, to the next string */
341 * expand tilde from the passwd file.
344 globtilde(pattern
, patbuf
, patbuf_len
, pglob
)
355 if (*pattern
!= TILDE
|| !(pglob
->gl_flags
& GLOB_TILDE
))
359 * Copy up to the end of the string or /
361 eb
= &patbuf
[patbuf_len
- 1];
362 for (p
= pattern
+ 1, h
= (char *) patbuf
;
363 h
< (char *)eb
&& *p
&& *p
!= SLASH
; *h
++ = *p
++)
368 if (((char *) patbuf
)[0] == EOS
) {
370 * handle a plain ~ or ~/ by expanding $HOME first (iff
371 * we're not running setuid or setgid) and then trying
376 #ifndef __NETBSD_SYSCALLS
380 (h
= getenv("HOME")) == NULL
) {
381 if (((h
= getlogin()) != NULL
&&
382 (pwd
= getpwnam(h
)) != NULL
) ||
383 (pwd
= getpwuid(getuid())) != NULL
)
393 if ((pwd
= getpwnam((char*) patbuf
)) == NULL
)
399 /* Copy the home directory */
400 for (b
= patbuf
; b
< eb
&& *h
; *b
++ = *h
++)
403 /* Append the rest of the pattern */
404 while (b
< eb
&& (*b
++ = *p
++) != EOS
)
413 * The main glob() routine: compiles the pattern (optionally processing
414 * quotes), calls glob1() to do the real pattern matching, and finally
415 * sorts the list (unless unsorted operation is requested). Returns 0
416 * if things went well, nonzero if errors occurred. It is not an error
417 * to find no matches.
420 glob0(pattern
, pglob
, limit
)
425 const Char
*qpatnext
;
426 int c
, err
, oldpathc
;
427 Char
*bufnext
, patbuf
[MAXPATHLEN
];
429 qpatnext
= globtilde(pattern
, patbuf
, MAXPATHLEN
, pglob
);
430 oldpathc
= pglob
->gl_pathc
;
433 /* We don't need to check for buffer overflow any more. */
434 while ((c
= *qpatnext
++) != EOS
) {
440 if (*qpatnext
== EOS
||
441 g_strchr((Char
*) qpatnext
+1, RBRACKET
) == NULL
) {
442 *bufnext
++ = LBRACKET
;
452 *bufnext
++ = CHAR(c
);
453 if (*qpatnext
== RANGE
&&
454 (c
= qpatnext
[1]) != RBRACKET
) {
456 *bufnext
++ = CHAR(c
);
459 } while ((c
= *qpatnext
++) != RBRACKET
);
460 pglob
->gl_flags
|= GLOB_MAGCHAR
;
464 pglob
->gl_flags
|= GLOB_MAGCHAR
;
468 pglob
->gl_flags
|= GLOB_MAGCHAR
;
469 /* collapse adjacent stars to one,
470 * to avoid exponential behavior
472 if (bufnext
== patbuf
|| bufnext
[-1] != M_ALL
)
476 *bufnext
++ = CHAR(c
);
482 qprintf("glob0:", patbuf
);
485 if ((err
= glob1(patbuf
, pglob
, limit
)) != 0)
489 * If there was no match we are going to append the pattern
490 * if GLOB_NOCHECK was specified or if GLOB_NOMAGIC was specified
491 * and the pattern did not contain any magic characters
492 * GLOB_NOMAGIC is there just for compatibility with csh.
494 if (pglob
->gl_pathc
== oldpathc
&&
495 ((pglob
->gl_flags
& GLOB_NOCHECK
) ||
496 ((pglob
->gl_flags
& GLOB_NOMAGIC
) &&
497 !(pglob
->gl_flags
& GLOB_MAGCHAR
))))
498 return(globextend(pattern
, pglob
, limit
));
499 else if (!(pglob
->gl_flags
& GLOB_NOSORT
))
500 qsort(pglob
->gl_pathv
+ pglob
->gl_offs
+ oldpathc
,
501 pglob
->gl_pathc
- oldpathc
, sizeof(char *), compare
);
509 return(strcmp(*(char **)p
, *(char **)q
));
513 glob1(pattern
, pglob
, limit
)
518 Char pathbuf
[MAXPATHLEN
];
520 /* A null pathname is invalid -- POSIX 1003.1 sect. 2.4. */
523 return(glob2(pathbuf
, pathbuf
, pathbuf
+ MAXPATHLEN
- 1,
524 pattern
, pglob
, limit
));
528 * The functions glob2 and glob3 are mutually recursive; there is one level
529 * of recursion for each segment in the pattern that contains one or more
533 glob2(pathbuf
, pathend
, pathend_last
, pattern
, pglob
, limit
)
534 Char
*pathbuf
, *pathend
, *pathend_last
, *pattern
;
543 * Loop over pattern segments until end of pattern or until
544 * segment with meta character found.
546 for (anymeta
= 0;;) {
547 if (*pattern
== EOS
) { /* End of pattern? */
549 if (g_lstat(pathbuf
, &sb
, pglob
))
552 if (((pglob
->gl_flags
& GLOB_MARK
) &&
553 pathend
[-1] != SEP
) && (S_ISDIR(sb
.st_mode
)
554 || (S_ISLNK(sb
.st_mode
) &&
555 (g_stat(pathbuf
, &sb
, pglob
) == 0) &&
556 S_ISDIR(sb
.st_mode
)))) {
557 if (pathend
+ 1 > pathend_last
)
563 return(globextend(pathbuf
, pglob
, limit
));
566 /* Find end of next segment, copy tentatively to pathend. */
569 while (*p
!= EOS
&& *p
!= SEP
) {
572 if (q
+ 1 > pathend_last
)
577 if (!anymeta
) { /* No expansion, do next segment. */
580 while (*pattern
== SEP
) {
581 if (pathend
+ 1 > pathend_last
)
583 *pathend
++ = *pattern
++;
585 } else /* Need expansion, recurse. */
586 return(glob3(pathbuf
, pathend
, pathend_last
, pattern
, p
,
593 glob3(pathbuf
, pathend
, pathend_last
, pattern
, restpattern
, pglob
, limit
)
594 Char
*pathbuf
, *pathend
, *pathend_last
, *pattern
, *restpattern
;
598 register struct dirent
*dp
;
601 char buf
[MAXPATHLEN
];
604 * The readdirfunc declaration can't be prototyped, because it is
605 * assigned, below, to two functions which are prototyped in glob.h
606 * and dirent.h as taking pointers to differently typed opaque
609 struct dirent
*(*readdirfunc
)();
611 if (pathend
> pathend_last
)
616 if ((dirp
= g_opendir(pathbuf
, pglob
)) == NULL
) {
617 /* TODO: don't call for ENOENT or ENOTDIR? */
618 if (pglob
->gl_errfunc
) {
619 if (g_Ctoc(pathbuf
, buf
, sizeof(buf
)))
621 if (pglob
->gl_errfunc(buf
, errno
) ||
622 pglob
->gl_flags
& GLOB_ERR
)
630 /* Search directory for matching names. */
631 if (pglob
->gl_flags
& GLOB_ALTDIRFUNC
)
632 readdirfunc
= pglob
->gl_readdir
;
634 readdirfunc
= readdir
;
635 while ((dp
= (*readdirfunc
)(dirp
))) {
639 /* Initial DOT must be matched literally. */
640 if (dp
->d_name
[0] == DOT
&& *pattern
!= DOT
)
643 sc
= (u_char
*) dp
->d_name
;
644 while (dc
< pathend_last
&& (*dc
++ = *sc
++) != EOS
)
646 if (!match(pathend
, pattern
, restpattern
)) {
650 err
= glob2(pathbuf
, --dc
, pathend_last
, restpattern
,
656 if (pglob
->gl_flags
& GLOB_ALTDIRFUNC
)
657 (*pglob
->gl_closedir
)(dirp
);
665 * Extend the gl_pathv member of a glob_t structure to accomodate a new item,
666 * add the new item, and update gl_pathc.
668 * This assumes the BSD realloc, which only copies the block when its size
669 * crosses a power-of-two boundary; for v7 realloc, this would cause quadratic
672 * Return 0 if new item added, error code if memory couldn't be allocated.
674 * Invariant of the glob_t structure:
675 * Either gl_pathc is zero and gl_pathv is NULL; or gl_pathc > 0 and
676 * gl_pathv points to (gl_offs + gl_pathc + 1) items.
679 globextend(path
, pglob
, limit
)
684 register char **pathv
;
690 if (*limit
&& pglob
->gl_pathc
> *limit
)
691 #if !defined(GLOB_LIMIT)
692 #define GLOB_LIMIT (-3)
696 newsize
= sizeof(*pathv
) * (2 + pglob
->gl_pathc
+ pglob
->gl_offs
);
697 pathv
= pglob
->gl_pathv ?
698 realloc((char *)pglob
->gl_pathv
, newsize
) :
701 if (pglob
->gl_pathv
) {
702 free(pglob
->gl_pathv
);
703 pglob
->gl_pathv
= NULL
;
705 return(GLOB_NOSPACE
);
708 if (pglob
->gl_pathv
== NULL
&& pglob
->gl_offs
> 0) {
709 /* first time around -- clear initial gl_offs items */
710 pathv
+= pglob
->gl_offs
;
711 for (i
= pglob
->gl_offs
; --i
>= 0; )
714 pglob
->gl_pathv
= pathv
;
716 for (p
= path
; *p
++;)
718 len
= (size_t)(p
- path
);
719 if ((copy
= malloc(len
)) != NULL
) {
720 if (g_Ctoc(path
, copy
, len
)) {
722 return (GLOB_NOSPACE
);
724 pathv
[pglob
->gl_offs
+ pglob
->gl_pathc
++] = copy
;
726 pathv
[pglob
->gl_offs
+ pglob
->gl_pathc
] = NULL
;
727 return(copy
== NULL ? GLOB_NOSPACE
: 0);
731 * pattern matching function for filenames. Each occurrence of the *
732 * pattern causes a recursion level.
735 match(name
, pat
, patend
)
736 register Char
*name
, *pat
, *patend
;
738 int ok
, negate_range
;
741 while (pat
< patend
) {
743 switch (c
& M_MASK
) {
748 if (match(name
, pat
, patend
))
750 while (*name
++ != EOS
);
758 if ((k
= *name
++) == EOS
)
760 if ((negate_range
= ((*pat
& M_MASK
) == M_NOT
)) != EOS
)
762 while (((c
= *pat
++) & M_MASK
) != M_END
)
763 if ((*pat
& M_MASK
) == M_RNG
) {
764 if (c
<= k
&& k
<= pat
[1])
769 if (ok
== negate_range
)
778 return(*name
== EOS
);
781 /* Free allocated data belonging to a glob_t structure. */
789 if (pglob
->gl_pathv
!= NULL
) {
790 pp
= pglob
->gl_pathv
+ pglob
->gl_offs
;
791 for (i
= pglob
->gl_pathc
; i
--; ++pp
)
794 free(pglob
->gl_pathv
);
795 pglob
->gl_pathv
= NULL
;
800 g_opendir(str
, pglob
)
804 char buf
[MAXPATHLEN
];
809 if (g_Ctoc(str
, buf
, sizeof(buf
)))
813 if (pglob
->gl_flags
& GLOB_ALTDIRFUNC
)
814 return((*pglob
->gl_opendir
)(buf
));
816 return(opendir(buf
));
820 g_lstat(fn
, sb
, pglob
)
825 char buf
[MAXPATHLEN
];
827 if (g_Ctoc(fn
, buf
, sizeof(buf
))) {
828 errno
= ENAMETOOLONG
;
831 if (pglob
->gl_flags
& GLOB_ALTDIRFUNC
)
832 return((*pglob
->gl_lstat
)(buf
, sb
));
833 return(lstat(buf
, sb
));
837 g_stat(fn
, sb
, pglob
)
842 char buf
[MAXPATHLEN
];
844 if (g_Ctoc(fn
, buf
, sizeof(buf
))) {
845 errno
= ENAMETOOLONG
;
848 if (pglob
->gl_flags
& GLOB_ALTDIRFUNC
)
849 return((*pglob
->gl_stat
)(buf
, sb
));
850 return(stat(buf
, sb
));
866 g_Ctoc(str
, buf
, len
)
873 if ((*buf
++ = *str
++) == '\0')
887 (void)printf("%s:\n", str
);
889 (void)printf("%c", CHAR(*p
));
892 (void)printf("%c", *p
& M_PROTECT ?
'"' : ' ');
895 (void)printf("%c", ismeta(*p
) ?
'_' : ' ');