159243Sobrien/* 259243Sobrien * Copyright (c) 1989 The Regents of the University of California. 359243Sobrien * 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. 16100616Smp * 3. Neither the name of the University nor the names of its contributors 1759243Sobrien * may be used to endorse or promote products derived from this software 1859243Sobrien * without specific prior written permission. 1959243Sobrien * 2059243Sobrien * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 2159243Sobrien * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 2259243Sobrien * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 2359243Sobrien * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 2459243Sobrien * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 2559243Sobrien * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 2659243Sobrien * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 2759243Sobrien * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 2859243Sobrien * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 2959243Sobrien * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 3059243Sobrien * SUCH DAMAGE. 3159243Sobrien */ 3259243Sobrien#if defined(LIBC_SCCS) && !defined(lint) 3359243Sobrienstatic char sccsid[] = "@(#)glob.c 5.12 (Berkeley) 6/24/91"; 3459243Sobrien#endif /* LIBC_SCCS and not lint */ 3559243Sobrien/* 3659243Sobrien * Glob: the interface is a superset of the one defined in POSIX 1003.2, 3759243Sobrien * draft 9. 3859243Sobrien * 3959243Sobrien * The [!...] convention to negate a range is supported (SysV, Posix, ksh). 4059243Sobrien * 4159243Sobrien * Optional extra services, controlled by flags not defined by POSIX: 4259243Sobrien * 4359243Sobrien * GLOB_QUOTE: 4459243Sobrien * Escaping convention: \ inhibits any special meaning the following 4559243Sobrien * character might have (except \ at end of string is retained). 4659243Sobrien * GLOB_MAGCHAR: 4759243Sobrien * Set in gl_flags if pattern contained a globbing character. 4859243Sobrien * GLOB_ALTNOT: 4959243Sobrien * Use ^ instead of ! for "not". 5059243Sobrien * gl_matchc: 5159243Sobrien * Number of matches in the current invocation of glob. 5259243Sobrien */ 5359243Sobrien 5469408Sache#ifdef WINNT_NATIVE 5559243Sobrien #pragma warning(disable:4244) 5669408Sache#endif /* WINNT_NATIVE */ 5759243Sobrien 5859243Sobrien#define Char __Char 5959243Sobrien#include "sh.h" 60145479Smp#include "glob.h" 61145479Smp 62316958Sdchagin#ifndef HAVE_MBLEN 63316958Sdchagin#undef mblen 64316958Sdchagin#define mblen(_s,_n) mbrlen((_s),(_n),NULL) 65316958Sdchagin#endif 66316958Sdchagin 6759243Sobrien#undef Char 6859243Sobrien#undef QUOTE 6959243Sobrien#undef TILDE 7059243Sobrien#undef META 7159243Sobrien#undef ismeta 7259243Sobrien#undef Strchr 7359243Sobrien 7459243Sobrien#ifndef S_ISDIR 7559243Sobrien#define S_ISDIR(a) (((a) & S_IFMT) == S_IFDIR) 7659243Sobrien#endif 7759243Sobrien 7859243Sobrien#if !defined(S_ISLNK) && defined(S_IFLNK) 7959243Sobrien#define S_ISLNK(a) (((a) & S_IFMT) == S_IFLNK) 8059243Sobrien#endif 8159243Sobrien 8259243Sobrien#if !defined(S_ISLNK) && !defined(lstat) 8359243Sobrien#define lstat stat 8459243Sobrien#endif 8559243Sobrien 8659243Sobrientypedef unsigned short Char; 8759243Sobrien 88167465Smpstatic int glob1 (Char *, glob_t *, int); 89167465Smpstatic int glob2 (struct strbuf *, const Char *, glob_t *, int); 90167465Smpstatic int glob3 (struct strbuf *, const Char *, const Char *, 91231990Smp const Char *, glob_t *, int); 92167465Smpstatic void globextend (const char *, glob_t *); 93167465Smpstatic int match (const char *, const Char *, const Char *, 94167465Smp int); 95167465Smpstatic int compare (const void *, const void *); 96167465Smpstatic DIR *Opendir (const char *); 9759243Sobrien#ifdef S_IFLNK 98167465Smpstatic int Lstat (const char *, struct stat *); 9959243Sobrien#endif 100167465Smpstatic int Stat (const char *, struct stat *sb); 101167465Smpstatic Char *Strchr (Char *, int); 10259243Sobrien#ifdef DEBUG 103167465Smpstatic void qprintf (const Char *); 10459243Sobrien#endif 10559243Sobrien 10659243Sobrien#define DOLLAR '$' 10759243Sobrien#define DOT '.' 10859243Sobrien#define EOS '\0' 10959243Sobrien#define LBRACKET '[' 11059243Sobrien#define NOT '!' 11159243Sobrien#define ALTNOT '^' 11259243Sobrien#define QUESTION '?' 11359243Sobrien#define QUOTE '\\' 11459243Sobrien#define RANGE '-' 11559243Sobrien#define RBRACKET ']' 11659243Sobrien#define SEP '/' 11759243Sobrien#define STAR '*' 11859243Sobrien#define TILDE '~' 11959243Sobrien#define UNDERSCORE '_' 12059243Sobrien 12159243Sobrien#define M_META 0x8000 12259243Sobrien#define M_PROTECT 0x4000 12359243Sobrien#define M_MASK 0xffff 12459243Sobrien#define M_ASCII 0x00ff 12559243Sobrien 126167465Smp#define LCHAR(c) ((c)&M_ASCII) 12759243Sobrien#define META(c) ((c)|M_META) 12859243Sobrien#define M_ALL META('*') 12959243Sobrien#define M_END META(']') 13059243Sobrien#define M_NOT META('!') 13159243Sobrien#define M_ALTNOT META('^') 13259243Sobrien#define M_ONE META('?') 13359243Sobrien#define M_RNG META('-') 13459243Sobrien#define M_SET META('[') 13559243Sobrien#define ismeta(c) (((c)&M_META) != 0) 13659243Sobrien 13759243Sobrienint 138167465Smpglobcharcoll(__Char c1, __Char c2, int cs) 13959243Sobrien{ 140167465Smp#if defined(NLS) && defined(LC_COLLATE) && defined(HAVE_STRCOLL) 141167465Smp# if defined(WIDE_STRINGS) 142145479Smp wchar_t s1[2], s2[2]; 143145479Smp 144145479Smp if (c1 == c2) 145145479Smp return (0); 146145479Smp if (cs) { 147145479Smp c1 = towlower(c1); 148145479Smp c2 = towlower(c2); 149145479Smp } else { 150145479Smp /* This should not be here, but I'll rather leave it in than engage in 151145479Smp a LC_COLLATE flamewar about a shell I don't use... */ 152145479Smp if (iswlower(c1) && iswupper(c2)) 153145479Smp return (1); 154145479Smp if (iswupper(c1) && iswlower(c2)) 155145479Smp return (-1); 156145479Smp } 157145479Smp s1[0] = c1; 158145479Smp s2[0] = c2; 159145479Smp s1[1] = s2[1] = '\0'; 160145479Smp return wcscoll(s1, s2); 161167465Smp# else /* not WIDE_STRINGS */ 16259243Sobrien char s1[2], s2[2]; 16359243Sobrien 16459243Sobrien if (c1 == c2) 16559243Sobrien return (0); 16659415Sobrien /* 16759415Sobrien * From kevin lyda <kevin@suberic.net>: 16859415Sobrien * strcoll does not guarantee case sorting, so we pre-process now: 16959415Sobrien */ 170131962Smp if (cs) { 171131962Smp c1 = islower(c1) ? c1 : tolower(c1); 172131962Smp c2 = islower(c2) ? c2 : tolower(c2); 173131962Smp } else { 174131962Smp if (islower(c1) && isupper(c2)) 175131962Smp return (1); 176145479Smp if (isupper(c1) && islower(c2)) 177145479Smp return (-1); 178131962Smp } 17959243Sobrien s1[0] = c1; 18059243Sobrien s2[0] = c2; 18159243Sobrien s1[1] = s2[1] = '\0'; 18259243Sobrien return strcoll(s1, s2); 183145479Smp# endif 18459243Sobrien#else 18559243Sobrien return (c1 - c2); 18659243Sobrien#endif 18759243Sobrien} 18859243Sobrien 18959243Sobrien/* 19059243Sobrien * Need to dodge two kernel bugs: 19159243Sobrien * opendir("") != opendir(".") 19259243Sobrien * NAMEI_BUG: on plain files trailing slashes are ignored in some kernels. 19359243Sobrien * POSIX specifies that they should be ignored in directories. 19459243Sobrien */ 19559243Sobrien 19659243Sobrienstatic DIR * 197167465SmpOpendir(const char *str) 19859243Sobrien{ 19959243Sobrien#if defined(hpux) || defined(__hpux) 20059243Sobrien struct stat st; 20159243Sobrien#endif 20259243Sobrien 20359243Sobrien if (!*str) 20459243Sobrien return (opendir(".")); 20559243Sobrien#if defined(hpux) || defined(__hpux) 20659243Sobrien /* 20759243Sobrien * Opendir on some device files hangs, so avoid it 20859243Sobrien */ 209167465Smp if (stat(str, &st) == -1 || !S_ISDIR(st.st_mode)) 21059243Sobrien return NULL; 21159243Sobrien#endif 212167465Smp return opendir(str); 21359243Sobrien} 21459243Sobrien 21559243Sobrien#ifdef S_IFLNK 21659243Sobrienstatic int 217167465SmpLstat(const char *fn, struct stat *sb) 21859243Sobrien{ 219167465Smp int st; 22059243Sobrien 221167465Smp st = lstat(fn, sb); 22259243Sobrien# ifdef NAMEI_BUG 223167465Smp if (*fn != 0 && strend(fn)[-1] == '/' && !S_ISDIR(sb->st_mode)) 224167465Smp st = -1; 22559243Sobrien# endif /* NAMEI_BUG */ 226167465Smp return st; 22759243Sobrien} 22859243Sobrien#else 22959243Sobrien#define Lstat Stat 23059243Sobrien#endif /* S_IFLNK */ 23159243Sobrien 23259243Sobrienstatic int 233167465SmpStat(const char *fn, struct stat *sb) 23459243Sobrien{ 235167465Smp int st; 23659243Sobrien 237167465Smp st = stat(fn, sb); 23859243Sobrien#ifdef NAMEI_BUG 239167465Smp if (*fn != 0 && strend(fn)[-1] == '/' && !S_ISDIR(sb->st_mode)) 240167465Smp st = -1; 24159243Sobrien#endif /* NAMEI_BUG */ 242167465Smp return st; 24359243Sobrien} 24459243Sobrien 24559243Sobrienstatic Char * 246167465SmpStrchr(Char *str, int ch) 24759243Sobrien{ 24859243Sobrien do 24959243Sobrien if (*str == ch) 25059243Sobrien return (str); 25159243Sobrien while (*str++); 25259243Sobrien return (NULL); 25359243Sobrien} 25459243Sobrien 25559243Sobrien#ifdef DEBUG 25659243Sobrienstatic void 257167465Smpqprintf(const Char *s) 25859243Sobrien{ 259167465Smp const Char *p; 26059243Sobrien 26159243Sobrien for (p = s; *p; p++) 26259243Sobrien printf("%c", *p & 0xff); 26359243Sobrien printf("\n"); 26459243Sobrien for (p = s; *p; p++) 26559243Sobrien printf("%c", *p & M_PROTECT ? '"' : ' '); 26659243Sobrien printf("\n"); 26759243Sobrien for (p = s; *p; p++) 26859243Sobrien printf("%c", *p & M_META ? '_' : ' '); 26959243Sobrien printf("\n"); 27059243Sobrien} 27159243Sobrien#endif /* DEBUG */ 27259243Sobrien 27359243Sobrienstatic int 274167465Smpcompare(const void *p, const void *q) 27559243Sobrien{ 276167465Smp#if defined(NLS) && defined(HAVE_STRCOLL) 277167465Smp return (strcoll(*(char *const *) p, *(char *const *) q)); 27859243Sobrien#else 279167465Smp return (strcmp(*(char *const *) p, *(char *const *) q)); 280167465Smp#endif /* NLS && HAVE_STRCOLL */ 28159243Sobrien} 28259243Sobrien 28359243Sobrien/* 28459243Sobrien * The main glob() routine: compiles the pattern (optionally processing 28559243Sobrien * quotes), calls glob1() to do the real pattern matching, and finally 28659243Sobrien * sorts the list (unless unsorted operation is requested). Returns 0 28759243Sobrien * if things went well, nonzero if errors occurred. It is not an error 28859243Sobrien * to find no matches. 28959243Sobrien */ 29059243Sobrienint 291167465Smpglob(const char *pattern, int flags, int (*errfunc) (const char *, int), 292167465Smp glob_t *pglob) 29359243Sobrien{ 29459243Sobrien int err, oldpathc; 295167465Smp Char *bufnext, m_not; 296167465Smp const unsigned char *patnext; 29759243Sobrien int c, not; 298167465Smp Char *qpatnext, *patbuf; 29959243Sobrien int no_match; 30059243Sobrien 301145479Smp patnext = (const unsigned char *) pattern; 30259243Sobrien if (!(flags & GLOB_APPEND)) { 30359243Sobrien pglob->gl_pathc = 0; 30459243Sobrien pglob->gl_pathv = NULL; 30559243Sobrien if (!(flags & GLOB_DOOFFS)) 30659243Sobrien pglob->gl_offs = 0; 30759243Sobrien } 30859243Sobrien pglob->gl_flags = flags & ~GLOB_MAGCHAR; 30959243Sobrien pglob->gl_errfunc = errfunc; 31059243Sobrien oldpathc = pglob->gl_pathc; 31159243Sobrien pglob->gl_matchc = 0; 31259243Sobrien 31359243Sobrien if (pglob->gl_flags & GLOB_ALTNOT) { 31459243Sobrien not = ALTNOT; 31559243Sobrien m_not = M_ALTNOT; 31659243Sobrien } 31759243Sobrien else { 31859243Sobrien not = NOT; 31959243Sobrien m_not = M_NOT; 32059243Sobrien } 32159243Sobrien 322167465Smp patbuf = xmalloc((strlen(pattern) + 1) * sizeof(*patbuf)); 32359243Sobrien bufnext = patbuf; 32459243Sobrien 32559243Sobrien no_match = *patnext == not; 32659243Sobrien if (no_match) 32759243Sobrien patnext++; 32859243Sobrien 32959243Sobrien if (flags & GLOB_QUOTE) { 33059243Sobrien /* Protect the quoted characters */ 331167465Smp while ((c = *patnext++) != EOS) { 332145479Smp#ifdef WIDE_STRINGS 333145479Smp int len; 334145479Smp 335145479Smp len = mblen((const char *)(patnext - 1), MB_LEN_MAX); 336145479Smp if (len == -1) 337231990Smp TCSH_IGNORE(mblen(NULL, 0)); 338195609Smp else if (len > 1) { 339145479Smp *bufnext++ = (Char) c; 340145479Smp while (--len != 0) 341145479Smp *bufnext++ = (Char) (*patnext++ | M_PROTECT); 342145479Smp } else 343145479Smp#endif /* WIDE_STRINGS */ 34459243Sobrien if (c == QUOTE) { 34559243Sobrien if ((c = *patnext++) == EOS) { 34659243Sobrien c = QUOTE; 34759243Sobrien --patnext; 34859243Sobrien } 34959243Sobrien *bufnext++ = (Char) (c | M_PROTECT); 35059243Sobrien } 35159243Sobrien else 35259243Sobrien *bufnext++ = (Char) c; 353145479Smp } 35459243Sobrien } 355167465Smp else 356167465Smp while ((c = *patnext++) != EOS) 35759243Sobrien *bufnext++ = (Char) c; 35859243Sobrien *bufnext = EOS; 35959243Sobrien 36059243Sobrien bufnext = patbuf; 36159243Sobrien qpatnext = patbuf; 36259243Sobrien while ((c = *qpatnext++) != EOS) { 36359243Sobrien switch (c) { 36459243Sobrien case LBRACKET: 36559243Sobrien c = *qpatnext; 36659243Sobrien if (c == not) 36759243Sobrien ++qpatnext; 36859243Sobrien if (*qpatnext == EOS || 36959243Sobrien Strchr(qpatnext + 1, RBRACKET) == NULL) { 37059243Sobrien *bufnext++ = LBRACKET; 37159243Sobrien if (c == not) 37259243Sobrien --qpatnext; 37359243Sobrien break; 37459243Sobrien } 37559243Sobrien pglob->gl_flags |= GLOB_MAGCHAR; 37659243Sobrien *bufnext++ = M_SET; 37759243Sobrien if (c == not) 37859243Sobrien *bufnext++ = m_not; 37959243Sobrien c = *qpatnext++; 38059243Sobrien do { 381167465Smp *bufnext++ = LCHAR(c); 38259243Sobrien if (*qpatnext == RANGE && 38359243Sobrien (c = qpatnext[1]) != RBRACKET) { 38459243Sobrien *bufnext++ = M_RNG; 385167465Smp *bufnext++ = LCHAR(c); 38659243Sobrien qpatnext += 2; 38759243Sobrien } 38859243Sobrien } while ((c = *qpatnext++) != RBRACKET); 38959243Sobrien *bufnext++ = M_END; 39059243Sobrien break; 39159243Sobrien case QUESTION: 39259243Sobrien pglob->gl_flags |= GLOB_MAGCHAR; 39359243Sobrien *bufnext++ = M_ONE; 39459243Sobrien break; 39559243Sobrien case STAR: 39659243Sobrien pglob->gl_flags |= GLOB_MAGCHAR; 397231990Smp /* collapse adjacent stars to one [or three if globstar], 398231990Smp * to avoid exponential behavior 39959243Sobrien */ 400231990Smp if (bufnext == patbuf || bufnext[-1] != M_ALL || 401231990Smp ((flags & GLOB_STAR) != 0 && 402231990Smp (bufnext - 1 == patbuf || bufnext[-2] != M_ALL || 403231990Smp bufnext - 2 == patbuf || bufnext[-3] != M_ALL))) 40459243Sobrien *bufnext++ = M_ALL; 40559243Sobrien break; 40659243Sobrien default: 407167465Smp *bufnext++ = LCHAR(c); 40859243Sobrien break; 40959243Sobrien } 41059243Sobrien } 41159243Sobrien *bufnext = EOS; 41259243Sobrien#ifdef DEBUG 41359243Sobrien qprintf(patbuf); 41459243Sobrien#endif 41559243Sobrien 416167465Smp if ((err = glob1(patbuf, pglob, no_match)) != 0) { 417167465Smp xfree(patbuf); 41859243Sobrien return (err); 419167465Smp } 42059243Sobrien 42159243Sobrien /* 42259243Sobrien * If there was no match we are going to append the pattern 42359243Sobrien * if GLOB_NOCHECK was specified or if GLOB_NOMAGIC was specified 42459243Sobrien * and the pattern did not contain any magic characters 42559243Sobrien * GLOB_NOMAGIC is there just for compatibility with csh. 42659243Sobrien */ 42759243Sobrien if (pglob->gl_pathc == oldpathc && 42859243Sobrien ((flags & GLOB_NOCHECK) || 42959243Sobrien ((flags & GLOB_NOMAGIC) && !(pglob->gl_flags & GLOB_MAGCHAR)))) { 430167465Smp if (!(flags & GLOB_QUOTE)) 431167465Smp globextend(pattern, pglob); 432167465Smp else { 433167465Smp char *copy, *dest; 434167465Smp const char *src; 43559243Sobrien 436167465Smp /* copy pattern, interpreting quotes */ 437167465Smp copy = xmalloc(strlen(pattern) + 1); 438167465Smp dest = copy; 439167465Smp src = pattern; 440167465Smp while (*src != EOS) { 441316958Sdchagin /* Don't interpret quotes. The spec does not say we should do */ 442167465Smp if (*src == QUOTE) { 443167465Smp if (*++src == EOS) 444167465Smp --src; 44559243Sobrien } 446167465Smp *dest++ = *src++; 44759243Sobrien } 448167465Smp *dest = EOS; 449167465Smp globextend(copy, pglob); 450167465Smp xfree(copy); 45159243Sobrien } 452167465Smp xfree(patbuf); 453167465Smp return 0; 45459243Sobrien } 45559415Sobrien else if (!(flags & GLOB_NOSORT) && (pglob->gl_pathc != oldpathc)) 456167465Smp qsort(pglob->gl_pathv + pglob->gl_offs + oldpathc, 457167465Smp pglob->gl_pathc - oldpathc, sizeof(char *), compare); 458167465Smp xfree(patbuf); 45959243Sobrien return (0); 46059243Sobrien} 46159243Sobrien 46259243Sobrienstatic int 463167465Smpglob1(Char *pattern, glob_t *pglob, int no_match) 46459243Sobrien{ 465167465Smp struct strbuf pathbuf = strbuf_INIT; 466167465Smp int err; 46759243Sobrien 46859243Sobrien /* 46959243Sobrien * a null pathname is invalid -- POSIX 1003.1 sect. 2.4. 47059243Sobrien */ 47159243Sobrien if (*pattern == EOS) 47259243Sobrien return (0); 473167465Smp err = glob2(&pathbuf, pattern, pglob, no_match); 474167465Smp xfree(pathbuf.s); 475167465Smp return err; 47659243Sobrien} 47759243Sobrien 47859243Sobrien/* 47959243Sobrien * functions glob2 and glob3 are mutually recursive; there is one level 48059243Sobrien * of recursion for each segment in the pattern that contains one or 48159243Sobrien * more meta characters. 48259243Sobrien */ 48359243Sobrienstatic int 484167465Smpglob2(struct strbuf *pathbuf, const Char *pattern, glob_t *pglob, int no_match) 48559243Sobrien{ 48659243Sobrien struct stat sbuf; 48759243Sobrien int anymeta; 488167465Smp const Char *p; 489167465Smp size_t orig_len; 49059243Sobrien 49159243Sobrien /* 49259243Sobrien * loop over pattern segments until end of pattern or until segment with 49359243Sobrien * meta character found. 49459243Sobrien */ 49559243Sobrien anymeta = 0; 49659243Sobrien for (;;) { 49759243Sobrien if (*pattern == EOS) { /* end of pattern? */ 498167465Smp strbuf_terminate(pathbuf); 49959243Sobrien 500167465Smp if (Lstat(pathbuf->s, &sbuf)) 50159243Sobrien return (0); 50259243Sobrien 50359243Sobrien if (((pglob->gl_flags & GLOB_MARK) && 504167465Smp pathbuf->s[pathbuf->len - 1] != SEP) && 50559243Sobrien (S_ISDIR(sbuf.st_mode) 50659243Sobrien#ifdef S_IFLNK 50759243Sobrien || (S_ISLNK(sbuf.st_mode) && 508167465Smp (Stat(pathbuf->s, &sbuf) == 0) && 50959243Sobrien S_ISDIR(sbuf.st_mode)) 51059243Sobrien#endif 51159243Sobrien )) { 512167465Smp strbuf_append1(pathbuf, SEP); 513167465Smp strbuf_terminate(pathbuf); 51459243Sobrien } 51559243Sobrien ++pglob->gl_matchc; 516167465Smp globextend(pathbuf->s, pglob); 517167465Smp return 0; 51859243Sobrien } 51959243Sobrien 520167465Smp /* find end of next segment, tentatively copy to pathbuf */ 52159243Sobrien p = pattern; 522167465Smp orig_len = pathbuf->len; 52359243Sobrien while (*p != EOS && *p != SEP) { 52459243Sobrien if (ismeta(*p)) 52559243Sobrien anymeta = 1; 526167465Smp strbuf_append1(pathbuf, *p++); 52759243Sobrien } 52859243Sobrien 52959243Sobrien if (!anymeta) { /* no expansion, do next segment */ 53059243Sobrien pattern = p; 53159243Sobrien while (*pattern == SEP) 532167465Smp strbuf_append1(pathbuf, *pattern++); 53359243Sobrien } 534167465Smp else { /* need expansion, recurse */ 535167465Smp pathbuf->len = orig_len; 536231990Smp return (glob3(pathbuf, pattern, p, pattern, pglob, no_match)); 537167465Smp } 53859243Sobrien } 53959243Sobrien /* NOTREACHED */ 54059243Sobrien} 54159243Sobrien 542231990Smpstatic size_t 543231990SmpOne_Char_mbtowc(__Char *pwc, const Char *s, size_t n) 544231990Smp{ 545231990Smp#ifdef WIDE_STRINGS 546231990Smp char buf[MB_LEN_MAX], *p; 54759243Sobrien 548231990Smp if (n > MB_LEN_MAX) 549231990Smp n = MB_LEN_MAX; 550231990Smp p = buf; 551231990Smp while (p < buf + n && (*p++ = LCHAR(*s++)) != 0) 552231990Smp ; 553231990Smp return one_mbtowc(pwc, buf, n); 554231990Smp#else 555231990Smp *pwc = *s & CHAR; 556231990Smp return 1; 557231990Smp#endif 558231990Smp} 559231990Smp 56059243Sobrienstatic int 561167465Smpglob3(struct strbuf *pathbuf, const Char *pattern, const Char *restpattern, 562231990Smp const Char *pglobstar, glob_t *pglob, int no_match) 56359243Sobrien{ 56459243Sobrien DIR *dirp; 56559243Sobrien struct dirent *dp; 566231990Smp struct stat sbuf; 56759243Sobrien int err; 56859243Sobrien Char m_not = (pglob->gl_flags & GLOB_ALTNOT) ? M_ALTNOT : M_NOT; 569167465Smp size_t orig_len; 570231990Smp int globstar = 0; 571231990Smp int chase_symlinks = 0; 572231990Smp const Char *termstar = NULL; 57359243Sobrien 574167465Smp strbuf_terminate(pathbuf); 575231990Smp orig_len = pathbuf->len; 576231990Smp errno = err = 0; 57759243Sobrien 578231990Smp while (pglobstar < restpattern) { 579231990Smp __Char wc; 580231990Smp size_t width = One_Char_mbtowc(&wc, pglobstar, MB_LEN_MAX); 581231990Smp if ((pglobstar[0] & M_MASK) == M_ALL && 582231990Smp (pglobstar[width] & M_MASK) == M_ALL) { 583231990Smp globstar = 1; 584231990Smp chase_symlinks = (pglobstar[2 * width] & M_MASK) == M_ALL; 585231990Smp termstar = pglobstar + (2 + chase_symlinks) * width; 586231990Smp break; 587231990Smp } 588231990Smp pglobstar += width; 589231990Smp } 590231990Smp 591231990Smp if (globstar) { 592231990Smp err = pglobstar==pattern && termstar==restpattern ? 593231990Smp *restpattern == EOS ? 594231990Smp glob2(pathbuf, restpattern - 1, pglob, no_match) : 595231990Smp glob2(pathbuf, restpattern + 1, pglob, no_match) : 596231990Smp glob3(pathbuf, pattern, restpattern, termstar, pglob, no_match); 597231990Smp if (err) 598231990Smp return err; 599231990Smp pathbuf->len = orig_len; 600231990Smp strbuf_terminate(pathbuf); 601231990Smp } 602231990Smp 603231990Smp if (*pathbuf->s && (Lstat(pathbuf->s, &sbuf) || !S_ISDIR(sbuf.st_mode) 604231990Smp#ifdef S_IFLINK 605231990Smp && ((globstar && !chase_symlinks) || !S_ISLNK(sbuf.st_mode)) 606231990Smp#endif 607231990Smp )) 608231990Smp return 0; 609231990Smp 610167465Smp if (!(dirp = Opendir(pathbuf->s))) { 61159243Sobrien /* todo: don't call for ENOENT or ENOTDIR? */ 612167465Smp if ((pglob->gl_errfunc && (*pglob->gl_errfunc) (pathbuf->s, errno)) || 61359243Sobrien (pglob->gl_flags & GLOB_ERR)) 61459243Sobrien return (GLOB_ABEND); 61559243Sobrien else 61659243Sobrien return (0); 61759243Sobrien } 61859243Sobrien 61959243Sobrien /* search directory for matching names */ 62059243Sobrien while ((dp = readdir(dirp)) != NULL) { 62159243Sobrien /* initial DOT must be matched literally */ 62259243Sobrien if (dp->d_name[0] == DOT && *pattern != DOT) 623231990Smp if (!(pglob->gl_flags & GLOB_DOT) || !dp->d_name[1] || 624231990Smp (dp->d_name[1] == DOT && !dp->d_name[2])) 625231990Smp continue; /*unless globdot and not . or .. */ 626167465Smp pathbuf->len = orig_len; 627167465Smp strbuf_append(pathbuf, dp->d_name); 628167465Smp strbuf_terminate(pathbuf); 629231990Smp 630231990Smp if (globstar) { 631231990Smp#ifdef S_IFLNK 632231990Smp if (!chase_symlinks && 633231990Smp (Lstat(pathbuf->s, &sbuf) || S_ISLNK(sbuf.st_mode))) 634231990Smp continue; 635231990Smp#endif 636231990Smp if (match(pathbuf->s + orig_len, pattern, termstar, 637231990Smp (int)m_not) == no_match) 638231990Smp continue; 639231990Smp strbuf_append1(pathbuf, SEP); 640231990Smp strbuf_terminate(pathbuf); 641231990Smp if ((err = glob2(pathbuf, pglobstar, pglob, no_match)) != 0) 642231990Smp break; 643231990Smp } else { 644231990Smp if (match(pathbuf->s + orig_len, pattern, restpattern, 645231990Smp (int) m_not) == no_match) 646231990Smp continue; 647231990Smp if ((err = glob2(pathbuf, restpattern, pglob, no_match)) != 0) 648231990Smp break; 649231990Smp } 65059243Sobrien } 65159243Sobrien /* todo: check error from readdir? */ 652167465Smp closedir(dirp); 65359243Sobrien return (err); 65459243Sobrien} 65559243Sobrien 65659243Sobrien 65759243Sobrien/* 65859243Sobrien * Extend the gl_pathv member of a glob_t structure to accomodate a new item, 65959243Sobrien * add the new item, and update gl_pathc. 66059243Sobrien * 66159243Sobrien * This assumes the BSD realloc, which only copies the block when its size 66259243Sobrien * crosses a power-of-two boundary; for v7 realloc, this would cause quadratic 66359243Sobrien * behavior. 66459243Sobrien * 66559243Sobrien * Return 0 if new item added, error code if memory couldn't be allocated. 66659243Sobrien * 66759243Sobrien * Invariant of the glob_t structure: 66859243Sobrien * Either gl_pathc is zero and gl_pathv is NULL; or gl_pathc > 0 and 66959243Sobrien * gl_pathv points to (gl_offs + gl_pathc + 1) items. 67059243Sobrien */ 671167465Smpstatic void 672167465Smpglobextend(const char *path, glob_t *pglob) 67359243Sobrien{ 674145479Smp char **pathv; 675145479Smp int i; 676167465Smp size_t newsize; 67759243Sobrien 67859243Sobrien newsize = sizeof(*pathv) * (2 + pglob->gl_pathc + pglob->gl_offs); 679167465Smp pathv = xrealloc(pglob->gl_pathv, newsize); 68059243Sobrien 68159243Sobrien if (pglob->gl_pathv == NULL && pglob->gl_offs > 0) { 68259243Sobrien /* first time around -- clear initial gl_offs items */ 68359243Sobrien pathv += pglob->gl_offs; 68459243Sobrien for (i = pglob->gl_offs; --i >= 0;) 68559243Sobrien *--pathv = NULL; 68659243Sobrien } 68759243Sobrien pglob->gl_pathv = pathv; 68859243Sobrien 689167465Smp pathv[pglob->gl_offs + pglob->gl_pathc++] = strsave(path); 69059243Sobrien pathv[pglob->gl_offs + pglob->gl_pathc] = NULL; 69159243Sobrien} 69259243Sobrien 69359243Sobrien/* 69459243Sobrien * pattern matching function for filenames. Each occurrence of the * 69559243Sobrien * pattern causes a recursion level. 69659243Sobrien */ 69759243Sobrienstatic int 698167465Smpmatch(const char *name, const Char *pat, const Char *patend, int m_not) 69959243Sobrien{ 70059243Sobrien int ok, negate_range; 701167465Smp Char c; 70259243Sobrien 70359243Sobrien while (pat < patend) { 704145479Smp size_t lwk; 705167465Smp __Char wc, wk; 706145479Smp 707145479Smp c = *pat; /* Only for M_MASK bits */ 708167465Smp pat += One_Char_mbtowc(&wc, pat, MB_LEN_MAX); 709167465Smp lwk = one_mbtowc(&wk, name, MB_LEN_MAX); 71059243Sobrien switch (c & M_MASK) { 71159243Sobrien case M_ALL: 712231990Smp while (pat < patend && (*pat & M_MASK) == M_ALL) /* eat consecutive '*' */ 713231990Smp pat += One_Char_mbtowc(&wc, pat, MB_LEN_MAX); 71459243Sobrien if (pat == patend) 715231990Smp return (1); 716231990Smp while (!match(name, pat, patend, m_not)) { 717145479Smp if (*name == EOS) 718231990Smp return (0); 719145479Smp name += lwk; 720167465Smp lwk = one_mbtowc(&wk, name, MB_LEN_MAX); 721145479Smp } 722231990Smp return (1); 72359243Sobrien case M_ONE: 724145479Smp if (*name == EOS) 72559243Sobrien return (0); 726145479Smp name += lwk; 72759243Sobrien break; 72859243Sobrien case M_SET: 72959243Sobrien ok = 0; 730145479Smp if (*name == EOS) 73159243Sobrien return (0); 732145479Smp name += lwk; 73359243Sobrien if ((negate_range = ((*pat & M_MASK) == m_not)) != 0) 73459243Sobrien ++pat; 735145479Smp while ((*pat & M_MASK) != M_END) { 736167465Smp pat += One_Char_mbtowc(&wc, pat, MB_LEN_MAX); 73759243Sobrien if ((*pat & M_MASK) == M_RNG) { 738167465Smp __Char wc2; 739167465Smp 740145479Smp pat++; 741167465Smp pat += One_Char_mbtowc(&wc2, pat, MB_LEN_MAX); 742145479Smp if (globcharcoll(wc, wk, 0) <= 0 && 743145479Smp globcharcoll(wk, wc2, 0) <= 0) 74459243Sobrien ok = 1; 745145479Smp } else if (wc == wk) 74659243Sobrien ok = 1; 74759243Sobrien } 748167465Smp pat += One_Char_mbtowc(&wc, pat, MB_LEN_MAX); 74959243Sobrien if (ok == negate_range) 75059243Sobrien return (0); 75159243Sobrien break; 75259243Sobrien default: 753231990Smp if (*name == EOS || samecase(wk) != samecase(wc)) 754231990Smp return (0); 755145479Smp name += lwk; 75659243Sobrien break; 75759243Sobrien } 75859243Sobrien } 75959243Sobrien return (*name == EOS); 76059243Sobrien} 76159243Sobrien 76259243Sobrien/* free allocated data belonging to a glob_t structure */ 76359243Sobrienvoid 764167465Smpglobfree(glob_t *pglob) 76559243Sobrien{ 766145479Smp int i; 767145479Smp char **pp; 76859243Sobrien 76959243Sobrien if (pglob->gl_pathv != NULL) { 77059243Sobrien pp = pglob->gl_pathv + pglob->gl_offs; 77159243Sobrien for (i = pglob->gl_pathc; i--; ++pp) 77259243Sobrien if (*pp) 773167465Smp xfree(*pp), *pp = NULL; 774167465Smp xfree(pglob->gl_pathv), pglob->gl_pathv = NULL; 77559243Sobrien } 77659243Sobrien} 777