155682Smarkm/* 255682Smarkm * Copyright (c) 1989, 1993 355682Smarkm * The Regents of the University of California. All rights reserved. 455682Smarkm * 555682Smarkm * This code is derived from software contributed to Berkeley by 655682Smarkm * Guido van Rossum. 755682Smarkm * 855682Smarkm * Redistribution and use in source and binary forms, with or without 955682Smarkm * modification, are permitted provided that the following conditions 1055682Smarkm * are met: 1155682Smarkm * 1. Redistributions of source code must retain the above copyright 1255682Smarkm * notice, this list of conditions and the following disclaimer. 1355682Smarkm * 2. Redistributions in binary form must reproduce the above copyright 1455682Smarkm * notice, this list of conditions and the following disclaimer in the 1555682Smarkm * documentation and/or other materials provided with the distribution. 16178825Sdfr * 3. Neither the name of the University nor the names of its contributors 1755682Smarkm * may be used to endorse or promote products derived from this software 1855682Smarkm * without specific prior written permission. 1955682Smarkm * 2055682Smarkm * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 2155682Smarkm * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 2255682Smarkm * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 2355682Smarkm * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 2455682Smarkm * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 2555682Smarkm * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 2655682Smarkm * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 2755682Smarkm * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 2855682Smarkm * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 2955682Smarkm * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 3055682Smarkm * SUCH DAMAGE. 3155682Smarkm */ 3255682Smarkm 3355682Smarkm/* 3455682Smarkm * glob(3) -- a superset of the one defined in POSIX 1003.2. 3555682Smarkm * 3655682Smarkm * The [!...] convention to negate a range is supported (SysV, Posix, ksh). 3755682Smarkm * 3855682Smarkm * Optional extra services, controlled by flags not defined by POSIX: 3955682Smarkm * 4055682Smarkm * GLOB_QUOTE: 4155682Smarkm * Escaping convention: \ inhibits any special meaning the following 4255682Smarkm * character might have (except \ at end of string is retained). 4355682Smarkm * GLOB_MAGCHAR: 4455682Smarkm * Set in gl_flags if pattern contained a globbing character. 4555682Smarkm * GLOB_NOMAGIC: 4655682Smarkm * Same as GLOB_NOCHECK, but it will only append pattern if it did 4755682Smarkm * not contain any magic characters. [Used in csh style globbing] 4855682Smarkm * GLOB_ALTDIRFUNC: 4955682Smarkm * Use alternately specified directory access functions. 5055682Smarkm * GLOB_TILDE: 5155682Smarkm * expand ~user/foo to the /home/dir/of/user/foo 5255682Smarkm * GLOB_BRACE: 53233294Sstas * expand {1,2}{a,b} to 1a 1b 2a 2b 5455682Smarkm * gl_matchc: 5555682Smarkm * Number of matches in the current invocation of glob. 5655682Smarkm */ 5755682Smarkm 5855682Smarkm#include <config.h> 5955682Smarkm 6055682Smarkm#ifdef HAVE_SYS_PARAM_H 6155682Smarkm#include <sys/param.h> 6255682Smarkm#endif 6355682Smarkm#ifdef HAVE_SYS_TYPES_H 6455682Smarkm#include <sys/types.h> 6555682Smarkm#endif 6655682Smarkm#ifdef HAVE_SYS_STAT_H 6755682Smarkm#include <sys/stat.h> 6855682Smarkm#endif 6955682Smarkm 7055682Smarkm#include <ctype.h> 7155682Smarkm#ifdef HAVE_DIRENT_H 7255682Smarkm#include <dirent.h> 7355682Smarkm#endif 7455682Smarkm#include <errno.h> 7555682Smarkm#ifdef HAVE_PWD_H 7655682Smarkm#include <pwd.h> 7755682Smarkm#endif 7855682Smarkm#include <stdio.h> 7955682Smarkm#include <stdlib.h> 8055682Smarkm#include <string.h> 8155682Smarkm#ifdef HAVE_UNISTD_H 8255682Smarkm#include <unistd.h> 8355682Smarkm#endif 8478527Sassar#ifdef HAVE_LIMITS_H 8578527Sassar#include <limits.h> 8678527Sassar#endif 8755682Smarkm 8855682Smarkm#include "glob.h" 8955682Smarkm#include "roken.h" 9055682Smarkm 9190926Snectar#ifndef ARG_MAX 9290926Snectar#define ARG_MAX _POSIX_ARG_MAX 9390926Snectar#endif 9490926Snectar 9555682Smarkm#define CHAR_DOLLAR '$' 9655682Smarkm#define CHAR_DOT '.' 9755682Smarkm#define CHAR_EOS '\0' 9855682Smarkm#define CHAR_LBRACKET '[' 9955682Smarkm#define CHAR_NOT '!' 10055682Smarkm#define CHAR_QUESTION '?' 10155682Smarkm#define CHAR_QUOTE '\\' 10255682Smarkm#define CHAR_RANGE '-' 10355682Smarkm#define CHAR_RBRACKET ']' 10455682Smarkm#define CHAR_SEP '/' 10555682Smarkm#define CHAR_STAR '*' 10655682Smarkm#define CHAR_TILDE '~' 10755682Smarkm#define CHAR_UNDERSCORE '_' 10855682Smarkm#define CHAR_LBRACE '{' 10955682Smarkm#define CHAR_RBRACE '}' 11055682Smarkm#define CHAR_SLASH '/' 11155682Smarkm#define CHAR_COMMA ',' 11255682Smarkm 11355682Smarkm#ifndef DEBUG 11455682Smarkm 11555682Smarkm#define M_QUOTE 0x8000 11655682Smarkm#define M_PROTECT 0x4000 11755682Smarkm#define M_MASK 0xffff 11855682Smarkm#define M_ASCII 0x00ff 11955682Smarkm 12055682Smarkmtypedef u_short Char; 12155682Smarkm 12255682Smarkm#else 12355682Smarkm 12455682Smarkm#define M_QUOTE 0x80 12555682Smarkm#define M_PROTECT 0x40 12655682Smarkm#define M_MASK 0xff 12755682Smarkm#define M_ASCII 0x7f 12855682Smarkm 12955682Smarkmtypedef char Char; 13055682Smarkm 13155682Smarkm#endif 13255682Smarkm 13355682Smarkm 13455682Smarkm#define CHAR(c) ((Char)((c)&M_ASCII)) 13555682Smarkm#define META(c) ((Char)((c)|M_QUOTE)) 13655682Smarkm#define M_ALL META('*') 13755682Smarkm#define M_END META(']') 13855682Smarkm#define M_NOT META('!') 13955682Smarkm#define M_ONE META('?') 14055682Smarkm#define M_RNG META('-') 14155682Smarkm#define M_SET META('[') 14255682Smarkm#define ismeta(c) (((c)&M_QUOTE) != 0) 14355682Smarkm 14455682Smarkm 14555682Smarkmstatic int compare (const void *, const void *); 14655682Smarkmstatic void g_Ctoc (const Char *, char *); 14755682Smarkmstatic int g_lstat (Char *, struct stat *, glob_t *); 14855682Smarkmstatic DIR *g_opendir (Char *, glob_t *); 14978527Sassarstatic Char *g_strchr (const Char *, int); 15055682Smarkm#ifdef notdef 15155682Smarkmstatic Char *g_strcat (Char *, const Char *); 15255682Smarkm#endif 15355682Smarkmstatic int g_stat (Char *, struct stat *, glob_t *); 15455682Smarkmstatic int glob0 (const Char *, glob_t *); 15578527Sassarstatic int glob1 (Char *, glob_t *, size_t *); 15678527Sassarstatic int glob2 (Char *, Char *, Char *, glob_t *, size_t *); 15778527Sassarstatic int glob3 (Char *, Char *, Char *, Char *, glob_t *, size_t *); 15878527Sassarstatic int globextend (const Char *, glob_t *, size_t *); 15955682Smarkmstatic const Char * globtilde (const Char *, Char *, glob_t *); 16055682Smarkmstatic int globexp1 (const Char *, glob_t *); 16155682Smarkmstatic int globexp2 (const Char *, const Char *, glob_t *, int *); 16255682Smarkmstatic int match (Char *, Char *, Char *); 16355682Smarkm#ifdef DEBUG 16455682Smarkmstatic void qprintf (const char *, Char *); 16555682Smarkm#endif 16655682Smarkm 167233294SstasROKEN_LIB_FUNCTION int ROKEN_LIB_CALL 168233294Sstasglob(const char *pattern, 169233294Sstas int flags, 170233294Sstas int (*errfunc)(const char *, int), 17155682Smarkm glob_t *pglob) 17255682Smarkm{ 17355682Smarkm const u_char *patnext; 17455682Smarkm int c; 17555682Smarkm Char *bufnext, *bufend, patbuf[MaxPathLen+1]; 17655682Smarkm 17778527Sassar patnext = (const u_char *) pattern; 17855682Smarkm if (!(flags & GLOB_APPEND)) { 17955682Smarkm pglob->gl_pathc = 0; 18055682Smarkm pglob->gl_pathv = NULL; 18155682Smarkm if (!(flags & GLOB_DOOFFS)) 18255682Smarkm pglob->gl_offs = 0; 18355682Smarkm } 18455682Smarkm pglob->gl_flags = flags & ~GLOB_MAGCHAR; 18555682Smarkm pglob->gl_errfunc = errfunc; 18655682Smarkm pglob->gl_matchc = 0; 18755682Smarkm 18855682Smarkm bufnext = patbuf; 18955682Smarkm bufend = bufnext + MaxPathLen; 19055682Smarkm if (flags & GLOB_QUOTE) { 19155682Smarkm /* Protect the quoted characters. */ 192233294Sstas while (bufnext < bufend && (c = *patnext++) != CHAR_EOS) 19355682Smarkm if (c == CHAR_QUOTE) { 19455682Smarkm if ((c = *patnext++) == CHAR_EOS) { 19555682Smarkm c = CHAR_QUOTE; 19655682Smarkm --patnext; 19755682Smarkm } 19855682Smarkm *bufnext++ = c | M_PROTECT; 19955682Smarkm } 20055682Smarkm else 20155682Smarkm *bufnext++ = c; 20255682Smarkm } 203233294Sstas else 204233294Sstas while (bufnext < bufend && (c = *patnext++) != CHAR_EOS) 20555682Smarkm *bufnext++ = c; 20655682Smarkm *bufnext = CHAR_EOS; 20755682Smarkm 20855682Smarkm if (flags & GLOB_BRACE) 20955682Smarkm return globexp1(patbuf, pglob); 21055682Smarkm else 21155682Smarkm return glob0(patbuf, pglob); 21255682Smarkm} 21355682Smarkm 21455682Smarkm/* 21555682Smarkm * Expand recursively a glob {} pattern. When there is no more expansion 21655682Smarkm * invoke the standard globbing routine to glob the rest of the magic 21755682Smarkm * characters 21855682Smarkm */ 21955682Smarkmstatic int globexp1(const Char *pattern, glob_t *pglob) 22055682Smarkm{ 22155682Smarkm const Char* ptr = pattern; 22255682Smarkm int rv; 22355682Smarkm 22455682Smarkm /* Protect a single {}, for find(1), like csh */ 22555682Smarkm if (pattern[0] == CHAR_LBRACE && pattern[1] == CHAR_RBRACE && pattern[2] == CHAR_EOS) 22655682Smarkm return glob0(pattern, pglob); 22755682Smarkm 22878527Sassar while ((ptr = (const Char *) g_strchr(ptr, CHAR_LBRACE)) != NULL) 22955682Smarkm if (!globexp2(ptr, pattern, pglob, &rv)) 23055682Smarkm return rv; 23155682Smarkm 23255682Smarkm return glob0(pattern, pglob); 23355682Smarkm} 23455682Smarkm 23555682Smarkm 23655682Smarkm/* 23755682Smarkm * Recursive brace globbing helper. Tries to expand a single brace. 23855682Smarkm * If it succeeds then it invokes globexp1 with the new pattern. 23955682Smarkm * If it fails then it tries to glob the rest of the pattern and returns. 24055682Smarkm */ 241233294Sstasstatic int globexp2(const Char *ptr, const Char *pattern, 24255682Smarkm glob_t *pglob, int *rv) 24355682Smarkm{ 24455682Smarkm int i; 24555682Smarkm Char *lm, *ls; 24655682Smarkm const Char *pe, *pm, *pl; 24755682Smarkm Char patbuf[MaxPathLen + 1]; 24855682Smarkm 24955682Smarkm /* copy part up to the brace */ 25055682Smarkm for (lm = patbuf, pm = pattern; pm != ptr; *lm++ = *pm++) 25155682Smarkm continue; 25255682Smarkm ls = lm; 25355682Smarkm 25455682Smarkm /* Find the balanced brace */ 25555682Smarkm for (i = 0, pe = ++ptr; *pe; pe++) 25655682Smarkm if (*pe == CHAR_LBRACKET) { 25755682Smarkm /* Ignore everything between [] */ 25855682Smarkm for (pm = pe++; *pe != CHAR_RBRACKET && *pe != CHAR_EOS; pe++) 25955682Smarkm continue; 26055682Smarkm if (*pe == CHAR_EOS) { 261233294Sstas /* 26255682Smarkm * We could not find a matching CHAR_RBRACKET. 26355682Smarkm * Ignore and just look for CHAR_RBRACE 26455682Smarkm */ 26555682Smarkm pe = pm; 26655682Smarkm } 26755682Smarkm } 26855682Smarkm else if (*pe == CHAR_LBRACE) 26955682Smarkm i++; 27055682Smarkm else if (*pe == CHAR_RBRACE) { 27155682Smarkm if (i == 0) 27255682Smarkm break; 27355682Smarkm i--; 27455682Smarkm } 27555682Smarkm 27655682Smarkm /* Non matching braces; just glob the pattern */ 27755682Smarkm if (i != 0 || *pe == CHAR_EOS) { 27855682Smarkm *rv = glob0(patbuf, pglob); 27955682Smarkm return 0; 28055682Smarkm } 28155682Smarkm 28255682Smarkm for (i = 0, pl = pm = ptr; pm <= pe; pm++) 28355682Smarkm switch (*pm) { 28455682Smarkm case CHAR_LBRACKET: 28555682Smarkm /* Ignore everything between [] */ 28655682Smarkm for (pl = pm++; *pm != CHAR_RBRACKET && *pm != CHAR_EOS; pm++) 28755682Smarkm continue; 28855682Smarkm if (*pm == CHAR_EOS) { 289233294Sstas /* 29055682Smarkm * We could not find a matching CHAR_RBRACKET. 29155682Smarkm * Ignore and just look for CHAR_RBRACE 29255682Smarkm */ 29355682Smarkm pm = pl; 29455682Smarkm } 29555682Smarkm break; 29655682Smarkm 29755682Smarkm case CHAR_LBRACE: 29855682Smarkm i++; 29955682Smarkm break; 30055682Smarkm 30155682Smarkm case CHAR_RBRACE: 30255682Smarkm if (i) { 30355682Smarkm i--; 30455682Smarkm break; 30555682Smarkm } 30655682Smarkm /* FALLTHROUGH */ 30755682Smarkm case CHAR_COMMA: 30855682Smarkm if (i && *pm == CHAR_COMMA) 30955682Smarkm break; 31055682Smarkm else { 31155682Smarkm /* Append the current string */ 31255682Smarkm for (lm = ls; (pl < pm); *lm++ = *pl++) 31355682Smarkm continue; 314233294Sstas /* 31555682Smarkm * Append the rest of the pattern after the 31655682Smarkm * closing brace 31755682Smarkm */ 31855682Smarkm for (pl = pe + 1; (*lm++ = *pl++) != CHAR_EOS;) 31955682Smarkm continue; 32055682Smarkm 32155682Smarkm /* Expand the current pattern */ 32255682Smarkm#ifdef DEBUG 32355682Smarkm qprintf("globexp2:", patbuf); 32455682Smarkm#endif 32555682Smarkm *rv = globexp1(patbuf, pglob); 32655682Smarkm 32755682Smarkm /* move after the comma, to the next string */ 32855682Smarkm pl = pm + 1; 32955682Smarkm } 33055682Smarkm break; 33155682Smarkm 33255682Smarkm default: 33355682Smarkm break; 33455682Smarkm } 33555682Smarkm *rv = 0; 33655682Smarkm return 0; 33755682Smarkm} 33855682Smarkm 33955682Smarkm 34055682Smarkm 34155682Smarkm/* 34255682Smarkm * expand tilde from the passwd file. 34355682Smarkm */ 34455682Smarkmstatic const Char * 34555682Smarkmglobtilde(const Char *pattern, Char *patbuf, glob_t *pglob) 34655682Smarkm{ 34755682Smarkm struct passwd *pwd; 34855682Smarkm char *h; 34955682Smarkm const Char *p; 35055682Smarkm Char *b; 35155682Smarkm 35255682Smarkm if (*pattern != CHAR_TILDE || !(pglob->gl_flags & GLOB_TILDE)) 35355682Smarkm return pattern; 35455682Smarkm 35555682Smarkm /* Copy up to the end of the string or / */ 356233294Sstas for (p = pattern + 1, h = (char *) patbuf; *p && *p != CHAR_SLASH; 35755682Smarkm *h++ = *p++) 35855682Smarkm continue; 35955682Smarkm 36055682Smarkm *h = CHAR_EOS; 36155682Smarkm 36255682Smarkm if (((char *) patbuf)[0] == CHAR_EOS) { 363233294Sstas /* 364233294Sstas * handle a plain ~ or ~/ by expanding $HOME 36555682Smarkm * first and then trying the password file 36655682Smarkm */ 36755682Smarkm if ((h = getenv("HOME")) == NULL) { 36855682Smarkm if ((pwd = k_getpwuid(getuid())) == NULL) 36955682Smarkm return pattern; 37055682Smarkm else 37155682Smarkm h = pwd->pw_dir; 37255682Smarkm } 37355682Smarkm } 37455682Smarkm else { 37555682Smarkm /* 37655682Smarkm * Expand a ~user 37755682Smarkm */ 37855682Smarkm if ((pwd = k_getpwnam((char*) patbuf)) == NULL) 37955682Smarkm return pattern; 38055682Smarkm else 38155682Smarkm h = pwd->pw_dir; 38255682Smarkm } 38355682Smarkm 38455682Smarkm /* Copy the home directory */ 38555682Smarkm for (b = patbuf; *h; *b++ = *h++) 38655682Smarkm continue; 387233294Sstas 38855682Smarkm /* Append the rest of the pattern */ 38955682Smarkm while ((*b++ = *p++) != CHAR_EOS) 39055682Smarkm continue; 39155682Smarkm 39255682Smarkm return patbuf; 39355682Smarkm} 39455682Smarkm 395233294Sstas 39655682Smarkm/* 39755682Smarkm * The main glob() routine: compiles the pattern (optionally processing 39855682Smarkm * quotes), calls glob1() to do the real pattern matching, and finally 39955682Smarkm * sorts the list (unless unsorted operation is requested). Returns 0 40055682Smarkm * if things went well, nonzero if errors occurred. It is not an error 40155682Smarkm * to find no matches. 40255682Smarkm */ 40355682Smarkmstatic int 40455682Smarkmglob0(const Char *pattern, glob_t *pglob) 40555682Smarkm{ 40655682Smarkm const Char *qpatnext; 40755682Smarkm int c, err, oldpathc; 40855682Smarkm Char *bufnext, patbuf[MaxPathLen+1]; 40978527Sassar size_t limit = 0; 41055682Smarkm 41155682Smarkm qpatnext = globtilde(pattern, patbuf, pglob); 41255682Smarkm oldpathc = pglob->gl_pathc; 41355682Smarkm bufnext = patbuf; 41455682Smarkm 41555682Smarkm /* We don't need to check for buffer overflow any more. */ 41655682Smarkm while ((c = *qpatnext++) != CHAR_EOS) { 41755682Smarkm switch (c) { 41855682Smarkm case CHAR_LBRACKET: 41955682Smarkm c = *qpatnext; 42055682Smarkm if (c == CHAR_NOT) 42155682Smarkm ++qpatnext; 42255682Smarkm if (*qpatnext == CHAR_EOS || 42378527Sassar g_strchr(qpatnext+1, CHAR_RBRACKET) == NULL) { 42455682Smarkm *bufnext++ = CHAR_LBRACKET; 42555682Smarkm if (c == CHAR_NOT) 42655682Smarkm --qpatnext; 42755682Smarkm break; 42855682Smarkm } 42955682Smarkm *bufnext++ = M_SET; 43055682Smarkm if (c == CHAR_NOT) 43155682Smarkm *bufnext++ = M_NOT; 43255682Smarkm c = *qpatnext++; 43355682Smarkm do { 43455682Smarkm *bufnext++ = CHAR(c); 43555682Smarkm if (*qpatnext == CHAR_RANGE && 43655682Smarkm (c = qpatnext[1]) != CHAR_RBRACKET) { 43755682Smarkm *bufnext++ = M_RNG; 43855682Smarkm *bufnext++ = CHAR(c); 43955682Smarkm qpatnext += 2; 44055682Smarkm } 44155682Smarkm } while ((c = *qpatnext++) != CHAR_RBRACKET); 44255682Smarkm pglob->gl_flags |= GLOB_MAGCHAR; 44355682Smarkm *bufnext++ = M_END; 44455682Smarkm break; 44555682Smarkm case CHAR_QUESTION: 44655682Smarkm pglob->gl_flags |= GLOB_MAGCHAR; 44755682Smarkm *bufnext++ = M_ONE; 44855682Smarkm break; 44955682Smarkm case CHAR_STAR: 45055682Smarkm pglob->gl_flags |= GLOB_MAGCHAR; 451233294Sstas /* collapse adjacent stars to one, 45255682Smarkm * to avoid exponential behavior 45355682Smarkm */ 45455682Smarkm if (bufnext == patbuf || bufnext[-1] != M_ALL) 45555682Smarkm *bufnext++ = M_ALL; 45655682Smarkm break; 45755682Smarkm default: 45855682Smarkm *bufnext++ = CHAR(c); 45955682Smarkm break; 46055682Smarkm } 46155682Smarkm } 46255682Smarkm *bufnext = CHAR_EOS; 46355682Smarkm#ifdef DEBUG 46455682Smarkm qprintf("glob0:", patbuf); 46555682Smarkm#endif 46655682Smarkm 46778527Sassar if ((err = glob1(patbuf, pglob, &limit)) != 0) 46855682Smarkm return(err); 46955682Smarkm 47055682Smarkm /* 471233294Sstas * If there was no match we are going to append the pattern 47255682Smarkm * if GLOB_NOCHECK was specified or if GLOB_NOMAGIC was specified 47355682Smarkm * and the pattern did not contain any magic characters 47455682Smarkm * GLOB_NOMAGIC is there just for compatibility with csh. 47555682Smarkm */ 476233294Sstas if (pglob->gl_pathc == oldpathc && 477233294Sstas ((pglob->gl_flags & GLOB_NOCHECK) || 47855682Smarkm ((pglob->gl_flags & GLOB_NOMAGIC) && 47955682Smarkm !(pglob->gl_flags & GLOB_MAGCHAR)))) 48078527Sassar return(globextend(pattern, pglob, &limit)); 481233294Sstas else if (!(pglob->gl_flags & GLOB_NOSORT)) 48255682Smarkm qsort(pglob->gl_pathv + pglob->gl_offs + oldpathc, 48355682Smarkm pglob->gl_pathc - oldpathc, sizeof(char *), compare); 48455682Smarkm return(0); 48555682Smarkm} 48655682Smarkm 48755682Smarkmstatic int 48855682Smarkmcompare(const void *p, const void *q) 48955682Smarkm{ 49055682Smarkm return(strcmp(*(char **)p, *(char **)q)); 49155682Smarkm} 49255682Smarkm 49355682Smarkmstatic int 49478527Sassarglob1(Char *pattern, glob_t *pglob, size_t *limit) 49555682Smarkm{ 49655682Smarkm Char pathbuf[MaxPathLen+1]; 49755682Smarkm 49855682Smarkm /* A null pathname is invalid -- POSIX 1003.1 sect. 2.4. */ 49955682Smarkm if (*pattern == CHAR_EOS) 50055682Smarkm return(0); 50178527Sassar return(glob2(pathbuf, pathbuf, pattern, pglob, limit)); 50255682Smarkm} 50355682Smarkm 50455682Smarkm/* 50555682Smarkm * The functions glob2 and glob3 are mutually recursive; there is one level 50655682Smarkm * of recursion for each segment in the pattern that contains one or more 50755682Smarkm * meta characters. 50855682Smarkm */ 50955682Smarkm 51055682Smarkm#ifndef S_ISLNK 51155682Smarkm#if defined(S_IFLNK) && defined(S_IFMT) 51255682Smarkm#define S_ISLNK(mode) (((mode) & S_IFMT) == S_IFLNK) 51355682Smarkm#else 51455682Smarkm#define S_ISLNK(mode) 0 51555682Smarkm#endif 51655682Smarkm#endif 51755682Smarkm 51855682Smarkmstatic int 51978527Sassarglob2(Char *pathbuf, Char *pathend, Char *pattern, glob_t *pglob, 52078527Sassar size_t *limit) 52155682Smarkm{ 52255682Smarkm struct stat sb; 52355682Smarkm Char *p, *q; 52455682Smarkm int anymeta; 52555682Smarkm 52655682Smarkm /* 52755682Smarkm * Loop over pattern segments until end of pattern or until 52855682Smarkm * segment with meta character found. 52955682Smarkm */ 53055682Smarkm for (anymeta = 0;;) { 53155682Smarkm if (*pattern == CHAR_EOS) { /* End of pattern? */ 53255682Smarkm *pathend = CHAR_EOS; 53355682Smarkm if (g_lstat(pathbuf, &sb, pglob)) 53455682Smarkm return(0); 535233294Sstas 53655682Smarkm if (((pglob->gl_flags & GLOB_MARK) && 53755682Smarkm pathend[-1] != CHAR_SEP) && (S_ISDIR(sb.st_mode) 53855682Smarkm || (S_ISLNK(sb.st_mode) && 53955682Smarkm (g_stat(pathbuf, &sb, pglob) == 0) && 54055682Smarkm S_ISDIR(sb.st_mode)))) { 54155682Smarkm *pathend++ = CHAR_SEP; 54255682Smarkm *pathend = CHAR_EOS; 54355682Smarkm } 54455682Smarkm ++pglob->gl_matchc; 54578527Sassar return(globextend(pathbuf, pglob, limit)); 54655682Smarkm } 54755682Smarkm 54855682Smarkm /* Find end of next segment, copy tentatively to pathend. */ 54955682Smarkm q = pathend; 55055682Smarkm p = pattern; 55155682Smarkm while (*p != CHAR_EOS && *p != CHAR_SEP) { 55255682Smarkm if (ismeta(*p)) 55355682Smarkm anymeta = 1; 55455682Smarkm *q++ = *p++; 55555682Smarkm } 55655682Smarkm 55755682Smarkm if (!anymeta) { /* No expansion, do next segment. */ 55855682Smarkm pathend = q; 55955682Smarkm pattern = p; 56055682Smarkm while (*pattern == CHAR_SEP) 56155682Smarkm *pathend++ = *pattern++; 56255682Smarkm } else /* Need expansion, recurse. */ 56378527Sassar return(glob3(pathbuf, pathend, pattern, p, pglob, 56478527Sassar limit)); 56555682Smarkm } 56678527Sassar /* NOTREACHED */ 56755682Smarkm} 56855682Smarkm 56955682Smarkmstatic int 570233294Sstasglob3(Char *pathbuf, Char *pathend, Char *pattern, Char *restpattern, 57178527Sassar glob_t *pglob, size_t *limit) 57255682Smarkm{ 57355682Smarkm struct dirent *dp; 57455682Smarkm DIR *dirp; 57555682Smarkm int err; 57655682Smarkm char buf[MaxPathLen]; 57755682Smarkm 57855682Smarkm /* 57955682Smarkm * The readdirfunc declaration can't be prototyped, because it is 58055682Smarkm * assigned, below, to two functions which are prototyped in glob.h 58155682Smarkm * and dirent.h as taking pointers to differently typed opaque 58255682Smarkm * structures. 58355682Smarkm */ 58455682Smarkm struct dirent *(*readdirfunc)(void *); 58555682Smarkm 58655682Smarkm *pathend = CHAR_EOS; 58755682Smarkm errno = 0; 588233294Sstas 58955682Smarkm if ((dirp = g_opendir(pathbuf, pglob)) == NULL) { 59055682Smarkm /* TODO: don't call for ENOENT or ENOTDIR? */ 59155682Smarkm if (pglob->gl_errfunc) { 59255682Smarkm g_Ctoc(pathbuf, buf); 59355682Smarkm if (pglob->gl_errfunc(buf, errno) || 59455682Smarkm pglob->gl_flags & GLOB_ERR) 59555682Smarkm return (GLOB_ABEND); 59655682Smarkm } 59755682Smarkm return(0); 59855682Smarkm } 59955682Smarkm 60055682Smarkm err = 0; 60155682Smarkm 60255682Smarkm /* Search directory for matching names. */ 60355682Smarkm if (pglob->gl_flags & GLOB_ALTDIRFUNC) 60455682Smarkm readdirfunc = pglob->gl_readdir; 60555682Smarkm else 60655682Smarkm readdirfunc = (struct dirent *(*)(void *))readdir; 60755682Smarkm while ((dp = (*readdirfunc)(dirp))) { 60855682Smarkm u_char *sc; 60955682Smarkm Char *dc; 61055682Smarkm 61155682Smarkm /* Initial CHAR_DOT must be matched literally. */ 61255682Smarkm if (dp->d_name[0] == CHAR_DOT && *pattern != CHAR_DOT) 61355682Smarkm continue; 614233294Sstas for (sc = (u_char *) dp->d_name, dc = pathend; 61555682Smarkm (*dc++ = *sc++) != CHAR_EOS;) 61655682Smarkm continue; 61755682Smarkm if (!match(pathend, pattern, restpattern)) { 61855682Smarkm *pathend = CHAR_EOS; 61955682Smarkm continue; 62055682Smarkm } 62178527Sassar err = glob2(pathbuf, --dc, restpattern, pglob, limit); 62255682Smarkm if (err) 62355682Smarkm break; 62455682Smarkm } 62555682Smarkm 62655682Smarkm if (pglob->gl_flags & GLOB_ALTDIRFUNC) 62755682Smarkm (*pglob->gl_closedir)(dirp); 62855682Smarkm else 62955682Smarkm closedir(dirp); 63055682Smarkm return(err); 63155682Smarkm} 63255682Smarkm 63355682Smarkm 63455682Smarkm/* 63555682Smarkm * Extend the gl_pathv member of a glob_t structure to accomodate a new item, 63655682Smarkm * add the new item, and update gl_pathc. 63755682Smarkm * 63855682Smarkm * This assumes the BSD realloc, which only copies the block when its size 63955682Smarkm * crosses a power-of-two boundary; for v7 realloc, this would cause quadratic 64055682Smarkm * behavior. 64155682Smarkm * 64255682Smarkm * Return 0 if new item added, error code if memory couldn't be allocated. 64355682Smarkm * 64455682Smarkm * Invariant of the glob_t structure: 64555682Smarkm * Either gl_pathc is zero and gl_pathv is NULL; or gl_pathc > 0 and 64655682Smarkm * gl_pathv points to (gl_offs + gl_pathc + 1) items. 64755682Smarkm */ 64855682Smarkmstatic int 64978527Sassarglobextend(const Char *path, glob_t *pglob, size_t *limit) 65055682Smarkm{ 65155682Smarkm char **pathv; 65255682Smarkm int i; 65378527Sassar size_t newsize, len; 65455682Smarkm char *copy; 65555682Smarkm const Char *p; 65655682Smarkm 65755682Smarkm newsize = sizeof(*pathv) * (2 + pglob->gl_pathc + pglob->gl_offs); 658233294Sstas pathv = pglob->gl_pathv ? 65955682Smarkm realloc(pglob->gl_pathv, newsize) : 66055682Smarkm malloc(newsize); 66155682Smarkm if (pathv == NULL) 66255682Smarkm return(GLOB_NOSPACE); 66355682Smarkm 66455682Smarkm if (pglob->gl_pathv == NULL && pglob->gl_offs > 0) { 66555682Smarkm /* first time around -- clear initial gl_offs items */ 66655682Smarkm pathv += pglob->gl_offs; 66755682Smarkm for (i = pglob->gl_offs; --i >= 0; ) 66855682Smarkm *--pathv = NULL; 66955682Smarkm } 67055682Smarkm pglob->gl_pathv = pathv; 67155682Smarkm 67255682Smarkm for (p = path; *p++;) 67355682Smarkm continue; 67478527Sassar len = (size_t)(p - path); 67578527Sassar *limit += len; 67678527Sassar if ((copy = malloc(len)) != NULL) { 67755682Smarkm g_Ctoc(path, copy); 67855682Smarkm pathv[pglob->gl_offs + pglob->gl_pathc++] = copy; 67955682Smarkm } 68055682Smarkm pathv[pglob->gl_offs + pglob->gl_pathc] = NULL; 68178527Sassar 68278527Sassar if ((pglob->gl_flags & GLOB_LIMIT) && (newsize + *limit) >= ARG_MAX) { 68378527Sassar errno = 0; 68478527Sassar return(GLOB_NOSPACE); 68578527Sassar } 68678527Sassar 68755682Smarkm return(copy == NULL ? GLOB_NOSPACE : 0); 68855682Smarkm} 68955682Smarkm 69055682Smarkm 69155682Smarkm/* 69255682Smarkm * pattern matching function for filenames. Each occurrence of the * 69355682Smarkm * pattern causes a recursion level. 69455682Smarkm */ 69555682Smarkmstatic int 69655682Smarkmmatch(Char *name, Char *pat, Char *patend) 69755682Smarkm{ 69855682Smarkm int ok, negate_range; 69955682Smarkm Char c, k; 70055682Smarkm 70155682Smarkm while (pat < patend) { 70255682Smarkm c = *pat++; 70355682Smarkm switch (c & M_MASK) { 70455682Smarkm case M_ALL: 70555682Smarkm if (pat == patend) 70655682Smarkm return(1); 707233294Sstas do 70855682Smarkm if (match(name, pat, patend)) 70955682Smarkm return(1); 71055682Smarkm while (*name++ != CHAR_EOS); 71155682Smarkm return(0); 71255682Smarkm case M_ONE: 71355682Smarkm if (*name++ == CHAR_EOS) 71455682Smarkm return(0); 71555682Smarkm break; 71655682Smarkm case M_SET: 71755682Smarkm ok = 0; 71855682Smarkm if ((k = *name++) == CHAR_EOS) 71955682Smarkm return(0); 72055682Smarkm if ((negate_range = ((*pat & M_MASK) == M_NOT)) != CHAR_EOS) 72155682Smarkm ++pat; 72255682Smarkm while (((c = *pat++) & M_MASK) != M_END) 72355682Smarkm if ((*pat & M_MASK) == M_RNG) { 72455682Smarkm if (c <= k && k <= pat[1]) 72555682Smarkm ok = 1; 72655682Smarkm pat += 2; 72755682Smarkm } else if (c == k) 72855682Smarkm ok = 1; 72955682Smarkm if (ok == negate_range) 73055682Smarkm return(0); 73155682Smarkm break; 73255682Smarkm default: 73355682Smarkm if (*name++ != c) 73455682Smarkm return(0); 73555682Smarkm break; 73655682Smarkm } 73755682Smarkm } 73855682Smarkm return(*name == CHAR_EOS); 73955682Smarkm} 74055682Smarkm 74155682Smarkm/* Free allocated data belonging to a glob_t structure. */ 742233294SstasROKEN_LIB_FUNCTION void ROKEN_LIB_CALL 74355682Smarkmglobfree(glob_t *pglob) 74455682Smarkm{ 74555682Smarkm int i; 74655682Smarkm char **pp; 74755682Smarkm 74855682Smarkm if (pglob->gl_pathv != NULL) { 74955682Smarkm pp = pglob->gl_pathv + pglob->gl_offs; 75055682Smarkm for (i = pglob->gl_pathc; i--; ++pp) 75155682Smarkm if (*pp) 75255682Smarkm free(*pp); 75355682Smarkm free(pglob->gl_pathv); 75478527Sassar pglob->gl_pathv = NULL; 75555682Smarkm } 75655682Smarkm} 75755682Smarkm 75855682Smarkmstatic DIR * 75955682Smarkmg_opendir(Char *str, glob_t *pglob) 76055682Smarkm{ 76155682Smarkm char buf[MaxPathLen]; 76255682Smarkm 76355682Smarkm if (!*str) 76455682Smarkm strlcpy(buf, ".", sizeof(buf)); 76555682Smarkm else 76655682Smarkm g_Ctoc(str, buf); 76755682Smarkm 76855682Smarkm if (pglob->gl_flags & GLOB_ALTDIRFUNC) 76955682Smarkm return((*pglob->gl_opendir)(buf)); 77055682Smarkm 77155682Smarkm return(opendir(buf)); 77255682Smarkm} 77355682Smarkm 77455682Smarkmstatic int 77555682Smarkmg_lstat(Char *fn, struct stat *sb, glob_t *pglob) 77655682Smarkm{ 77755682Smarkm char buf[MaxPathLen]; 77855682Smarkm 77955682Smarkm g_Ctoc(fn, buf); 78055682Smarkm if (pglob->gl_flags & GLOB_ALTDIRFUNC) 78155682Smarkm return((*pglob->gl_lstat)(buf, sb)); 78255682Smarkm return(lstat(buf, sb)); 78355682Smarkm} 78455682Smarkm 78555682Smarkmstatic int 78655682Smarkmg_stat(Char *fn, struct stat *sb, glob_t *pglob) 78755682Smarkm{ 78855682Smarkm char buf[MaxPathLen]; 78955682Smarkm 79055682Smarkm g_Ctoc(fn, buf); 79155682Smarkm if (pglob->gl_flags & GLOB_ALTDIRFUNC) 79255682Smarkm return((*pglob->gl_stat)(buf, sb)); 79355682Smarkm return(stat(buf, sb)); 79455682Smarkm} 79555682Smarkm 79655682Smarkmstatic Char * 79778527Sassarg_strchr(const Char *str, int ch) 79855682Smarkm{ 79955682Smarkm do { 80055682Smarkm if (*str == ch) 80178527Sassar return (Char *)str; 80255682Smarkm } while (*str++); 80355682Smarkm return (NULL); 80455682Smarkm} 80555682Smarkm 80655682Smarkm#ifdef notdef 80755682Smarkmstatic Char * 80855682Smarkmg_strcat(Char *dst, const Char *src) 80955682Smarkm{ 81055682Smarkm Char *sdst = dst; 81155682Smarkm 81255682Smarkm while (*dst++) 81355682Smarkm continue; 81455682Smarkm --dst; 81555682Smarkm while((*dst++ = *src++) != CHAR_EOS) 81655682Smarkm continue; 81755682Smarkm 81855682Smarkm return (sdst); 81955682Smarkm} 82055682Smarkm#endif 82155682Smarkm 82255682Smarkmstatic void 82355682Smarkmg_Ctoc(const Char *str, char *buf) 82455682Smarkm{ 82555682Smarkm char *dc; 82655682Smarkm 82755682Smarkm for (dc = buf; (*dc++ = *str++) != CHAR_EOS;) 82855682Smarkm continue; 82955682Smarkm} 83055682Smarkm 83155682Smarkm#ifdef DEBUG 832233294Sstasstatic void 83355682Smarkmqprintf(const Char *str, Char *s) 83455682Smarkm{ 83555682Smarkm Char *p; 83655682Smarkm 83755682Smarkm printf("%s:\n", str); 83855682Smarkm for (p = s; *p; p++) 83955682Smarkm printf("%c", CHAR(*p)); 84055682Smarkm printf("\n"); 84155682Smarkm for (p = s; *p; p++) 84255682Smarkm printf("%c", *p & M_PROTECT ? '"' : ' '); 84355682Smarkm printf("\n"); 84455682Smarkm for (p = s; *p; p++) 84555682Smarkm printf("%c", ismeta(*p) ? '_' : ' '); 84655682Smarkm printf("\n"); 84755682Smarkm} 84855682Smarkm#endif 849