glob.c revision 80525
11573Srgrimes/* 21573Srgrimes * Copyright (c) 1989, 1993 31573Srgrimes * The Regents of the University of California. All rights reserved. 41573Srgrimes * 51573Srgrimes * This code is derived from software contributed to Berkeley by 61573Srgrimes * Guido van Rossum. 71573Srgrimes * 81573Srgrimes * Redistribution and use in source and binary forms, with or without 91573Srgrimes * modification, are permitted provided that the following conditions 101573Srgrimes * are met: 111573Srgrimes * 1. Redistributions of source code must retain the above copyright 121573Srgrimes * notice, this list of conditions and the following disclaimer. 131573Srgrimes * 2. Redistributions in binary form must reproduce the above copyright 141573Srgrimes * notice, this list of conditions and the following disclaimer in the 151573Srgrimes * documentation and/or other materials provided with the distribution. 161573Srgrimes * 3. All advertising materials mentioning features or use of this software 171573Srgrimes * must display the following acknowledgement: 181573Srgrimes * This product includes software developed by the University of 191573Srgrimes * California, Berkeley and its contributors. 201573Srgrimes * 4. Neither the name of the University nor the names of its contributors 211573Srgrimes * may be used to endorse or promote products derived from this software 221573Srgrimes * without specific prior written permission. 231573Srgrimes * 241573Srgrimes * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 251573Srgrimes * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 261573Srgrimes * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 271573Srgrimes * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 281573Srgrimes * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 291573Srgrimes * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 301573Srgrimes * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 311573Srgrimes * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 321573Srgrimes * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 331573Srgrimes * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 341573Srgrimes * SUCH DAMAGE. 3574307Sjlemon * 3674307Sjlemon * $FreeBSD: head/lib/libc/gen/glob.c 80525 2001-07-29 00:52:37Z mikeh $ 371573Srgrimes */ 381573Srgrimes 391573Srgrimes#if defined(LIBC_SCCS) && !defined(lint) 401573Srgrimesstatic char sccsid[] = "@(#)glob.c 8.3 (Berkeley) 10/13/93"; 411573Srgrimes#endif /* LIBC_SCCS and not lint */ 421573Srgrimes 431573Srgrimes/* 441573Srgrimes * glob(3) -- a superset of the one defined in POSIX 1003.2. 451573Srgrimes * 461573Srgrimes * The [!...] convention to negate a range is supported (SysV, Posix, ksh). 471573Srgrimes * 481573Srgrimes * Optional extra services, controlled by flags not defined by POSIX: 491573Srgrimes * 501573Srgrimes * GLOB_QUOTE: 511573Srgrimes * Escaping convention: \ inhibits any special meaning the following 521573Srgrimes * character might have (except \ at end of string is retained). 531573Srgrimes * GLOB_MAGCHAR: 541573Srgrimes * Set in gl_flags if pattern contained a globbing character. 551573Srgrimes * GLOB_NOMAGIC: 561573Srgrimes * Same as GLOB_NOCHECK, but it will only append pattern if it did 571573Srgrimes * not contain any magic characters. [Used in csh style globbing] 581573Srgrimes * GLOB_ALTDIRFUNC: 591573Srgrimes * Use alternately specified directory access functions. 601573Srgrimes * GLOB_TILDE: 611573Srgrimes * expand ~user/foo to the /home/dir/of/user/foo 621573Srgrimes * GLOB_BRACE: 638870Srgrimes * expand {1,2}{a,b} to 1a 1b 2a 2b 641573Srgrimes * gl_matchc: 651573Srgrimes * Number of matches in the current invocation of glob. 661573Srgrimes */ 671573Srgrimes 681573Srgrimes#include <sys/param.h> 691573Srgrimes#include <sys/stat.h> 701573Srgrimes 711573Srgrimes#include <ctype.h> 721573Srgrimes#include <dirent.h> 731573Srgrimes#include <errno.h> 741573Srgrimes#include <glob.h> 751573Srgrimes#include <pwd.h> 761573Srgrimes#include <stdio.h> 771573Srgrimes#include <stdlib.h> 781573Srgrimes#include <string.h> 791573Srgrimes#include <unistd.h> 801573Srgrimes 8119276Sache#include "collate.h" 8219276Sache 831573Srgrimes#define DOLLAR '$' 841573Srgrimes#define DOT '.' 851573Srgrimes#define EOS '\0' 861573Srgrimes#define LBRACKET '[' 871573Srgrimes#define NOT '!' 881573Srgrimes#define QUESTION '?' 891573Srgrimes#define QUOTE '\\' 901573Srgrimes#define RANGE '-' 911573Srgrimes#define RBRACKET ']' 921573Srgrimes#define SEP '/' 931573Srgrimes#define STAR '*' 941573Srgrimes#define TILDE '~' 951573Srgrimes#define UNDERSCORE '_' 961573Srgrimes#define LBRACE '{' 971573Srgrimes#define RBRACE '}' 981573Srgrimes#define SLASH '/' 991573Srgrimes#define COMMA ',' 1001573Srgrimes 1011573Srgrimes#ifndef DEBUG 1021573Srgrimes 1031573Srgrimes#define M_QUOTE 0x8000 1041573Srgrimes#define M_PROTECT 0x4000 1051573Srgrimes#define M_MASK 0xffff 1061573Srgrimes#define M_ASCII 0x00ff 1071573Srgrimes 1081573Srgrimestypedef u_short Char; 1091573Srgrimes 1101573Srgrimes#else 1111573Srgrimes 1121573Srgrimes#define M_QUOTE 0x80 1131573Srgrimes#define M_PROTECT 0x40 1141573Srgrimes#define M_MASK 0xff 1151573Srgrimes#define M_ASCII 0x7f 1161573Srgrimes 1171573Srgrimestypedef char Char; 1181573Srgrimes 1191573Srgrimes#endif 1201573Srgrimes 1211573Srgrimes 1221573Srgrimes#define CHAR(c) ((Char)((c)&M_ASCII)) 1231573Srgrimes#define META(c) ((Char)((c)|M_QUOTE)) 1241573Srgrimes#define M_ALL META('*') 1251573Srgrimes#define M_END META(']') 1261573Srgrimes#define M_NOT META('!') 1271573Srgrimes#define M_ONE META('?') 1281573Srgrimes#define M_RNG META('-') 1291573Srgrimes#define M_SET META('[') 1301573Srgrimes#define ismeta(c) (((c)&M_QUOTE) != 0) 1311573Srgrimes 1321573Srgrimes 1331573Srgrimesstatic int compare __P((const void *, const void *)); 13474921Speterstatic int g_Ctoc __P((const Char *, char *, u_int)); 1351573Srgrimesstatic int g_lstat __P((Char *, struct stat *, glob_t *)); 1361573Srgrimesstatic DIR *g_opendir __P((Char *, glob_t *)); 1371573Srgrimesstatic Char *g_strchr __P((Char *, int)); 1381573Srgrimes#ifdef notdef 1391573Srgrimesstatic Char *g_strcat __P((Char *, const Char *)); 1401573Srgrimes#endif 1411573Srgrimesstatic int g_stat __P((Char *, struct stat *, glob_t *)); 14274469Sjlemonstatic int glob0 __P((const Char *, glob_t *, int *)); 14374469Sjlemonstatic int glob1 __P((Char *, glob_t *, int *)); 14474963Speterstatic int glob2 __P((Char *, Char *, Char *, Char *, glob_t *, int *)); 14574963Speterstatic int glob3 __P((Char *, Char *, Char *, Char *, Char *, glob_t *, int *)); 14674469Sjlemonstatic int globextend __P((const Char *, glob_t *, int *)); 14774963Speterstatic const Char * 14874963Speter globtilde __P((const Char *, Char *, size_t, glob_t *)); 14974469Sjlemonstatic int globexp1 __P((const Char *, glob_t *, int *)); 15074469Sjlemonstatic int globexp2 __P((const Char *, const Char *, glob_t *, int *, int *)); 1511573Srgrimesstatic int match __P((Char *, Char *, Char *)); 1521573Srgrimes#ifdef DEBUG 1531573Srgrimesstatic void qprintf __P((const char *, Char *)); 1541573Srgrimes#endif 1551573Srgrimes 1561573Srgrimesint 1571573Srgrimesglob(pattern, flags, errfunc, pglob) 1581573Srgrimes const char *pattern; 1591573Srgrimes int flags, (*errfunc) __P((const char *, int)); 1601573Srgrimes glob_t *pglob; 1611573Srgrimes{ 1621573Srgrimes const u_char *patnext; 16374469Sjlemon int c, limit; 16474963Speter Char *bufnext, *bufend, patbuf[MAXPATHLEN]; 1651573Srgrimes 1661573Srgrimes patnext = (u_char *) pattern; 1671573Srgrimes if (!(flags & GLOB_APPEND)) { 1681573Srgrimes pglob->gl_pathc = 0; 1691573Srgrimes pglob->gl_pathv = NULL; 1701573Srgrimes if (!(flags & GLOB_DOOFFS)) 1711573Srgrimes pglob->gl_offs = 0; 1721573Srgrimes } 17380525Smikeh if (flags & GLOB_LIMIT) { 17474469Sjlemon limit = pglob->gl_matchc; 17580525Smikeh if (limit == 0) 17680525Smikeh limit = ARG_MAX; 17780525Smikeh } else 17874469Sjlemon limit = 0; 1791573Srgrimes pglob->gl_flags = flags & ~GLOB_MAGCHAR; 1801573Srgrimes pglob->gl_errfunc = errfunc; 1811573Srgrimes pglob->gl_matchc = 0; 1821573Srgrimes 1831573Srgrimes bufnext = patbuf; 18474963Speter bufend = bufnext + MAXPATHLEN - 1; 1851573Srgrimes if (flags & GLOB_QUOTE) { 1861573Srgrimes /* Protect the quoted characters. */ 1878870Srgrimes while (bufnext < bufend && (c = *patnext++) != EOS) 1881573Srgrimes if (c == QUOTE) { 1891573Srgrimes if ((c = *patnext++) == EOS) { 1901573Srgrimes c = QUOTE; 1911573Srgrimes --patnext; 1921573Srgrimes } 1931573Srgrimes *bufnext++ = c | M_PROTECT; 1941573Srgrimes } 1951573Srgrimes else 1961573Srgrimes *bufnext++ = c; 1971573Srgrimes } 1988870Srgrimes else 1998870Srgrimes while (bufnext < bufend && (c = *patnext++) != EOS) 2001573Srgrimes *bufnext++ = c; 2011573Srgrimes *bufnext = EOS; 2021573Srgrimes 2031573Srgrimes if (flags & GLOB_BRACE) 20474469Sjlemon return globexp1(patbuf, pglob, &limit); 2051573Srgrimes else 20674469Sjlemon return glob0(patbuf, pglob, &limit); 2071573Srgrimes} 2081573Srgrimes 2091573Srgrimes/* 2101573Srgrimes * Expand recursively a glob {} pattern. When there is no more expansion 2111573Srgrimes * invoke the standard globbing routine to glob the rest of the magic 2121573Srgrimes * characters 2131573Srgrimes */ 21474963Speterstatic int 21574963Speterglobexp1(pattern, pglob, limit) 2161573Srgrimes const Char *pattern; 2171573Srgrimes glob_t *pglob; 21874469Sjlemon int *limit; 2191573Srgrimes{ 2201573Srgrimes const Char* ptr = pattern; 2211573Srgrimes int rv; 2221573Srgrimes 2231573Srgrimes /* Protect a single {}, for find(1), like csh */ 2241573Srgrimes if (pattern[0] == LBRACE && pattern[1] == RBRACE && pattern[2] == EOS) 22574469Sjlemon return glob0(pattern, pglob, limit); 2261573Srgrimes 2271573Srgrimes while ((ptr = (const Char *) g_strchr((Char *) ptr, LBRACE)) != NULL) 22874469Sjlemon if (!globexp2(ptr, pattern, pglob, &rv, limit)) 2291573Srgrimes return rv; 2301573Srgrimes 23174469Sjlemon return glob0(pattern, pglob, limit); 2321573Srgrimes} 2331573Srgrimes 2341573Srgrimes 2351573Srgrimes/* 2361573Srgrimes * Recursive brace globbing helper. Tries to expand a single brace. 2371573Srgrimes * If it succeeds then it invokes globexp1 with the new pattern. 2381573Srgrimes * If it fails then it tries to glob the rest of the pattern and returns. 2391573Srgrimes */ 24074963Speterstatic int 24174963Speterglobexp2(ptr, pattern, pglob, rv, limit) 2421573Srgrimes const Char *ptr, *pattern; 2431573Srgrimes glob_t *pglob; 24474469Sjlemon int *rv, *limit; 2451573Srgrimes{ 2461573Srgrimes int i; 2471573Srgrimes Char *lm, *ls; 2481573Srgrimes const Char *pe, *pm, *pl; 24974963Speter Char patbuf[MAXPATHLEN]; 2501573Srgrimes 2511573Srgrimes /* copy part up to the brace */ 2521573Srgrimes for (lm = patbuf, pm = pattern; pm != ptr; *lm++ = *pm++) 2531573Srgrimes continue; 25474963Speter *lm = EOS; 2551573Srgrimes ls = lm; 2561573Srgrimes 2571573Srgrimes /* Find the balanced brace */ 2581573Srgrimes for (i = 0, pe = ++ptr; *pe; pe++) 2591573Srgrimes if (*pe == LBRACKET) { 2601573Srgrimes /* Ignore everything between [] */ 2611573Srgrimes for (pm = pe++; *pe != RBRACKET && *pe != EOS; pe++) 2621573Srgrimes continue; 2631573Srgrimes if (*pe == EOS) { 2648870Srgrimes /* 2651573Srgrimes * We could not find a matching RBRACKET. 2661573Srgrimes * Ignore and just look for RBRACE 2671573Srgrimes */ 2681573Srgrimes pe = pm; 2691573Srgrimes } 2701573Srgrimes } 2711573Srgrimes else if (*pe == LBRACE) 2721573Srgrimes i++; 2731573Srgrimes else if (*pe == RBRACE) { 2741573Srgrimes if (i == 0) 2751573Srgrimes break; 2761573Srgrimes i--; 2771573Srgrimes } 2781573Srgrimes 2791573Srgrimes /* Non matching braces; just glob the pattern */ 2801573Srgrimes if (i != 0 || *pe == EOS) { 28174469Sjlemon *rv = glob0(patbuf, pglob, limit); 2821573Srgrimes return 0; 2831573Srgrimes } 2841573Srgrimes 2851573Srgrimes for (i = 0, pl = pm = ptr; pm <= pe; pm++) 2861573Srgrimes switch (*pm) { 2871573Srgrimes case LBRACKET: 2881573Srgrimes /* Ignore everything between [] */ 2891573Srgrimes for (pl = pm++; *pm != RBRACKET && *pm != EOS; pm++) 2901573Srgrimes continue; 2911573Srgrimes if (*pm == EOS) { 2928870Srgrimes /* 2931573Srgrimes * We could not find a matching RBRACKET. 2941573Srgrimes * Ignore and just look for RBRACE 2951573Srgrimes */ 2961573Srgrimes pm = pl; 2971573Srgrimes } 2981573Srgrimes break; 2991573Srgrimes 3001573Srgrimes case LBRACE: 3011573Srgrimes i++; 3021573Srgrimes break; 3031573Srgrimes 3041573Srgrimes case RBRACE: 3051573Srgrimes if (i) { 3061573Srgrimes i--; 3071573Srgrimes break; 3081573Srgrimes } 3091573Srgrimes /* FALLTHROUGH */ 3101573Srgrimes case COMMA: 3111573Srgrimes if (i && *pm == COMMA) 3121573Srgrimes break; 3131573Srgrimes else { 3141573Srgrimes /* Append the current string */ 3151573Srgrimes for (lm = ls; (pl < pm); *lm++ = *pl++) 3161573Srgrimes continue; 3178870Srgrimes /* 3181573Srgrimes * Append the rest of the pattern after the 3191573Srgrimes * closing brace 3201573Srgrimes */ 3211573Srgrimes for (pl = pe + 1; (*lm++ = *pl++) != EOS;) 3221573Srgrimes continue; 3231573Srgrimes 3241573Srgrimes /* Expand the current pattern */ 3251573Srgrimes#ifdef DEBUG 3261573Srgrimes qprintf("globexp2:", patbuf); 3271573Srgrimes#endif 32874469Sjlemon *rv = globexp1(patbuf, pglob, limit); 3291573Srgrimes 3301573Srgrimes /* move after the comma, to the next string */ 3311573Srgrimes pl = pm + 1; 3321573Srgrimes } 3331573Srgrimes break; 3341573Srgrimes 3351573Srgrimes default: 3361573Srgrimes break; 3371573Srgrimes } 3381573Srgrimes *rv = 0; 3391573Srgrimes return 0; 3401573Srgrimes} 3411573Srgrimes 3421573Srgrimes 3431573Srgrimes 3441573Srgrimes/* 3451573Srgrimes * expand tilde from the passwd file. 3461573Srgrimes */ 3471573Srgrimesstatic const Char * 34824158Simpglobtilde(pattern, patbuf, patbuf_len, pglob) 3491573Srgrimes const Char *pattern; 3501573Srgrimes Char *patbuf; 35124158Simp size_t patbuf_len; 3521573Srgrimes glob_t *pglob; 3531573Srgrimes{ 3541573Srgrimes struct passwd *pwd; 3551573Srgrimes char *h; 3561573Srgrimes const Char *p; 35724158Simp Char *b, *eb; 3581573Srgrimes 3591573Srgrimes if (*pattern != TILDE || !(pglob->gl_flags & GLOB_TILDE)) 3601573Srgrimes return pattern; 3611573Srgrimes 36224158Simp /* 36324158Simp * Copy up to the end of the string or / 36424158Simp */ 36524158Simp eb = &patbuf[patbuf_len - 1]; 36624158Simp for (p = pattern + 1, h = (char *) patbuf; 36724158Simp h < (char *)eb && *p && *p != SLASH; *h++ = *p++) 3681573Srgrimes continue; 3691573Srgrimes 3701573Srgrimes *h = EOS; 3711573Srgrimes 3721573Srgrimes if (((char *) patbuf)[0] == EOS) { 3738870Srgrimes /* 37428820Simp * handle a plain ~ or ~/ by expanding $HOME first (iff 37528820Simp * we're not running setuid or setgid) and then trying 37628820Simp * the password file 3771573Srgrimes */ 37833664Sjb if ( 37933664Sjb#ifndef __NETBSD_SYSCALLS 38033664Sjb issetugid() != 0 || 38133664Sjb#endif 38233664Sjb (h = getenv("HOME")) == NULL) { 38328836Sache if (((h = getlogin()) != NULL && 38428836Sache (pwd = getpwnam(h)) != NULL) || 38528836Sache (pwd = getpwuid(getuid())) != NULL) 38628836Sache h = pwd->pw_dir; 38728836Sache else 3881573Srgrimes return pattern; 3891573Srgrimes } 3901573Srgrimes } 3911573Srgrimes else { 3921573Srgrimes /* 3931573Srgrimes * Expand a ~user 3941573Srgrimes */ 3951573Srgrimes if ((pwd = getpwnam((char*) patbuf)) == NULL) 3961573Srgrimes return pattern; 3971573Srgrimes else 3981573Srgrimes h = pwd->pw_dir; 3991573Srgrimes } 4001573Srgrimes 4011573Srgrimes /* Copy the home directory */ 40224158Simp for (b = patbuf; b < eb && *h; *b++ = *h++) 4031573Srgrimes continue; 4048870Srgrimes 4051573Srgrimes /* Append the rest of the pattern */ 40624158Simp while (b < eb && (*b++ = *p++) != EOS) 4071573Srgrimes continue; 40824158Simp *b = EOS; 4091573Srgrimes 4101573Srgrimes return patbuf; 4111573Srgrimes} 4121573Srgrimes 4138870Srgrimes 4141573Srgrimes/* 4151573Srgrimes * The main glob() routine: compiles the pattern (optionally processing 4161573Srgrimes * quotes), calls glob1() to do the real pattern matching, and finally 4171573Srgrimes * sorts the list (unless unsorted operation is requested). Returns 0 4181573Srgrimes * if things went well, nonzero if errors occurred. It is not an error 4191573Srgrimes * to find no matches. 4201573Srgrimes */ 4211573Srgrimesstatic int 42274469Sjlemonglob0(pattern, pglob, limit) 4231573Srgrimes const Char *pattern; 4241573Srgrimes glob_t *pglob; 42574469Sjlemon int *limit; 4261573Srgrimes{ 4271573Srgrimes const Char *qpatnext; 4281573Srgrimes int c, err, oldpathc; 42974963Speter Char *bufnext, patbuf[MAXPATHLEN]; 4301573Srgrimes 43174963Speter qpatnext = globtilde(pattern, patbuf, MAXPATHLEN, pglob); 4321573Srgrimes oldpathc = pglob->gl_pathc; 4331573Srgrimes bufnext = patbuf; 4341573Srgrimes 4351573Srgrimes /* We don't need to check for buffer overflow any more. */ 4361573Srgrimes while ((c = *qpatnext++) != EOS) { 4371573Srgrimes switch (c) { 4381573Srgrimes case LBRACKET: 4391573Srgrimes c = *qpatnext; 4401573Srgrimes if (c == NOT) 4411573Srgrimes ++qpatnext; 4421573Srgrimes if (*qpatnext == EOS || 4431573Srgrimes g_strchr((Char *) qpatnext+1, RBRACKET) == NULL) { 4441573Srgrimes *bufnext++ = LBRACKET; 4451573Srgrimes if (c == NOT) 4461573Srgrimes --qpatnext; 4471573Srgrimes break; 4481573Srgrimes } 4491573Srgrimes *bufnext++ = M_SET; 4501573Srgrimes if (c == NOT) 4511573Srgrimes *bufnext++ = M_NOT; 4521573Srgrimes c = *qpatnext++; 4531573Srgrimes do { 4541573Srgrimes *bufnext++ = CHAR(c); 4551573Srgrimes if (*qpatnext == RANGE && 4561573Srgrimes (c = qpatnext[1]) != RBRACKET) { 4571573Srgrimes *bufnext++ = M_RNG; 4581573Srgrimes *bufnext++ = CHAR(c); 4591573Srgrimes qpatnext += 2; 4601573Srgrimes } 4611573Srgrimes } while ((c = *qpatnext++) != RBRACKET); 4621573Srgrimes pglob->gl_flags |= GLOB_MAGCHAR; 4631573Srgrimes *bufnext++ = M_END; 4641573Srgrimes break; 4651573Srgrimes case QUESTION: 4661573Srgrimes pglob->gl_flags |= GLOB_MAGCHAR; 4671573Srgrimes *bufnext++ = M_ONE; 4681573Srgrimes break; 4691573Srgrimes case STAR: 4701573Srgrimes pglob->gl_flags |= GLOB_MAGCHAR; 4718870Srgrimes /* collapse adjacent stars to one, 4721573Srgrimes * to avoid exponential behavior 4731573Srgrimes */ 4741573Srgrimes if (bufnext == patbuf || bufnext[-1] != M_ALL) 4751573Srgrimes *bufnext++ = M_ALL; 4761573Srgrimes break; 4771573Srgrimes default: 4781573Srgrimes *bufnext++ = CHAR(c); 4791573Srgrimes break; 4801573Srgrimes } 4811573Srgrimes } 4821573Srgrimes *bufnext = EOS; 4831573Srgrimes#ifdef DEBUG 4841573Srgrimes qprintf("glob0:", patbuf); 4851573Srgrimes#endif 4861573Srgrimes 48774469Sjlemon if ((err = glob1(patbuf, pglob, limit)) != 0) 4881573Srgrimes return(err); 4891573Srgrimes 4901573Srgrimes /* 4918870Srgrimes * If there was no match we are going to append the pattern 4921573Srgrimes * if GLOB_NOCHECK was specified or if GLOB_NOMAGIC was specified 4931573Srgrimes * and the pattern did not contain any magic characters 4941573Srgrimes * GLOB_NOMAGIC is there just for compatibility with csh. 4951573Srgrimes */ 4968870Srgrimes if (pglob->gl_pathc == oldpathc && 4978870Srgrimes ((pglob->gl_flags & GLOB_NOCHECK) || 4981573Srgrimes ((pglob->gl_flags & GLOB_NOMAGIC) && 4991573Srgrimes !(pglob->gl_flags & GLOB_MAGCHAR)))) 50074469Sjlemon return(globextend(pattern, pglob, limit)); 5018870Srgrimes else if (!(pglob->gl_flags & GLOB_NOSORT)) 5021573Srgrimes qsort(pglob->gl_pathv + pglob->gl_offs + oldpathc, 5031573Srgrimes pglob->gl_pathc - oldpathc, sizeof(char *), compare); 5041573Srgrimes return(0); 5051573Srgrimes} 5061573Srgrimes 5071573Srgrimesstatic int 5081573Srgrimescompare(p, q) 5091573Srgrimes const void *p, *q; 5101573Srgrimes{ 5111573Srgrimes return(strcmp(*(char **)p, *(char **)q)); 5121573Srgrimes} 5131573Srgrimes 5141573Srgrimesstatic int 51574469Sjlemonglob1(pattern, pglob, limit) 5161573Srgrimes Char *pattern; 5171573Srgrimes glob_t *pglob; 51874469Sjlemon int *limit; 5191573Srgrimes{ 52074963Speter Char pathbuf[MAXPATHLEN]; 5211573Srgrimes 5221573Srgrimes /* A null pathname is invalid -- POSIX 1003.1 sect. 2.4. */ 5231573Srgrimes if (*pattern == EOS) 5241573Srgrimes return(0); 52574963Speter return(glob2(pathbuf, pathbuf, pathbuf + MAXPATHLEN - 1, 52674963Speter pattern, pglob, limit)); 5271573Srgrimes} 5281573Srgrimes 5291573Srgrimes/* 5301573Srgrimes * The functions glob2 and glob3 are mutually recursive; there is one level 5311573Srgrimes * of recursion for each segment in the pattern that contains one or more 5321573Srgrimes * meta characters. 5331573Srgrimes */ 5341573Srgrimesstatic int 53574963Speterglob2(pathbuf, pathend, pathend_last, pattern, pglob, limit) 53674963Speter Char *pathbuf, *pathend, *pathend_last, *pattern; 5371573Srgrimes glob_t *pglob; 53874469Sjlemon int *limit; 5391573Srgrimes{ 5401573Srgrimes struct stat sb; 5411573Srgrimes Char *p, *q; 5421573Srgrimes int anymeta; 5431573Srgrimes 5441573Srgrimes /* 5451573Srgrimes * Loop over pattern segments until end of pattern or until 5461573Srgrimes * segment with meta character found. 5471573Srgrimes */ 5481573Srgrimes for (anymeta = 0;;) { 5491573Srgrimes if (*pattern == EOS) { /* End of pattern? */ 5501573Srgrimes *pathend = EOS; 5511573Srgrimes if (g_lstat(pathbuf, &sb, pglob)) 5521573Srgrimes return(0); 5538870Srgrimes 5541573Srgrimes if (((pglob->gl_flags & GLOB_MARK) && 5551573Srgrimes pathend[-1] != SEP) && (S_ISDIR(sb.st_mode) 5561573Srgrimes || (S_ISLNK(sb.st_mode) && 5571573Srgrimes (g_stat(pathbuf, &sb, pglob) == 0) && 5581573Srgrimes S_ISDIR(sb.st_mode)))) { 55974963Speter if (pathend + 1 > pathend_last) 56074963Speter return (1); 5611573Srgrimes *pathend++ = SEP; 5621573Srgrimes *pathend = EOS; 5631573Srgrimes } 5641573Srgrimes ++pglob->gl_matchc; 56574469Sjlemon return(globextend(pathbuf, pglob, limit)); 5661573Srgrimes } 5671573Srgrimes 5681573Srgrimes /* Find end of next segment, copy tentatively to pathend. */ 5691573Srgrimes q = pathend; 5701573Srgrimes p = pattern; 5711573Srgrimes while (*p != EOS && *p != SEP) { 5721573Srgrimes if (ismeta(*p)) 5731573Srgrimes anymeta = 1; 57474963Speter if (q + 1 > pathend_last) 57574963Speter return (1); 5761573Srgrimes *q++ = *p++; 5771573Srgrimes } 5781573Srgrimes 5791573Srgrimes if (!anymeta) { /* No expansion, do next segment. */ 5801573Srgrimes pathend = q; 5811573Srgrimes pattern = p; 58274963Speter while (*pattern == SEP) { 58374963Speter if (pathend + 1 > pathend_last) 58474963Speter return (1); 5851573Srgrimes *pathend++ = *pattern++; 58674963Speter } 5871573Srgrimes } else /* Need expansion, recurse. */ 58874963Speter return(glob3(pathbuf, pathend, pathend_last, pattern, p, 58974963Speter pglob, limit)); 5901573Srgrimes } 5911573Srgrimes /* NOTREACHED */ 5921573Srgrimes} 5931573Srgrimes 5941573Srgrimesstatic int 59574963Speterglob3(pathbuf, pathend, pathend_last, pattern, restpattern, pglob, limit) 59674963Speter Char *pathbuf, *pathend, *pathend_last, *pattern, *restpattern; 5971573Srgrimes glob_t *pglob; 59874469Sjlemon int *limit; 5991573Srgrimes{ 6001573Srgrimes register struct dirent *dp; 6011573Srgrimes DIR *dirp; 6021573Srgrimes int err; 6031573Srgrimes char buf[MAXPATHLEN]; 6041573Srgrimes 6051573Srgrimes /* 6061573Srgrimes * The readdirfunc declaration can't be prototyped, because it is 6071573Srgrimes * assigned, below, to two functions which are prototyped in glob.h 6081573Srgrimes * and dirent.h as taking pointers to differently typed opaque 6091573Srgrimes * structures. 6101573Srgrimes */ 6111573Srgrimes struct dirent *(*readdirfunc)(); 6121573Srgrimes 61374963Speter if (pathend > pathend_last) 61474963Speter return (1); 6151573Srgrimes *pathend = EOS; 6161573Srgrimes errno = 0; 6178870Srgrimes 6181573Srgrimes if ((dirp = g_opendir(pathbuf, pglob)) == NULL) { 6191573Srgrimes /* TODO: don't call for ENOENT or ENOTDIR? */ 6201573Srgrimes if (pglob->gl_errfunc) { 62174921Speter if (g_Ctoc(pathbuf, buf, sizeof(buf))) 62274918Speter return (GLOB_ABEND); 6231573Srgrimes if (pglob->gl_errfunc(buf, errno) || 6241573Srgrimes pglob->gl_flags & GLOB_ERR) 6251573Srgrimes return (GLOB_ABEND); 6261573Srgrimes } 6271573Srgrimes return(0); 6281573Srgrimes } 6291573Srgrimes 6301573Srgrimes err = 0; 6311573Srgrimes 6321573Srgrimes /* Search directory for matching names. */ 6331573Srgrimes if (pglob->gl_flags & GLOB_ALTDIRFUNC) 6341573Srgrimes readdirfunc = pglob->gl_readdir; 6351573Srgrimes else 6361573Srgrimes readdirfunc = readdir; 6371573Srgrimes while ((dp = (*readdirfunc)(dirp))) { 6381573Srgrimes register u_char *sc; 6391573Srgrimes register Char *dc; 6401573Srgrimes 6411573Srgrimes /* Initial DOT must be matched literally. */ 6421573Srgrimes if (dp->d_name[0] == DOT && *pattern != DOT) 6431573Srgrimes continue; 64474963Speter dc = pathend; 64574963Speter sc = (u_char *) dp->d_name; 64674963Speter while (dc < pathend_last && (*dc++ = *sc++) != EOS) 64774963Speter ; 6481573Srgrimes if (!match(pathend, pattern, restpattern)) { 6491573Srgrimes *pathend = EOS; 6501573Srgrimes continue; 6511573Srgrimes } 65274963Speter err = glob2(pathbuf, --dc, pathend_last, restpattern, 65374963Speter pglob, limit); 6541573Srgrimes if (err) 6551573Srgrimes break; 6561573Srgrimes } 6571573Srgrimes 6581573Srgrimes if (pglob->gl_flags & GLOB_ALTDIRFUNC) 6591573Srgrimes (*pglob->gl_closedir)(dirp); 6601573Srgrimes else 6611573Srgrimes closedir(dirp); 6621573Srgrimes return(err); 6631573Srgrimes} 6641573Srgrimes 6651573Srgrimes 6661573Srgrimes/* 6671573Srgrimes * Extend the gl_pathv member of a glob_t structure to accomodate a new item, 6681573Srgrimes * add the new item, and update gl_pathc. 6691573Srgrimes * 6701573Srgrimes * This assumes the BSD realloc, which only copies the block when its size 6711573Srgrimes * crosses a power-of-two boundary; for v7 realloc, this would cause quadratic 6721573Srgrimes * behavior. 6731573Srgrimes * 6741573Srgrimes * Return 0 if new item added, error code if memory couldn't be allocated. 6751573Srgrimes * 6761573Srgrimes * Invariant of the glob_t structure: 6771573Srgrimes * Either gl_pathc is zero and gl_pathv is NULL; or gl_pathc > 0 and 6781573Srgrimes * gl_pathv points to (gl_offs + gl_pathc + 1) items. 6791573Srgrimes */ 6801573Srgrimesstatic int 68174469Sjlemonglobextend(path, pglob, limit) 6821573Srgrimes const Char *path; 6831573Srgrimes glob_t *pglob; 68474469Sjlemon int *limit; 6851573Srgrimes{ 6861573Srgrimes register char **pathv; 6871573Srgrimes register int i; 68874918Speter u_int newsize, len; 6891573Srgrimes char *copy; 6901573Srgrimes const Char *p; 6911573Srgrimes 69280525Smikeh if (*limit && pglob->gl_pathc > *limit) { 69380525Smikeh errno = 0; 69480525Smikeh return (GLOB_NOSPACE); 69580525Smikeh } 69674307Sjlemon 6971573Srgrimes newsize = sizeof(*pathv) * (2 + pglob->gl_pathc + pglob->gl_offs); 6988870Srgrimes pathv = pglob->gl_pathv ? 6991573Srgrimes realloc((char *)pglob->gl_pathv, newsize) : 7001573Srgrimes malloc(newsize); 70174918Speter if (pathv == NULL) { 70274918Speter if (pglob->gl_pathv) { 70374918Speter free(pglob->gl_pathv); 70474918Speter pglob->gl_pathv = NULL; 70574918Speter } 7061573Srgrimes return(GLOB_NOSPACE); 70774918Speter } 7081573Srgrimes 7091573Srgrimes if (pglob->gl_pathv == NULL && pglob->gl_offs > 0) { 7101573Srgrimes /* first time around -- clear initial gl_offs items */ 7111573Srgrimes pathv += pglob->gl_offs; 7121573Srgrimes for (i = pglob->gl_offs; --i >= 0; ) 7131573Srgrimes *--pathv = NULL; 7141573Srgrimes } 7151573Srgrimes pglob->gl_pathv = pathv; 7161573Srgrimes 7171573Srgrimes for (p = path; *p++;) 7181573Srgrimes continue; 71974918Speter len = (size_t)(p - path); 72074921Speter if ((copy = malloc(len)) != NULL) { 72174921Speter if (g_Ctoc(path, copy, len)) { 72274918Speter free(copy); 72374918Speter return (GLOB_NOSPACE); 72474918Speter } 7251573Srgrimes pathv[pglob->gl_offs + pglob->gl_pathc++] = copy; 7261573Srgrimes } 7271573Srgrimes pathv[pglob->gl_offs + pglob->gl_pathc] = NULL; 7281573Srgrimes return(copy == NULL ? GLOB_NOSPACE : 0); 7291573Srgrimes} 7301573Srgrimes 7311573Srgrimes/* 7321573Srgrimes * pattern matching function for filenames. Each occurrence of the * 7331573Srgrimes * pattern causes a recursion level. 7341573Srgrimes */ 7351573Srgrimesstatic int 7361573Srgrimesmatch(name, pat, patend) 7371573Srgrimes register Char *name, *pat, *patend; 7381573Srgrimes{ 7391573Srgrimes int ok, negate_range; 7401573Srgrimes Char c, k; 7411573Srgrimes 7421573Srgrimes while (pat < patend) { 7431573Srgrimes c = *pat++; 7441573Srgrimes switch (c & M_MASK) { 7451573Srgrimes case M_ALL: 7461573Srgrimes if (pat == patend) 7471573Srgrimes return(1); 7488870Srgrimes do 7491573Srgrimes if (match(name, pat, patend)) 7501573Srgrimes return(1); 7511573Srgrimes while (*name++ != EOS); 7521573Srgrimes return(0); 7531573Srgrimes case M_ONE: 7541573Srgrimes if (*name++ == EOS) 7551573Srgrimes return(0); 7561573Srgrimes break; 7571573Srgrimes case M_SET: 7581573Srgrimes ok = 0; 7591573Srgrimes if ((k = *name++) == EOS) 7601573Srgrimes return(0); 7611573Srgrimes if ((negate_range = ((*pat & M_MASK) == M_NOT)) != EOS) 7621573Srgrimes ++pat; 7631573Srgrimes while (((c = *pat++) & M_MASK) != M_END) 7641573Srgrimes if ((*pat & M_MASK) == M_RNG) { 76524633Sache if (__collate_load_error ? 76624633Sache CHAR(c) <= CHAR(k) && CHAR(k) <= CHAR(pat[1]) : 76724633Sache __collate_range_cmp(CHAR(c), CHAR(k)) <= 0 76819276Sache && __collate_range_cmp(CHAR(k), CHAR(pat[1])) <= 0 76917528Sache ) 7701573Srgrimes ok = 1; 7711573Srgrimes pat += 2; 7721573Srgrimes } else if (c == k) 7731573Srgrimes ok = 1; 7741573Srgrimes if (ok == negate_range) 7751573Srgrimes return(0); 7761573Srgrimes break; 7771573Srgrimes default: 7781573Srgrimes if (*name++ != c) 7791573Srgrimes return(0); 7801573Srgrimes break; 7811573Srgrimes } 7821573Srgrimes } 7831573Srgrimes return(*name == EOS); 7841573Srgrimes} 7851573Srgrimes 7861573Srgrimes/* Free allocated data belonging to a glob_t structure. */ 7871573Srgrimesvoid 7881573Srgrimesglobfree(pglob) 7891573Srgrimes glob_t *pglob; 7901573Srgrimes{ 7911573Srgrimes register int i; 7921573Srgrimes register char **pp; 7931573Srgrimes 7941573Srgrimes if (pglob->gl_pathv != NULL) { 7951573Srgrimes pp = pglob->gl_pathv + pglob->gl_offs; 7961573Srgrimes for (i = pglob->gl_pathc; i--; ++pp) 7971573Srgrimes if (*pp) 7981573Srgrimes free(*pp); 7991573Srgrimes free(pglob->gl_pathv); 80074918Speter pglob->gl_pathv = NULL; 8011573Srgrimes } 8021573Srgrimes} 8031573Srgrimes 8041573Srgrimesstatic DIR * 8051573Srgrimesg_opendir(str, pglob) 8061573Srgrimes register Char *str; 8071573Srgrimes glob_t *pglob; 8081573Srgrimes{ 8091573Srgrimes char buf[MAXPATHLEN]; 8101573Srgrimes 8111573Srgrimes if (!*str) 8121573Srgrimes strcpy(buf, "."); 81374918Speter else { 81474921Speter if (g_Ctoc(str, buf, sizeof(buf))) 81574918Speter return (NULL); 81674918Speter } 8171573Srgrimes 8181573Srgrimes if (pglob->gl_flags & GLOB_ALTDIRFUNC) 8191573Srgrimes return((*pglob->gl_opendir)(buf)); 8201573Srgrimes 8211573Srgrimes return(opendir(buf)); 8221573Srgrimes} 8231573Srgrimes 8241573Srgrimesstatic int 8251573Srgrimesg_lstat(fn, sb, pglob) 8261573Srgrimes register Char *fn; 8271573Srgrimes struct stat *sb; 8281573Srgrimes glob_t *pglob; 8291573Srgrimes{ 8301573Srgrimes char buf[MAXPATHLEN]; 8311573Srgrimes 83274921Speter if (g_Ctoc(fn, buf, sizeof(buf))) { 83374918Speter errno = ENAMETOOLONG; 83474918Speter return (-1); 83574918Speter } 8361573Srgrimes if (pglob->gl_flags & GLOB_ALTDIRFUNC) 8371573Srgrimes return((*pglob->gl_lstat)(buf, sb)); 8381573Srgrimes return(lstat(buf, sb)); 8391573Srgrimes} 8401573Srgrimes 8411573Srgrimesstatic int 8421573Srgrimesg_stat(fn, sb, pglob) 8431573Srgrimes register Char *fn; 8441573Srgrimes struct stat *sb; 8451573Srgrimes glob_t *pglob; 8461573Srgrimes{ 8471573Srgrimes char buf[MAXPATHLEN]; 8481573Srgrimes 84974921Speter if (g_Ctoc(fn, buf, sizeof(buf))) { 85074918Speter errno = ENAMETOOLONG; 85174918Speter return (-1); 85274918Speter } 8531573Srgrimes if (pglob->gl_flags & GLOB_ALTDIRFUNC) 8541573Srgrimes return((*pglob->gl_stat)(buf, sb)); 8551573Srgrimes return(stat(buf, sb)); 8561573Srgrimes} 8571573Srgrimes 8581573Srgrimesstatic Char * 8591573Srgrimesg_strchr(str, ch) 8601573Srgrimes Char *str; 8611573Srgrimes int ch; 8621573Srgrimes{ 8631573Srgrimes do { 8641573Srgrimes if (*str == ch) 8651573Srgrimes return (str); 8661573Srgrimes } while (*str++); 8671573Srgrimes return (NULL); 8681573Srgrimes} 8691573Srgrimes 87074918Speterstatic int 87174921Speterg_Ctoc(str, buf, len) 87274921Speter const Char *str; 87374921Speter char *buf; 87474921Speter u_int len; 8751573Srgrimes{ 8761573Srgrimes 87774921Speter while (len--) { 87874921Speter if ((*buf++ = *str++) == '\0') 87974921Speter return (0); 88074921Speter } 88174921Speter return (1); 8821573Srgrimes} 8831573Srgrimes 8841573Srgrimes#ifdef DEBUG 8858870Srgrimesstatic void 8861573Srgrimesqprintf(str, s) 8871573Srgrimes const char *str; 8881573Srgrimes register Char *s; 8891573Srgrimes{ 8901573Srgrimes register Char *p; 8911573Srgrimes 8921573Srgrimes (void)printf("%s:\n", str); 8931573Srgrimes for (p = s; *p; p++) 8941573Srgrimes (void)printf("%c", CHAR(*p)); 8951573Srgrimes (void)printf("\n"); 8961573Srgrimes for (p = s; *p; p++) 8971573Srgrimes (void)printf("%c", *p & M_PROTECT ? '"' : ' '); 8981573Srgrimes (void)printf("\n"); 8991573Srgrimes for (p = s; *p; p++) 9001573Srgrimes (void)printf("%c", ismeta(*p) ? '_' : ' '); 9011573Srgrimes (void)printf("\n"); 9021573Srgrimes} 9031573Srgrimes#endif 904