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: 5355682Smarkm * 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#ifdef HAVE_CONFIG_H 5955682Smarkm#include <config.h> 6055682Smarkm#endif 6155682Smarkm 6255682Smarkm#ifdef HAVE_SYS_PARAM_H 6355682Smarkm#include <sys/param.h> 6455682Smarkm#endif 6555682Smarkm#ifdef HAVE_SYS_TYPES_H 6655682Smarkm#include <sys/types.h> 6755682Smarkm#endif 6855682Smarkm#ifdef HAVE_SYS_STAT_H 6955682Smarkm#include <sys/stat.h> 7055682Smarkm#endif 7155682Smarkm 7255682Smarkm#include <ctype.h> 7355682Smarkm#ifdef HAVE_DIRENT_H 7455682Smarkm#include <dirent.h> 7555682Smarkm#endif 7655682Smarkm#include <errno.h> 7755682Smarkm#ifdef HAVE_PWD_H 7855682Smarkm#include <pwd.h> 7955682Smarkm#endif 8055682Smarkm#include <stdio.h> 8155682Smarkm#include <stdlib.h> 8255682Smarkm#include <string.h> 8355682Smarkm#ifdef HAVE_UNISTD_H 8455682Smarkm#include <unistd.h> 8555682Smarkm#endif 8678527Sassar#ifdef HAVE_LIMITS_H 8778527Sassar#include <limits.h> 8878527Sassar#endif 8955682Smarkm 9055682Smarkm#include "glob.h" 9155682Smarkm#include "roken.h" 9255682Smarkm 9390926Snectar#ifndef ARG_MAX 9490926Snectar#define ARG_MAX _POSIX_ARG_MAX 9590926Snectar#endif 9690926Snectar 9755682Smarkm#define CHAR_DOLLAR '$' 9855682Smarkm#define CHAR_DOT '.' 9955682Smarkm#define CHAR_EOS '\0' 10055682Smarkm#define CHAR_LBRACKET '[' 10155682Smarkm#define CHAR_NOT '!' 10255682Smarkm#define CHAR_QUESTION '?' 10355682Smarkm#define CHAR_QUOTE '\\' 10455682Smarkm#define CHAR_RANGE '-' 10555682Smarkm#define CHAR_RBRACKET ']' 10655682Smarkm#define CHAR_SEP '/' 10755682Smarkm#define CHAR_STAR '*' 10855682Smarkm#define CHAR_TILDE '~' 10955682Smarkm#define CHAR_UNDERSCORE '_' 11055682Smarkm#define CHAR_LBRACE '{' 11155682Smarkm#define CHAR_RBRACE '}' 11255682Smarkm#define CHAR_SLASH '/' 11355682Smarkm#define CHAR_COMMA ',' 11455682Smarkm 11555682Smarkm#ifndef DEBUG 11655682Smarkm 11755682Smarkm#define M_QUOTE 0x8000 11855682Smarkm#define M_PROTECT 0x4000 11955682Smarkm#define M_MASK 0xffff 12055682Smarkm#define M_ASCII 0x00ff 12155682Smarkm 12255682Smarkmtypedef u_short Char; 12355682Smarkm 12455682Smarkm#else 12555682Smarkm 12655682Smarkm#define M_QUOTE 0x80 12755682Smarkm#define M_PROTECT 0x40 12855682Smarkm#define M_MASK 0xff 12955682Smarkm#define M_ASCII 0x7f 13055682Smarkm 13155682Smarkmtypedef char Char; 13255682Smarkm 13355682Smarkm#endif 13455682Smarkm 13555682Smarkm 13655682Smarkm#define CHAR(c) ((Char)((c)&M_ASCII)) 13755682Smarkm#define META(c) ((Char)((c)|M_QUOTE)) 13855682Smarkm#define M_ALL META('*') 13955682Smarkm#define M_END META(']') 14055682Smarkm#define M_NOT META('!') 14155682Smarkm#define M_ONE META('?') 14255682Smarkm#define M_RNG META('-') 14355682Smarkm#define M_SET META('[') 14455682Smarkm#define ismeta(c) (((c)&M_QUOTE) != 0) 14555682Smarkm 14655682Smarkm 14755682Smarkmstatic int compare (const void *, const void *); 14855682Smarkmstatic void g_Ctoc (const Char *, char *); 14955682Smarkmstatic int g_lstat (Char *, struct stat *, glob_t *); 15055682Smarkmstatic DIR *g_opendir (Char *, glob_t *); 15178527Sassarstatic Char *g_strchr (const Char *, int); 15255682Smarkm#ifdef notdef 15355682Smarkmstatic Char *g_strcat (Char *, const Char *); 15455682Smarkm#endif 15555682Smarkmstatic int g_stat (Char *, struct stat *, glob_t *); 15655682Smarkmstatic int glob0 (const Char *, glob_t *); 15778527Sassarstatic int glob1 (Char *, glob_t *, size_t *); 15878527Sassarstatic int glob2 (Char *, Char *, Char *, glob_t *, size_t *); 15978527Sassarstatic int glob3 (Char *, Char *, Char *, Char *, glob_t *, size_t *); 16078527Sassarstatic int globextend (const Char *, glob_t *, size_t *); 16155682Smarkmstatic const Char * globtilde (const Char *, Char *, glob_t *); 16255682Smarkmstatic int globexp1 (const Char *, glob_t *); 16355682Smarkmstatic int globexp2 (const Char *, const Char *, glob_t *, int *); 16455682Smarkmstatic int match (Char *, Char *, Char *); 16555682Smarkm#ifdef DEBUG 16655682Smarkmstatic void qprintf (const char *, Char *); 16755682Smarkm#endif 16855682Smarkm 169178825Sdfrint ROKEN_LIB_FUNCTION 17055682Smarkmglob(const char *pattern, 17155682Smarkm int flags, 17255682Smarkm int (*errfunc)(const char *, int), 17355682Smarkm glob_t *pglob) 17455682Smarkm{ 17555682Smarkm const u_char *patnext; 17655682Smarkm int c; 17755682Smarkm Char *bufnext, *bufend, patbuf[MaxPathLen+1]; 17855682Smarkm 17978527Sassar patnext = (const u_char *) pattern; 18055682Smarkm if (!(flags & GLOB_APPEND)) { 18155682Smarkm pglob->gl_pathc = 0; 18255682Smarkm pglob->gl_pathv = NULL; 18355682Smarkm if (!(flags & GLOB_DOOFFS)) 18455682Smarkm pglob->gl_offs = 0; 18555682Smarkm } 18655682Smarkm pglob->gl_flags = flags & ~GLOB_MAGCHAR; 18755682Smarkm pglob->gl_errfunc = errfunc; 18855682Smarkm pglob->gl_matchc = 0; 18955682Smarkm 19055682Smarkm bufnext = patbuf; 19155682Smarkm bufend = bufnext + MaxPathLen; 19255682Smarkm if (flags & GLOB_QUOTE) { 19355682Smarkm /* Protect the quoted characters. */ 19455682Smarkm while (bufnext < bufend && (c = *patnext++) != CHAR_EOS) 19555682Smarkm if (c == CHAR_QUOTE) { 19655682Smarkm if ((c = *patnext++) == CHAR_EOS) { 19755682Smarkm c = CHAR_QUOTE; 19855682Smarkm --patnext; 19955682Smarkm } 20055682Smarkm *bufnext++ = c | M_PROTECT; 20155682Smarkm } 20255682Smarkm else 20355682Smarkm *bufnext++ = c; 20455682Smarkm } 20555682Smarkm else 20655682Smarkm while (bufnext < bufend && (c = *patnext++) != CHAR_EOS) 20755682Smarkm *bufnext++ = c; 20855682Smarkm *bufnext = CHAR_EOS; 20955682Smarkm 21055682Smarkm if (flags & GLOB_BRACE) 21155682Smarkm return globexp1(patbuf, pglob); 21255682Smarkm else 21355682Smarkm return glob0(patbuf, pglob); 21455682Smarkm} 21555682Smarkm 21655682Smarkm/* 21755682Smarkm * Expand recursively a glob {} pattern. When there is no more expansion 21855682Smarkm * invoke the standard globbing routine to glob the rest of the magic 21955682Smarkm * characters 22055682Smarkm */ 22155682Smarkmstatic int globexp1(const Char *pattern, glob_t *pglob) 22255682Smarkm{ 22355682Smarkm const Char* ptr = pattern; 22455682Smarkm int rv; 22555682Smarkm 22655682Smarkm /* Protect a single {}, for find(1), like csh */ 22755682Smarkm if (pattern[0] == CHAR_LBRACE && pattern[1] == CHAR_RBRACE && pattern[2] == CHAR_EOS) 22855682Smarkm return glob0(pattern, pglob); 22955682Smarkm 23078527Sassar while ((ptr = (const Char *) g_strchr(ptr, CHAR_LBRACE)) != NULL) 23155682Smarkm if (!globexp2(ptr, pattern, pglob, &rv)) 23255682Smarkm return rv; 23355682Smarkm 23455682Smarkm return glob0(pattern, pglob); 23555682Smarkm} 23655682Smarkm 23755682Smarkm 23855682Smarkm/* 23955682Smarkm * Recursive brace globbing helper. Tries to expand a single brace. 24055682Smarkm * If it succeeds then it invokes globexp1 with the new pattern. 24155682Smarkm * If it fails then it tries to glob the rest of the pattern and returns. 24255682Smarkm */ 24355682Smarkmstatic int globexp2(const Char *ptr, const Char *pattern, 24455682Smarkm glob_t *pglob, int *rv) 24555682Smarkm{ 24655682Smarkm int i; 24755682Smarkm Char *lm, *ls; 24855682Smarkm const Char *pe, *pm, *pl; 24955682Smarkm Char patbuf[MaxPathLen + 1]; 25055682Smarkm 25155682Smarkm /* copy part up to the brace */ 25255682Smarkm for (lm = patbuf, pm = pattern; pm != ptr; *lm++ = *pm++) 25355682Smarkm continue; 25455682Smarkm ls = lm; 25555682Smarkm 25655682Smarkm /* Find the balanced brace */ 25755682Smarkm for (i = 0, pe = ++ptr; *pe; pe++) 25855682Smarkm if (*pe == CHAR_LBRACKET) { 25955682Smarkm /* Ignore everything between [] */ 26055682Smarkm for (pm = pe++; *pe != CHAR_RBRACKET && *pe != CHAR_EOS; pe++) 26155682Smarkm continue; 26255682Smarkm if (*pe == CHAR_EOS) { 26355682Smarkm /* 26455682Smarkm * We could not find a matching CHAR_RBRACKET. 26555682Smarkm * Ignore and just look for CHAR_RBRACE 26655682Smarkm */ 26755682Smarkm pe = pm; 26855682Smarkm } 26955682Smarkm } 27055682Smarkm else if (*pe == CHAR_LBRACE) 27155682Smarkm i++; 27255682Smarkm else if (*pe == CHAR_RBRACE) { 27355682Smarkm if (i == 0) 27455682Smarkm break; 27555682Smarkm i--; 27655682Smarkm } 27755682Smarkm 27855682Smarkm /* Non matching braces; just glob the pattern */ 27955682Smarkm if (i != 0 || *pe == CHAR_EOS) { 28055682Smarkm *rv = glob0(patbuf, pglob); 28155682Smarkm return 0; 28255682Smarkm } 28355682Smarkm 28455682Smarkm for (i = 0, pl = pm = ptr; pm <= pe; pm++) 28555682Smarkm switch (*pm) { 28655682Smarkm case CHAR_LBRACKET: 28755682Smarkm /* Ignore everything between [] */ 28855682Smarkm for (pl = pm++; *pm != CHAR_RBRACKET && *pm != CHAR_EOS; pm++) 28955682Smarkm continue; 29055682Smarkm if (*pm == CHAR_EOS) { 29155682Smarkm /* 29255682Smarkm * We could not find a matching CHAR_RBRACKET. 29355682Smarkm * Ignore and just look for CHAR_RBRACE 29455682Smarkm */ 29555682Smarkm pm = pl; 29655682Smarkm } 29755682Smarkm break; 29855682Smarkm 29955682Smarkm case CHAR_LBRACE: 30055682Smarkm i++; 30155682Smarkm break; 30255682Smarkm 30355682Smarkm case CHAR_RBRACE: 30455682Smarkm if (i) { 30555682Smarkm i--; 30655682Smarkm break; 30755682Smarkm } 30855682Smarkm /* FALLTHROUGH */ 30955682Smarkm case CHAR_COMMA: 31055682Smarkm if (i && *pm == CHAR_COMMA) 31155682Smarkm break; 31255682Smarkm else { 31355682Smarkm /* Append the current string */ 31455682Smarkm for (lm = ls; (pl < pm); *lm++ = *pl++) 31555682Smarkm continue; 31655682Smarkm /* 31755682Smarkm * Append the rest of the pattern after the 31855682Smarkm * closing brace 31955682Smarkm */ 32055682Smarkm for (pl = pe + 1; (*lm++ = *pl++) != CHAR_EOS;) 32155682Smarkm continue; 32255682Smarkm 32355682Smarkm /* Expand the current pattern */ 32455682Smarkm#ifdef DEBUG 32555682Smarkm qprintf("globexp2:", patbuf); 32655682Smarkm#endif 32755682Smarkm *rv = globexp1(patbuf, pglob); 32855682Smarkm 32955682Smarkm /* move after the comma, to the next string */ 33055682Smarkm pl = pm + 1; 33155682Smarkm } 33255682Smarkm break; 33355682Smarkm 33455682Smarkm default: 33555682Smarkm break; 33655682Smarkm } 33755682Smarkm *rv = 0; 33855682Smarkm return 0; 33955682Smarkm} 34055682Smarkm 34155682Smarkm 34255682Smarkm 34355682Smarkm/* 34455682Smarkm * expand tilde from the passwd file. 34555682Smarkm */ 34655682Smarkmstatic const Char * 34755682Smarkmglobtilde(const Char *pattern, Char *patbuf, glob_t *pglob) 34855682Smarkm{ 34955682Smarkm struct passwd *pwd; 35055682Smarkm char *h; 35155682Smarkm const Char *p; 35255682Smarkm Char *b; 35355682Smarkm 35455682Smarkm if (*pattern != CHAR_TILDE || !(pglob->gl_flags & GLOB_TILDE)) 35555682Smarkm return pattern; 35655682Smarkm 35755682Smarkm /* Copy up to the end of the string or / */ 35855682Smarkm for (p = pattern + 1, h = (char *) patbuf; *p && *p != CHAR_SLASH; 35955682Smarkm *h++ = *p++) 36055682Smarkm continue; 36155682Smarkm 36255682Smarkm *h = CHAR_EOS; 36355682Smarkm 36455682Smarkm if (((char *) patbuf)[0] == CHAR_EOS) { 36555682Smarkm /* 36655682Smarkm * handle a plain ~ or ~/ by expanding $HOME 36755682Smarkm * first and then trying the password file 36855682Smarkm */ 36955682Smarkm if ((h = getenv("HOME")) == NULL) { 37055682Smarkm if ((pwd = k_getpwuid(getuid())) == NULL) 37155682Smarkm return pattern; 37255682Smarkm else 37355682Smarkm h = pwd->pw_dir; 37455682Smarkm } 37555682Smarkm } 37655682Smarkm else { 37755682Smarkm /* 37855682Smarkm * Expand a ~user 37955682Smarkm */ 38055682Smarkm if ((pwd = k_getpwnam((char*) patbuf)) == NULL) 38155682Smarkm return pattern; 38255682Smarkm else 38355682Smarkm h = pwd->pw_dir; 38455682Smarkm } 38555682Smarkm 38655682Smarkm /* Copy the home directory */ 38755682Smarkm for (b = patbuf; *h; *b++ = *h++) 38855682Smarkm continue; 38955682Smarkm 39055682Smarkm /* Append the rest of the pattern */ 39155682Smarkm while ((*b++ = *p++) != CHAR_EOS) 39255682Smarkm continue; 39355682Smarkm 39455682Smarkm return patbuf; 39555682Smarkm} 39655682Smarkm 39755682Smarkm 39855682Smarkm/* 39955682Smarkm * The main glob() routine: compiles the pattern (optionally processing 40055682Smarkm * quotes), calls glob1() to do the real pattern matching, and finally 40155682Smarkm * sorts the list (unless unsorted operation is requested). Returns 0 40255682Smarkm * if things went well, nonzero if errors occurred. It is not an error 40355682Smarkm * to find no matches. 40455682Smarkm */ 40555682Smarkmstatic int 40655682Smarkmglob0(const Char *pattern, glob_t *pglob) 40755682Smarkm{ 40855682Smarkm const Char *qpatnext; 40955682Smarkm int c, err, oldpathc; 41055682Smarkm Char *bufnext, patbuf[MaxPathLen+1]; 41178527Sassar size_t limit = 0; 41255682Smarkm 41355682Smarkm qpatnext = globtilde(pattern, patbuf, pglob); 41455682Smarkm oldpathc = pglob->gl_pathc; 41555682Smarkm bufnext = patbuf; 41655682Smarkm 41755682Smarkm /* We don't need to check for buffer overflow any more. */ 41855682Smarkm while ((c = *qpatnext++) != CHAR_EOS) { 41955682Smarkm switch (c) { 42055682Smarkm case CHAR_LBRACKET: 42155682Smarkm c = *qpatnext; 42255682Smarkm if (c == CHAR_NOT) 42355682Smarkm ++qpatnext; 42455682Smarkm if (*qpatnext == CHAR_EOS || 42578527Sassar g_strchr(qpatnext+1, CHAR_RBRACKET) == NULL) { 42655682Smarkm *bufnext++ = CHAR_LBRACKET; 42755682Smarkm if (c == CHAR_NOT) 42855682Smarkm --qpatnext; 42955682Smarkm break; 43055682Smarkm } 43155682Smarkm *bufnext++ = M_SET; 43255682Smarkm if (c == CHAR_NOT) 43355682Smarkm *bufnext++ = M_NOT; 43455682Smarkm c = *qpatnext++; 43555682Smarkm do { 43655682Smarkm *bufnext++ = CHAR(c); 43755682Smarkm if (*qpatnext == CHAR_RANGE && 43855682Smarkm (c = qpatnext[1]) != CHAR_RBRACKET) { 43955682Smarkm *bufnext++ = M_RNG; 44055682Smarkm *bufnext++ = CHAR(c); 44155682Smarkm qpatnext += 2; 44255682Smarkm } 44355682Smarkm } while ((c = *qpatnext++) != CHAR_RBRACKET); 44455682Smarkm pglob->gl_flags |= GLOB_MAGCHAR; 44555682Smarkm *bufnext++ = M_END; 44655682Smarkm break; 44755682Smarkm case CHAR_QUESTION: 44855682Smarkm pglob->gl_flags |= GLOB_MAGCHAR; 44955682Smarkm *bufnext++ = M_ONE; 45055682Smarkm break; 45155682Smarkm case CHAR_STAR: 45255682Smarkm pglob->gl_flags |= GLOB_MAGCHAR; 45355682Smarkm /* collapse adjacent stars to one, 45455682Smarkm * to avoid exponential behavior 45555682Smarkm */ 45655682Smarkm if (bufnext == patbuf || bufnext[-1] != M_ALL) 45755682Smarkm *bufnext++ = M_ALL; 45855682Smarkm break; 45955682Smarkm default: 46055682Smarkm *bufnext++ = CHAR(c); 46155682Smarkm break; 46255682Smarkm } 46355682Smarkm } 46455682Smarkm *bufnext = CHAR_EOS; 46555682Smarkm#ifdef DEBUG 46655682Smarkm qprintf("glob0:", patbuf); 46755682Smarkm#endif 46855682Smarkm 46978527Sassar if ((err = glob1(patbuf, pglob, &limit)) != 0) 47055682Smarkm return(err); 47155682Smarkm 47255682Smarkm /* 47355682Smarkm * If there was no match we are going to append the pattern 47455682Smarkm * if GLOB_NOCHECK was specified or if GLOB_NOMAGIC was specified 47555682Smarkm * and the pattern did not contain any magic characters 47655682Smarkm * GLOB_NOMAGIC is there just for compatibility with csh. 47755682Smarkm */ 47855682Smarkm if (pglob->gl_pathc == oldpathc && 47955682Smarkm ((pglob->gl_flags & GLOB_NOCHECK) || 48055682Smarkm ((pglob->gl_flags & GLOB_NOMAGIC) && 48155682Smarkm !(pglob->gl_flags & GLOB_MAGCHAR)))) 48278527Sassar return(globextend(pattern, pglob, &limit)); 48355682Smarkm else if (!(pglob->gl_flags & GLOB_NOSORT)) 48455682Smarkm qsort(pglob->gl_pathv + pglob->gl_offs + oldpathc, 48555682Smarkm pglob->gl_pathc - oldpathc, sizeof(char *), compare); 48655682Smarkm return(0); 48755682Smarkm} 48855682Smarkm 48955682Smarkmstatic int 49055682Smarkmcompare(const void *p, const void *q) 49155682Smarkm{ 49255682Smarkm return(strcmp(*(char **)p, *(char **)q)); 49355682Smarkm} 49455682Smarkm 49555682Smarkmstatic int 49678527Sassarglob1(Char *pattern, glob_t *pglob, size_t *limit) 49755682Smarkm{ 49855682Smarkm Char pathbuf[MaxPathLen+1]; 49955682Smarkm 50055682Smarkm /* A null pathname is invalid -- POSIX 1003.1 sect. 2.4. */ 50155682Smarkm if (*pattern == CHAR_EOS) 50255682Smarkm return(0); 50378527Sassar return(glob2(pathbuf, pathbuf, pattern, pglob, limit)); 50455682Smarkm} 50555682Smarkm 50655682Smarkm/* 50755682Smarkm * The functions glob2 and glob3 are mutually recursive; there is one level 50855682Smarkm * of recursion for each segment in the pattern that contains one or more 50955682Smarkm * meta characters. 51055682Smarkm */ 51155682Smarkm 51255682Smarkm#ifndef S_ISLNK 51355682Smarkm#if defined(S_IFLNK) && defined(S_IFMT) 51455682Smarkm#define S_ISLNK(mode) (((mode) & S_IFMT) == S_IFLNK) 51555682Smarkm#else 51655682Smarkm#define S_ISLNK(mode) 0 51755682Smarkm#endif 51855682Smarkm#endif 51955682Smarkm 52055682Smarkmstatic int 52178527Sassarglob2(Char *pathbuf, Char *pathend, Char *pattern, glob_t *pglob, 52278527Sassar size_t *limit) 52355682Smarkm{ 52455682Smarkm struct stat sb; 52555682Smarkm Char *p, *q; 52655682Smarkm int anymeta; 52755682Smarkm 52855682Smarkm /* 52955682Smarkm * Loop over pattern segments until end of pattern or until 53055682Smarkm * segment with meta character found. 53155682Smarkm */ 53255682Smarkm for (anymeta = 0;;) { 53355682Smarkm if (*pattern == CHAR_EOS) { /* End of pattern? */ 53455682Smarkm *pathend = CHAR_EOS; 53555682Smarkm if (g_lstat(pathbuf, &sb, pglob)) 53655682Smarkm return(0); 53755682Smarkm 53855682Smarkm if (((pglob->gl_flags & GLOB_MARK) && 53955682Smarkm pathend[-1] != CHAR_SEP) && (S_ISDIR(sb.st_mode) 54055682Smarkm || (S_ISLNK(sb.st_mode) && 54155682Smarkm (g_stat(pathbuf, &sb, pglob) == 0) && 54255682Smarkm S_ISDIR(sb.st_mode)))) { 54355682Smarkm *pathend++ = CHAR_SEP; 54455682Smarkm *pathend = CHAR_EOS; 54555682Smarkm } 54655682Smarkm ++pglob->gl_matchc; 54778527Sassar return(globextend(pathbuf, pglob, limit)); 54855682Smarkm } 54955682Smarkm 55055682Smarkm /* Find end of next segment, copy tentatively to pathend. */ 55155682Smarkm q = pathend; 55255682Smarkm p = pattern; 55355682Smarkm while (*p != CHAR_EOS && *p != CHAR_SEP) { 55455682Smarkm if (ismeta(*p)) 55555682Smarkm anymeta = 1; 55655682Smarkm *q++ = *p++; 55755682Smarkm } 55855682Smarkm 55955682Smarkm if (!anymeta) { /* No expansion, do next segment. */ 56055682Smarkm pathend = q; 56155682Smarkm pattern = p; 56255682Smarkm while (*pattern == CHAR_SEP) 56355682Smarkm *pathend++ = *pattern++; 56455682Smarkm } else /* Need expansion, recurse. */ 56578527Sassar return(glob3(pathbuf, pathend, pattern, p, pglob, 56678527Sassar limit)); 56755682Smarkm } 56878527Sassar /* NOTREACHED */ 56955682Smarkm} 57055682Smarkm 57155682Smarkmstatic int 57255682Smarkmglob3(Char *pathbuf, Char *pathend, Char *pattern, Char *restpattern, 57378527Sassar glob_t *pglob, size_t *limit) 57455682Smarkm{ 57555682Smarkm struct dirent *dp; 57655682Smarkm DIR *dirp; 57755682Smarkm int err; 57855682Smarkm char buf[MaxPathLen]; 57955682Smarkm 58055682Smarkm /* 58155682Smarkm * The readdirfunc declaration can't be prototyped, because it is 58255682Smarkm * assigned, below, to two functions which are prototyped in glob.h 58355682Smarkm * and dirent.h as taking pointers to differently typed opaque 58455682Smarkm * structures. 58555682Smarkm */ 58655682Smarkm struct dirent *(*readdirfunc)(void *); 58755682Smarkm 58855682Smarkm *pathend = CHAR_EOS; 58955682Smarkm errno = 0; 59055682Smarkm 59155682Smarkm if ((dirp = g_opendir(pathbuf, pglob)) == NULL) { 59255682Smarkm /* TODO: don't call for ENOENT or ENOTDIR? */ 59355682Smarkm if (pglob->gl_errfunc) { 59455682Smarkm g_Ctoc(pathbuf, buf); 59555682Smarkm if (pglob->gl_errfunc(buf, errno) || 59655682Smarkm pglob->gl_flags & GLOB_ERR) 59755682Smarkm return (GLOB_ABEND); 59855682Smarkm } 59955682Smarkm return(0); 60055682Smarkm } 60155682Smarkm 60255682Smarkm err = 0; 60355682Smarkm 60455682Smarkm /* Search directory for matching names. */ 60555682Smarkm if (pglob->gl_flags & GLOB_ALTDIRFUNC) 60655682Smarkm readdirfunc = pglob->gl_readdir; 60755682Smarkm else 60855682Smarkm readdirfunc = (struct dirent *(*)(void *))readdir; 60955682Smarkm while ((dp = (*readdirfunc)(dirp))) { 61055682Smarkm u_char *sc; 61155682Smarkm Char *dc; 61255682Smarkm 61355682Smarkm /* Initial CHAR_DOT must be matched literally. */ 61455682Smarkm if (dp->d_name[0] == CHAR_DOT && *pattern != CHAR_DOT) 61555682Smarkm continue; 61655682Smarkm for (sc = (u_char *) dp->d_name, dc = pathend; 61755682Smarkm (*dc++ = *sc++) != CHAR_EOS;) 61855682Smarkm continue; 61955682Smarkm if (!match(pathend, pattern, restpattern)) { 62055682Smarkm *pathend = CHAR_EOS; 62155682Smarkm continue; 62255682Smarkm } 62378527Sassar err = glob2(pathbuf, --dc, restpattern, pglob, limit); 62455682Smarkm if (err) 62555682Smarkm break; 62655682Smarkm } 62755682Smarkm 62855682Smarkm if (pglob->gl_flags & GLOB_ALTDIRFUNC) 62955682Smarkm (*pglob->gl_closedir)(dirp); 63055682Smarkm else 63155682Smarkm closedir(dirp); 63255682Smarkm return(err); 63355682Smarkm} 63455682Smarkm 63555682Smarkm 63655682Smarkm/* 63755682Smarkm * Extend the gl_pathv member of a glob_t structure to accomodate a new item, 63855682Smarkm * add the new item, and update gl_pathc. 63955682Smarkm * 64055682Smarkm * This assumes the BSD realloc, which only copies the block when its size 64155682Smarkm * crosses a power-of-two boundary; for v7 realloc, this would cause quadratic 64255682Smarkm * behavior. 64355682Smarkm * 64455682Smarkm * Return 0 if new item added, error code if memory couldn't be allocated. 64555682Smarkm * 64655682Smarkm * Invariant of the glob_t structure: 64755682Smarkm * Either gl_pathc is zero and gl_pathv is NULL; or gl_pathc > 0 and 64855682Smarkm * gl_pathv points to (gl_offs + gl_pathc + 1) items. 64955682Smarkm */ 65055682Smarkmstatic int 65178527Sassarglobextend(const Char *path, glob_t *pglob, size_t *limit) 65255682Smarkm{ 65355682Smarkm char **pathv; 65455682Smarkm int i; 65578527Sassar size_t newsize, len; 65655682Smarkm char *copy; 65755682Smarkm const Char *p; 65855682Smarkm 65955682Smarkm newsize = sizeof(*pathv) * (2 + pglob->gl_pathc + pglob->gl_offs); 66055682Smarkm pathv = pglob->gl_pathv ? 66155682Smarkm realloc(pglob->gl_pathv, newsize) : 66255682Smarkm malloc(newsize); 66355682Smarkm if (pathv == NULL) 66455682Smarkm return(GLOB_NOSPACE); 66555682Smarkm 66655682Smarkm if (pglob->gl_pathv == NULL && pglob->gl_offs > 0) { 66755682Smarkm /* first time around -- clear initial gl_offs items */ 66855682Smarkm pathv += pglob->gl_offs; 66955682Smarkm for (i = pglob->gl_offs; --i >= 0; ) 67055682Smarkm *--pathv = NULL; 67155682Smarkm } 67255682Smarkm pglob->gl_pathv = pathv; 67355682Smarkm 67455682Smarkm for (p = path; *p++;) 67555682Smarkm continue; 67678527Sassar len = (size_t)(p - path); 67778527Sassar *limit += len; 67878527Sassar if ((copy = malloc(len)) != NULL) { 67955682Smarkm g_Ctoc(path, copy); 68055682Smarkm pathv[pglob->gl_offs + pglob->gl_pathc++] = copy; 68155682Smarkm } 68255682Smarkm pathv[pglob->gl_offs + pglob->gl_pathc] = NULL; 68378527Sassar 68478527Sassar if ((pglob->gl_flags & GLOB_LIMIT) && (newsize + *limit) >= ARG_MAX) { 68578527Sassar errno = 0; 68678527Sassar return(GLOB_NOSPACE); 68778527Sassar } 68878527Sassar 68955682Smarkm return(copy == NULL ? GLOB_NOSPACE : 0); 69055682Smarkm} 69155682Smarkm 69255682Smarkm 69355682Smarkm/* 69455682Smarkm * pattern matching function for filenames. Each occurrence of the * 69555682Smarkm * pattern causes a recursion level. 69655682Smarkm */ 69755682Smarkmstatic int 69855682Smarkmmatch(Char *name, Char *pat, Char *patend) 69955682Smarkm{ 70055682Smarkm int ok, negate_range; 70155682Smarkm Char c, k; 70255682Smarkm 70355682Smarkm while (pat < patend) { 70455682Smarkm c = *pat++; 70555682Smarkm switch (c & M_MASK) { 70655682Smarkm case M_ALL: 70755682Smarkm if (pat == patend) 70855682Smarkm return(1); 70955682Smarkm do 71055682Smarkm if (match(name, pat, patend)) 71155682Smarkm return(1); 71255682Smarkm while (*name++ != CHAR_EOS); 71355682Smarkm return(0); 71455682Smarkm case M_ONE: 71555682Smarkm if (*name++ == CHAR_EOS) 71655682Smarkm return(0); 71755682Smarkm break; 71855682Smarkm case M_SET: 71955682Smarkm ok = 0; 72055682Smarkm if ((k = *name++) == CHAR_EOS) 72155682Smarkm return(0); 72255682Smarkm if ((negate_range = ((*pat & M_MASK) == M_NOT)) != CHAR_EOS) 72355682Smarkm ++pat; 72455682Smarkm while (((c = *pat++) & M_MASK) != M_END) 72555682Smarkm if ((*pat & M_MASK) == M_RNG) { 72655682Smarkm if (c <= k && k <= pat[1]) 72755682Smarkm ok = 1; 72855682Smarkm pat += 2; 72955682Smarkm } else if (c == k) 73055682Smarkm ok = 1; 73155682Smarkm if (ok == negate_range) 73255682Smarkm return(0); 73355682Smarkm break; 73455682Smarkm default: 73555682Smarkm if (*name++ != c) 73655682Smarkm return(0); 73755682Smarkm break; 73855682Smarkm } 73955682Smarkm } 74055682Smarkm return(*name == CHAR_EOS); 74155682Smarkm} 74255682Smarkm 74355682Smarkm/* Free allocated data belonging to a glob_t structure. */ 744178825Sdfrvoid ROKEN_LIB_FUNCTION 74555682Smarkmglobfree(glob_t *pglob) 74655682Smarkm{ 74755682Smarkm int i; 74855682Smarkm char **pp; 74955682Smarkm 75055682Smarkm if (pglob->gl_pathv != NULL) { 75155682Smarkm pp = pglob->gl_pathv + pglob->gl_offs; 75255682Smarkm for (i = pglob->gl_pathc; i--; ++pp) 75355682Smarkm if (*pp) 75455682Smarkm free(*pp); 75555682Smarkm free(pglob->gl_pathv); 75678527Sassar pglob->gl_pathv = NULL; 75755682Smarkm } 75855682Smarkm} 75955682Smarkm 76055682Smarkmstatic DIR * 76155682Smarkmg_opendir(Char *str, glob_t *pglob) 76255682Smarkm{ 76355682Smarkm char buf[MaxPathLen]; 76455682Smarkm 76555682Smarkm if (!*str) 76655682Smarkm strlcpy(buf, ".", sizeof(buf)); 76755682Smarkm else 76855682Smarkm g_Ctoc(str, buf); 76955682Smarkm 77055682Smarkm if (pglob->gl_flags & GLOB_ALTDIRFUNC) 77155682Smarkm return((*pglob->gl_opendir)(buf)); 77255682Smarkm 77355682Smarkm return(opendir(buf)); 77455682Smarkm} 77555682Smarkm 77655682Smarkmstatic int 77755682Smarkmg_lstat(Char *fn, struct stat *sb, glob_t *pglob) 77855682Smarkm{ 77955682Smarkm char buf[MaxPathLen]; 78055682Smarkm 78155682Smarkm g_Ctoc(fn, buf); 78255682Smarkm if (pglob->gl_flags & GLOB_ALTDIRFUNC) 78355682Smarkm return((*pglob->gl_lstat)(buf, sb)); 78455682Smarkm return(lstat(buf, sb)); 78555682Smarkm} 78655682Smarkm 78755682Smarkmstatic int 78855682Smarkmg_stat(Char *fn, struct stat *sb, glob_t *pglob) 78955682Smarkm{ 79055682Smarkm char buf[MaxPathLen]; 79155682Smarkm 79255682Smarkm g_Ctoc(fn, buf); 79355682Smarkm if (pglob->gl_flags & GLOB_ALTDIRFUNC) 79455682Smarkm return((*pglob->gl_stat)(buf, sb)); 79555682Smarkm return(stat(buf, sb)); 79655682Smarkm} 79755682Smarkm 79855682Smarkmstatic Char * 79978527Sassarg_strchr(const Char *str, int ch) 80055682Smarkm{ 80155682Smarkm do { 80255682Smarkm if (*str == ch) 80378527Sassar return (Char *)str; 80455682Smarkm } while (*str++); 80555682Smarkm return (NULL); 80655682Smarkm} 80755682Smarkm 80855682Smarkm#ifdef notdef 80955682Smarkmstatic Char * 81055682Smarkmg_strcat(Char *dst, const Char *src) 81155682Smarkm{ 81255682Smarkm Char *sdst = dst; 81355682Smarkm 81455682Smarkm while (*dst++) 81555682Smarkm continue; 81655682Smarkm --dst; 81755682Smarkm while((*dst++ = *src++) != CHAR_EOS) 81855682Smarkm continue; 81955682Smarkm 82055682Smarkm return (sdst); 82155682Smarkm} 82255682Smarkm#endif 82355682Smarkm 82455682Smarkmstatic void 82555682Smarkmg_Ctoc(const Char *str, char *buf) 82655682Smarkm{ 82755682Smarkm char *dc; 82855682Smarkm 82955682Smarkm for (dc = buf; (*dc++ = *str++) != CHAR_EOS;) 83055682Smarkm continue; 83155682Smarkm} 83255682Smarkm 83355682Smarkm#ifdef DEBUG 83455682Smarkmstatic void 83555682Smarkmqprintf(const Char *str, Char *s) 83655682Smarkm{ 83755682Smarkm Char *p; 83855682Smarkm 83955682Smarkm printf("%s:\n", str); 84055682Smarkm for (p = s; *p; p++) 84155682Smarkm printf("%c", CHAR(*p)); 84255682Smarkm printf("\n"); 84355682Smarkm for (p = s; *p; p++) 84455682Smarkm printf("%c", *p & M_PROTECT ? '"' : ' '); 84555682Smarkm printf("\n"); 84655682Smarkm for (p = s; *p; p++) 84755682Smarkm printf("%c", ismeta(*p) ? '_' : ' '); 84855682Smarkm printf("\n"); 84955682Smarkm} 85055682Smarkm#endif 851