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. 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
33
#if defined(LIBC_SCCS) && !defined(lint)
34
static char sccsid[] = "@(#)glob.c 8.3 (Berkeley) 10/13/93";
35
/* most changes between the version above and the one below have been ported:
36
static char sscsid[]= "$OpenBSD: glob.c,v 1.8.10.1 2001/04/10 jason Exp $";
38
#endif /* LIBC_SCCS and not lint */
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.
64
* sort alphabetically like csh (case doesn't matter) instead of in ASCII
71
#define MAXPATHLEN 255
79
#define BG_LBRACKET '['
81
#define BG_QUESTION '?'
84
#define BG_RBRACKET ']'
91
#define BG_UNDERSCORE '_'
98
#define M_PROTECT 0x40
104
#include <sys/types.h>
105
#include <sys/stat.h>
109
typedef unsigned char Char;
110
typedef unsigned char U8;
111
typedef size_t STRLEN;
112
typedef struct stat Stat_t;
113
typedef struct dirent Direntry_t;
116
#define CHAR(c) ((Char)((c)&M_ASCII))
117
#define META(c) ((Char)((c)|M_QUOTE))
118
#define M_ALL META('*')
119
#define M_END META(']')
120
#define M_NOT META('!')
121
#define M_ONE META('?')
122
#define M_RNG META('-')
123
#define M_SET META('[')
124
#define ismeta(c) (((c)&M_QUOTE) != 0)
127
static int compare(const void *, const void *);
128
static int ci_compare(const void *, const void *);
129
static int g_Ctoc(const Char *, char *, STRLEN);
130
static int g_lstat(Char *, Stat_t *, glob_t *);
131
static DIR *g_opendir(Char *, glob_t *);
133
g_strchr(const Char *, int);
134
static int glob0(const Char *, glob_t *);
135
static int glob1(Char *, Char *, glob_t *, size_t *);
136
static int glob2(Char *, Char *, Char *, Char *, Char *, Char *,
138
static int glob3(Char *, Char *, Char *, Char *, Char *, Char *,
139
Char *, Char *, glob_t *, size_t *);
140
static int globextend(const Char *, glob_t *, size_t *);
142
globtilde(const Char *, Char *, size_t, glob_t *);
143
static int globexp1(const Char *, glob_t *);
144
static int globexp2(const Char *, const Char *, glob_t *, int *);
145
static int match(Char *, Char *, Char *, int);
147
static void qprintf(const char *, Char *);
148
#endif /* GLOB_DEBUG */
151
dos_glob(const char *pattern, int flags,
152
int (*errfunc)(const char *, int), glob_t *pglob)
156
Char *bufnext, *bufend, patbuf[MAXPATHLEN];
158
patnext = (U8 *) pattern;
160
if (!(flags & GLOB_APPEND)) {
162
pglob->gl_pathv = NULL;
163
if (!(flags & GLOB_DOOFFS))
168
pglob->gl_pathv = NULL;
171
pglob->gl_flags = flags & ~GLOB_MAGCHAR;
172
pglob->gl_errfunc = errfunc;
173
pglob->gl_matchc = 0;
176
bufend = bufnext + MAXPATHLEN - 1;
178
/* Nasty hack to treat patterns like "C:*" correctly. In this
179
* case, the * should match any file in the current directory
180
* on the C: drive. However, the glob code does not treat the
181
* colon specially, so it looks for files beginning "C:" in
182
* the current directory. To fix this, change the pattern to
183
* add an explicit "./" at the start (just after the drive
184
* letter and colon - ie change to "C:./").
186
if (isalpha(pattern[0]) && pattern[1] == ':' &&
187
pattern[2] != BG_SEP && pattern[2] != BG_SEP2 &&
188
bufend - bufnext > 4) {
189
*bufnext++ = pattern[0];
197
if (flags & GLOB_QUOTE) {
198
/* Protect the quoted characters. */
199
while (bufnext < bufend && (c = *patnext++) != BG_EOS)
202
/* To avoid backslashitis on Win32,
203
* we only treat \ as a quoting character
204
* if it precedes one of the
205
* metacharacters []-{}~\
207
if ((c = *patnext++) != '[' && c != ']' &&
208
c != '-' && c != '{' && c != '}' &&
209
c != '~' && c != '\\') {
211
if ((c = *patnext++) == BG_EOS) {
216
*bufnext++ = c | M_PROTECT;
220
while (bufnext < bufend && (c = *patnext++) != BG_EOS)
224
if (flags & GLOB_BRACE)
225
return globexp1(patbuf, pglob);
227
return glob0(patbuf, pglob);
231
* Expand recursively a glob {} pattern. When there is no more expansion
232
* invoke the standard globbing routine to glob the rest of the magic
236
globexp1(const Char *pattern, glob_t *pglob)
238
const Char* ptr = pattern;
241
/* Protect a single {}, for find(1), like csh */
242
if (pattern[0] == BG_LBRACE && pattern[1] == BG_RBRACE && pattern[2] == BG_EOS)
243
return glob0(pattern, pglob);
245
while ((ptr = (const Char *) g_strchr(ptr, BG_LBRACE)) != NULL)
246
if (!globexp2(ptr, pattern, pglob, &rv))
249
return glob0(pattern, pglob);
254
* Recursive brace globbing helper. Tries to expand a single brace.
255
* If it succeeds then it invokes globexp1 with the new pattern.
256
* If it fails then it tries to glob the rest of the pattern and returns.
259
globexp2(const Char *ptr, const Char *pattern,
260
glob_t *pglob, int *rv)
264
const Char *pe, *pm, *pl;
265
Char patbuf[MAXPATHLEN];
267
/* copy part up to the brace */
268
for (lm = patbuf, pm = pattern; pm != ptr; *lm++ = *pm++)
273
/* Find the balanced brace */
274
for (i = 0, pe = ++ptr; *pe; pe++)
275
if (*pe == BG_LBRACKET) {
276
/* Ignore everything between [] */
277
for (pm = pe++; *pe != BG_RBRACKET && *pe != BG_EOS; pe++)
281
* We could not find a matching BG_RBRACKET.
282
* Ignore and just look for BG_RBRACE
286
} else if (*pe == BG_LBRACE)
288
else if (*pe == BG_RBRACE) {
294
/* Non matching braces; just glob the pattern */
295
if (i != 0 || *pe == BG_EOS) {
296
*rv = glob0(patbuf, pglob);
300
for (i = 0, pl = pm = ptr; pm <= pe; pm++) {
303
/* Ignore everything between [] */
304
for (pl = pm++; *pm != BG_RBRACKET && *pm != BG_EOS; pm++)
308
* We could not find a matching BG_RBRACKET.
309
* Ignore and just look for BG_RBRACE
326
if (i && *pm == BG_COMMA)
329
/* Append the current string */
330
for (lm = ls; (pl < pm); *lm++ = *pl++)
334
* Append the rest of the pattern after the
337
for (pl = pe + 1; (*lm++ = *pl++) != BG_EOS; )
340
/* Expand the current pattern */
342
qprintf("globexp2:", patbuf);
343
#endif /* GLOB_DEBUG */
344
*rv = globexp1(patbuf, pglob);
346
/* move after the comma, to the next string */
362
* expand tilde from the passwd file: not supported.
365
globtilde(const Char *pattern, Char *patbuf, size_t patbuf_len, glob_t *pglob)
371
if (*pattern != BG_TILDE || !(pglob->gl_flags & GLOB_TILDE))
374
/* Copy up to the end of the string or / */
375
eb = &patbuf[patbuf_len - 1];
376
for (p = pattern + 1, h = (char *) patbuf;
377
h < (char*)eb && *p && *p != BG_SLASH; *h++ = (char)*p++)
382
if (((char *) patbuf)[0] == BG_EOS) {
384
* handle a plain ~ or ~/ by expanding $HOME
385
* first and then trying the password file
387
if ((h = getenv("R_USER")) == NULL) {
397
/* Copy the home directory */
398
for (b = patbuf; b < eb && *h; *b++ = *h++)
401
/* Append the rest of the pattern */
402
while (b < eb && (*b++ = *p++) != BG_EOS)
411
* The main glob() routine: compiles the pattern (optionally processing
412
* quotes), calls glob1() to do the real pattern matching, and finally
413
* sorts the list (unless unsorted operation is requested). Returns 0
414
* if things went well, nonzero if errors occurred. It is not an error
415
* to find no matches.
418
glob0(const Char *pattern, glob_t *pglob)
420
const Char *qpat, *qpatnext;
421
int c, err, oldflags, oldpathc;
422
Char *bufnext, patbuf[MAXPATHLEN];
425
qpat = globtilde(pattern, patbuf, MAXPATHLEN, pglob);
427
oldflags = pglob->gl_flags;
428
oldpathc = pglob->gl_pathc;
431
/* We don't need to check for buffer overflow any more. */
432
while ((c = *qpatnext++) != BG_EOS) {
438
if (*qpatnext == BG_EOS ||
439
g_strchr((Char *) qpatnext+1, BG_RBRACKET) == NULL) {
440
*bufnext++ = BG_LBRACKET;
450
*bufnext++ = CHAR(c);
451
if (*qpatnext == BG_RANGE &&
452
(c = qpatnext[1]) != BG_RBRACKET) {
454
*bufnext++ = CHAR(c);
457
} while ((c = *qpatnext++) != BG_RBRACKET);
458
pglob->gl_flags |= GLOB_MAGCHAR;
462
pglob->gl_flags |= GLOB_MAGCHAR;
466
pglob->gl_flags |= GLOB_MAGCHAR;
467
/* collapse adjacent stars to one,
468
* to avoid exponential behavior
470
if (bufnext == patbuf || bufnext[-1] != M_ALL)
474
*bufnext++ = CHAR(c);
480
qprintf("glob0:", patbuf);
481
#endif /* GLOB_DEBUG */
483
if ((err = glob1(patbuf, patbuf+MAXPATHLEN-1, pglob, &limit)) != 0) {
484
pglob->gl_flags = oldflags;
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))))
500
printf("calling globextend from glob0\n");
501
#endif /* GLOB_DEBUG */
502
pglob->gl_flags = oldflags;
503
return(globextend(qpat, pglob, &limit));
505
else if (!(pglob->gl_flags & GLOB_NOSORT))
506
qsort(pglob->gl_pathv + pglob->gl_offs + oldpathc,
507
pglob->gl_pathc - oldpathc, sizeof(char *),
508
(pglob->gl_flags & (GLOB_ALPHASORT|GLOB_NOCASE))
509
? ci_compare : compare);
510
pglob->gl_flags = oldflags;
515
ci_compare(const void *p, const void *q)
517
const char *pp = *(const char **)p;
518
const char *qq = *(const char **)q;
521
if (tolower(*pp) != tolower(*qq))
526
ci = tolower(*pp) - tolower(*qq);
528
return compare(p, q);
533
compare(const void *p, const void *q)
535
return(strcmp(*(char **)p, *(char **)q));
539
glob1(Char *pattern, Char *pattern_last, glob_t *pglob, size_t *limitp)
541
Char pathbuf[MAXPATHLEN];
543
/* A null pathname is invalid -- POSIX 1003.1 sect. 2.4. */
544
if (*pattern == BG_EOS) return(0);
545
return(glob2(pathbuf, pathbuf+MAXPATHLEN-1,
546
pathbuf, pathbuf+MAXPATHLEN-1,
547
pattern, pattern_last, pglob, limitp));
551
* The functions glob2 and glob3 are mutually recursive; there is one level
552
* of recursion for each segment in the pattern that contains one or more
556
glob2(Char *pathbuf, Char *pathbuf_last, Char *pathend, Char *pathend_last,
557
Char *pattern, Char *pattern_last, glob_t *pglob, size_t *limitp)
564
* Loop over pattern segments until end of pattern or until
565
* segment with meta character found.
567
for (anymeta = 0;;) {
568
if (*pattern == BG_EOS) { /* End of pattern? */
570
if (g_lstat(pathbuf, &sb, pglob)) return(0);
572
if (((pglob->gl_flags & GLOB_MARK) &&
573
pathend[-1] != BG_SEP
575
&& pathend[-1] != BG_SEP2
577
) && S_ISDIR(sb.st_mode) ) {
578
if (pathend+1 > pathend_last)
585
printf("calling globextend from glob2\n");
586
#endif /* GLOB_DEBUG */
587
return(globextend(pathbuf, pglob, limitp));
590
/* Find end of next segment, copy tentatively to pathend. */
593
while (*p != BG_EOS && *p != BG_SEP
598
if (ismeta(*p)) anymeta = 1;
599
if (q+1 > pathend_last) return (1);
603
if (!anymeta) { /* No expansion, do next segment. */
606
while (*pattern == BG_SEP
608
|| *pattern == BG_SEP2
611
if (pathend+1 > pathend_last) return (1);
612
*pathend++ = *pattern++;
615
/* Need expansion, recurse. */
616
return(glob3(pathbuf, pathbuf_last, pathend,
617
pathend_last, pattern, pattern_last,
618
p, pattern_last, pglob, limitp));
624
glob3(Char *pathbuf, Char *pathbuf_last, Char *pathend, Char *pathend_last,
625
Char *pattern, Char *pattern_last,
626
Char *restpattern, Char *restpattern_last, glob_t *pglob, size_t *limitp)
628
register Direntry_t *dp;
632
char buf[MAXPATHLEN];
634
if (pathend > pathend_last)
642
if (q - pathbuf > 5) {
645
tolower(q[1]) == 'd' && tolower(q[2]) == 'i' &&
646
tolower(q[3]) == 'r' && q[4] == '/')
656
if ((dirp = g_opendir(pathbuf, pglob)) == NULL) {
657
/* TODO: don't call for ENOENT or ENOTDIR? */
658
if (pglob->gl_errfunc) {
659
if (g_Ctoc(pathbuf, buf, sizeof(buf)))
661
if (pglob->gl_errfunc(buf, errno) ||
662
(pglob->gl_flags & GLOB_ERR))
669
nocase = ((pglob->gl_flags & GLOB_NOCASE) != 0);
671
/* Search directory for matching names. */
672
while ((dp = readdir(dirp))) {
676
/* Initial BG_DOT must be matched literally. */
677
if (dp->d_name[0] == BG_DOT && *pattern != BG_DOT)
680
sc = (U8 *) dp->d_name;
681
while (dc < pathend_last && (*dc++ = *sc++) != BG_EOS)
683
if (dc >= pathend_last) {
689
if (!match(pathend, pattern, restpattern, nocase)) {
693
err = glob2(pathbuf, pathbuf_last, --dc, pathend_last,
694
restpattern, restpattern_last, pglob, limitp);
704
#include <R_ext/RS.h> /* for Calloc, Realloc, Free */
707
* Extend the gl_pathv member of a glob_t structure to accomodate a new item,
708
* add the new item, and update gl_pathc.
710
* This assumes the BSD realloc, which only copies the block when its size
711
* crosses a power-of-two boundary; for v7 realloc, this would cause quadratic
714
* Return 0 if new item added, error code if memory couldn't be allocated.
716
* Invariant of the glob_t structure:
717
* Either gl_pathc is zero and gl_pathv is NULL; or gl_pathc > 0 and
718
* gl_pathv points to (gl_offs + gl_pathc + 1) items.
721
globextend(const Char *path, glob_t *pglob, size_t *limitp)
723
register char **pathv;
731
for (p = path; *p; p++)
732
(void)printf("%c", CHAR(*p));
734
#endif /* GLOB_DEBUG */
736
newsize = sizeof(*pathv) * (2 + pglob->gl_pathc + pglob->gl_offs);
738
pathv = Realloc(pglob->gl_pathv, newsize, char*);
740
pathv = Calloc(newsize,char*);
742
if (pglob->gl_pathv) {
743
Free(pglob->gl_pathv);
744
pglob->gl_pathv = NULL;
746
return(GLOB_NOSPACE);
749
if (pglob->gl_pathv == NULL && pglob->gl_offs > 0) {
750
/* first time around -- clear initial gl_offs items */
751
pathv += pglob->gl_offs;
752
for (i = pglob->gl_offs; --i >= 0; )
755
pglob->gl_pathv = pathv;
757
for (p = path; *p++;)
759
len = (STRLEN)(p - path);
761
copy = Calloc(p-path, char);
763
if (g_Ctoc(path, copy, len)) {
765
return(GLOB_NOSPACE);
767
pathv[pglob->gl_offs + pglob->gl_pathc++] = copy;
769
pathv[pglob->gl_offs + pglob->gl_pathc] = NULL;
771
if ((pglob->gl_flags & GLOB_LIMIT) &&
772
newsize + *limitp >= ARG_MAX) {
774
return(GLOB_NOSPACE);
777
return(copy == NULL ? GLOB_NOSPACE : 0);
782
* pattern matching function for filenames. Each occurrence of the *
783
* pattern causes a recursion level.
786
match(register Char *name, register Char *pat, register Char *patend, int nocase)
788
int ok, negate_range;
791
while (pat < patend) {
793
switch (c & M_MASK) {
798
if (match(name, pat, patend, nocase))
800
while (*name++ != BG_EOS)
804
if (*name++ == BG_EOS)
809
if ((k = *name++) == BG_EOS)
811
if ((negate_range = ((*pat & M_MASK) == M_NOT)) != BG_EOS)
813
while (((c = *pat++) & M_MASK) != M_END)
814
if ((*pat & M_MASK) == M_RNG) {
816
if (tolower(c) <= tolower(k) && tolower(k) <= tolower(pat[1]))
819
if (c <= k && k <= pat[1])
823
} else if (nocase ? (tolower(c) == tolower(k)) : (c == k))
825
if (ok == negate_range)
830
if (nocase ? (tolower(k) != tolower(c)) : (k != c))
835
return(*name == BG_EOS);
838
/* Free allocated data belonging to a glob_t structure. */
840
dos_globfree(glob_t *pglob)
845
if (pglob->gl_pathv != NULL) {
846
pp = pglob->gl_pathv + pglob->gl_offs;
847
for (i = pglob->gl_pathc; i--; ++pp)
850
Free(pglob->gl_pathv);
851
pglob->gl_pathv = NULL;
856
g_opendir(register Char *str, glob_t *pglob)
858
char buf[MAXPATHLEN];
863
if (g_Ctoc(str, buf, sizeof(buf)))
867
return(opendir(buf));
871
g_lstat(register Char *fn, Stat_t *sb, glob_t *pglob)
873
char buf[MAXPATHLEN];
875
if (g_Ctoc(fn, buf, sizeof(buf)))
877
return(stat(buf, sb));
881
g_strchr(const Char *str, int ch)
891
g_Ctoc(register const Char *str, char *buf, STRLEN len)
894
if ((*buf++ = (char)*str++) == BG_EOS)
902
qprintf(const char *str, register Char *s)
906
(void)printf("%s:\n", str);
908
(void)printf("%c", CHAR(*p));
911
(void)printf("%c", *p & M_PROTECT ? '"' : ' ');
914
(void)printf("%c", ismeta(*p) ? '_' : ' ');
917
#endif /* GLOB_DEBUG */