glob.c revision 74963
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 74963 2001-03-28 23:55:51Z peter $ 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 } 17374469Sjlemon if (flags & GLOB_MAXPATH) 17474469Sjlemon limit = pglob->gl_matchc; 17574469Sjlemon else 17674469Sjlemon limit = 0; 1771573Srgrimes pglob->gl_flags = flags & ~GLOB_MAGCHAR; 1781573Srgrimes pglob->gl_errfunc = errfunc; 1791573Srgrimes pglob->gl_matchc = 0; 1801573Srgrimes 1811573Srgrimes bufnext = patbuf; 18274963Speter bufend = bufnext + MAXPATHLEN - 1; 1831573Srgrimes if (flags & GLOB_QUOTE) { 1841573Srgrimes /* Protect the quoted characters. */ 1858870Srgrimes while (bufnext < bufend && (c = *patnext++) != EOS) 1861573Srgrimes if (c == QUOTE) { 1871573Srgrimes if ((c = *patnext++) == EOS) { 1881573Srgrimes c = QUOTE; 1891573Srgrimes --patnext; 1901573Srgrimes } 1911573Srgrimes *bufnext++ = c | M_PROTECT; 1921573Srgrimes } 1931573Srgrimes else 1941573Srgrimes *bufnext++ = c; 1951573Srgrimes } 1968870Srgrimes else 1978870Srgrimes while (bufnext < bufend && (c = *patnext++) != EOS) 1981573Srgrimes *bufnext++ = c; 1991573Srgrimes *bufnext = EOS; 2001573Srgrimes 2011573Srgrimes if (flags & GLOB_BRACE) 20274469Sjlemon return globexp1(patbuf, pglob, &limit); 2031573Srgrimes else 20474469Sjlemon return glob0(patbuf, pglob, &limit); 2051573Srgrimes} 2061573Srgrimes 2071573Srgrimes/* 2081573Srgrimes * Expand recursively a glob {} pattern. When there is no more expansion 2091573Srgrimes * invoke the standard globbing routine to glob the rest of the magic 2101573Srgrimes * characters 2111573Srgrimes */ 21274963Speterstatic int 21374963Speterglobexp1(pattern, pglob, limit) 2141573Srgrimes const Char *pattern; 2151573Srgrimes glob_t *pglob; 21674469Sjlemon int *limit; 2171573Srgrimes{ 2181573Srgrimes const Char* ptr = pattern; 2191573Srgrimes int rv; 2201573Srgrimes 2211573Srgrimes /* Protect a single {}, for find(1), like csh */ 2221573Srgrimes if (pattern[0] == LBRACE && pattern[1] == RBRACE && pattern[2] == EOS) 22374469Sjlemon return glob0(pattern, pglob, limit); 2241573Srgrimes 2251573Srgrimes while ((ptr = (const Char *) g_strchr((Char *) ptr, LBRACE)) != NULL) 22674469Sjlemon if (!globexp2(ptr, pattern, pglob, &rv, limit)) 2271573Srgrimes return rv; 2281573Srgrimes 22974469Sjlemon return glob0(pattern, pglob, limit); 2301573Srgrimes} 2311573Srgrimes 2321573Srgrimes 2331573Srgrimes/* 2341573Srgrimes * Recursive brace globbing helper. Tries to expand a single brace. 2351573Srgrimes * If it succeeds then it invokes globexp1 with the new pattern. 2361573Srgrimes * If it fails then it tries to glob the rest of the pattern and returns. 2371573Srgrimes */ 23874963Speterstatic int 23974963Speterglobexp2(ptr, pattern, pglob, rv, limit) 2401573Srgrimes const Char *ptr, *pattern; 2411573Srgrimes glob_t *pglob; 24274469Sjlemon int *rv, *limit; 2431573Srgrimes{ 2441573Srgrimes int i; 2451573Srgrimes Char *lm, *ls; 2461573Srgrimes const Char *pe, *pm, *pl; 24774963Speter Char patbuf[MAXPATHLEN]; 2481573Srgrimes 2491573Srgrimes /* copy part up to the brace */ 2501573Srgrimes for (lm = patbuf, pm = pattern; pm != ptr; *lm++ = *pm++) 2511573Srgrimes continue; 25274963Speter *lm = EOS; 2531573Srgrimes ls = lm; 2541573Srgrimes 2551573Srgrimes /* Find the balanced brace */ 2561573Srgrimes for (i = 0, pe = ++ptr; *pe; pe++) 2571573Srgrimes if (*pe == LBRACKET) { 2581573Srgrimes /* Ignore everything between [] */ 2591573Srgrimes for (pm = pe++; *pe != RBRACKET && *pe != EOS; pe++) 2601573Srgrimes continue; 2611573Srgrimes if (*pe == EOS) { 2628870Srgrimes /* 2631573Srgrimes * We could not find a matching RBRACKET. 2641573Srgrimes * Ignore and just look for RBRACE 2651573Srgrimes */ 2661573Srgrimes pe = pm; 2671573Srgrimes } 2681573Srgrimes } 2691573Srgrimes else if (*pe == LBRACE) 2701573Srgrimes i++; 2711573Srgrimes else if (*pe == RBRACE) { 2721573Srgrimes if (i == 0) 2731573Srgrimes break; 2741573Srgrimes i--; 2751573Srgrimes } 2761573Srgrimes 2771573Srgrimes /* Non matching braces; just glob the pattern */ 2781573Srgrimes if (i != 0 || *pe == EOS) { 27974469Sjlemon *rv = glob0(patbuf, pglob, limit); 2801573Srgrimes return 0; 2811573Srgrimes } 2821573Srgrimes 2831573Srgrimes for (i = 0, pl = pm = ptr; pm <= pe; pm++) 2841573Srgrimes switch (*pm) { 2851573Srgrimes case LBRACKET: 2861573Srgrimes /* Ignore everything between [] */ 2871573Srgrimes for (pl = pm++; *pm != RBRACKET && *pm != EOS; pm++) 2881573Srgrimes continue; 2891573Srgrimes if (*pm == EOS) { 2908870Srgrimes /* 2911573Srgrimes * We could not find a matching RBRACKET. 2921573Srgrimes * Ignore and just look for RBRACE 2931573Srgrimes */ 2941573Srgrimes pm = pl; 2951573Srgrimes } 2961573Srgrimes break; 2971573Srgrimes 2981573Srgrimes case LBRACE: 2991573Srgrimes i++; 3001573Srgrimes break; 3011573Srgrimes 3021573Srgrimes case RBRACE: 3031573Srgrimes if (i) { 3041573Srgrimes i--; 3051573Srgrimes break; 3061573Srgrimes } 3071573Srgrimes /* FALLTHROUGH */ 3081573Srgrimes case COMMA: 3091573Srgrimes if (i && *pm == COMMA) 3101573Srgrimes break; 3111573Srgrimes else { 3121573Srgrimes /* Append the current string */ 3131573Srgrimes for (lm = ls; (pl < pm); *lm++ = *pl++) 3141573Srgrimes continue; 3158870Srgrimes /* 3161573Srgrimes * Append the rest of the pattern after the 3171573Srgrimes * closing brace 3181573Srgrimes */ 3191573Srgrimes for (pl = pe + 1; (*lm++ = *pl++) != EOS;) 3201573Srgrimes continue; 3211573Srgrimes 3221573Srgrimes /* Expand the current pattern */ 3231573Srgrimes#ifdef DEBUG 3241573Srgrimes qprintf("globexp2:", patbuf); 3251573Srgrimes#endif 32674469Sjlemon *rv = globexp1(patbuf, pglob, limit); 3271573Srgrimes 3281573Srgrimes /* move after the comma, to the next string */ 3291573Srgrimes pl = pm + 1; 3301573Srgrimes } 3311573Srgrimes break; 3321573Srgrimes 3331573Srgrimes default: 3341573Srgrimes break; 3351573Srgrimes } 3361573Srgrimes *rv = 0; 3371573Srgrimes return 0; 3381573Srgrimes} 3391573Srgrimes 3401573Srgrimes 3411573Srgrimes 3421573Srgrimes/* 3431573Srgrimes * expand tilde from the passwd file. 3441573Srgrimes */ 3451573Srgrimesstatic const Char * 34624158Simpglobtilde(pattern, patbuf, patbuf_len, pglob) 3471573Srgrimes const Char *pattern; 3481573Srgrimes Char *patbuf; 34924158Simp size_t patbuf_len; 3501573Srgrimes glob_t *pglob; 3511573Srgrimes{ 3521573Srgrimes struct passwd *pwd; 3531573Srgrimes char *h; 3541573Srgrimes const Char *p; 35524158Simp Char *b, *eb; 3561573Srgrimes 3571573Srgrimes if (*pattern != TILDE || !(pglob->gl_flags & GLOB_TILDE)) 3581573Srgrimes return pattern; 3591573Srgrimes 36024158Simp /* 36124158Simp * Copy up to the end of the string or / 36224158Simp */ 36324158Simp eb = &patbuf[patbuf_len - 1]; 36424158Simp for (p = pattern + 1, h = (char *) patbuf; 36524158Simp h < (char *)eb && *p && *p != SLASH; *h++ = *p++) 3661573Srgrimes continue; 3671573Srgrimes 3681573Srgrimes *h = EOS; 3691573Srgrimes 3701573Srgrimes if (((char *) patbuf)[0] == EOS) { 3718870Srgrimes /* 37228820Simp * handle a plain ~ or ~/ by expanding $HOME first (iff 37328820Simp * we're not running setuid or setgid) and then trying 37428820Simp * the password file 3751573Srgrimes */ 37633664Sjb if ( 37733664Sjb#ifndef __NETBSD_SYSCALLS 37833664Sjb issetugid() != 0 || 37933664Sjb#endif 38033664Sjb (h = getenv("HOME")) == NULL) { 38128836Sache if (((h = getlogin()) != NULL && 38228836Sache (pwd = getpwnam(h)) != NULL) || 38328836Sache (pwd = getpwuid(getuid())) != NULL) 38428836Sache h = pwd->pw_dir; 38528836Sache else 3861573Srgrimes return pattern; 3871573Srgrimes } 3881573Srgrimes } 3891573Srgrimes else { 3901573Srgrimes /* 3911573Srgrimes * Expand a ~user 3921573Srgrimes */ 3931573Srgrimes if ((pwd = getpwnam((char*) patbuf)) == NULL) 3941573Srgrimes return pattern; 3951573Srgrimes else 3961573Srgrimes h = pwd->pw_dir; 3971573Srgrimes } 3981573Srgrimes 3991573Srgrimes /* Copy the home directory */ 40024158Simp for (b = patbuf; b < eb && *h; *b++ = *h++) 4011573Srgrimes continue; 4028870Srgrimes 4031573Srgrimes /* Append the rest of the pattern */ 40424158Simp while (b < eb && (*b++ = *p++) != EOS) 4051573Srgrimes continue; 40624158Simp *b = EOS; 4071573Srgrimes 4081573Srgrimes return patbuf; 4091573Srgrimes} 4101573Srgrimes 4118870Srgrimes 4121573Srgrimes/* 4131573Srgrimes * The main glob() routine: compiles the pattern (optionally processing 4141573Srgrimes * quotes), calls glob1() to do the real pattern matching, and finally 4151573Srgrimes * sorts the list (unless unsorted operation is requested). Returns 0 4161573Srgrimes * if things went well, nonzero if errors occurred. It is not an error 4171573Srgrimes * to find no matches. 4181573Srgrimes */ 4191573Srgrimesstatic int 42074469Sjlemonglob0(pattern, pglob, limit) 4211573Srgrimes const Char *pattern; 4221573Srgrimes glob_t *pglob; 42374469Sjlemon int *limit; 4241573Srgrimes{ 4251573Srgrimes const Char *qpatnext; 4261573Srgrimes int c, err, oldpathc; 42774963Speter Char *bufnext, patbuf[MAXPATHLEN]; 4281573Srgrimes 42974963Speter qpatnext = globtilde(pattern, patbuf, MAXPATHLEN, pglob); 4301573Srgrimes oldpathc = pglob->gl_pathc; 4311573Srgrimes bufnext = patbuf; 4321573Srgrimes 4331573Srgrimes /* We don't need to check for buffer overflow any more. */ 4341573Srgrimes while ((c = *qpatnext++) != EOS) { 4351573Srgrimes switch (c) { 4361573Srgrimes case LBRACKET: 4371573Srgrimes c = *qpatnext; 4381573Srgrimes if (c == NOT) 4391573Srgrimes ++qpatnext; 4401573Srgrimes if (*qpatnext == EOS || 4411573Srgrimes g_strchr((Char *) qpatnext+1, RBRACKET) == NULL) { 4421573Srgrimes *bufnext++ = LBRACKET; 4431573Srgrimes if (c == NOT) 4441573Srgrimes --qpatnext; 4451573Srgrimes break; 4461573Srgrimes } 4471573Srgrimes *bufnext++ = M_SET; 4481573Srgrimes if (c == NOT) 4491573Srgrimes *bufnext++ = M_NOT; 4501573Srgrimes c = *qpatnext++; 4511573Srgrimes do { 4521573Srgrimes *bufnext++ = CHAR(c); 4531573Srgrimes if (*qpatnext == RANGE && 4541573Srgrimes (c = qpatnext[1]) != RBRACKET) { 4551573Srgrimes *bufnext++ = M_RNG; 4561573Srgrimes *bufnext++ = CHAR(c); 4571573Srgrimes qpatnext += 2; 4581573Srgrimes } 4591573Srgrimes } while ((c = *qpatnext++) != RBRACKET); 4601573Srgrimes pglob->gl_flags |= GLOB_MAGCHAR; 4611573Srgrimes *bufnext++ = M_END; 4621573Srgrimes break; 4631573Srgrimes case QUESTION: 4641573Srgrimes pglob->gl_flags |= GLOB_MAGCHAR; 4651573Srgrimes *bufnext++ = M_ONE; 4661573Srgrimes break; 4671573Srgrimes case STAR: 4681573Srgrimes pglob->gl_flags |= GLOB_MAGCHAR; 4698870Srgrimes /* collapse adjacent stars to one, 4701573Srgrimes * to avoid exponential behavior 4711573Srgrimes */ 4721573Srgrimes if (bufnext == patbuf || bufnext[-1] != M_ALL) 4731573Srgrimes *bufnext++ = M_ALL; 4741573Srgrimes break; 4751573Srgrimes default: 4761573Srgrimes *bufnext++ = CHAR(c); 4771573Srgrimes break; 4781573Srgrimes } 4791573Srgrimes } 4801573Srgrimes *bufnext = EOS; 4811573Srgrimes#ifdef DEBUG 4821573Srgrimes qprintf("glob0:", patbuf); 4831573Srgrimes#endif 4841573Srgrimes 48574469Sjlemon if ((err = glob1(patbuf, pglob, limit)) != 0) 4861573Srgrimes return(err); 4871573Srgrimes 4881573Srgrimes /* 4898870Srgrimes * If there was no match we are going to append the pattern 4901573Srgrimes * if GLOB_NOCHECK was specified or if GLOB_NOMAGIC was specified 4911573Srgrimes * and the pattern did not contain any magic characters 4921573Srgrimes * GLOB_NOMAGIC is there just for compatibility with csh. 4931573Srgrimes */ 4948870Srgrimes if (pglob->gl_pathc == oldpathc && 4958870Srgrimes ((pglob->gl_flags & GLOB_NOCHECK) || 4961573Srgrimes ((pglob->gl_flags & GLOB_NOMAGIC) && 4971573Srgrimes !(pglob->gl_flags & GLOB_MAGCHAR)))) 49874469Sjlemon return(globextend(pattern, pglob, limit)); 4998870Srgrimes else if (!(pglob->gl_flags & GLOB_NOSORT)) 5001573Srgrimes qsort(pglob->gl_pathv + pglob->gl_offs + oldpathc, 5011573Srgrimes pglob->gl_pathc - oldpathc, sizeof(char *), compare); 5021573Srgrimes return(0); 5031573Srgrimes} 5041573Srgrimes 5051573Srgrimesstatic int 5061573Srgrimescompare(p, q) 5071573Srgrimes const void *p, *q; 5081573Srgrimes{ 5091573Srgrimes return(strcmp(*(char **)p, *(char **)q)); 5101573Srgrimes} 5111573Srgrimes 5121573Srgrimesstatic int 51374469Sjlemonglob1(pattern, pglob, limit) 5141573Srgrimes Char *pattern; 5151573Srgrimes glob_t *pglob; 51674469Sjlemon int *limit; 5171573Srgrimes{ 51874963Speter Char pathbuf[MAXPATHLEN]; 5191573Srgrimes 5201573Srgrimes /* A null pathname is invalid -- POSIX 1003.1 sect. 2.4. */ 5211573Srgrimes if (*pattern == EOS) 5221573Srgrimes return(0); 52374963Speter return(glob2(pathbuf, pathbuf, pathbuf + MAXPATHLEN - 1, 52474963Speter pattern, pglob, limit)); 5251573Srgrimes} 5261573Srgrimes 5271573Srgrimes/* 5281573Srgrimes * The functions glob2 and glob3 are mutually recursive; there is one level 5291573Srgrimes * of recursion for each segment in the pattern that contains one or more 5301573Srgrimes * meta characters. 5311573Srgrimes */ 5321573Srgrimesstatic int 53374963Speterglob2(pathbuf, pathend, pathend_last, pattern, pglob, limit) 53474963Speter Char *pathbuf, *pathend, *pathend_last, *pattern; 5351573Srgrimes glob_t *pglob; 53674469Sjlemon int *limit; 5371573Srgrimes{ 5381573Srgrimes struct stat sb; 5391573Srgrimes Char *p, *q; 5401573Srgrimes int anymeta; 5411573Srgrimes 5421573Srgrimes /* 5431573Srgrimes * Loop over pattern segments until end of pattern or until 5441573Srgrimes * segment with meta character found. 5451573Srgrimes */ 5461573Srgrimes for (anymeta = 0;;) { 5471573Srgrimes if (*pattern == EOS) { /* End of pattern? */ 5481573Srgrimes *pathend = EOS; 5491573Srgrimes if (g_lstat(pathbuf, &sb, pglob)) 5501573Srgrimes return(0); 5518870Srgrimes 5521573Srgrimes if (((pglob->gl_flags & GLOB_MARK) && 5531573Srgrimes pathend[-1] != SEP) && (S_ISDIR(sb.st_mode) 5541573Srgrimes || (S_ISLNK(sb.st_mode) && 5551573Srgrimes (g_stat(pathbuf, &sb, pglob) == 0) && 5561573Srgrimes S_ISDIR(sb.st_mode)))) { 55774963Speter if (pathend + 1 > pathend_last) 55874963Speter return (1); 5591573Srgrimes *pathend++ = SEP; 5601573Srgrimes *pathend = EOS; 5611573Srgrimes } 5621573Srgrimes ++pglob->gl_matchc; 56374469Sjlemon return(globextend(pathbuf, pglob, limit)); 5641573Srgrimes } 5651573Srgrimes 5661573Srgrimes /* Find end of next segment, copy tentatively to pathend. */ 5671573Srgrimes q = pathend; 5681573Srgrimes p = pattern; 5691573Srgrimes while (*p != EOS && *p != SEP) { 5701573Srgrimes if (ismeta(*p)) 5711573Srgrimes anymeta = 1; 57274963Speter if (q + 1 > pathend_last) 57374963Speter return (1); 5741573Srgrimes *q++ = *p++; 5751573Srgrimes } 5761573Srgrimes 5771573Srgrimes if (!anymeta) { /* No expansion, do next segment. */ 5781573Srgrimes pathend = q; 5791573Srgrimes pattern = p; 58074963Speter while (*pattern == SEP) { 58174963Speter if (pathend + 1 > pathend_last) 58274963Speter return (1); 5831573Srgrimes *pathend++ = *pattern++; 58474963Speter } 5851573Srgrimes } else /* Need expansion, recurse. */ 58674963Speter return(glob3(pathbuf, pathend, pathend_last, pattern, p, 58774963Speter pglob, limit)); 5881573Srgrimes } 5891573Srgrimes /* NOTREACHED */ 5901573Srgrimes} 5911573Srgrimes 5921573Srgrimesstatic int 59374963Speterglob3(pathbuf, pathend, pathend_last, pattern, restpattern, pglob, limit) 59474963Speter Char *pathbuf, *pathend, *pathend_last, *pattern, *restpattern; 5951573Srgrimes glob_t *pglob; 59674469Sjlemon int *limit; 5971573Srgrimes{ 5981573Srgrimes register struct dirent *dp; 5991573Srgrimes DIR *dirp; 6001573Srgrimes int err; 6011573Srgrimes char buf[MAXPATHLEN]; 6021573Srgrimes 6031573Srgrimes /* 6041573Srgrimes * The readdirfunc declaration can't be prototyped, because it is 6051573Srgrimes * assigned, below, to two functions which are prototyped in glob.h 6061573Srgrimes * and dirent.h as taking pointers to differently typed opaque 6071573Srgrimes * structures. 6081573Srgrimes */ 6091573Srgrimes struct dirent *(*readdirfunc)(); 6101573Srgrimes 61174963Speter if (pathend > pathend_last) 61274963Speter return (1); 6131573Srgrimes *pathend = EOS; 6141573Srgrimes errno = 0; 6158870Srgrimes 6161573Srgrimes if ((dirp = g_opendir(pathbuf, pglob)) == NULL) { 6171573Srgrimes /* TODO: don't call for ENOENT or ENOTDIR? */ 6181573Srgrimes if (pglob->gl_errfunc) { 61974921Speter if (g_Ctoc(pathbuf, buf, sizeof(buf))) 62074918Speter return (GLOB_ABEND); 6211573Srgrimes if (pglob->gl_errfunc(buf, errno) || 6221573Srgrimes pglob->gl_flags & GLOB_ERR) 6231573Srgrimes return (GLOB_ABEND); 6241573Srgrimes } 6251573Srgrimes return(0); 6261573Srgrimes } 6271573Srgrimes 6281573Srgrimes err = 0; 6291573Srgrimes 6301573Srgrimes /* Search directory for matching names. */ 6311573Srgrimes if (pglob->gl_flags & GLOB_ALTDIRFUNC) 6321573Srgrimes readdirfunc = pglob->gl_readdir; 6331573Srgrimes else 6341573Srgrimes readdirfunc = readdir; 6351573Srgrimes while ((dp = (*readdirfunc)(dirp))) { 6361573Srgrimes register u_char *sc; 6371573Srgrimes register Char *dc; 6381573Srgrimes 6391573Srgrimes /* Initial DOT must be matched literally. */ 6401573Srgrimes if (dp->d_name[0] == DOT && *pattern != DOT) 6411573Srgrimes continue; 64274963Speter dc = pathend; 64374963Speter sc = (u_char *) dp->d_name; 64474963Speter while (dc < pathend_last && (*dc++ = *sc++) != EOS) 64574963Speter ; 6461573Srgrimes if (!match(pathend, pattern, restpattern)) { 6471573Srgrimes *pathend = EOS; 6481573Srgrimes continue; 6491573Srgrimes } 65074963Speter err = glob2(pathbuf, --dc, pathend_last, restpattern, 65174963Speter pglob, limit); 6521573Srgrimes if (err) 6531573Srgrimes break; 6541573Srgrimes } 6551573Srgrimes 6561573Srgrimes if (pglob->gl_flags & GLOB_ALTDIRFUNC) 6571573Srgrimes (*pglob->gl_closedir)(dirp); 6581573Srgrimes else 6591573Srgrimes closedir(dirp); 6601573Srgrimes return(err); 6611573Srgrimes} 6621573Srgrimes 6631573Srgrimes 6641573Srgrimes/* 6651573Srgrimes * Extend the gl_pathv member of a glob_t structure to accomodate a new item, 6661573Srgrimes * add the new item, and update gl_pathc. 6671573Srgrimes * 6681573Srgrimes * This assumes the BSD realloc, which only copies the block when its size 6691573Srgrimes * crosses a power-of-two boundary; for v7 realloc, this would cause quadratic 6701573Srgrimes * behavior. 6711573Srgrimes * 6721573Srgrimes * Return 0 if new item added, error code if memory couldn't be allocated. 6731573Srgrimes * 6741573Srgrimes * Invariant of the glob_t structure: 6751573Srgrimes * Either gl_pathc is zero and gl_pathv is NULL; or gl_pathc > 0 and 6761573Srgrimes * gl_pathv points to (gl_offs + gl_pathc + 1) items. 6771573Srgrimes */ 6781573Srgrimesstatic int 67974469Sjlemonglobextend(path, pglob, limit) 6801573Srgrimes const Char *path; 6811573Srgrimes glob_t *pglob; 68274469Sjlemon int *limit; 6831573Srgrimes{ 6841573Srgrimes register char **pathv; 6851573Srgrimes register int i; 68674918Speter u_int newsize, len; 6871573Srgrimes char *copy; 6881573Srgrimes const Char *p; 6891573Srgrimes 69074469Sjlemon if (*limit && pglob->gl_pathc > *limit) 69174469Sjlemon return (GLOB_LIMIT); 69274307Sjlemon 6931573Srgrimes newsize = sizeof(*pathv) * (2 + pglob->gl_pathc + pglob->gl_offs); 6948870Srgrimes pathv = pglob->gl_pathv ? 6951573Srgrimes realloc((char *)pglob->gl_pathv, newsize) : 6961573Srgrimes malloc(newsize); 69774918Speter if (pathv == NULL) { 69874918Speter if (pglob->gl_pathv) { 69974918Speter free(pglob->gl_pathv); 70074918Speter pglob->gl_pathv = NULL; 70174918Speter } 7021573Srgrimes return(GLOB_NOSPACE); 70374918Speter } 7041573Srgrimes 7051573Srgrimes if (pglob->gl_pathv == NULL && pglob->gl_offs > 0) { 7061573Srgrimes /* first time around -- clear initial gl_offs items */ 7071573Srgrimes pathv += pglob->gl_offs; 7081573Srgrimes for (i = pglob->gl_offs; --i >= 0; ) 7091573Srgrimes *--pathv = NULL; 7101573Srgrimes } 7111573Srgrimes pglob->gl_pathv = pathv; 7121573Srgrimes 7131573Srgrimes for (p = path; *p++;) 7141573Srgrimes continue; 71574918Speter len = (size_t)(p - path); 71674921Speter if ((copy = malloc(len)) != NULL) { 71774921Speter if (g_Ctoc(path, copy, len)) { 71874918Speter free(copy); 71974918Speter return (GLOB_NOSPACE); 72074918Speter } 7211573Srgrimes pathv[pglob->gl_offs + pglob->gl_pathc++] = copy; 7221573Srgrimes } 7231573Srgrimes pathv[pglob->gl_offs + pglob->gl_pathc] = NULL; 7241573Srgrimes return(copy == NULL ? GLOB_NOSPACE : 0); 7251573Srgrimes} 7261573Srgrimes 7271573Srgrimes/* 7281573Srgrimes * pattern matching function for filenames. Each occurrence of the * 7291573Srgrimes * pattern causes a recursion level. 7301573Srgrimes */ 7311573Srgrimesstatic int 7321573Srgrimesmatch(name, pat, patend) 7331573Srgrimes register Char *name, *pat, *patend; 7341573Srgrimes{ 7351573Srgrimes int ok, negate_range; 7361573Srgrimes Char c, k; 7371573Srgrimes 7381573Srgrimes while (pat < patend) { 7391573Srgrimes c = *pat++; 7401573Srgrimes switch (c & M_MASK) { 7411573Srgrimes case M_ALL: 7421573Srgrimes if (pat == patend) 7431573Srgrimes return(1); 7448870Srgrimes do 7451573Srgrimes if (match(name, pat, patend)) 7461573Srgrimes return(1); 7471573Srgrimes while (*name++ != EOS); 7481573Srgrimes return(0); 7491573Srgrimes case M_ONE: 7501573Srgrimes if (*name++ == EOS) 7511573Srgrimes return(0); 7521573Srgrimes break; 7531573Srgrimes case M_SET: 7541573Srgrimes ok = 0; 7551573Srgrimes if ((k = *name++) == EOS) 7561573Srgrimes return(0); 7571573Srgrimes if ((negate_range = ((*pat & M_MASK) == M_NOT)) != EOS) 7581573Srgrimes ++pat; 7591573Srgrimes while (((c = *pat++) & M_MASK) != M_END) 7601573Srgrimes if ((*pat & M_MASK) == M_RNG) { 76124633Sache if (__collate_load_error ? 76224633Sache CHAR(c) <= CHAR(k) && CHAR(k) <= CHAR(pat[1]) : 76324633Sache __collate_range_cmp(CHAR(c), CHAR(k)) <= 0 76419276Sache && __collate_range_cmp(CHAR(k), CHAR(pat[1])) <= 0 76517528Sache ) 7661573Srgrimes ok = 1; 7671573Srgrimes pat += 2; 7681573Srgrimes } else if (c == k) 7691573Srgrimes ok = 1; 7701573Srgrimes if (ok == negate_range) 7711573Srgrimes return(0); 7721573Srgrimes break; 7731573Srgrimes default: 7741573Srgrimes if (*name++ != c) 7751573Srgrimes return(0); 7761573Srgrimes break; 7771573Srgrimes } 7781573Srgrimes } 7791573Srgrimes return(*name == EOS); 7801573Srgrimes} 7811573Srgrimes 7821573Srgrimes/* Free allocated data belonging to a glob_t structure. */ 7831573Srgrimesvoid 7841573Srgrimesglobfree(pglob) 7851573Srgrimes glob_t *pglob; 7861573Srgrimes{ 7871573Srgrimes register int i; 7881573Srgrimes register char **pp; 7891573Srgrimes 7901573Srgrimes if (pglob->gl_pathv != NULL) { 7911573Srgrimes pp = pglob->gl_pathv + pglob->gl_offs; 7921573Srgrimes for (i = pglob->gl_pathc; i--; ++pp) 7931573Srgrimes if (*pp) 7941573Srgrimes free(*pp); 7951573Srgrimes free(pglob->gl_pathv); 79674918Speter pglob->gl_pathv = NULL; 7971573Srgrimes } 7981573Srgrimes} 7991573Srgrimes 8001573Srgrimesstatic DIR * 8011573Srgrimesg_opendir(str, pglob) 8021573Srgrimes register Char *str; 8031573Srgrimes glob_t *pglob; 8041573Srgrimes{ 8051573Srgrimes char buf[MAXPATHLEN]; 8061573Srgrimes 8071573Srgrimes if (!*str) 8081573Srgrimes strcpy(buf, "."); 80974918Speter else { 81074921Speter if (g_Ctoc(str, buf, sizeof(buf))) 81174918Speter return (NULL); 81274918Speter } 8131573Srgrimes 8141573Srgrimes if (pglob->gl_flags & GLOB_ALTDIRFUNC) 8151573Srgrimes return((*pglob->gl_opendir)(buf)); 8161573Srgrimes 8171573Srgrimes return(opendir(buf)); 8181573Srgrimes} 8191573Srgrimes 8201573Srgrimesstatic int 8211573Srgrimesg_lstat(fn, sb, pglob) 8221573Srgrimes register Char *fn; 8231573Srgrimes struct stat *sb; 8241573Srgrimes glob_t *pglob; 8251573Srgrimes{ 8261573Srgrimes char buf[MAXPATHLEN]; 8271573Srgrimes 82874921Speter if (g_Ctoc(fn, buf, sizeof(buf))) { 82974918Speter errno = ENAMETOOLONG; 83074918Speter return (-1); 83174918Speter } 8321573Srgrimes if (pglob->gl_flags & GLOB_ALTDIRFUNC) 8331573Srgrimes return((*pglob->gl_lstat)(buf, sb)); 8341573Srgrimes return(lstat(buf, sb)); 8351573Srgrimes} 8361573Srgrimes 8371573Srgrimesstatic int 8381573Srgrimesg_stat(fn, sb, pglob) 8391573Srgrimes register Char *fn; 8401573Srgrimes struct stat *sb; 8411573Srgrimes glob_t *pglob; 8421573Srgrimes{ 8431573Srgrimes char buf[MAXPATHLEN]; 8441573Srgrimes 84574921Speter if (g_Ctoc(fn, buf, sizeof(buf))) { 84674918Speter errno = ENAMETOOLONG; 84774918Speter return (-1); 84874918Speter } 8491573Srgrimes if (pglob->gl_flags & GLOB_ALTDIRFUNC) 8501573Srgrimes return((*pglob->gl_stat)(buf, sb)); 8511573Srgrimes return(stat(buf, sb)); 8521573Srgrimes} 8531573Srgrimes 8541573Srgrimesstatic Char * 8551573Srgrimesg_strchr(str, ch) 8561573Srgrimes Char *str; 8571573Srgrimes int ch; 8581573Srgrimes{ 8591573Srgrimes do { 8601573Srgrimes if (*str == ch) 8611573Srgrimes return (str); 8621573Srgrimes } while (*str++); 8631573Srgrimes return (NULL); 8641573Srgrimes} 8651573Srgrimes 86674918Speterstatic int 86774921Speterg_Ctoc(str, buf, len) 86874921Speter const Char *str; 86974921Speter char *buf; 87074921Speter u_int len; 8711573Srgrimes{ 8721573Srgrimes 87374921Speter while (len--) { 87474921Speter if ((*buf++ = *str++) == '\0') 87574921Speter return (0); 87674921Speter } 87774921Speter return (1); 8781573Srgrimes} 8791573Srgrimes 8801573Srgrimes#ifdef DEBUG 8818870Srgrimesstatic void 8821573Srgrimesqprintf(str, s) 8831573Srgrimes const char *str; 8841573Srgrimes register Char *s; 8851573Srgrimes{ 8861573Srgrimes register Char *p; 8871573Srgrimes 8881573Srgrimes (void)printf("%s:\n", str); 8891573Srgrimes for (p = s; *p; p++) 8901573Srgrimes (void)printf("%c", CHAR(*p)); 8911573Srgrimes (void)printf("\n"); 8921573Srgrimes for (p = s; *p; p++) 8931573Srgrimes (void)printf("%c", *p & M_PROTECT ? '"' : ' '); 8941573Srgrimes (void)printf("\n"); 8951573Srgrimes for (p = s; *p; p++) 8961573Srgrimes (void)printf("%c", ismeta(*p) ? '_' : ' '); 8971573Srgrimes (void)printf("\n"); 8981573Srgrimes} 8991573Srgrimes#endif 900