glob.c revision 304284
1109998Smarkm/* 2296465Sdelphij * Copyright (c) 1989, 1993 3296465Sdelphij * The Regents of the University of California. All rights reserved. 4296465Sdelphij * 5109998Smarkm * This code is derived from software contributed to Berkeley by 6109998Smarkm * Guido van Rossum. 7109998Smarkm * 8109998Smarkm * Copyright (c) 2011 The FreeBSD Foundation 9109998Smarkm * All rights reserved. 10109998Smarkm * Portions of this software were developed by David Chisnall 11109998Smarkm * under sponsorship from the FreeBSD Foundation. 12109998Smarkm * 13109998Smarkm * Redistribution and use in source and binary forms, with or without 14296465Sdelphij * modification, are permitted provided that the following conditions 15109998Smarkm * are met: 16109998Smarkm * 1. Redistributions of source code must retain the above copyright 17109998Smarkm * notice, this list of conditions and the following disclaimer. 18109998Smarkm * 2. Redistributions in binary form must reproduce the above copyright 19109998Smarkm * notice, this list of conditions and the following disclaimer in the 20109998Smarkm * documentation and/or other materials provided with the distribution. 21109998Smarkm * 4. Neither the name of the University nor the names of its contributors 22109998Smarkm * may be used to endorse or promote products derived from this software 23109998Smarkm * without specific prior written permission. 24109998Smarkm * 25109998Smarkm * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 26109998Smarkm * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 27109998Smarkm * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 28109998Smarkm * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 29109998Smarkm * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 30109998Smarkm * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 31109998Smarkm * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 32109998Smarkm * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 33109998Smarkm * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 34109998Smarkm * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 35109998Smarkm * SUCH DAMAGE. 36109998Smarkm */ 37109998Smarkm 38109998Smarkm#if defined(LIBC_SCCS) && !defined(lint) 39109998Smarkmstatic char sccsid[] = "@(#)glob.c 8.3 (Berkeley) 10/13/93"; 40109998Smarkm#endif /* LIBC_SCCS and not lint */ 41109998Smarkm#include <sys/cdefs.h> 42109998Smarkm__FBSDID("$FreeBSD: stable/11/lib/libc/gen/glob.c 304284 2016-08-17 09:34:56Z ache $"); 43109998Smarkm 44109998Smarkm/* 45109998Smarkm * glob(3) -- a superset of the one defined in POSIX 1003.2. 46109998Smarkm * 47109998Smarkm * The [!...] convention to negate a range is supported (SysV, Posix, ksh). 48109998Smarkm * 49109998Smarkm * Optional extra services, controlled by flags not defined by POSIX: 50109998Smarkm * 51109998Smarkm * GLOB_QUOTE: 52109998Smarkm * Escaping convention: \ inhibits any special meaning the following 53109998Smarkm * character might have (except \ at end of string is retained). 54109998Smarkm * GLOB_MAGCHAR: 55109998Smarkm * Set in gl_flags if pattern contained a globbing character. 56109998Smarkm * GLOB_NOMAGIC: 57109998Smarkm * Same as GLOB_NOCHECK, but it will only append pattern if it did 58109998Smarkm * not contain any magic characters. [Used in csh style globbing] 59109998Smarkm * GLOB_ALTDIRFUNC: 60109998Smarkm * Use alternately specified directory access functions. 61109998Smarkm * GLOB_TILDE: 62109998Smarkm * expand ~user/foo to the /home/dir/of/user/foo 63109998Smarkm * GLOB_BRACE: 64109998Smarkm * expand {1,2}{a,b} to 1a 1b 2a 2b 65109998Smarkm * gl_matchc: 66109998Smarkm * Number of matches in the current invocation of glob. 67109998Smarkm */ 68109998Smarkm 69109998Smarkm/* 70109998Smarkm * Some notes on multibyte character support: 71296465Sdelphij * 1. Patterns with illegal byte sequences match nothing - even if 72296465Sdelphij * GLOB_NOCHECK is specified. 73296465Sdelphij * 2. Illegal byte sequences in filenames are handled by treating them as 74109998Smarkm * single-byte characters with a values of such bytes of the sequence 75109998Smarkm * cast to wchar_t. 76296465Sdelphij * 3. State-dependent encodings are not currently supported. 77296465Sdelphij */ 78296465Sdelphij 79296465Sdelphij#include <sys/param.h> 80296465Sdelphij#include <sys/stat.h> 81296465Sdelphij 82296465Sdelphij#include <ctype.h> 83296465Sdelphij#include <dirent.h> 84296465Sdelphij#include <errno.h> 85296465Sdelphij#include <glob.h> 86296465Sdelphij#include <limits.h> 87296465Sdelphij#include <pwd.h> 88296465Sdelphij#include <stdint.h> 89109998Smarkm#include <stdio.h> 90296465Sdelphij#include <stdlib.h> 91296465Sdelphij#include <string.h> 92296465Sdelphij#include <unistd.h> 93296465Sdelphij#include <wchar.h> 94109998Smarkm 95109998Smarkm#include "collate.h" 96296465Sdelphij 97296465Sdelphij/* 98296465Sdelphij * glob(3) expansion limits. Stop the expansion if any of these limits 99296465Sdelphij * is reached. This caps the runtime in the face of DoS attacks. See 100296465Sdelphij * also CVE-2010-2632 101296465Sdelphij */ 102296465Sdelphij#define GLOB_LIMIT_BRACE 128 /* number of brace calls */ 103109998Smarkm#define GLOB_LIMIT_PATH 65536 /* number of path elements */ 104109998Smarkm#define GLOB_LIMIT_READDIR 16384 /* number of readdirs */ 105109998Smarkm#define GLOB_LIMIT_STAT 1024 /* number of stat system calls */ 106109998Smarkm#define GLOB_LIMIT_STRING ARG_MAX /* maximum total size for paths */ 107109998Smarkm 108109998Smarkmstruct glob_limit { 109109998Smarkm size_t l_brace_cnt; 110296465Sdelphij size_t l_path_lim; 111109998Smarkm size_t l_readdir_cnt; 112296465Sdelphij size_t l_stat_cnt; 113296465Sdelphij size_t l_string_cnt; 114109998Smarkm}; 115109998Smarkm 116296465Sdelphij#define DOT L'.' 117109998Smarkm#define EOS L'\0' 118296465Sdelphij#define LBRACKET L'[' 119109998Smarkm#define NOT L'!' 120109998Smarkm#define QUESTION L'?' 121109998Smarkm#define QUOTE L'\\' 122109998Smarkm#define RANGE L'-' 123296465Sdelphij#define RBRACKET L']' 124296465Sdelphij#define SEP L'/' 125296465Sdelphij#define STAR L'*' 126296465Sdelphij#define TILDE L'~' 127296465Sdelphij#define LBRACE L'{' 128109998Smarkm#define RBRACE L'}' 129296465Sdelphij#define COMMA L',' 130109998Smarkm 131296465Sdelphij#define M_QUOTE 0x8000000000ULL 132296465Sdelphij#define M_PROTECT 0x4000000000ULL 133109998Smarkm#define M_MASK 0xffffffffffULL 134296465Sdelphij#define M_CHAR 0x00ffffffffULL 135296465Sdelphij 136109998Smarkmtypedef uint_fast64_t Char; 137296465Sdelphij 138296465Sdelphij#define CHAR(c) ((Char)((c)&M_CHAR)) 139109998Smarkm#define META(c) ((Char)((c)|M_QUOTE)) 140296465Sdelphij#define UNPROT(c) ((c) & ~M_PROTECT) 141296465Sdelphij#define M_ALL META(L'*') 142296465Sdelphij#define M_END META(L']') 143296465Sdelphij#define M_NOT META(L'!') 144109998Smarkm#define M_ONE META(L'?') 145296465Sdelphij#define M_RNG META(L'-') 146109998Smarkm#define M_SET META(L'[') 147296465Sdelphij#define ismeta(c) (((c)&M_QUOTE) != 0) 148296465Sdelphij#ifdef DEBUG 149109998Smarkm#define isprot(c) (((c)&M_PROTECT) != 0) 150296465Sdelphij#endif 151296465Sdelphij 152296465Sdelphijstatic int compare(const void *, const void *); 153296465Sdelphijstatic int g_Ctoc(const Char *, char *, size_t); 154296465Sdelphijstatic int g_lstat(Char *, struct stat *, glob_t *); 155296465Sdelphijstatic DIR *g_opendir(Char *, glob_t *); 156296465Sdelphijstatic const Char *g_strchr(const Char *, wchar_t); 157109998Smarkm#ifdef notdef 158296465Sdelphijstatic Char *g_strcat(Char *, const Char *); 159109998Smarkm#endif 160296465Sdelphijstatic int g_stat(Char *, struct stat *, glob_t *); 161109998Smarkmstatic int glob0(const Char *, glob_t *, struct glob_limit *, 162109998Smarkm const char *); 163296465Sdelphijstatic int glob1(Char *, glob_t *, struct glob_limit *); 164296465Sdelphijstatic int glob2(Char *, Char *, Char *, Char *, glob_t *, 165296465Sdelphij struct glob_limit *); 166296465Sdelphijstatic int glob3(Char *, Char *, Char *, Char *, Char *, glob_t *, 167296465Sdelphij struct glob_limit *); 168296465Sdelphijstatic int globextend(const Char *, glob_t *, struct glob_limit *, 169296465Sdelphij const char *); 170296465Sdelphijstatic const Char * 171109998Smarkm globtilde(const Char *, Char *, size_t, glob_t *); 172296465Sdelphijstatic int globexp0(const Char *, glob_t *, struct glob_limit *, 173296465Sdelphij const char *); 174296465Sdelphijstatic int globexp1(const Char *, glob_t *, struct glob_limit *); 175296465Sdelphijstatic int globexp2(const Char *, const Char *, glob_t *, 176296465Sdelphij struct glob_limit *); 177296465Sdelphijstatic int globfinal(glob_t *, struct glob_limit *, size_t, 178109998Smarkm const char *); 179296465Sdelphijstatic int match(Char *, Char *, Char *); 180296465Sdelphijstatic int err_nomatch(glob_t *, struct glob_limit *, const char *); 181296465Sdelphijstatic int err_aborted(glob_t *, int, char *); 182296465Sdelphij#ifdef DEBUG 183296465Sdelphijstatic void qprintf(const char *, Char *); 184296465Sdelphij#endif 185296465Sdelphij 186296465Sdelphijint 187109998Smarkmglob(const char * __restrict pattern, int flags, 188296465Sdelphij int (*errfunc)(const char *, int), glob_t * __restrict pglob) 189109998Smarkm{ 190296465Sdelphij struct glob_limit limit = { 0, 0, 0, 0, 0 }; 191296465Sdelphij const char *patnext; 192296465Sdelphij Char *bufnext, *bufend, patbuf[MAXPATHLEN], prot; 193296465Sdelphij mbstate_t mbs; 194109998Smarkm wchar_t wc; 195296465Sdelphij size_t clen; 196296465Sdelphij int too_long; 197109998Smarkm 198109998Smarkm patnext = pattern; 199296465Sdelphij if (!(flags & GLOB_APPEND)) { 200296465Sdelphij pglob->gl_pathc = 0; 201296465Sdelphij pglob->gl_pathv = NULL; 202296465Sdelphij if (!(flags & GLOB_DOOFFS)) 203109998Smarkm pglob->gl_offs = 0; 204296465Sdelphij } 205109998Smarkm if (flags & GLOB_LIMIT) { 206296465Sdelphij limit.l_path_lim = pglob->gl_matchc; 207296465Sdelphij if (limit.l_path_lim == 0) 208296465Sdelphij limit.l_path_lim = GLOB_LIMIT_PATH; 209109998Smarkm } 210296465Sdelphij pglob->gl_flags = flags & ~GLOB_MAGCHAR; 211296465Sdelphij pglob->gl_errfunc = errfunc; 212296465Sdelphij pglob->gl_matchc = 0; 213296465Sdelphij 214296465Sdelphij bufnext = patbuf; 215296465Sdelphij bufend = bufnext + MAXPATHLEN - 1; 216296465Sdelphij too_long = 1; 217109998Smarkm if (flags & GLOB_NOESCAPE) { 218296465Sdelphij memset(&mbs, 0, sizeof(mbs)); 219109998Smarkm while (bufnext <= bufend) { 220296465Sdelphij clen = mbrtowc(&wc, patnext, MB_LEN_MAX, &mbs); 221296465Sdelphij if (clen == (size_t)-1 || clen == (size_t)-2) 222296465Sdelphij return (err_nomatch(pglob, &limit, pattern)); 223296465Sdelphij else if (clen == 0) { 224296465Sdelphij too_long = 0; 225296465Sdelphij break; 226296465Sdelphij } 227296465Sdelphij *bufnext++ = wc; 228296465Sdelphij patnext += clen; 229109998Smarkm } 230296465Sdelphij } else { 231296465Sdelphij /* Protect the quoted characters. */ 232109998Smarkm memset(&mbs, 0, sizeof(mbs)); 233109998Smarkm while (bufnext <= bufend) { 234109998Smarkm if (*patnext == '\\') { 235296465Sdelphij if (*++patnext == '\0') { 236296465Sdelphij *bufnext++ = QUOTE; 237296465Sdelphij continue; 238296465Sdelphij } 239296465Sdelphij prot = M_PROTECT; 240296465Sdelphij } else 241296465Sdelphij prot = 0; 242296465Sdelphij clen = mbrtowc(&wc, patnext, MB_LEN_MAX, &mbs); 243296465Sdelphij if (clen == (size_t)-1 || clen == (size_t)-2) 244296465Sdelphij return (err_nomatch(pglob, &limit, pattern)); 245296465Sdelphij else if (clen == 0) { 246296465Sdelphij too_long = 0; 247296465Sdelphij break; 248296465Sdelphij } 249296465Sdelphij *bufnext++ = wc | prot; 250296465Sdelphij patnext += clen; 251296465Sdelphij } 252296465Sdelphij } 253296465Sdelphij if (too_long) 254296465Sdelphij return (err_nomatch(pglob, &limit, pattern)); 255296465Sdelphij *bufnext = EOS; 256296465Sdelphij 257296465Sdelphij if (flags & GLOB_BRACE) 258296465Sdelphij return (globexp0(patbuf, pglob, &limit, pattern)); 259296465Sdelphij else 260296465Sdelphij return (glob0(patbuf, pglob, &limit, pattern)); 261296465Sdelphij} 262109998Smarkm 263296465Sdelphijstatic int 264296465Sdelphijglobexp0(const Char *pattern, glob_t *pglob, struct glob_limit *limit, 265109998Smarkm const char *origpat) { 266296465Sdelphij int rv; 267109998Smarkm size_t oldpathc; 268296465Sdelphij 269296465Sdelphij /* Protect a single {}, for find(1), like csh */ 270296465Sdelphij if (pattern[0] == LBRACE && pattern[1] == RBRACE && pattern[2] == EOS) { 271296465Sdelphij if ((pglob->gl_flags & GLOB_LIMIT) && 272296465Sdelphij limit->l_brace_cnt++ >= GLOB_LIMIT_BRACE) { 273296465Sdelphij errno = E2BIG; 274296465Sdelphij return (GLOB_NOSPACE); 275109998Smarkm } 276109998Smarkm return (glob0(pattern, pglob, limit, origpat)); 277109998Smarkm } 278296465Sdelphij 279296465Sdelphij oldpathc = pglob->gl_pathc; 280296465Sdelphij 281296465Sdelphij if ((rv = globexp1(pattern, pglob, limit)) != 0) 282296465Sdelphij return rv; 283296465Sdelphij 284296465Sdelphij return (globfinal(pglob, limit, oldpathc, origpat)); 285296465Sdelphij} 286296465Sdelphij 287296465Sdelphij/* 288109998Smarkm * Expand recursively a glob {} pattern. When there is no more expansion 289296465Sdelphij * invoke the standard globbing routine to glob the rest of the magic 290296465Sdelphij * characters 291296465Sdelphij */ 292296465Sdelphijstatic int 293296465Sdelphijglobexp1(const Char *pattern, glob_t *pglob, struct glob_limit *limit) 294109998Smarkm{ 295296465Sdelphij const Char* ptr; 296296465Sdelphij 297296465Sdelphij if ((ptr = g_strchr(pattern, LBRACE)) != NULL) { 298296465Sdelphij if ((pglob->gl_flags & GLOB_LIMIT) && 299109998Smarkm limit->l_brace_cnt++ >= GLOB_LIMIT_BRACE) { 300296465Sdelphij errno = E2BIG; 301296465Sdelphij return (GLOB_NOSPACE); 302109998Smarkm } 303296465Sdelphij return (globexp2(ptr, pattern, pglob, limit)); 304296465Sdelphij } 305296465Sdelphij 306296465Sdelphij return (glob0(pattern, pglob, limit, NULL)); 307109998Smarkm} 308109998Smarkm 309109998Smarkm 310296465Sdelphij/* 311296465Sdelphij * Recursive brace globbing helper. Tries to expand a single brace. 312296465Sdelphij * If it succeeds then it invokes globexp1 with the new pattern. 313296465Sdelphij * If it fails then it tries to glob the rest of the pattern and returns. 314296465Sdelphij */ 315109998Smarkmstatic int 316296465Sdelphijglobexp2(const Char *ptr, const Char *pattern, glob_t *pglob, 317296465Sdelphij struct glob_limit *limit) 318296465Sdelphij{ 319296465Sdelphij int i, rv; 320109998Smarkm Char *lm, *ls; 321296465Sdelphij const Char *pe, *pm, *pm1, *pl; 322296465Sdelphij Char patbuf[MAXPATHLEN]; 323296465Sdelphij 324296465Sdelphij /* copy part up to the brace */ 325296465Sdelphij for (lm = patbuf, pm = pattern; pm != ptr; *lm++ = *pm++) 326109998Smarkm continue; 327296465Sdelphij *lm = EOS; 328109998Smarkm ls = lm; 329296465Sdelphij 330109998Smarkm /* Find the balanced brace */ 331109998Smarkm for (i = 0, pe = ++ptr; *pe != EOS; pe++) 332109998Smarkm if (*pe == LBRACKET) { 333296465Sdelphij /* Ignore everything between [] */ 334296465Sdelphij for (pm = pe++; *pe != RBRACKET && *pe != EOS; pe++) 335296465Sdelphij continue; 336296465Sdelphij if (*pe == EOS) { 337296465Sdelphij /* 338109998Smarkm * We could not find a matching RBRACKET. 339296465Sdelphij * Ignore and just look for RBRACE 340296465Sdelphij */ 341296465Sdelphij pe = pm; 342296465Sdelphij } 343109998Smarkm } 344296465Sdelphij else if (*pe == LBRACE) 345296465Sdelphij i++; 346296465Sdelphij else if (*pe == RBRACE) { 347296465Sdelphij if (i == 0) 348109998Smarkm break; 349296465Sdelphij i--; 350296465Sdelphij } 351109998Smarkm 352296465Sdelphij /* Non matching braces; just glob the pattern */ 353296465Sdelphij if (i != 0 || *pe == EOS) 354296465Sdelphij return (glob0(pattern, pglob, limit, NULL)); 355296465Sdelphij 356296465Sdelphij for (i = 0, pl = pm = ptr; pm <= pe; pm++) 357296465Sdelphij switch (*pm) { 358296465Sdelphij case LBRACKET: 359296465Sdelphij /* Ignore everything between [] */ 360109998Smarkm for (pm1 = pm++; *pm != RBRACKET && *pm != EOS; pm++) 361296465Sdelphij continue; 362296465Sdelphij if (*pm == EOS) { 363296465Sdelphij /* 364296465Sdelphij * We could not find a matching RBRACKET. 365296465Sdelphij * Ignore and just look for RBRACE 366296465Sdelphij */ 367296465Sdelphij pm = pm1; 368109998Smarkm } 369296465Sdelphij break; 370296465Sdelphij 371296465Sdelphij case LBRACE: 372296465Sdelphij i++; 373109998Smarkm break; 374296465Sdelphij 375109998Smarkm case RBRACE: 376296465Sdelphij if (i) { 377109998Smarkm i--; 378296465Sdelphij break; 379109998Smarkm } 380296465Sdelphij /* FALLTHROUGH */ 381296465Sdelphij case COMMA: 382296465Sdelphij if (i && *pm == COMMA) 383109998Smarkm break; 384296465Sdelphij else { 385296465Sdelphij /* Append the current string */ 386296465Sdelphij for (lm = ls; (pl < pm); *lm++ = *pl++) 387296465Sdelphij continue; 388296465Sdelphij /* 389296465Sdelphij * Append the rest of the pattern after the 390296465Sdelphij * closing brace 391296465Sdelphij */ 392109998Smarkm for (pl = pe + 1; (*lm++ = *pl++) != EOS;) 393296465Sdelphij continue; 394109998Smarkm 395296465Sdelphij /* Expand the current pattern */ 396109998Smarkm#ifdef DEBUG 397296465Sdelphij qprintf("globexp2:", patbuf); 398296465Sdelphij#endif 399296465Sdelphij rv = globexp1(patbuf, pglob, limit); 400296465Sdelphij if (rv) 401109998Smarkm return (rv); 402109998Smarkm 403109998Smarkm /* move after the comma, to the next string */ 404296465Sdelphij pl = pm + 1; 405296465Sdelphij } 406296465Sdelphij break; 407296465Sdelphij 408296465Sdelphij default: 409296465Sdelphij break; 410296465Sdelphij } 411296465Sdelphij return (0); 412296465Sdelphij} 413296465Sdelphij 414296465Sdelphij 415296465Sdelphij 416296465Sdelphij/* 417296465Sdelphij * expand tilde from the passwd file. 418296465Sdelphij */ 419296465Sdelphijstatic const Char * 420296465Sdelphijglobtilde(const Char *pattern, Char *patbuf, size_t patbuf_len, glob_t *pglob) 421296465Sdelphij{ 422296465Sdelphij struct passwd *pwd; 423109998Smarkm char *h, *sc; 424109998Smarkm const Char *p; 425109998Smarkm Char *b, *eb; 426296465Sdelphij wchar_t wc; 427296465Sdelphij wchar_t wbuf[MAXPATHLEN]; 428296465Sdelphij wchar_t *wbufend, *dc; 429296465Sdelphij size_t clen; 430296465Sdelphij mbstate_t mbs; 431296465Sdelphij int too_long; 432109998Smarkm 433109998Smarkm if (*pattern != TILDE || !(pglob->gl_flags & GLOB_TILDE)) 434109998Smarkm return (pattern); 435109998Smarkm 436296465Sdelphij /* 437296465Sdelphij * Copy up to the end of the string or / 438296465Sdelphij */ 439296465Sdelphij eb = &patbuf[patbuf_len - 1]; 440296465Sdelphij for (p = pattern + 1, b = patbuf; 441296465Sdelphij b < eb && *p != EOS && UNPROT(*p) != SEP; *b++ = *p++) 442296465Sdelphij continue; 443296465Sdelphij 444296465Sdelphij if (*p != EOS && UNPROT(*p) != SEP) 445109998Smarkm return (NULL); 446109998Smarkm 447109998Smarkm *b = EOS; 448109998Smarkm h = NULL; 449296465Sdelphij 450296465Sdelphij if (patbuf[0] == EOS) { 451296465Sdelphij /* 452296465Sdelphij * handle a plain ~ or ~/ by expanding $HOME first (iff 453296465Sdelphij * we're not running setuid or setgid) and then trying 454296465Sdelphij * the password file 455296465Sdelphij */ 456296465Sdelphij if (issetugid() != 0 || 457109998Smarkm (h = getenv("HOME")) == NULL) { 458109998Smarkm if (((h = getlogin()) != NULL && 459109998Smarkm (pwd = getpwnam(h)) != NULL) || 460296465Sdelphij (pwd = getpwuid(getuid())) != NULL) 461296465Sdelphij h = pwd->pw_dir; 462296465Sdelphij else 463296465Sdelphij return (pattern); 464296465Sdelphij } 465296465Sdelphij } 466296465Sdelphij else { 467296465Sdelphij /* 468109998Smarkm * Expand a ~user 469109998Smarkm */ 470296465Sdelphij if (g_Ctoc(patbuf, (char *)wbuf, sizeof(wbuf))) 471296465Sdelphij return (NULL); 472296465Sdelphij if ((pwd = getpwnam((char *)wbuf)) == NULL) 473296465Sdelphij return (pattern); 474109998Smarkm else 475109998Smarkm h = pwd->pw_dir; 476109998Smarkm } 477109998Smarkm 478296465Sdelphij /* Copy the home directory */ 479296465Sdelphij dc = wbuf; 480296465Sdelphij sc = h; 481109998Smarkm wbufend = wbuf + MAXPATHLEN - 1; 482109998Smarkm too_long = 1; 483296465Sdelphij memset(&mbs, 0, sizeof(mbs)); 484296465Sdelphij while (dc <= wbufend) { 485296465Sdelphij clen = mbrtowc(&wc, sc, MB_LEN_MAX, &mbs); 486109998Smarkm if (clen == (size_t)-1 || clen == (size_t)-2) { 487109998Smarkm /* XXX See initial comment #2. */ 488296465Sdelphij wc = (unsigned char)*sc; 489296465Sdelphij clen = 1; 490296465Sdelphij memset(&mbs, 0, sizeof(mbs)); 491109998Smarkm } 492109998Smarkm if ((*dc++ = wc) == EOS) { 493296465Sdelphij too_long = 0; 494296465Sdelphij break; 495296465Sdelphij } 496109998Smarkm sc += clen; 497109998Smarkm } 498296465Sdelphij if (too_long) 499296465Sdelphij return (NULL); 500296465Sdelphij 501109998Smarkm dc = wbuf; 502109998Smarkm for (b = patbuf; b < eb && *dc != EOS; *b++ = *dc++ | M_PROTECT) 503296465Sdelphij continue; 504296465Sdelphij if (*dc != EOS) 505296465Sdelphij return (NULL); 506109998Smarkm 507109998Smarkm /* Append the rest of the pattern */ 508296465Sdelphij if (*p != EOS) { 509296465Sdelphij too_long = 1; 510296465Sdelphij while (b <= eb) { 511109998Smarkm if ((*b++ = *p++) == EOS) { 512109998Smarkm too_long = 0; 513296465Sdelphij break; 514296465Sdelphij } 515296465Sdelphij } 516109998Smarkm if (too_long) 517109998Smarkm return (NULL); 518296465Sdelphij } else 519296465Sdelphij *b = EOS; 520296465Sdelphij 521109998Smarkm return (patbuf); 522109998Smarkm} 523109998Smarkm 524109998Smarkm 525296465Sdelphij/* 526296465Sdelphij * The main glob() routine: compiles the pattern (optionally processing 527296465Sdelphij * quotes), calls glob1() to do the real pattern matching, and finally 528109998Smarkm * sorts the list (unless unsorted operation is requested). Returns 0 529296465Sdelphij * if things went well, nonzero if errors occurred. 530296465Sdelphij */ 531296465Sdelphijstatic int 532109998Smarkmglob0(const Char *pattern, glob_t *pglob, struct glob_limit *limit, 533296465Sdelphij const char *origpat) { 534109998Smarkm const Char *qpatnext; 535296465Sdelphij int err; 536109998Smarkm size_t oldpathc; 537296465Sdelphij Char *bufnext, c, patbuf[MAXPATHLEN]; 538109998Smarkm 539296465Sdelphij qpatnext = globtilde(pattern, patbuf, MAXPATHLEN, pglob); 540109998Smarkm if (qpatnext == NULL) { 541296465Sdelphij errno = E2BIG; 542296465Sdelphij return (GLOB_NOSPACE); 543296465Sdelphij } 544109998Smarkm oldpathc = pglob->gl_pathc; 545296465Sdelphij bufnext = patbuf; 546109998Smarkm 547296465Sdelphij /* We don't need to check for buffer overflow any more. */ 548109998Smarkm while ((c = *qpatnext++) != EOS) { 549296465Sdelphij switch (c) { 550296465Sdelphij case LBRACKET: 551109998Smarkm c = *qpatnext; 552296465Sdelphij if (c == NOT) 553296465Sdelphij ++qpatnext; 554296465Sdelphij if (*qpatnext == EOS || 555296465Sdelphij g_strchr(qpatnext+1, RBRACKET) == NULL) { 556296465Sdelphij *bufnext++ = LBRACKET; 557109998Smarkm if (c == NOT) 558109998Smarkm --qpatnext; 559127128Snectar break; 560296465Sdelphij } 561296465Sdelphij *bufnext++ = M_SET; 562296465Sdelphij if (c == NOT) 563296465Sdelphij *bufnext++ = M_NOT; 564296465Sdelphij c = *qpatnext++; 565296465Sdelphij do { 566109998Smarkm *bufnext++ = CHAR(c); 567296465Sdelphij if (*qpatnext == RANGE && 568296465Sdelphij (c = qpatnext[1]) != RBRACKET) { 569296465Sdelphij *bufnext++ = M_RNG; 570296465Sdelphij *bufnext++ = CHAR(c); 571296465Sdelphij qpatnext += 2; 572296465Sdelphij } 573296465Sdelphij } while ((c = *qpatnext++) != RBRACKET); 574296465Sdelphij pglob->gl_flags |= GLOB_MAGCHAR; 575296465Sdelphij *bufnext++ = M_END; 576296465Sdelphij break; 577296465Sdelphij case QUESTION: 578296465Sdelphij pglob->gl_flags |= GLOB_MAGCHAR; 579296465Sdelphij *bufnext++ = M_ONE; 580296465Sdelphij break; 581296465Sdelphij case STAR: 582296465Sdelphij pglob->gl_flags |= GLOB_MAGCHAR; 583296465Sdelphij /* collapse adjacent stars to one, 584296465Sdelphij * to avoid exponential behavior 585296465Sdelphij */ 586296465Sdelphij if (bufnext == patbuf || bufnext[-1] != M_ALL) 587296465Sdelphij *bufnext++ = M_ALL; 588296465Sdelphij break; 589296465Sdelphij default: 590296465Sdelphij *bufnext++ = CHAR(c); 591296465Sdelphij break; 592296465Sdelphij } 593 } 594 *bufnext = EOS; 595#ifdef DEBUG 596 qprintf("glob0:", patbuf); 597#endif 598 599 if ((err = glob1(patbuf, pglob, limit)) != 0) 600 return(err); 601 602 if (origpat != NULL) 603 return (globfinal(pglob, limit, oldpathc, origpat)); 604 605 return (0); 606} 607 608static int 609globfinal(glob_t *pglob, struct glob_limit *limit, size_t oldpathc, 610 const char *origpat) { 611 if (pglob->gl_pathc == oldpathc) 612 return (err_nomatch(pglob, limit, origpat)); 613 614 if (!(pglob->gl_flags & GLOB_NOSORT)) 615 qsort(pglob->gl_pathv + pglob->gl_offs + oldpathc, 616 pglob->gl_pathc - oldpathc, sizeof(char *), compare); 617 618 return (0); 619} 620 621static int 622compare(const void *p, const void *q) 623{ 624 return (strcoll(*(char **)p, *(char **)q)); 625} 626 627static int 628glob1(Char *pattern, glob_t *pglob, struct glob_limit *limit) 629{ 630 Char pathbuf[MAXPATHLEN]; 631 632 /* A null pathname is invalid -- POSIX 1003.1 sect. 2.4. */ 633 if (*pattern == EOS) 634 return (0); 635 return (glob2(pathbuf, pathbuf, pathbuf + MAXPATHLEN - 1, 636 pattern, pglob, limit)); 637} 638 639/* 640 * The functions glob2 and glob3 are mutually recursive; there is one level 641 * of recursion for each segment in the pattern that contains one or more 642 * meta characters. 643 */ 644static int 645glob2(Char *pathbuf, Char *pathend, Char *pathend_last, Char *pattern, 646 glob_t *pglob, struct glob_limit *limit) 647{ 648 struct stat sb; 649 Char *p, *q; 650 int anymeta; 651 652 /* 653 * Loop over pattern segments until end of pattern or until 654 * segment with meta character found. 655 */ 656 for (anymeta = 0;;) { 657 if (*pattern == EOS) { /* End of pattern? */ 658 *pathend = EOS; 659 if (g_lstat(pathbuf, &sb, pglob)) 660 return (0); 661 662 if ((pglob->gl_flags & GLOB_LIMIT) && 663 limit->l_stat_cnt++ >= GLOB_LIMIT_STAT) { 664 errno = E2BIG; 665 return (GLOB_NOSPACE); 666 } 667 if ((pglob->gl_flags & GLOB_MARK) && 668 UNPROT(pathend[-1]) != SEP && 669 (S_ISDIR(sb.st_mode) || 670 (S_ISLNK(sb.st_mode) && 671 g_stat(pathbuf, &sb, pglob) == 0 && 672 S_ISDIR(sb.st_mode)))) { 673 if (pathend + 1 > pathend_last) { 674 errno = E2BIG; 675 return (GLOB_NOSPACE); 676 } 677 *pathend++ = SEP; 678 *pathend = EOS; 679 } 680 ++pglob->gl_matchc; 681 return (globextend(pathbuf, pglob, limit, NULL)); 682 } 683 684 /* Find end of next segment, copy tentatively to pathend. */ 685 q = pathend; 686 p = pattern; 687 while (*p != EOS && UNPROT(*p) != SEP) { 688 if (ismeta(*p)) 689 anymeta = 1; 690 if (q + 1 > pathend_last) { 691 errno = E2BIG; 692 return (GLOB_NOSPACE); 693 } 694 *q++ = *p++; 695 } 696 697 if (!anymeta) { /* No expansion, do next segment. */ 698 pathend = q; 699 pattern = p; 700 while (UNPROT(*pattern) == SEP) { 701 if (pathend + 1 > pathend_last) { 702 errno = E2BIG; 703 return (GLOB_NOSPACE); 704 } 705 *pathend++ = *pattern++; 706 } 707 } else /* Need expansion, recurse. */ 708 return (glob3(pathbuf, pathend, pathend_last, pattern, 709 p, pglob, limit)); 710 } 711 /* NOTREACHED */ 712} 713 714static int 715glob3(Char *pathbuf, Char *pathend, Char *pathend_last, 716 Char *pattern, Char *restpattern, 717 glob_t *pglob, struct glob_limit *limit) 718{ 719 struct dirent *dp; 720 DIR *dirp; 721 int err, too_long, saverrno, saverrno2; 722 char buf[MAXPATHLEN + MB_LEN_MAX - 1]; 723 724 struct dirent *(*readdirfunc)(DIR *); 725 726 if (pathend > pathend_last) { 727 errno = E2BIG; 728 return (GLOB_NOSPACE); 729 } 730 *pathend = EOS; 731 if (pglob->gl_errfunc != NULL && 732 g_Ctoc(pathbuf, buf, sizeof(buf))) { 733 errno = E2BIG; 734 return (GLOB_NOSPACE); 735 } 736 737 saverrno = errno; 738 errno = 0; 739 if ((dirp = g_opendir(pathbuf, pglob)) == NULL) { 740 if (errno == ENOENT || errno == ENOTDIR) 741 return (0); 742 err = err_aborted(pglob, errno, buf); 743 if (errno == 0) 744 errno = saverrno; 745 return (err); 746 } 747 748 err = 0; 749 750 /* pglob->gl_readdir takes a void *, fix this manually */ 751 if (pglob->gl_flags & GLOB_ALTDIRFUNC) 752 readdirfunc = (struct dirent *(*)(DIR *))pglob->gl_readdir; 753 else 754 readdirfunc = readdir; 755 756 errno = 0; 757 /* Search directory for matching names. */ 758 while ((dp = (*readdirfunc)(dirp)) != NULL) { 759 char *sc; 760 Char *dc; 761 wchar_t wc; 762 size_t clen; 763 mbstate_t mbs; 764 765 if ((pglob->gl_flags & GLOB_LIMIT) && 766 limit->l_readdir_cnt++ >= GLOB_LIMIT_READDIR) { 767 errno = E2BIG; 768 err = GLOB_NOSPACE; 769 break; 770 } 771 772 /* Initial DOT must be matched literally. */ 773 if (dp->d_name[0] == '.' && UNPROT(*pattern) != DOT) { 774 errno = 0; 775 continue; 776 } 777 memset(&mbs, 0, sizeof(mbs)); 778 dc = pathend; 779 sc = dp->d_name; 780 too_long = 1; 781 while (dc <= pathend_last) { 782 clen = mbrtowc(&wc, sc, MB_LEN_MAX, &mbs); 783 if (clen == (size_t)-1 || clen == (size_t)-2) { 784 /* XXX See initial comment #2. */ 785 wc = (unsigned char)*sc; 786 clen = 1; 787 memset(&mbs, 0, sizeof(mbs)); 788 } 789 if ((*dc++ = wc) == EOS) { 790 too_long = 0; 791 break; 792 } 793 sc += clen; 794 } 795 if (too_long && (err = err_aborted(pglob, ENAMETOOLONG, 796 buf))) { 797 errno = ENAMETOOLONG; 798 break; 799 } 800 if (too_long || !match(pathend, pattern, restpattern)) { 801 *pathend = EOS; 802 errno = 0; 803 continue; 804 } 805 if (errno == 0) 806 errno = saverrno; 807 err = glob2(pathbuf, --dc, pathend_last, restpattern, 808 pglob, limit); 809 if (err) 810 break; 811 errno = 0; 812 } 813 814 saverrno2 = errno; 815 if (pglob->gl_flags & GLOB_ALTDIRFUNC) 816 (*pglob->gl_closedir)(dirp); 817 else 818 closedir(dirp); 819 errno = saverrno2; 820 821 if (err) 822 return (err); 823 824 if (dp == NULL && errno != 0 && 825 (err = err_aborted(pglob, errno, buf))) 826 return (err); 827 828 if (errno == 0) 829 errno = saverrno; 830 return (0); 831} 832 833 834/* 835 * Extend the gl_pathv member of a glob_t structure to accommodate a new item, 836 * add the new item, and update gl_pathc. 837 * 838 * This assumes the BSD realloc, which only copies the block when its size 839 * crosses a power-of-two boundary; for v7 realloc, this would cause quadratic 840 * behavior. 841 * 842 * Return 0 if new item added, error code if memory couldn't be allocated. 843 * 844 * Invariant of the glob_t structure: 845 * Either gl_pathc is zero and gl_pathv is NULL; or gl_pathc > 0 and 846 * gl_pathv points to (gl_offs + gl_pathc + 1) items. 847 */ 848static int 849globextend(const Char *path, glob_t *pglob, struct glob_limit *limit, 850 const char *origpat) 851{ 852 char **pathv; 853 size_t i, newsize, len; 854 char *copy; 855 const Char *p; 856 857 if ((pglob->gl_flags & GLOB_LIMIT) && 858 pglob->gl_matchc > limit->l_path_lim) { 859 errno = E2BIG; 860 return (GLOB_NOSPACE); 861 } 862 863 newsize = sizeof(*pathv) * (2 + pglob->gl_pathc + pglob->gl_offs); 864 /* realloc(NULL, newsize) is equivalent to malloc(newsize). */ 865 pathv = realloc((void *)pglob->gl_pathv, newsize); 866 if (pathv == NULL) 867 return (GLOB_NOSPACE); 868 869 if (pglob->gl_pathv == NULL && pglob->gl_offs > 0) { 870 /* first time around -- clear initial gl_offs items */ 871 pathv += pglob->gl_offs; 872 for (i = pglob->gl_offs + 1; --i > 0; ) 873 *--pathv = NULL; 874 } 875 pglob->gl_pathv = pathv; 876 877 if (origpat != NULL) 878 copy = strdup(origpat); 879 else { 880 for (p = path; *p++ != EOS;) 881 continue; 882 len = MB_CUR_MAX * (size_t)(p - path); /* XXX overallocation */ 883 if ((copy = malloc(len)) != NULL) { 884 if (g_Ctoc(path, copy, len)) { 885 free(copy); 886 errno = E2BIG; 887 return (GLOB_NOSPACE); 888 } 889 } 890 } 891 if (copy != NULL) { 892 limit->l_string_cnt += strlen(copy) + 1; 893 if ((pglob->gl_flags & GLOB_LIMIT) && 894 limit->l_string_cnt >= GLOB_LIMIT_STRING) { 895 free(copy); 896 errno = E2BIG; 897 return (GLOB_NOSPACE); 898 } 899 pathv[pglob->gl_offs + pglob->gl_pathc++] = copy; 900 } 901 pathv[pglob->gl_offs + pglob->gl_pathc] = NULL; 902 return (copy == NULL ? GLOB_NOSPACE : 0); 903} 904 905/* 906 * pattern matching function for filenames. Each occurrence of the * 907 * pattern causes a recursion level. 908 */ 909static int 910match(Char *name, Char *pat, Char *patend) 911{ 912 int ok, negate_range; 913 Char c, k; 914 struct xlocale_collate *table = 915 (struct xlocale_collate*)__get_locale()->components[XLC_COLLATE]; 916 917 while (pat < patend) { 918 c = *pat++; 919 switch (c & M_MASK) { 920 case M_ALL: 921 if (pat == patend) 922 return (1); 923 do 924 if (match(name, pat, patend)) 925 return (1); 926 while (*name++ != EOS); 927 return (0); 928 case M_ONE: 929 if (*name++ == EOS) 930 return (0); 931 break; 932 case M_SET: 933 ok = 0; 934 if ((k = *name++) == EOS) 935 return (0); 936 if ((negate_range = ((*pat & M_MASK) == M_NOT)) != 0) 937 ++pat; 938 while (((c = *pat++) & M_MASK) != M_END) 939 if ((*pat & M_MASK) == M_RNG) { 940 if (table->__collate_load_error ? 941 CHAR(c) <= CHAR(k) && 942 CHAR(k) <= CHAR(pat[1]) : 943 __wcollate_range_cmp(CHAR(c), 944 CHAR(k)) <= 0 && 945 __wcollate_range_cmp(CHAR(k), 946 CHAR(pat[1])) <= 0) 947 ok = 1; 948 pat += 2; 949 } else if (c == k) 950 ok = 1; 951 if (ok == negate_range) 952 return (0); 953 break; 954 default: 955 if (*name++ != c) 956 return (0); 957 break; 958 } 959 } 960 return (*name == EOS); 961} 962 963/* Free allocated data belonging to a glob_t structure. */ 964void 965globfree(glob_t *pglob) 966{ 967 size_t i; 968 char **pp; 969 970 if (pglob->gl_pathv != NULL) { 971 pp = pglob->gl_pathv + pglob->gl_offs; 972 for (i = pglob->gl_pathc; i--; ++pp) 973 if (*pp) 974 free(*pp); 975 free(pglob->gl_pathv); 976 pglob->gl_pathv = NULL; 977 } 978} 979 980static DIR * 981g_opendir(Char *str, glob_t *pglob) 982{ 983 char buf[MAXPATHLEN + MB_LEN_MAX - 1]; 984 985 if (*str == EOS) 986 strcpy(buf, "."); 987 else { 988 if (g_Ctoc(str, buf, sizeof(buf))) { 989 errno = ENAMETOOLONG; 990 return (NULL); 991 } 992 } 993 994 if (pglob->gl_flags & GLOB_ALTDIRFUNC) 995 return ((*pglob->gl_opendir)(buf)); 996 997 return (opendir(buf)); 998} 999 1000static int 1001g_lstat(Char *fn, struct stat *sb, glob_t *pglob) 1002{ 1003 char buf[MAXPATHLEN + MB_LEN_MAX - 1]; 1004 1005 if (g_Ctoc(fn, buf, sizeof(buf))) { 1006 errno = ENAMETOOLONG; 1007 return (-1); 1008 } 1009 if (pglob->gl_flags & GLOB_ALTDIRFUNC) 1010 return((*pglob->gl_lstat)(buf, sb)); 1011 return (lstat(buf, sb)); 1012} 1013 1014static int 1015g_stat(Char *fn, struct stat *sb, glob_t *pglob) 1016{ 1017 char buf[MAXPATHLEN + MB_LEN_MAX - 1]; 1018 1019 if (g_Ctoc(fn, buf, sizeof(buf))) { 1020 errno = ENAMETOOLONG; 1021 return (-1); 1022 } 1023 if (pglob->gl_flags & GLOB_ALTDIRFUNC) 1024 return ((*pglob->gl_stat)(buf, sb)); 1025 return (stat(buf, sb)); 1026} 1027 1028static const Char * 1029g_strchr(const Char *str, wchar_t ch) 1030{ 1031 1032 do { 1033 if (*str == ch) 1034 return (str); 1035 } while (*str++); 1036 return (NULL); 1037} 1038 1039static int 1040g_Ctoc(const Char *str, char *buf, size_t len) 1041{ 1042 mbstate_t mbs; 1043 size_t clen; 1044 1045 memset(&mbs, 0, sizeof(mbs)); 1046 while (len >= MB_CUR_MAX) { 1047 clen = wcrtomb(buf, CHAR(*str), &mbs); 1048 if (clen == (size_t)-1) { 1049 /* XXX See initial comment #2. */ 1050 *buf = (char)CHAR(*str); 1051 clen = 1; 1052 memset(&mbs, 0, sizeof(mbs)); 1053 } 1054 if (CHAR(*str) == EOS) 1055 return (0); 1056 str++; 1057 buf += clen; 1058 len -= clen; 1059 } 1060 return (1); 1061} 1062 1063static int 1064err_nomatch(glob_t *pglob, struct glob_limit *limit, const char *origpat) { 1065 /* 1066 * If there was no match we are going to append the origpat 1067 * if GLOB_NOCHECK was specified or if GLOB_NOMAGIC was specified 1068 * and the origpat did not contain any magic characters 1069 * GLOB_NOMAGIC is there just for compatibility with csh. 1070 */ 1071 if ((pglob->gl_flags & GLOB_NOCHECK) || 1072 ((pglob->gl_flags & GLOB_NOMAGIC) && 1073 !(pglob->gl_flags & GLOB_MAGCHAR))) 1074 return (globextend(NULL, pglob, limit, origpat)); 1075 return (GLOB_NOMATCH); 1076} 1077 1078static int 1079err_aborted(glob_t *pglob, int err, char *buf) { 1080 if ((pglob->gl_errfunc != NULL && pglob->gl_errfunc(buf, err)) || 1081 (pglob->gl_flags & GLOB_ERR)) 1082 return (GLOB_ABORTED); 1083 return (0); 1084} 1085 1086#ifdef DEBUG 1087static void 1088qprintf(const char *str, Char *s) 1089{ 1090 Char *p; 1091 1092 (void)printf("%s\n", str); 1093 if (s != NULL) { 1094 for (p = s; *p != EOS; p++) 1095 (void)printf("%c", (char)CHAR(*p)); 1096 (void)printf("\n"); 1097 for (p = s; *p != EOS; p++) 1098 (void)printf("%c", (isprot(*p) ? '\\' : ' ')); 1099 (void)printf("\n"); 1100 for (p = s; *p != EOS; p++) 1101 (void)printf("%c", (ismeta(*p) ? '_' : ' ')); 1102 (void)printf("\n"); 1103 } 1104} 1105#endif 1106