2 * Natanael Arndt, 2011: removed collate.h dependencies
3 * (my changes are trivial)
5 * Copyright (c) 1989, 1993
6 * The Regents of the University of California. All rights reserved.
8 * This code is derived from software contributed to Berkeley by
11 * Redistribution and use in source and binary forms, with or without
12 * modification, are permitted provided that the following conditions
14 * 1. Redistributions of source code must retain the above copyright
15 * notice, this list of conditions and the following disclaimer.
16 * 2. Redistributions in binary form must reproduce the above copyright
17 * notice, this list of conditions and the following disclaimer in the
18 * documentation and/or other materials provided with the distribution.
19 * 4. Neither the name of the University nor the names of its contributors
20 * may be used to endorse or promote products derived from this software
21 * without specific prior written permission.
23 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
24 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
25 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
26 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
27 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
28 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
29 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
30 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
31 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
32 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
36 #if defined(LIBC_SCCS) && !defined(lint)
37 static char sccsid
[] = "@(#)glob.c 8.3 (Berkeley) 10/13/93";
38 #endif /* LIBC_SCCS and not lint */
39 #include <sys/cdefs.h>
40 __FBSDID("$FreeBSD$");
43 * glob(3) -- a superset of the one defined in POSIX 1003.2.
45 * The [!...] convention to negate a range is supported (SysV, Posix, ksh).
47 * Optional extra services, controlled by flags not defined by POSIX:
50 * Escaping convention: \ inhibits any special meaning the following
51 * character might have (except \ at end of string is retained).
53 * Set in gl_flags if pattern contained a globbing character.
55 * Same as GLOB_NOCHECK, but it will only append pattern if it did
56 * not contain any magic characters. [Used in csh style globbing]
58 * Use alternately specified directory access functions.
60 * expand ~user/foo to the /home/dir/of/user/foo
62 * expand {1,2}{a,b} to 1a 1b 2a 2b
64 * Number of matches in the current invocation of glob.
68 * Some notes on multibyte character support:
69 * 1. Patterns with illegal byte sequences match nothing - even if
70 * GLOB_NOCHECK is specified.
71 * 2. Illegal byte sequences in filenames are handled by treating them as
72 * single-byte characters with a value of the first byte of the sequence
74 * 3. State-dependent encodings are not currently supported.
77 #include <sys/param.h>
105 #define UNDERSCORE '_'
113 #define M_QUOTE 0x8000000000ULL
114 #define M_PROTECT 0x4000000000ULL
115 #define M_MASK 0xffffffffffULL
116 #define M_CHAR 0x00ffffffffULL
118 typedef uint_fast64_t Char
;
123 #define M_PROTECT 0x40
132 #define CHAR(c) ((Char)((c)&M_CHAR))
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 int g_Ctoc(const Char
*, char *, size_t);
145 static int g_lstat(Char
*, struct stat
*, glob_t
*);
146 static DIR *g_opendir(Char
*, glob_t
*);
147 static const Char
*g_strchr(const Char
*, wchar_t);
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
*, size_t *);
153 static int glob1(Char
*, glob_t
*, size_t *);
154 static int glob2(Char
*, Char
*, Char
*, Char
*, glob_t
*, size_t *);
155 static int glob3(Char
*, Char
*, Char
*, Char
*, Char
*, glob_t
*, size_t *);
156 static int globextend(const Char
*, glob_t
*, size_t *);
158 globtilde(const Char
*, Char
*, size_t, glob_t
*);
159 static int globexp1(const Char
*, glob_t
*, size_t *);
160 static int globexp2(const Char
*, const Char
*, glob_t
*, int *, size_t *);
161 static int match(Char
*, Char
*, Char
*);
163 static void qprintf(const char *, Char
*);
167 glob(const char *pattern
, int flags
, int (*errfunc
)(const char *, int), glob_t
*pglob
)
171 Char
*bufnext
, *bufend
, patbuf
[MAXPATHLEN
], prot
;
177 if (!(flags
& GLOB_APPEND
)) {
179 pglob
->gl_pathv
= NULL
;
180 if (!(flags
& GLOB_DOOFFS
))
183 if (flags
& GLOB_LIMIT
) {
184 limit
= pglob
->gl_matchc
;
186 limit
= sysconf(_SC_ARG_MAX
);
189 pglob
->gl_flags
= flags
& ~GLOB_MAGCHAR
;
190 pglob
->gl_errfunc
= errfunc
;
191 pglob
->gl_matchc
= 0;
194 bufend
= bufnext
+ MAXPATHLEN
- 1;
195 if (flags
& GLOB_NOESCAPE
) {
196 memset(&mbs
, 0, sizeof(mbs
));
197 while (bufend
- bufnext
>= MB_CUR_MAX
) {
198 clen
= mbrtowc(&wc
, patnext
, MB_LEN_MAX
, &mbs
);
199 if (clen
== (size_t)-1 || clen
== (size_t)-2)
200 return (GLOB_NOMATCH
);
207 /* Protect the quoted characters. */
208 memset(&mbs
, 0, sizeof(mbs
));
209 while (bufend
- bufnext
>= MB_CUR_MAX
) {
210 if (*patnext
== QUOTE
) {
211 if (*++patnext
== EOS
) {
212 *bufnext
++ = QUOTE
| M_PROTECT
;
218 clen
= mbrtowc(&wc
, patnext
, MB_LEN_MAX
, &mbs
);
219 if (clen
== (size_t)-1 || clen
== (size_t)-2)
220 return (GLOB_NOMATCH
);
223 *bufnext
++ = wc
| prot
;
229 if (flags
& GLOB_BRACE
)
230 return globexp1(patbuf
, pglob
, &limit
);
232 return glob0(patbuf
, pglob
, &limit
);
236 * Expand recursively a glob {} pattern. When there is no more expansion
237 * invoke the standard globbing routine to glob the rest of the magic
241 globexp1(const Char
*pattern
, glob_t
*pglob
, size_t *limit
)
243 const Char
* ptr
= pattern
;
246 /* Protect a single {}, for find(1), like csh */
247 if (pattern
[0] == LBRACE
&& pattern
[1] == RBRACE
&& pattern
[2] == EOS
)
248 return glob0(pattern
, pglob
, limit
);
250 while ((ptr
= g_strchr(ptr
, LBRACE
)) != NULL
)
251 if (!globexp2(ptr
, pattern
, pglob
, &rv
, limit
))
254 return glob0(pattern
, pglob
, limit
);
259 * Recursive brace globbing helper. Tries to expand a single brace.
260 * If it succeeds then it invokes globexp1 with the new pattern.
261 * If it fails then it tries to glob the rest of the pattern and returns.
264 globexp2(const Char
*ptr
, const Char
*pattern
, glob_t
*pglob
, int *rv
, size_t *limit
)
268 const Char
*pe
, *pm
, *pm1
, *pl
;
269 Char patbuf
[MAXPATHLEN
];
271 /* copy part up to the brace */
272 for (lm
= patbuf
, pm
= pattern
; pm
!= ptr
; *lm
++ = *pm
++)
277 /* Find the balanced brace */
278 for (i
= 0, pe
= ++ptr
; *pe
; pe
++)
279 if (*pe
== LBRACKET
) {
280 /* Ignore everything between [] */
281 for (pm
= pe
++; *pe
!= RBRACKET
&& *pe
!= EOS
; pe
++)
285 * We could not find a matching RBRACKET.
286 * Ignore and just look for RBRACE
291 else if (*pe
== LBRACE
)
293 else if (*pe
== RBRACE
) {
299 /* Non matching braces; just glob the pattern */
300 if (i
!= 0 || *pe
== EOS
) {
301 *rv
= glob0(patbuf
, pglob
, limit
);
305 for (i
= 0, pl
= pm
= ptr
; pm
<= pe
; pm
++)
308 /* Ignore everything between [] */
309 for (pm1
= pm
++; *pm
!= RBRACKET
&& *pm
!= EOS
; pm
++)
313 * We could not find a matching RBRACKET.
314 * Ignore and just look for RBRACE
331 if (i
&& *pm
== COMMA
)
334 /* Append the current string */
335 for (lm
= ls
; (pl
< pm
); *lm
++ = *pl
++)
338 * Append the rest of the pattern after the
341 for (pl
= pe
+ 1; (*lm
++ = *pl
++) != EOS
;)
344 /* Expand the current pattern */
346 qprintf("globexp2:", patbuf
);
348 *rv
= globexp1(patbuf
, pglob
, limit
);
350 /* move after the comma, to the next string */
365 * expand tilde from the passwd file.
368 globtilde(const Char
*pattern
, Char
*patbuf
, size_t patbuf_len
, glob_t
*pglob
)
375 if (*pattern
!= TILDE
|| !(pglob
->gl_flags
& GLOB_TILDE
))
379 * Copy up to the end of the string or /
381 eb
= &patbuf
[patbuf_len
- 1];
382 for (p
= pattern
+ 1, h
= (char *) patbuf
;
383 h
< (char *)eb
&& *p
&& *p
!= SLASH
; *h
++ = *p
++)
388 if (((char *) patbuf
)[0] == EOS
) {
390 * handle a plain ~ or ~/ by expanding $HOME first (iff
391 * we're not running setuid or setgid) and then trying
398 (h
= getenv("HOME")) == NULL
) {
399 if (((h
= getlogin()) != NULL
&&
400 (pwd
= getpwnam(h
)) != NULL
) ||
401 (pwd
= getpwuid(getuid())) != NULL
)
411 if ((pwd
= getpwnam((char*) patbuf
)) == NULL
)
417 /* Copy the home directory */
418 for (b
= patbuf
; b
< eb
&& *h
; *b
++ = *h
++)
421 /* Append the rest of the pattern */
422 while (b
< eb
&& (*b
++ = *p
++) != EOS
)
431 * The main glob() routine: compiles the pattern (optionally processing
432 * quotes), calls glob1() to do the real pattern matching, and finally
433 * sorts the list (unless unsorted operation is requested). Returns 0
434 * if things went well, nonzero if errors occurred.
437 glob0(const Char
*pattern
, glob_t
*pglob
, size_t *limit
)
439 const Char
*qpatnext
;
442 Char
*bufnext
, c
, patbuf
[MAXPATHLEN
];
444 qpatnext
= globtilde(pattern
, patbuf
, MAXPATHLEN
, pglob
);
445 oldpathc
= pglob
->gl_pathc
;
448 /* We don't need to check for buffer overflow any more. */
449 while ((c
= *qpatnext
++) != EOS
) {
455 if (*qpatnext
== EOS
||
456 g_strchr(qpatnext
+1, RBRACKET
) == NULL
) {
457 *bufnext
++ = LBRACKET
;
467 *bufnext
++ = CHAR(c
);
468 if (*qpatnext
== RANGE
&&
469 (c
= qpatnext
[1]) != RBRACKET
) {
471 *bufnext
++ = CHAR(c
);
474 } while ((c
= *qpatnext
++) != RBRACKET
);
475 pglob
->gl_flags
|= GLOB_MAGCHAR
;
479 pglob
->gl_flags
|= GLOB_MAGCHAR
;
483 pglob
->gl_flags
|= GLOB_MAGCHAR
;
484 /* collapse adjacent stars to one,
485 * to avoid exponential behavior
487 if (bufnext
== patbuf
|| bufnext
[-1] != M_ALL
)
491 *bufnext
++ = CHAR(c
);
497 qprintf("glob0:", patbuf
);
500 if ((err
= glob1(patbuf
, pglob
, limit
)) != 0)
504 * If there was no match we are going to append the pattern
505 * if GLOB_NOCHECK was specified or if GLOB_NOMAGIC was specified
506 * and the pattern did not contain any magic characters
507 * GLOB_NOMAGIC is there just for compatibility with csh.
509 if (pglob
->gl_pathc
== oldpathc
) {
510 if (((pglob
->gl_flags
& GLOB_NOCHECK
) ||
511 ((pglob
->gl_flags
& GLOB_NOMAGIC
) &&
512 !(pglob
->gl_flags
& GLOB_MAGCHAR
))))
513 return(globextend(pattern
, pglob
, limit
));
515 return(GLOB_NOMATCH
);
517 if (!(pglob
->gl_flags
& GLOB_NOSORT
))
518 qsort(pglob
->gl_pathv
+ pglob
->gl_offs
+ oldpathc
,
519 pglob
->gl_pathc
- oldpathc
, sizeof(char *), compare
);
524 compare(const void *p
, const void *q
)
526 return(strcmp(*(char **)p
, *(char **)q
));
530 glob1(Char
*pattern
, glob_t
*pglob
, size_t *limit
)
532 Char pathbuf
[MAXPATHLEN
];
534 /* A null pathname is invalid -- POSIX 1003.1 sect. 2.4. */
537 return(glob2(pathbuf
, pathbuf
, pathbuf
+ MAXPATHLEN
- 1,
538 pattern
, pglob
, limit
));
542 * The functions glob2 and glob3 are mutually recursive; there is one level
543 * of recursion for each segment in the pattern that contains one or more
547 glob2(Char
*pathbuf
, Char
*pathend
, Char
*pathend_last
, Char
*pattern
,
548 glob_t
*pglob
, size_t *limit
)
555 * Loop over pattern segments until end of pattern or until
556 * segment with meta character found.
558 for (anymeta
= 0;;) {
559 if (*pattern
== EOS
) { /* End of pattern? */
561 if (g_lstat(pathbuf
, &sb
, pglob
))
564 if (((pglob
->gl_flags
& GLOB_MARK
) &&
565 pathend
[-1] != SEP
) && (S_ISDIR(sb
.st_mode
)
566 || (S_ISLNK(sb
.st_mode
) &&
567 (g_stat(pathbuf
, &sb
, pglob
) == 0) &&
568 S_ISDIR(sb
.st_mode
)))) {
569 if (pathend
+ 1 > pathend_last
)
570 return (GLOB_ABORTED
);
575 return(globextend(pathbuf
, pglob
, limit
));
578 /* Find end of next segment, copy tentatively to pathend. */
581 while (*p
!= EOS
&& *p
!= SEP
) {
584 if (q
+ 1 > pathend_last
)
585 return (GLOB_ABORTED
);
589 if (!anymeta
) { /* No expansion, do next segment. */
592 while (*pattern
== SEP
) {
593 if (pathend
+ 1 > pathend_last
)
594 return (GLOB_ABORTED
);
595 *pathend
++ = *pattern
++;
597 } else /* Need expansion, recurse. */
598 return(glob3(pathbuf
, pathend
, pathend_last
, pattern
, p
,
605 glob3(Char
*pathbuf
, Char
*pathend
, Char
*pathend_last
,
606 Char
*pattern
, Char
*restpattern
,
607 glob_t
*pglob
, size_t *limit
)
612 char buf
[MAXPATHLEN
];
615 * The readdirfunc declaration can't be prototyped, because it is
616 * assigned, below, to two functions which are prototyped in glob.h
617 * and dirent.h as taking pointers to differently typed opaque
620 struct dirent
*(*readdirfunc
)();
622 if (pathend
> pathend_last
)
623 return (GLOB_ABORTED
);
627 if ((dirp
= g_opendir(pathbuf
, pglob
)) == NULL
) {
628 /* TODO: don't call for ENOENT or ENOTDIR? */
629 if (pglob
->gl_errfunc
) {
630 if (g_Ctoc(pathbuf
, buf
, sizeof(buf
)))
631 return (GLOB_ABORTED
);
632 if (pglob
->gl_errfunc(buf
, errno
) ||
633 pglob
->gl_flags
& GLOB_ERR
)
634 return (GLOB_ABORTED
);
641 /* Search directory for matching names. */
642 if (pglob
->gl_flags
& GLOB_ALTDIRFUNC
)
643 readdirfunc
= pglob
->gl_readdir
;
645 readdirfunc
= readdir
;
646 while ((dp
= (*readdirfunc
)(dirp
))) {
653 /* Initial DOT must be matched literally. */
654 if (dp
->d_name
[0] == DOT
&& *pattern
!= DOT
)
656 memset(&mbs
, 0, sizeof(mbs
));
659 while (dc
< pathend_last
) {
660 clen
= mbrtowc(&wc
, sc
, MB_LEN_MAX
, &mbs
);
661 if (clen
== (size_t)-1 || clen
== (size_t)-2) {
664 memset(&mbs
, 0, sizeof(mbs
));
666 if ((*dc
++ = wc
) == EOS
)
670 if (!match(pathend
, pattern
, restpattern
)) {
674 err
= glob2(pathbuf
, --dc
, pathend_last
, restpattern
,
680 if (pglob
->gl_flags
& GLOB_ALTDIRFUNC
)
681 (*pglob
->gl_closedir
)(dirp
);
689 * Extend the gl_pathv member of a glob_t structure to accomodate a new item,
690 * add the new item, and update gl_pathc.
692 * This assumes the BSD realloc, which only copies the block when its size
693 * crosses a power-of-two boundary; for v7 realloc, this would cause quadratic
696 * Return 0 if new item added, error code if memory couldn't be allocated.
698 * Invariant of the glob_t structure:
699 * Either gl_pathc is zero and gl_pathv is NULL; or gl_pathc > 0 and
700 * gl_pathv points to (gl_offs + gl_pathc + 1) items.
703 globextend(const Char
*path
, glob_t
*pglob
, size_t *limit
)
706 size_t i
, newsize
, len
;
710 if (*limit
&& pglob
->gl_pathc
> *limit
) {
712 return (GLOB_NOSPACE
);
715 newsize
= sizeof(*pathv
) * (2 + pglob
->gl_pathc
+ pglob
->gl_offs
);
716 pathv
= pglob
->gl_pathv ?
717 realloc((char *)pglob
->gl_pathv
, newsize
) :
720 if (pglob
->gl_pathv
) {
721 free(pglob
->gl_pathv
);
722 pglob
->gl_pathv
= NULL
;
724 return(GLOB_NOSPACE
);
727 if (pglob
->gl_pathv
== NULL
&& pglob
->gl_offs
> 0) {
728 /* first time around -- clear initial gl_offs items */
729 pathv
+= pglob
->gl_offs
;
730 for (i
= pglob
->gl_offs
+ 1; --i
> 0; )
733 pglob
->gl_pathv
= pathv
;
735 for (p
= path
; *p
++;)
737 len
= MB_CUR_MAX
* (size_t)(p
- path
); /* XXX overallocation */
738 if ((copy
= malloc(len
)) != NULL
) {
739 if (g_Ctoc(path
, copy
, len
)) {
741 return (GLOB_NOSPACE
);
743 pathv
[pglob
->gl_offs
+ pglob
->gl_pathc
++] = copy
;
745 pathv
[pglob
->gl_offs
+ pglob
->gl_pathc
] = NULL
;
746 return(copy
== NULL ? GLOB_NOSPACE
: 0);
750 * pattern matching function for filenames. Each occurrence of the *
751 * pattern causes a recursion level.
754 match(Char
*name
, Char
*pat
, Char
*patend
)
756 int ok
, negate_range
;
759 while (pat
< patend
) {
761 switch (c
& M_MASK
) {
766 if (match(name
, pat
, patend
))
768 while (*name
++ != EOS
);
776 if ((k
= *name
++) == EOS
)
778 if ((negate_range
= ((*pat
& M_MASK
) == M_NOT
)) != EOS
)
780 while (((c
= *pat
++) & M_MASK
) != M_END
)
781 if ((*pat
& M_MASK
) == M_RNG
) {
782 if (CHAR(c
) <= CHAR(k
) && CHAR(k
) <= CHAR(pat
[1])) ok
= 1;
786 if (ok
== negate_range
)
795 return(*name
== EOS
);
798 /* Free allocated data belonging to a glob_t structure. */
800 globfree(glob_t
*pglob
)
805 if (pglob
->gl_pathv
!= NULL
) {
806 pp
= pglob
->gl_pathv
+ pglob
->gl_offs
;
807 for (i
= pglob
->gl_pathc
; i
--; ++pp
)
810 free(pglob
->gl_pathv
);
811 pglob
->gl_pathv
= NULL
;
816 g_opendir(Char
*str
, glob_t
*pglob
)
818 char buf
[MAXPATHLEN
];
823 if (g_Ctoc(str
, buf
, sizeof(buf
)))
827 if (pglob
->gl_flags
& GLOB_ALTDIRFUNC
)
828 return((*pglob
->gl_opendir
)(buf
));
830 return(opendir(buf
));
834 g_lstat(Char
*fn
, struct stat
*sb
, glob_t
*pglob
)
836 char buf
[MAXPATHLEN
];
838 if (g_Ctoc(fn
, buf
, sizeof(buf
))) {
839 errno
= ENAMETOOLONG
;
842 if (pglob
->gl_flags
& GLOB_ALTDIRFUNC
)
843 return((*pglob
->gl_lstat
)(buf
, sb
));
844 return(lstat(buf
, sb
));
848 g_stat(Char
*fn
, struct stat
*sb
, glob_t
*pglob
)
850 char buf
[MAXPATHLEN
];
852 if (g_Ctoc(fn
, buf
, sizeof(buf
))) {
853 errno
= ENAMETOOLONG
;
856 if (pglob
->gl_flags
& GLOB_ALTDIRFUNC
)
857 return((*pglob
->gl_stat
)(buf
, sb
));
858 return(stat(buf
, sb
));
862 g_strchr(const Char
*str
, wchar_t ch
)
873 g_Ctoc(const Char
*str
, char *buf
, size_t len
)
878 memset(&mbs
, 0, sizeof(mbs
));
879 while (len
>= MB_CUR_MAX
) {
880 clen
= wcrtomb(buf
, *str
, &mbs
);
881 if (clen
== (size_t)-1)
894 qprintf(const char *str
, Char
*s
)
898 (void)printf("%s:\n", str
);
900 (void)printf("%c", CHAR(*p
));
903 (void)printf("%c", *p
& M_PROTECT ?
'"' : ' ');
906 (void)printf("%c", ismeta(*p
) ?
'_' : ' ');