2 * Copyright (c) 1989 The Regents of the University of California.
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. Neither the name of the University nor the names of its contributors
17 * may be used to endorse or promote products derived from this software
18 * without specific prior written permission.
20 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
21 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
22 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
23 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
24 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
25 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
26 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
27 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
28 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
29 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
32 #if defined(LIBC_SCCS) && !defined(lint)
33 static char sccsid
[] = "@(#)glob.c 5.12 (Berkeley) 6/24/91";
34 #endif /* LIBC_SCCS and not lint */
36 * Glob: the interface is a superset of the one defined in POSIX 1003.2,
39 * The [!...] convention to negate a range is supported (SysV, Posix, ksh).
41 * Optional extra services, controlled by flags not defined by POSIX:
44 * Escaping convention: \ inhibits any special meaning the following
45 * character might have (except \ at end of string is retained).
47 * Set in gl_flags if pattern contained a globbing character.
49 * Use ^ instead of ! for "not".
51 * Number of matches in the current invocation of glob.
55 #pragma warning(disable:4244)
56 #endif /* WINNT_NATIVE */
70 #define S_ISDIR(a) (((a) & S_IFMT) == S_IFDIR)
73 #if !defined(S_ISLNK) && defined(S_IFLNK)
74 #define S_ISLNK(a) (((a) & S_IFMT) == S_IFLNK)
77 #if !defined(S_ISLNK) && !defined(lstat)
81 typedef unsigned short Char
;
83 static int glob1 (Char
*, glob_t
*, int);
84 static int glob2 (struct strbuf
*, const Char
*, glob_t
*, int);
85 static int glob3 (struct strbuf
*, const Char
*, const Char
*,
86 const Char
*, glob_t
*, int);
87 static void globextend (const char *, glob_t
*);
88 static int match (const char *, const Char
*, const Char
*,
90 static int compare (const void *, const void *);
91 static DIR *Opendir (const char *);
93 static int Lstat (const char *, struct stat
*);
95 static int Stat (const char *, struct stat
*sb
);
96 static Char
*Strchr (Char
*, int);
98 static void qprintf (const Char
*);
114 #define UNDERSCORE '_'
116 #define M_META 0x8000
117 #define M_PROTECT 0x4000
118 #define M_MASK 0xffff
119 #define M_ASCII 0x00ff
121 #define LCHAR(c) ((c)&M_ASCII)
122 #define META(c) ((c)|M_META)
123 #define M_ALL META('*')
124 #define M_END META(']')
125 #define M_NOT META('!')
126 #define M_ALTNOT META('^')
127 #define M_ONE META('?')
128 #define M_RNG META('-')
129 #define M_SET META('[')
130 #define ismeta(c) (((c)&M_META) != 0)
133 globcharcoll(__Char c1
, __Char c2
, int cs
)
135 #if defined(NLS) && defined(LC_COLLATE) && defined(HAVE_STRCOLL)
136 # if defined(WIDE_STRINGS)
137 wchar_t s1
[2], s2
[2];
145 /* This should not be here, but I'll rather leave it in than engage in
146 a LC_COLLATE flamewar about a shell I don't use... */
147 if (iswlower(c1
) && iswupper(c2
))
149 if (iswupper(c1
) && iswlower(c2
))
154 s1
[1] = s2
[1] = '\0';
155 return wcscoll(s1
, s2
);
156 # else /* not WIDE_STRINGS */
162 * From kevin lyda <kevin@suberic.net>:
163 * strcoll does not guarantee case sorting, so we pre-process now:
166 c1
= islower(c1
) ? c1
: tolower(c1
);
167 c2
= islower(c2
) ? c2
: tolower(c2
);
169 if (islower(c1
) && isupper(c2
))
171 if (isupper(c1
) && islower(c2
))
176 s1
[1] = s2
[1] = '\0';
177 return strcoll(s1
, s2
);
185 * Need to dodge two kernel bugs:
186 * opendir("") != opendir(".")
187 * NAMEI_BUG: on plain files trailing slashes are ignored in some kernels.
188 * POSIX specifies that they should be ignored in directories.
192 Opendir(const char *str
)
194 #if defined(hpux) || defined(__hpux)
199 return (opendir("."));
200 #if defined(hpux) || defined(__hpux)
202 * Opendir on some device files hangs, so avoid it
204 if (stat(str
, &st
) == -1 || !S_ISDIR(st
.st_mode
))
212 Lstat(const char *fn
, struct stat
*sb
)
218 if (*fn
!= 0 && strend(fn
)[-1] == '/' && !S_ISDIR(sb
->st_mode
))
220 # endif /* NAMEI_BUG */
228 Stat(const char *fn
, struct stat
*sb
)
234 if (*fn
!= 0 && strend(fn
)[-1] == '/' && !S_ISDIR(sb
->st_mode
))
236 #endif /* NAMEI_BUG */
241 Strchr(Char
*str
, int ch
)
252 qprintf(const Char
*s
)
257 printf("%c", *p
& 0xff);
260 printf("%c", *p
& M_PROTECT
? '"' : ' ');
263 printf("%c", *p
& M_META
? '_' : ' ');
269 compare(const void *p
, const void *q
)
271 #if defined(NLS) && defined(HAVE_STRCOLL)
272 return (strcoll(*(char *const *) p
, *(char *const *) q
));
274 return (strcmp(*(char *const *) p
, *(char *const *) q
));
275 #endif /* NLS && HAVE_STRCOLL */
279 * The main glob() routine: compiles the pattern (optionally processing
280 * quotes), calls glob1() to do the real pattern matching, and finally
281 * sorts the list (unless unsorted operation is requested). Returns 0
282 * if things went well, nonzero if errors occurred. It is not an error
283 * to find no matches.
286 glob(const char *pattern
, int flags
, int (*errfunc
) (const char *, int),
290 Char
*bufnext
, m_not
;
291 const unsigned char *patnext
;
293 Char
*qpatnext
, *patbuf
;
296 patnext
= (const unsigned char *) pattern
;
297 if (!(flags
& GLOB_APPEND
)) {
299 pglob
->gl_pathv
= NULL
;
300 if (!(flags
& GLOB_DOOFFS
))
303 pglob
->gl_flags
= flags
& ~GLOB_MAGCHAR
;
304 pglob
->gl_errfunc
= errfunc
;
305 oldpathc
= pglob
->gl_pathc
;
306 pglob
->gl_matchc
= 0;
308 if (pglob
->gl_flags
& GLOB_ALTNOT
) {
317 patbuf
= xmalloc((strlen(pattern
) + 1) * sizeof(*patbuf
));
320 no_match
= *patnext
== not;
324 if (flags
& GLOB_QUOTE
) {
325 /* Protect the quoted characters */
326 while ((c
= *patnext
++) != EOS
) {
330 len
= mblen((const char *)(patnext
- 1), MB_LEN_MAX
);
332 TCSH_IGNORE(mblen(NULL
, 0));
334 *bufnext
++ = (Char
) c
;
336 *bufnext
++ = (Char
) (*patnext
++ | M_PROTECT
);
338 #endif /* WIDE_STRINGS */
340 if ((c
= *patnext
++) == EOS
) {
344 *bufnext
++ = (Char
) (c
| M_PROTECT
);
347 *bufnext
++ = (Char
) c
;
351 while ((c
= *patnext
++) != EOS
)
352 *bufnext
++ = (Char
) c
;
357 while ((c
= *qpatnext
++) != EOS
) {
363 if (*qpatnext
== EOS
||
364 Strchr(qpatnext
+ 1, RBRACKET
) == NULL
) {
365 *bufnext
++ = LBRACKET
;
370 pglob
->gl_flags
|= GLOB_MAGCHAR
;
376 *bufnext
++ = LCHAR(c
);
377 if (*qpatnext
== RANGE
&&
378 (c
= qpatnext
[1]) != RBRACKET
) {
380 *bufnext
++ = LCHAR(c
);
383 } while ((c
= *qpatnext
++) != RBRACKET
);
387 pglob
->gl_flags
|= GLOB_MAGCHAR
;
391 pglob
->gl_flags
|= GLOB_MAGCHAR
;
392 /* collapse adjacent stars to one [or three if globstar],
393 * to avoid exponential behavior
395 if (bufnext
== patbuf
|| bufnext
[-1] != M_ALL
||
396 ((flags
& GLOB_STAR
) != 0 &&
397 (bufnext
- 1 == patbuf
|| bufnext
[-2] != M_ALL
||
398 bufnext
- 2 == patbuf
|| bufnext
[-3] != M_ALL
)))
402 *bufnext
++ = LCHAR(c
);
411 if ((err
= glob1(patbuf
, pglob
, no_match
)) != 0) {
417 * If there was no match we are going to append the pattern
418 * if GLOB_NOCHECK was specified or if GLOB_NOMAGIC was specified
419 * and the pattern did not contain any magic characters
420 * GLOB_NOMAGIC is there just for compatibility with csh.
422 if (pglob
->gl_pathc
== oldpathc
&&
423 ((flags
& GLOB_NOCHECK
) ||
424 ((flags
& GLOB_NOMAGIC
) && !(pglob
->gl_flags
& GLOB_MAGCHAR
)))) {
425 if (!(flags
& GLOB_QUOTE
))
426 globextend(pattern
, pglob
);
431 /* copy pattern, interpreting quotes */
432 copy
= xmalloc(strlen(pattern
) + 1);
435 while (*src
!= EOS
) {
436 /* Don't interpret quotes. The spec does not say we should do */
444 globextend(copy
, pglob
);
450 else if (!(flags
& GLOB_NOSORT
) && (pglob
->gl_pathc
!= oldpathc
))
451 qsort(pglob
->gl_pathv
+ pglob
->gl_offs
+ oldpathc
,
452 pglob
->gl_pathc
- oldpathc
, sizeof(char *), compare
);
458 glob1(Char
*pattern
, glob_t
*pglob
, int no_match
)
460 struct strbuf pathbuf
= strbuf_INIT
;
464 * a null pathname is invalid -- POSIX 1003.1 sect. 2.4.
468 err
= glob2(&pathbuf
, pattern
, pglob
, no_match
);
474 * functions glob2 and glob3 are mutually recursive; there is one level
475 * of recursion for each segment in the pattern that contains one or
476 * more meta characters.
479 glob2(struct strbuf
*pathbuf
, const Char
*pattern
, glob_t
*pglob
, int no_match
)
487 * loop over pattern segments until end of pattern or until segment with
488 * meta character found.
492 if (*pattern
== EOS
) { /* end of pattern? */
493 strbuf_terminate(pathbuf
);
495 if (Lstat(pathbuf
->s
, &sbuf
))
498 if (((pglob
->gl_flags
& GLOB_MARK
) &&
499 pathbuf
->s
[pathbuf
->len
- 1] != SEP
) &&
500 (S_ISDIR(sbuf
.st_mode
)
502 || (S_ISLNK(sbuf
.st_mode
) &&
503 (Stat(pathbuf
->s
, &sbuf
) == 0) &&
504 S_ISDIR(sbuf
.st_mode
))
507 strbuf_append1(pathbuf
, SEP
);
508 strbuf_terminate(pathbuf
);
511 globextend(pathbuf
->s
, pglob
);
515 /* find end of next segment, tentatively copy to pathbuf */
517 orig_len
= pathbuf
->len
;
518 while (*p
!= EOS
&& *p
!= SEP
) {
521 strbuf_append1(pathbuf
, *p
++);
524 if (!anymeta
) { /* no expansion, do next segment */
526 while (*pattern
== SEP
)
527 strbuf_append1(pathbuf
, *pattern
++);
529 else { /* need expansion, recurse */
530 pathbuf
->len
= orig_len
;
531 return (glob3(pathbuf
, pattern
, p
, pattern
, pglob
, no_match
));
538 One_Char_mbtowc(__Char
*pwc
, const Char
*s
, size_t n
)
541 char buf
[MB_LEN_MAX
], *p
;
546 while (p
< buf
+ n
&& (*p
++ = LCHAR(*s
++)) != 0)
548 return one_mbtowc(pwc
, buf
, n
);
556 glob3(struct strbuf
*pathbuf
, const Char
*pattern
, const Char
*restpattern
,
557 const Char
*pglobstar
, glob_t
*pglob
, int no_match
)
563 Char m_not
= (pglob
->gl_flags
& GLOB_ALTNOT
) ? M_ALTNOT
: M_NOT
;
566 int chase_symlinks
= 0;
567 const Char
*termstar
= NULL
;
569 strbuf_terminate(pathbuf
);
570 orig_len
= pathbuf
->len
;
573 while (pglobstar
< restpattern
) {
575 size_t width
= One_Char_mbtowc(&wc
, pglobstar
, MB_LEN_MAX
);
576 if ((pglobstar
[0] & M_MASK
) == M_ALL
&&
577 (pglobstar
[width
] & M_MASK
) == M_ALL
) {
579 chase_symlinks
= (pglobstar
[2 * width
] & M_MASK
) == M_ALL
;
580 termstar
= pglobstar
+ (2 + chase_symlinks
) * width
;
587 err
= pglobstar
==pattern
&& termstar
==restpattern
?
588 *restpattern
== EOS
?
589 glob2(pathbuf
, restpattern
- 1, pglob
, no_match
) :
590 glob2(pathbuf
, restpattern
+ 1, pglob
, no_match
) :
591 glob3(pathbuf
, pattern
, restpattern
, termstar
, pglob
, no_match
);
594 pathbuf
->len
= orig_len
;
595 strbuf_terminate(pathbuf
);
598 if (*pathbuf
->s
&& (Lstat(pathbuf
->s
, &sbuf
) || !S_ISDIR(sbuf
.st_mode
)
600 && ((globstar
&& !chase_symlinks
) || !S_ISLNK(sbuf
.st_mode
))
605 if (!(dirp
= Opendir(pathbuf
->s
))) {
606 /* todo: don't call for ENOENT or ENOTDIR? */
607 if ((pglob
->gl_errfunc
&& (*pglob
->gl_errfunc
) (pathbuf
->s
, errno
)) ||
608 (pglob
->gl_flags
& GLOB_ERR
))
614 /* search directory for matching names */
615 while ((dp
= readdir(dirp
)) != NULL
) {
616 /* initial DOT must be matched literally */
617 if (dp
->d_name
[0] == DOT
&& *pattern
!= DOT
)
618 if (!(pglob
->gl_flags
& GLOB_DOT
) || !dp
->d_name
[1] ||
619 (dp
->d_name
[1] == DOT
&& !dp
->d_name
[2]))
620 continue; /*unless globdot and not . or .. */
621 pathbuf
->len
= orig_len
;
622 strbuf_append(pathbuf
, dp
->d_name
);
623 strbuf_terminate(pathbuf
);
627 if (!chase_symlinks
&&
628 (Lstat(pathbuf
->s
, &sbuf
) || S_ISLNK(sbuf
.st_mode
)))
631 if (match(pathbuf
->s
+ orig_len
, pattern
, termstar
,
632 (int)m_not
) == no_match
)
634 strbuf_append1(pathbuf
, SEP
);
635 strbuf_terminate(pathbuf
);
636 if ((err
= glob2(pathbuf
, pglobstar
, pglob
, no_match
)) != 0)
639 if (match(pathbuf
->s
+ orig_len
, pattern
, restpattern
,
640 (int) m_not
) == no_match
)
642 if ((err
= glob2(pathbuf
, restpattern
, pglob
, no_match
)) != 0)
646 /* todo: check error from readdir? */
653 * Extend the gl_pathv member of a glob_t structure to accomodate a new item,
654 * add the new item, and update gl_pathc.
656 * This assumes the BSD realloc, which only copies the block when its size
657 * crosses a power-of-two boundary; for v7 realloc, this would cause quadratic
660 * Return 0 if new item added, error code if memory couldn't be allocated.
662 * Invariant of the glob_t structure:
663 * Either gl_pathc is zero and gl_pathv is NULL; or gl_pathc > 0 and
664 * gl_pathv points to (gl_offs + gl_pathc + 1) items.
667 globextend(const char *path
, glob_t
*pglob
)
673 newsize
= sizeof(*pathv
) * (2 + pglob
->gl_pathc
+ pglob
->gl_offs
);
674 pathv
= xrealloc(pglob
->gl_pathv
, newsize
);
676 if (pglob
->gl_pathv
== NULL
&& pglob
->gl_offs
> 0) {
677 /* first time around -- clear initial gl_offs items */
678 pathv
+= pglob
->gl_offs
;
679 for (i
= pglob
->gl_offs
; --i
>= 0;)
682 pglob
->gl_pathv
= pathv
;
684 pathv
[pglob
->gl_offs
+ pglob
->gl_pathc
++] = strsave(path
);
685 pathv
[pglob
->gl_offs
+ pglob
->gl_pathc
] = NULL
;
689 * pattern matching function for filenames. Each occurrence of the *
690 * pattern causes a recursion level.
693 match(const char *name
, const Char
*pat
, const Char
*patend
, int m_not
)
695 int ok
, negate_range
;
698 while (pat
< patend
) {
702 c
= *pat
; /* Only for M_MASK bits */
703 pat
+= One_Char_mbtowc(&wc
, pat
, MB_LEN_MAX
);
704 lwk
= one_mbtowc(&wk
, name
, MB_LEN_MAX
);
705 switch (c
& M_MASK
) {
707 while (pat
< patend
&& (*pat
& M_MASK
) == M_ALL
) /* eat consecutive '*' */
708 pat
+= One_Char_mbtowc(&wc
, pat
, MB_LEN_MAX
);
711 while (!match(name
, pat
, patend
, m_not
)) {
715 lwk
= one_mbtowc(&wk
, name
, MB_LEN_MAX
);
728 if ((negate_range
= ((*pat
& M_MASK
) == m_not
)) != 0)
730 while ((*pat
& M_MASK
) != M_END
) {
731 pat
+= One_Char_mbtowc(&wc
, pat
, MB_LEN_MAX
);
732 if ((*pat
& M_MASK
) == M_RNG
) {
736 pat
+= One_Char_mbtowc(&wc2
, pat
, MB_LEN_MAX
);
737 if (globcharcoll(wc
, wk
, 0) <= 0 &&
738 globcharcoll(wk
, wc2
, 0) <= 0)
743 pat
+= One_Char_mbtowc(&wc
, pat
, MB_LEN_MAX
);
744 if (ok
== negate_range
)
748 if (*name
== EOS
|| samecase(wk
) != samecase(wc
))
754 return (*name
== EOS
);
757 /* free allocated data belonging to a glob_t structure */
759 globfree(glob_t
*pglob
)
764 if (pglob
->gl_pathv
!= NULL
) {
765 pp
= pglob
->gl_pathv
+ pglob
->gl_offs
;
766 for (i
= pglob
->gl_pathc
; i
--; ++pp
)
768 xfree(*pp
), *pp
= NULL
;
769 xfree(pglob
->gl_pathv
), pglob
->gl_pathv
= NULL
;