glob.c revision 90045
1167465Smp/* 259243Sobrien * Copyright (c) 1989, 1993 359243Sobrien * The Regents of the University of California. All rights reserved. 459243Sobrien * 559243Sobrien * This code is derived from software contributed to Berkeley by 659243Sobrien * Guido van Rossum. 759243Sobrien * 859243Sobrien * Redistribution and use in source and binary forms, with or without 959243Sobrien * modification, are permitted provided that the following conditions 1059243Sobrien * are met: 1159243Sobrien * 1. Redistributions of source code must retain the above copyright 1259243Sobrien * notice, this list of conditions and the following disclaimer. 1359243Sobrien * 2. Redistributions in binary form must reproduce the above copyright 1459243Sobrien * notice, this list of conditions and the following disclaimer in the 1559243Sobrien * documentation and/or other materials provided with the distribution. 1659243Sobrien * 3. All advertising materials mentioning features or use of this software 17100616Smp * must display the following acknowledgement: 1859243Sobrien * This product includes software developed by the University of 1959243Sobrien * California, Berkeley and its contributors. 2059243Sobrien * 4. Neither the name of the University nor the names of its contributors 2159243Sobrien * may be used to endorse or promote products derived from this software 2259243Sobrien * without specific prior written permission. 2359243Sobrien * 2459243Sobrien * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 2559243Sobrien * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 2659243Sobrien * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 2759243Sobrien * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 2859243Sobrien * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 2959243Sobrien * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 3059243Sobrien * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 3159243Sobrien * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 3259243Sobrien * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 3359243Sobrien * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 3459243Sobrien * SUCH DAMAGE. 35167465Smp */ 3659243Sobrien 3759243Sobrien#if defined(LIBC_SCCS) && !defined(lint) 3859243Sobrienstatic char sccsid[] = "@(#)glob.c 8.3 (Berkeley) 10/13/93"; 3959243Sobrien#endif /* LIBC_SCCS and not lint */ 4059243Sobrien#include <sys/cdefs.h> 4159243Sobrien__FBSDID("$FreeBSD: head/lib/libc/gen/glob.c 90045 2002-02-01 01:32:19Z obrien $"); 4259243Sobrien 4359243Sobrien/* 4459243Sobrien * glob(3) -- a superset of the one defined in POSIX 1003.2. 45145479Smp * 4659243Sobrien * The [!...] convention to negate a range is supported (SysV, Posix, ksh). 4759243Sobrien * 4859243Sobrien * Optional extra services, controlled by flags not defined by POSIX: 4959243Sobrien * 5059243Sobrien * GLOB_QUOTE: 5159243Sobrien * Escaping convention: \ inhibits any special meaning the following 52145479Smp * character might have (except \ at end of string is retained). 53145479Smp * GLOB_MAGCHAR: 54145479Smp * Set in gl_flags if pattern contained a globbing character. 55145479Smp * GLOB_NOMAGIC: 56145479Smp * Same as GLOB_NOCHECK, but it will only append pattern if it did 57145479Smp * not contain any magic characters. [Used in csh style globbing] 58145479Smp * GLOB_ALTDIRFUNC: 59145479Smp * Use alternately specified directory access functions. 60145479Smp * GLOB_TILDE: 61145479Smp * expand ~user/foo to the /home/dir/of/user/foo 62145479Smp * GLOB_BRACE: 63145479Smp * expand {1,2}{a,b} to 1a 1b 2a 2b 64145479Smp * gl_matchc: 65145479Smp * Number of matches in the current invocation of glob. 66145479Smp */ 67145479Smp 68145479Smp#include <sys/param.h> 69145479Smp#include <sys/stat.h> 70145479Smp 71145479Smp#include <ctype.h> 72145479Smp#include <dirent.h> 73145479Smp#include <errno.h> 7469408Sache#include <glob.h> 75145479Smp#include <pwd.h> 76145479Smp#include <stdio.h> 77145479Smp#include <stdlib.h> 78145479Smp#include <string.h> 79145479Smp#include <unistd.h> 80145479Smp 8159243Sobrien#include "collate.h" 8269408Sache 83145479Smp#define DOLLAR '$' 8459243Sobrien#define DOT '.' 8559243Sobrien#define EOS '\0' 8659243Sobrien#define LBRACKET '[' 8759243Sobrien#define NOT '!' 88145479Smp#define QUESTION '?' 8959243Sobrien#define QUOTE '\\' 9059243Sobrien#define RANGE '-' 9159243Sobrien#define RBRACKET ']' 9259243Sobrien#define SEP '/' 9359243Sobrien#define STAR '*' 94145479Smp#define TILDE '~' 9559243Sobrien#define UNDERSCORE '_' 9659243Sobrien#define LBRACE '{' 9759243Sobrien#define RBRACE '}' 9859243Sobrien#define SLASH '/' 9959243Sobrien#define COMMA ',' 10059243Sobrien 101145479Smp#ifndef DEBUG 10259243Sobrien 10359243Sobrien#define M_QUOTE 0x8000 10459243Sobrien#define M_PROTECT 0x4000 10559243Sobrien#define M_MASK 0xffff 10659243Sobrien#define M_ASCII 0x00ff 107145479Smp 10859243Sobrientypedef u_short Char; 10959243Sobrien 110145479Smp#else 11159243Sobrien 112145479Smp#define M_QUOTE 0x80 113145479Smp#define M_PROTECT 0x40 114145479Smp#define M_MASK 0xff 11559243Sobrien#define M_ASCII 0x7f 116145479Smp 11759243Sobrientypedef char Char; 118145479Smp 11959243Sobrien#endif 12059243Sobrien 12159243Sobrien 12259243Sobrien#define CHAR(c) ((Char)((c)&M_ASCII)) 12359243Sobrien#define META(c) ((Char)((c)|M_QUOTE)) 12459243Sobrien#define M_ALL META('*') 12559243Sobrien#define M_END META(']') 12659243Sobrien#define M_NOT META('!') 127145479Smp#define M_ONE META('?') 12859243Sobrien#define M_RNG META('-') 129145479Smp#define M_SET META('[') 13059243Sobrien#define ismeta(c) (((c)&M_QUOTE) != 0) 13159243Sobrien 13259243Sobrien 13359243Sobrienstatic int compare(const void *, const void *); 13459243Sobrienstatic int g_Ctoc(const Char *, char *, u_int); 13559243Sobrienstatic int g_lstat(Char *, struct stat *, glob_t *); 13659243Sobrienstatic DIR *g_opendir(Char *, glob_t *); 13759243Sobrienstatic Char *g_strchr(Char *, int); 138167465Smp#ifdef notdef 13959243Sobrienstatic Char *g_strcat(Char *, const Char *); 140167465Smp#endif 14159243Sobrienstatic int g_stat(Char *, struct stat *, glob_t *); 14259243Sobrienstatic int glob0(const Char *, glob_t *, int *); 14359243Sobrienstatic int glob1(Char *, glob_t *, int *); 14459243Sobrienstatic int glob2(Char *, Char *, Char *, Char *, glob_t *, int *); 14559243Sobrienstatic int glob3(Char *, Char *, Char *, Char *, Char *, glob_t *, int *); 14659243Sobrienstatic int globextend(const Char *, glob_t *, int *); 14759243Sobrienstatic const Char * 148167465Smp globtilde(const Char *, Char *, size_t, glob_t *); 14959243Sobrienstatic int globexp1(const Char *, glob_t *, int *); 15059243Sobrienstatic int globexp2(const Char *, const Char *, glob_t *, int *, int *); 15159243Sobrienstatic int match(Char *, Char *, Char *); 15259243Sobrien#ifdef DEBUG 15359243Sobrienstatic void qprintf(const char *, Char *); 15459243Sobrien#endif 15559243Sobrien 15659243Sobrienint 157167465Smpglob(pattern, flags, errfunc, pglob) 15859243Sobrien const char *pattern; 15959243Sobrien int flags, (*errfunc)(const char *, int); 16059243Sobrien glob_t *pglob; 16159243Sobrien{ 16259243Sobrien const u_char *patnext; 16359243Sobrien int c, limit; 16459243Sobrien Char *bufnext, *bufend, patbuf[MAXPATHLEN]; 16559243Sobrien 16659243Sobrien patnext = (u_char *) pattern; 16759243Sobrien if (!(flags & GLOB_APPEND)) { 168167465Smp pglob->gl_pathc = 0; 16959243Sobrien pglob->gl_pathv = NULL; 17059243Sobrien if (!(flags & GLOB_DOOFFS)) 17159243Sobrien pglob->gl_offs = 0; 17259243Sobrien } 17359243Sobrien if (flags & GLOB_LIMIT) { 17459243Sobrien limit = pglob->gl_matchc; 17559243Sobrien if (limit == 0) 17659243Sobrien limit = ARG_MAX; 17759243Sobrien } else 17859243Sobrien limit = 0; 179167465Smp pglob->gl_flags = flags & ~GLOB_MAGCHAR; 18059243Sobrien pglob->gl_errfunc = errfunc; 181145479Smp pglob->gl_matchc = 0; 18259243Sobrien 183145479Smp bufnext = patbuf; 184145479Smp bufend = bufnext + MAXPATHLEN - 1; 185145479Smp if (flags & GLOB_QUOTE) { 186145479Smp /* Protect the quoted characters. */ 187145479Smp while (bufnext < bufend && (c = *patnext++) != EOS) 18859243Sobrien if (c == QUOTE) { 18959243Sobrien if ((c = *patnext++) == EOS) { 19059243Sobrien c = QUOTE; 19159243Sobrien --patnext; 19259243Sobrien } 19359243Sobrien *bufnext++ = c | M_PROTECT; 194145479Smp } 19559243Sobrien else 19659243Sobrien *bufnext++ = c; 19769408Sache } 19859243Sobrien else 19959243Sobrien while (bufnext < bufend && (c = *patnext++) != EOS) 20059243Sobrien *bufnext++ = c; 20159243Sobrien *bufnext = EOS; 20259243Sobrien 20369408Sache if (flags & GLOB_BRACE) 20459243Sobrien return globexp1(patbuf, pglob, &limit); 20559243Sobrien else 206167465Smp return glob0(patbuf, pglob, &limit); 207167465Smp} 20859243Sobrien 20959243Sobrien/* 210100616Smp * Expand recursively a glob {} pattern. When there is no more expansion 211167465Smp * invoke the standard globbing routine to glob the rest of the magic 21259243Sobrien * characters 21359243Sobrien */ 21459243Sobrienstatic int 21559243Sobrienglobexp1(pattern, pglob, limit) 21659243Sobrien const Char *pattern; 21759243Sobrien glob_t *pglob; 21859243Sobrien int *limit; 21959243Sobrien{ 22059243Sobrien const Char* ptr = pattern; 22159243Sobrien int rv; 22259243Sobrien 22369408Sache /* Protect a single {}, for find(1), like csh */ 22459243Sobrien if (pattern[0] == LBRACE && pattern[1] == RBRACE && pattern[2] == EOS) 22559243Sobrien return glob0(pattern, pglob, limit); 22659243Sobrien 22759243Sobrien while ((ptr = (const Char *) g_strchr((Char *) ptr, LBRACE)) != NULL) 22859243Sobrien if (!globexp2(ptr, pattern, pglob, &rv, limit)) 229167465Smp return rv; 23059243Sobrien 23159243Sobrien return glob0(pattern, pglob, limit); 23259243Sobrien} 23359243Sobrien 23459243Sobrien 23569408Sache/* 23659243Sobrien * Recursive brace globbing helper. Tries to expand a single brace. 237167465Smp * If it succeeds then it invokes globexp1 with the new pattern. 23859243Sobrien * If it fails then it tries to glob the rest of the pattern and returns. 23959243Sobrien */ 24059243Sobrienstatic int 24169408Sacheglobexp2(ptr, pattern, pglob, rv, limit) 24259243Sobrien const Char *ptr, *pattern; 24369408Sache glob_t *pglob; 24459243Sobrien int *rv, *limit; 24559243Sobrien{ 24659243Sobrien int i; 24759243Sobrien Char *lm, *ls; 24859243Sobrien const Char *pe, *pm, *pl; 249145479Smp Char patbuf[MAXPATHLEN]; 25061515Sobrien 25161515Sobrien /* copy part up to the brace */ 25261515Sobrien for (lm = patbuf, pm = pattern; pm != ptr; *lm++ = *pm++) 253145479Smp continue; 254167465Smp *lm = EOS; 25559243Sobrien ls = lm; 25659243Sobrien 25759243Sobrien /* Find the balanced brace */ 258167465Smp for (i = 0, pe = ++ptr; *pe; pe++) 25959243Sobrien if (*pe == LBRACKET) { 26059243Sobrien /* Ignore everything between [] */ 26159243Sobrien for (pm = pe++; *pe != RBRACKET && *pe != EOS; pe++) 262145479Smp continue; 263145479Smp if (*pe == EOS) { 264145479Smp /* 265167465Smp * We could not find a matching RBRACKET. 26661515Sobrien * Ignore and just look for RBRACE 26761515Sobrien */ 26861515Sobrien pe = pm; 269145479Smp } 270167465Smp } 27159243Sobrien else if (*pe == LBRACE) 27259243Sobrien i++; 273167465Smp else if (*pe == RBRACE) { 274145479Smp if (i == 0) 27559243Sobrien break; 27659243Sobrien i--; 27759243Sobrien } 27859243Sobrien 27959243Sobrien /* Non matching braces; just glob the pattern */ 280167465Smp if (i != 0 || *pe == EOS) { 281167465Smp *rv = glob0(patbuf, pglob, limit); 28259243Sobrien return 0; 28359243Sobrien } 28459243Sobrien 28559243Sobrien for (i = 0, pl = pm = ptr; pm <= pe; pm++) 28659243Sobrien switch (*pm) { 287145479Smp case LBRACKET: 288145479Smp /* Ignore everything between [] */ 289145479Smp for (pl = pm++; *pm != RBRACKET && *pm != EOS; pm++) 290145479Smp continue; 291167465Smp if (*pm == EOS) { 292145479Smp /* 29359243Sobrien * We could not find a matching RBRACKET. 29459243Sobrien * Ignore and just look for RBRACE 29559243Sobrien */ 29659243Sobrien pm = pl; 29759243Sobrien } 29859243Sobrien break; 29959243Sobrien 30059243Sobrien case LBRACE: 30159243Sobrien i++; 30259243Sobrien break; 30359243Sobrien 30459243Sobrien case RBRACE: 30559243Sobrien if (i) { 30659243Sobrien i--; 30759243Sobrien break; 30859243Sobrien } 30959243Sobrien /* FALLTHROUGH */ 31059243Sobrien case COMMA: 31159243Sobrien if (i && *pm == COMMA) 31259243Sobrien break; 31359243Sobrien else { 31459243Sobrien /* Append the current string */ 31559243Sobrien for (lm = ls; (pl < pm); *lm++ = *pl++) 316167465Smp continue; 317167465Smp /* 31859243Sobrien * Append the rest of the pattern after the 31959243Sobrien * closing brace 32059243Sobrien */ 32159243Sobrien for (pl = pe + 1; (*lm++ = *pl++) != EOS;) 32259243Sobrien continue; 32359243Sobrien 32459243Sobrien /* Expand the current pattern */ 32559243Sobrien#ifdef DEBUG 32659243Sobrien qprintf("globexp2:", patbuf); 32759243Sobrien#endif 32859243Sobrien *rv = globexp1(patbuf, pglob, limit); 32959243Sobrien 33059243Sobrien /* move after the comma, to the next string */ 33159243Sobrien pl = pm + 1; 332167465Smp } 33359243Sobrien break; 33459243Sobrien 33559243Sobrien default: 336145479Smp break; 33759243Sobrien } 33859243Sobrien *rv = 0; 33959243Sobrien return 0; 34059243Sobrien} 34159243Sobrien 34259243Sobrien 34359243Sobrien 34459243Sobrien/* 34559243Sobrien * expand tilde from the passwd file. 346145479Smp */ 34759243Sobrienstatic const Char * 34859243Sobrienglobtilde(pattern, patbuf, patbuf_len, pglob) 34959243Sobrien const Char *pattern; 35059243Sobrien Char *patbuf; 35159243Sobrien size_t patbuf_len; 35259243Sobrien glob_t *pglob; 35359243Sobrien{ 35459243Sobrien struct passwd *pwd; 355167465Smp char *h; 35659243Sobrien const Char *p; 357145479Smp Char *b, *eb; 35859243Sobrien 35959243Sobrien if (*pattern != TILDE || !(pglob->gl_flags & GLOB_TILDE)) 36059243Sobrien return pattern; 36159243Sobrien 36259243Sobrien /* 36359243Sobrien * Copy up to the end of the string or / 36459243Sobrien */ 36559243Sobrien eb = &patbuf[patbuf_len - 1]; 36659243Sobrien for (p = pattern + 1, h = (char *) patbuf; 367145479Smp h < (char *)eb && *p && *p != SLASH; *h++ = *p++) 36859243Sobrien continue; 36959243Sobrien 37059243Sobrien *h = EOS; 37159243Sobrien 37259243Sobrien if (((char *) patbuf)[0] == EOS) { 37359243Sobrien /* 37459243Sobrien * handle a plain ~ or ~/ by expanding $HOME first (iff 37559243Sobrien * we're not running setuid or setgid) and then trying 37659243Sobrien * the password file 37759243Sobrien */ 37859243Sobrien if ( 37959243Sobrien#ifndef __NETBSD_SYSCALLS 38059243Sobrien issetugid() != 0 || 38159243Sobrien#endif 38259243Sobrien (h = getenv("HOME")) == NULL) { 38359243Sobrien if (((h = getlogin()) != NULL && 38459243Sobrien (pwd = getpwnam(h)) != NULL) || 38559243Sobrien (pwd = getpwuid(getuid())) != NULL) 38659243Sobrien h = pwd->pw_dir; 38759243Sobrien else 38859243Sobrien return pattern; 38959243Sobrien } 390145479Smp } 391145479Smp else { 392145479Smp /* 393167465Smp * Expand a ~user 394145479Smp */ 395145479Smp if ((pwd = getpwnam((char*) patbuf)) == NULL) 39659243Sobrien return pattern; 39759243Sobrien else 39869408Sache h = pwd->pw_dir; 39959243Sobrien } 400167465Smp 401167465Smp /* Copy the home directory */ 40259243Sobrien for (b = patbuf; b < eb && *h; *b++ = *h++) 403167465Smp continue; 40459243Sobrien 40559243Sobrien /* Append the rest of the pattern */ 40659243Sobrien while (b < eb && (*b++ = *p++) != EOS) 40759243Sobrien continue; 40859243Sobrien *b = EOS; 40959243Sobrien 41059243Sobrien return patbuf; 41159243Sobrien} 41259243Sobrien 41359243Sobrien 41459243Sobrien/* 41559243Sobrien * The main glob() routine: compiles the pattern (optionally processing 41659243Sobrien * quotes), calls glob1() to do the real pattern matching, and finally 41759243Sobrien * sorts the list (unless unsorted operation is requested). Returns 0 41859243Sobrien * if things went well, nonzero if errors occurred. It is not an error 41959243Sobrien * to find no matches. 42059243Sobrien */ 42159243Sobrienstatic int 42259243Sobrienglob0(pattern, pglob, limit) 42359243Sobrien const Char *pattern; 42459243Sobrien glob_t *pglob; 42559243Sobrien int *limit; 42659243Sobrien{ 427167465Smp const Char *qpatnext; 42859243Sobrien int c, err, oldpathc; 429167465Smp Char *bufnext, patbuf[MAXPATHLEN]; 430167465Smp 43159243Sobrien qpatnext = globtilde(pattern, patbuf, MAXPATHLEN, pglob); 43259243Sobrien oldpathc = pglob->gl_pathc; 43359243Sobrien bufnext = patbuf; 43459243Sobrien 43559243Sobrien /* We don't need to check for buffer overflow any more. */ 43659243Sobrien while ((c = *qpatnext++) != EOS) { 43759243Sobrien switch (c) { 43859243Sobrien case LBRACKET: 43959243Sobrien c = *qpatnext; 44059243Sobrien if (c == NOT) 44159243Sobrien ++qpatnext; 44259243Sobrien if (*qpatnext == EOS || 44359243Sobrien g_strchr((Char *) qpatnext+1, RBRACKET) == NULL) { 44459243Sobrien *bufnext++ = LBRACKET; 44559243Sobrien if (c == NOT) 44659243Sobrien --qpatnext; 44759243Sobrien break; 44859243Sobrien } 44959243Sobrien *bufnext++ = M_SET; 45059243Sobrien if (c == NOT) 45159243Sobrien *bufnext++ = M_NOT; 45259243Sobrien c = *qpatnext++; 45359243Sobrien do { 45459243Sobrien *bufnext++ = CHAR(c); 45559243Sobrien if (*qpatnext == RANGE && 456167465Smp (c = qpatnext[1]) != RBRACKET) { 45759243Sobrien *bufnext++ = M_RNG; 45859243Sobrien *bufnext++ = CHAR(c); 45959243Sobrien qpatnext += 2; 46059243Sobrien } 461167465Smp } while ((c = *qpatnext++) != RBRACKET); 46259243Sobrien pglob->gl_flags |= GLOB_MAGCHAR; 463145479Smp *bufnext++ = M_END; 46459243Sobrien break; 46559243Sobrien case QUESTION: 46659243Sobrien pglob->gl_flags |= GLOB_MAGCHAR; 46759243Sobrien *bufnext++ = M_ONE; 46859243Sobrien break; 46959243Sobrien case STAR: 47059243Sobrien pglob->gl_flags |= GLOB_MAGCHAR; 47159243Sobrien /* collapse adjacent stars to one, 47259243Sobrien * to avoid exponential behavior 47359243Sobrien */ 47459243Sobrien if (bufnext == patbuf || bufnext[-1] != M_ALL) 47559243Sobrien *bufnext++ = M_ALL; 47659243Sobrien break; 47759243Sobrien default: 47859243Sobrien *bufnext++ = CHAR(c); 47959243Sobrien break; 48059243Sobrien } 48159243Sobrien } 48259243Sobrien *bufnext = EOS; 48359243Sobrien#ifdef DEBUG 48459243Sobrien qprintf("glob0:", patbuf); 48559243Sobrien#endif 48659243Sobrien 48759243Sobrien if ((err = glob1(patbuf, pglob, limit)) != 0) 48859243Sobrien return(err); 48959243Sobrien 49059243Sobrien /* 49159243Sobrien * If there was no match we are going to append the pattern 49259243Sobrien * if GLOB_NOCHECK was specified or if GLOB_NOMAGIC was specified 49359243Sobrien * and the pattern did not contain any magic characters 49459243Sobrien * GLOB_NOMAGIC is there just for compatibility with csh. 495167465Smp */ 49659243Sobrien if (pglob->gl_pathc == oldpathc && 497145479Smp ((pglob->gl_flags & GLOB_NOCHECK) || 49859243Sobrien ((pglob->gl_flags & GLOB_NOMAGIC) && 49959243Sobrien !(pglob->gl_flags & GLOB_MAGCHAR)))) 50059243Sobrien return(globextend(pattern, pglob, limit)); 501145479Smp else if (!(pglob->gl_flags & GLOB_NOSORT)) 50259243Sobrien qsort(pglob->gl_pathv + pglob->gl_offs + oldpathc, 503167465Smp pglob->gl_pathc - oldpathc, sizeof(char *), compare); 50459243Sobrien return(0); 505100616Smp} 50659243Sobrien 50759243Sobrienstatic int 508167465Smpcompare(p, q) 509167465Smp const void *p, *q; 510167465Smp{ 511145479Smp return(strcmp(*(char **)p, *(char **)q)); 512167465Smp} 51359243Sobrien 51459243Sobrienstatic int 51559243Sobrienglob1(pattern, pglob, limit) 51659243Sobrien Char *pattern; 517167465Smp glob_t *pglob; 518167465Smp int *limit; 519167465Smp{ 520167465Smp Char pathbuf[MAXPATHLEN]; 52159243Sobrien 522145479Smp /* A null pathname is invalid -- POSIX 1003.1 sect. 2.4. */ 523167465Smp if (*pattern == EOS) 52459243Sobrien return(0); 52559243Sobrien return(glob2(pathbuf, pathbuf, pathbuf + MAXPATHLEN - 1, 526145479Smp pattern, pglob, limit)); 52759243Sobrien} 52859243Sobrien 52959243Sobrien/* 53059243Sobrien * The functions glob2 and glob3 are mutually recursive; there is one level 53159243Sobrien * of recursion for each segment in the pattern that contains one or more 53259243Sobrien * meta characters. 533167465Smp */ 53459243Sobrienstatic int 535167465Smpglob2(pathbuf, pathend, pathend_last, pattern, pglob, limit) 53659243Sobrien Char *pathbuf, *pathend, *pathend_last, *pattern; 53759243Sobrien glob_t *pglob; 53859243Sobrien int *limit; 53959243Sobrien{ 54059243Sobrien struct stat sb; 54159243Sobrien Char *p, *q; 54259243Sobrien int anymeta; 54359243Sobrien 544167465Smp /* 54559243Sobrien * Loop over pattern segments until end of pattern or until 546167465Smp * segment with meta character found. 54759243Sobrien */ 548167465Smp for (anymeta = 0;;) { 54959243Sobrien if (*pattern == EOS) { /* End of pattern? */ 55059243Sobrien *pathend = EOS; 55159243Sobrien if (g_lstat(pathbuf, &sb, pglob)) 55259243Sobrien return(0); 55359243Sobrien 554145479Smp if (((pglob->gl_flags & GLOB_MARK) && 55559243Sobrien pathend[-1] != SEP) && (S_ISDIR(sb.st_mode) 55659243Sobrien || (S_ISLNK(sb.st_mode) && 557167465Smp (g_stat(pathbuf, &sb, pglob) == 0) && 55859243Sobrien S_ISDIR(sb.st_mode)))) { 559167465Smp if (pathend + 1 > pathend_last) 560167465Smp return (1); 561167465Smp *pathend++ = SEP; 56259243Sobrien *pathend = EOS; 563167465Smp } 564167465Smp ++pglob->gl_matchc; 56559243Sobrien return(globextend(pathbuf, pglob, limit)); 56659243Sobrien } 56759243Sobrien 568145479Smp /* Find end of next segment, copy tentatively to pathend. */ 569145479Smp q = pathend; 57059243Sobrien p = pattern; 57159243Sobrien while (*p != EOS && *p != SEP) { 57259243Sobrien if (ismeta(*p)) 57359243Sobrien anymeta = 1; 57459243Sobrien if (q + 1 > pathend_last) 57559243Sobrien return (1); 57659243Sobrien *q++ = *p++; 577167465Smp } 57859243Sobrien 579167465Smp if (!anymeta) { /* No expansion, do next segment. */ 580167465Smp pathend = q; 581167465Smp pattern = p; 582167465Smp while (*pattern == SEP) { 583145479Smp if (pathend + 1 > pathend_last) 584145479Smp return (1); 58559243Sobrien *pathend++ = *pattern++; 58659243Sobrien } 58759243Sobrien } else /* Need expansion, recurse. */ 588145479Smp return(glob3(pathbuf, pathend, pathend_last, pattern, p, 58959243Sobrien pglob, limit)); 59059243Sobrien } 591167465Smp /* NOTREACHED */ 59259243Sobrien} 59359243Sobrien 594167465Smpstatic int 59559243Sobrienglob3(pathbuf, pathend, pathend_last, pattern, restpattern, pglob, limit) 59659243Sobrien Char *pathbuf, *pathend, *pathend_last, *pattern, *restpattern; 59759243Sobrien glob_t *pglob; 59859243Sobrien int *limit; 59959243Sobrien{ 60059243Sobrien struct dirent *dp; 60159243Sobrien DIR *dirp; 60259243Sobrien int err; 60359243Sobrien char buf[MAXPATHLEN]; 60459243Sobrien 605167465Smp /* 60659243Sobrien * The readdirfunc declaration can't be prototyped, because it is 60759243Sobrien * assigned, below, to two functions which are prototyped in glob.h 60859243Sobrien * and dirent.h as taking pointers to differently typed opaque 60959243Sobrien * structures. 61059243Sobrien */ 61159243Sobrien struct dirent *(*readdirfunc)(); 61259243Sobrien 61359243Sobrien if (pathend > pathend_last) 61459243Sobrien return (1); 61559243Sobrien *pathend = EOS; 61659243Sobrien errno = 0; 61759243Sobrien 61859243Sobrien if ((dirp = g_opendir(pathbuf, pglob)) == NULL) { 61959243Sobrien /* TODO: don't call for ENOENT or ENOTDIR? */ 62059243Sobrien if (pglob->gl_errfunc) { 62159243Sobrien if (g_Ctoc(pathbuf, buf, sizeof(buf))) 62259243Sobrien return (GLOB_ABEND); 623145479Smp if (pglob->gl_errfunc(buf, errno) || 62469408Sache pglob->gl_flags & GLOB_ERR) 625167465Smp return (GLOB_ABEND); 62669408Sache } 62769408Sache return(0); 62869408Sache } 62969408Sache 63059243Sobrien err = 0; 631167465Smp 63259243Sobrien /* Search directory for matching names. */ 63359243Sobrien if (pglob->gl_flags & GLOB_ALTDIRFUNC) 63459243Sobrien readdirfunc = pglob->gl_readdir; 63559243Sobrien else 63659243Sobrien readdirfunc = readdir; 63759243Sobrien while ((dp = (*readdirfunc)(dirp))) { 63859243Sobrien u_char *sc; 63959243Sobrien Char *dc; 64059243Sobrien 64159243Sobrien /* Initial DOT must be matched literally. */ 64259243Sobrien if (dp->d_name[0] == DOT && *pattern != DOT) 64359243Sobrien continue; 64459243Sobrien dc = pathend; 64559243Sobrien sc = (u_char *) dp->d_name; 64659243Sobrien while (dc < pathend_last && (*dc++ = *sc++) != EOS) 647145479Smp ; 64859243Sobrien if (!match(pathend, pattern, restpattern)) { 64969408Sache *pathend = EOS; 65059243Sobrien continue; 65159243Sobrien } 65259243Sobrien err = glob2(pathbuf, --dc, pathend_last, restpattern, 65359243Sobrien pglob, limit); 65459243Sobrien if (err) 65559243Sobrien break; 65659243Sobrien } 65759243Sobrien 65859243Sobrien if (pglob->gl_flags & GLOB_ALTDIRFUNC) 65959243Sobrien (*pglob->gl_closedir)(dirp); 66059243Sobrien else 66159243Sobrien closedir(dirp); 66259243Sobrien return(err); 66359243Sobrien} 66459243Sobrien 66559243Sobrien 66659243Sobrien/* 66759243Sobrien * Extend the gl_pathv member of a glob_t structure to accomodate a new item, 66859243Sobrien * add the new item, and update gl_pathc. 66959243Sobrien * 67059243Sobrien * This assumes the BSD realloc, which only copies the block when its size 67159243Sobrien * crosses a power-of-two boundary; for v7 realloc, this would cause quadratic 67259243Sobrien * behavior. 67359243Sobrien * 67459243Sobrien * Return 0 if new item added, error code if memory couldn't be allocated. 67559243Sobrien * 67659243Sobrien * Invariant of the glob_t structure: 67759243Sobrien * Either gl_pathc is zero and gl_pathv is NULL; or gl_pathc > 0 and 67859243Sobrien * gl_pathv points to (gl_offs + gl_pathc + 1) items. 67959243Sobrien */ 68059243Sobrienstatic int 68159243Sobrienglobextend(path, pglob, limit) 68259243Sobrien const Char *path; 683167465Smp glob_t *pglob; 68459243Sobrien int *limit; 68559243Sobrien{ 68659243Sobrien char **pathv; 68759243Sobrien int i; 68859243Sobrien u_int newsize, len; 68959243Sobrien char *copy; 69059243Sobrien const Char *p; 69159243Sobrien 69259243Sobrien if (*limit && pglob->gl_pathc > *limit) { 69359243Sobrien errno = 0; 69459243Sobrien return (GLOB_NOSPACE); 69559243Sobrien } 69659243Sobrien 69759243Sobrien newsize = sizeof(*pathv) * (2 + pglob->gl_pathc + pglob->gl_offs); 69859243Sobrien pathv = pglob->gl_pathv ? 69959243Sobrien realloc((char *)pglob->gl_pathv, newsize) : 70059243Sobrien malloc(newsize); 70159243Sobrien if (pathv == NULL) { 70269408Sache if (pglob->gl_pathv) { 70359243Sobrien free(pglob->gl_pathv); 704 pglob->gl_pathv = NULL; 705 } 706 return(GLOB_NOSPACE); 707 } 708 709 if (pglob->gl_pathv == NULL && pglob->gl_offs > 0) { 710 /* first time around -- clear initial gl_offs items */ 711 pathv += pglob->gl_offs; 712 for (i = pglob->gl_offs; --i >= 0; ) 713 *--pathv = NULL; 714 } 715 pglob->gl_pathv = pathv; 716 717 for (p = path; *p++;) 718 continue; 719 len = (size_t)(p - path); 720 if ((copy = malloc(len)) != NULL) { 721 if (g_Ctoc(path, copy, len)) { 722 free(copy); 723 return (GLOB_NOSPACE); 724 } 725 pathv[pglob->gl_offs + pglob->gl_pathc++] = copy; 726 } 727 pathv[pglob->gl_offs + pglob->gl_pathc] = NULL; 728 return(copy == NULL ? GLOB_NOSPACE : 0); 729} 730 731/* 732 * pattern matching function for filenames. Each occurrence of the * 733 * pattern causes a recursion level. 734 */ 735static int 736match(name, pat, patend) 737 Char *name, *pat, *patend; 738{ 739 int ok, negate_range; 740 Char c, k; 741 742 while (pat < patend) { 743 c = *pat++; 744 switch (c & M_MASK) { 745 case M_ALL: 746 if (pat == patend) 747 return(1); 748 do 749 if (match(name, pat, patend)) 750 return(1); 751 while (*name++ != EOS); 752 return(0); 753 case M_ONE: 754 if (*name++ == EOS) 755 return(0); 756 break; 757 case M_SET: 758 ok = 0; 759 if ((k = *name++) == EOS) 760 return(0); 761 if ((negate_range = ((*pat & M_MASK) == M_NOT)) != EOS) 762 ++pat; 763 while (((c = *pat++) & M_MASK) != M_END) 764 if ((*pat & M_MASK) == M_RNG) { 765 if (__collate_load_error ? 766 CHAR(c) <= CHAR(k) && CHAR(k) <= CHAR(pat[1]) : 767 __collate_range_cmp(CHAR(c), CHAR(k)) <= 0 768 && __collate_range_cmp(CHAR(k), CHAR(pat[1])) <= 0 769 ) 770 ok = 1; 771 pat += 2; 772 } else if (c == k) 773 ok = 1; 774 if (ok == negate_range) 775 return(0); 776 break; 777 default: 778 if (*name++ != c) 779 return(0); 780 break; 781 } 782 } 783 return(*name == EOS); 784} 785 786/* Free allocated data belonging to a glob_t structure. */ 787void 788globfree(pglob) 789 glob_t *pglob; 790{ 791 int i; 792 char **pp; 793 794 if (pglob->gl_pathv != NULL) { 795 pp = pglob->gl_pathv + pglob->gl_offs; 796 for (i = pglob->gl_pathc; i--; ++pp) 797 if (*pp) 798 free(*pp); 799 free(pglob->gl_pathv); 800 pglob->gl_pathv = NULL; 801 } 802} 803 804static DIR * 805g_opendir(str, pglob) 806 Char *str; 807 glob_t *pglob; 808{ 809 char buf[MAXPATHLEN]; 810 811 if (!*str) 812 strcpy(buf, "."); 813 else { 814 if (g_Ctoc(str, buf, sizeof(buf))) 815 return (NULL); 816 } 817 818 if (pglob->gl_flags & GLOB_ALTDIRFUNC) 819 return((*pglob->gl_opendir)(buf)); 820 821 return(opendir(buf)); 822} 823 824static int 825g_lstat(fn, sb, pglob) 826 Char *fn; 827 struct stat *sb; 828 glob_t *pglob; 829{ 830 char buf[MAXPATHLEN]; 831 832 if (g_Ctoc(fn, buf, sizeof(buf))) { 833 errno = ENAMETOOLONG; 834 return (-1); 835 } 836 if (pglob->gl_flags & GLOB_ALTDIRFUNC) 837 return((*pglob->gl_lstat)(buf, sb)); 838 return(lstat(buf, sb)); 839} 840 841static int 842g_stat(fn, sb, pglob) 843 Char *fn; 844 struct stat *sb; 845 glob_t *pglob; 846{ 847 char buf[MAXPATHLEN]; 848 849 if (g_Ctoc(fn, buf, sizeof(buf))) { 850 errno = ENAMETOOLONG; 851 return (-1); 852 } 853 if (pglob->gl_flags & GLOB_ALTDIRFUNC) 854 return((*pglob->gl_stat)(buf, sb)); 855 return(stat(buf, sb)); 856} 857 858static Char * 859g_strchr(str, ch) 860 Char *str; 861 int ch; 862{ 863 do { 864 if (*str == ch) 865 return (str); 866 } while (*str++); 867 return (NULL); 868} 869 870static int 871g_Ctoc(str, buf, len) 872 const Char *str; 873 char *buf; 874 u_int len; 875{ 876 877 while (len--) { 878 if ((*buf++ = *str++) == '\0') 879 return (0); 880 } 881 return (1); 882} 883 884#ifdef DEBUG 885static void 886qprintf(str, s) 887 const char *str; 888 Char *s; 889{ 890 Char *p; 891 892 (void)printf("%s:\n", str); 893 for (p = s; *p; p++) 894 (void)printf("%c", CHAR(*p)); 895 (void)printf("\n"); 896 for (p = s; *p; p++) 897 (void)printf("%c", *p & M_PROTECT ? '"' : ' '); 898 (void)printf("\n"); 899 for (p = s; *p; p++) 900 (void)printf("%c", ismeta(*p) ? '_' : ' '); 901 (void)printf("\n"); 902} 903#endif 904