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 62316957Sdchagin#ifndef HAVE_MBLEN 63316957Sdchagin#undef mblen 64316957Sdchagin#define mblen(_s,_n) mbrlen((_s),(_n),NULL) 65316957Sdchagin#endif 66316957Sdchagin 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 103354195Sbrooksstatic void qprintf (const char *, 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 { 150304276Sache#ifndef __FreeBSD__ 151145479Smp /* This should not be here, but I'll rather leave it in than engage in 152145479Smp a LC_COLLATE flamewar about a shell I don't use... */ 153145479Smp if (iswlower(c1) && iswupper(c2)) 154145479Smp return (1); 155145479Smp if (iswupper(c1) && iswlower(c2)) 156145479Smp return (-1); 157304276Sache#endif 158145479Smp } 159145479Smp s1[0] = c1; 160145479Smp s2[0] = c2; 161145479Smp s1[1] = s2[1] = '\0'; 162145479Smp return wcscoll(s1, s2); 163167465Smp# else /* not WIDE_STRINGS */ 16459243Sobrien char s1[2], s2[2]; 16559243Sobrien 16659243Sobrien if (c1 == c2) 16759243Sobrien return (0); 16859415Sobrien /* 16959415Sobrien * From kevin lyda <kevin@suberic.net>: 17059415Sobrien * strcoll does not guarantee case sorting, so we pre-process now: 17159415Sobrien */ 172131962Smp if (cs) { 173131962Smp c1 = islower(c1) ? c1 : tolower(c1); 174131962Smp c2 = islower(c2) ? c2 : tolower(c2); 175131962Smp } else { 176131962Smp if (islower(c1) && isupper(c2)) 177131962Smp return (1); 178145479Smp if (isupper(c1) && islower(c2)) 179145479Smp return (-1); 180131962Smp } 18159243Sobrien s1[0] = c1; 18259243Sobrien s2[0] = c2; 18359243Sobrien s1[1] = s2[1] = '\0'; 18459243Sobrien return strcoll(s1, s2); 185145479Smp# endif 18659243Sobrien#else 18759243Sobrien return (c1 - c2); 18859243Sobrien#endif 18959243Sobrien} 19059243Sobrien 19159243Sobrien/* 19259243Sobrien * Need to dodge two kernel bugs: 19359243Sobrien * opendir("") != opendir(".") 19459243Sobrien * NAMEI_BUG: on plain files trailing slashes are ignored in some kernels. 19559243Sobrien * POSIX specifies that they should be ignored in directories. 19659243Sobrien */ 19759243Sobrien 19859243Sobrienstatic DIR * 199167465SmpOpendir(const char *str) 20059243Sobrien{ 20159243Sobrien#if defined(hpux) || defined(__hpux) 20259243Sobrien struct stat st; 20359243Sobrien#endif 20459243Sobrien 20559243Sobrien if (!*str) 20659243Sobrien return (opendir(".")); 20759243Sobrien#if defined(hpux) || defined(__hpux) 20859243Sobrien /* 20959243Sobrien * Opendir on some device files hangs, so avoid it 21059243Sobrien */ 211167465Smp if (stat(str, &st) == -1 || !S_ISDIR(st.st_mode)) 21259243Sobrien return NULL; 21359243Sobrien#endif 214167465Smp return opendir(str); 21559243Sobrien} 21659243Sobrien 21759243Sobrien#ifdef S_IFLNK 21859243Sobrienstatic int 219167465SmpLstat(const char *fn, struct stat *sb) 22059243Sobrien{ 221167465Smp int st; 22259243Sobrien 223167465Smp st = lstat(fn, sb); 22459243Sobrien# ifdef NAMEI_BUG 225167465Smp if (*fn != 0 && strend(fn)[-1] == '/' && !S_ISDIR(sb->st_mode)) 226167465Smp st = -1; 22759243Sobrien# endif /* NAMEI_BUG */ 228167465Smp return st; 22959243Sobrien} 23059243Sobrien#else 23159243Sobrien#define Lstat Stat 23259243Sobrien#endif /* S_IFLNK */ 23359243Sobrien 23459243Sobrienstatic int 235167465SmpStat(const char *fn, struct stat *sb) 23659243Sobrien{ 237167465Smp int st; 23859243Sobrien 239167465Smp st = stat(fn, sb); 24059243Sobrien#ifdef NAMEI_BUG 241167465Smp if (*fn != 0 && strend(fn)[-1] == '/' && !S_ISDIR(sb->st_mode)) 242167465Smp st = -1; 24359243Sobrien#endif /* NAMEI_BUG */ 244167465Smp return st; 24559243Sobrien} 24659243Sobrien 24759243Sobrienstatic Char * 248167465SmpStrchr(Char *str, int ch) 24959243Sobrien{ 25059243Sobrien do 25159243Sobrien if (*str == ch) 25259243Sobrien return (str); 25359243Sobrien while (*str++); 25459243Sobrien return (NULL); 25559243Sobrien} 25659243Sobrien 25759243Sobrien#ifdef DEBUG 25859243Sobrienstatic void 259354195Sbrooksqprintf(const char *pre, const Char *s) 26059243Sobrien{ 261167465Smp const Char *p; 262354195Sbrooks 263354195Sbrooks xprintf("%s", pre); 26459243Sobrien for (p = s; *p; p++) 265354195Sbrooks xprintf("%c", *p & 0xff); 266354195Sbrooks xprintf("\n%s", pre); 26759243Sobrien for (p = s; *p; p++) 268354195Sbrooks xprintf("%c", *p & M_PROTECT ? '"' : ' '); 269354195Sbrooks xprintf("\n%s", pre); 27059243Sobrien for (p = s; *p; p++) 271354195Sbrooks xprintf("%c", *p & M_META ? '_' : ' '); 272354195Sbrooks xprintf("\n"); 27359243Sobrien} 27459243Sobrien#endif /* DEBUG */ 27559243Sobrien 27659243Sobrienstatic int 277167465Smpcompare(const void *p, const void *q) 27859243Sobrien{ 279167465Smp#if defined(NLS) && defined(HAVE_STRCOLL) 280167465Smp return (strcoll(*(char *const *) p, *(char *const *) q)); 28159243Sobrien#else 282167465Smp return (strcmp(*(char *const *) p, *(char *const *) q)); 283167465Smp#endif /* NLS && HAVE_STRCOLL */ 28459243Sobrien} 28559243Sobrien 28659243Sobrien/* 28759243Sobrien * The main glob() routine: compiles the pattern (optionally processing 28859243Sobrien * quotes), calls glob1() to do the real pattern matching, and finally 28959243Sobrien * sorts the list (unless unsorted operation is requested). Returns 0 29059243Sobrien * if things went well, nonzero if errors occurred. It is not an error 29159243Sobrien * to find no matches. 29259243Sobrien */ 29359243Sobrienint 294167465Smpglob(const char *pattern, int flags, int (*errfunc) (const char *, int), 295167465Smp glob_t *pglob) 29659243Sobrien{ 29759243Sobrien int err, oldpathc; 298167465Smp Char *bufnext, m_not; 299167465Smp const unsigned char *patnext; 30059243Sobrien int c, not; 301167465Smp Char *qpatnext, *patbuf; 30259243Sobrien int no_match; 30359243Sobrien 304145479Smp patnext = (const unsigned char *) pattern; 30559243Sobrien if (!(flags & GLOB_APPEND)) { 30659243Sobrien pglob->gl_pathc = 0; 30759243Sobrien pglob->gl_pathv = NULL; 30859243Sobrien if (!(flags & GLOB_DOOFFS)) 30959243Sobrien pglob->gl_offs = 0; 31059243Sobrien } 31159243Sobrien pglob->gl_flags = flags & ~GLOB_MAGCHAR; 31259243Sobrien pglob->gl_errfunc = errfunc; 31359243Sobrien oldpathc = pglob->gl_pathc; 31459243Sobrien pglob->gl_matchc = 0; 31559243Sobrien 31659243Sobrien if (pglob->gl_flags & GLOB_ALTNOT) { 31759243Sobrien not = ALTNOT; 31859243Sobrien m_not = M_ALTNOT; 31959243Sobrien } 32059243Sobrien else { 32159243Sobrien not = NOT; 32259243Sobrien m_not = M_NOT; 32359243Sobrien } 32459243Sobrien 325167465Smp patbuf = xmalloc((strlen(pattern) + 1) * sizeof(*patbuf)); 32659243Sobrien bufnext = patbuf; 32759243Sobrien 32859243Sobrien no_match = *patnext == not; 32959243Sobrien if (no_match) 33059243Sobrien patnext++; 33159243Sobrien 33259243Sobrien if (flags & GLOB_QUOTE) { 33359243Sobrien /* Protect the quoted characters */ 334167465Smp while ((c = *patnext++) != EOS) { 335145479Smp#ifdef WIDE_STRINGS 336145479Smp int len; 337145479Smp 338145479Smp len = mblen((const char *)(patnext - 1), MB_LEN_MAX); 339145479Smp if (len == -1) 340231990Smp TCSH_IGNORE(mblen(NULL, 0)); 341195609Smp else if (len > 1) { 342145479Smp *bufnext++ = (Char) c; 343145479Smp while (--len != 0) 344145479Smp *bufnext++ = (Char) (*patnext++ | M_PROTECT); 345145479Smp } else 346145479Smp#endif /* WIDE_STRINGS */ 34759243Sobrien if (c == QUOTE) { 34859243Sobrien if ((c = *patnext++) == EOS) { 34959243Sobrien c = QUOTE; 35059243Sobrien --patnext; 35159243Sobrien } 35259243Sobrien *bufnext++ = (Char) (c | M_PROTECT); 35359243Sobrien } 35459243Sobrien else 35559243Sobrien *bufnext++ = (Char) c; 356145479Smp } 35759243Sobrien } 358167465Smp else 359167465Smp while ((c = *patnext++) != EOS) 36059243Sobrien *bufnext++ = (Char) c; 36159243Sobrien *bufnext = EOS; 36259243Sobrien 36359243Sobrien bufnext = patbuf; 36459243Sobrien qpatnext = patbuf; 36559243Sobrien while ((c = *qpatnext++) != EOS) { 36659243Sobrien switch (c) { 36759243Sobrien case LBRACKET: 36859243Sobrien c = *qpatnext; 36959243Sobrien if (c == not) 37059243Sobrien ++qpatnext; 37159243Sobrien if (*qpatnext == EOS || 37259243Sobrien Strchr(qpatnext + 1, RBRACKET) == NULL) { 37359243Sobrien *bufnext++ = LBRACKET; 37459243Sobrien if (c == not) 37559243Sobrien --qpatnext; 37659243Sobrien break; 37759243Sobrien } 37859243Sobrien pglob->gl_flags |= GLOB_MAGCHAR; 37959243Sobrien *bufnext++ = M_SET; 38059243Sobrien if (c == not) 38159243Sobrien *bufnext++ = m_not; 38259243Sobrien c = *qpatnext++; 38359243Sobrien do { 384167465Smp *bufnext++ = LCHAR(c); 38559243Sobrien if (*qpatnext == RANGE && 38659243Sobrien (c = qpatnext[1]) != RBRACKET) { 38759243Sobrien *bufnext++ = M_RNG; 388167465Smp *bufnext++ = LCHAR(c); 38959243Sobrien qpatnext += 2; 39059243Sobrien } 39159243Sobrien } while ((c = *qpatnext++) != RBRACKET); 39259243Sobrien *bufnext++ = M_END; 39359243Sobrien break; 39459243Sobrien case QUESTION: 39559243Sobrien pglob->gl_flags |= GLOB_MAGCHAR; 39659243Sobrien *bufnext++ = M_ONE; 39759243Sobrien break; 39859243Sobrien case STAR: 39959243Sobrien pglob->gl_flags |= GLOB_MAGCHAR; 400231990Smp /* collapse adjacent stars to one [or three if globstar], 401231990Smp * to avoid exponential behavior 40259243Sobrien */ 403231990Smp if (bufnext == patbuf || bufnext[-1] != M_ALL || 404231990Smp ((flags & GLOB_STAR) != 0 && 405231990Smp (bufnext - 1 == patbuf || bufnext[-2] != M_ALL || 406231990Smp bufnext - 2 == patbuf || bufnext[-3] != M_ALL))) 40759243Sobrien *bufnext++ = M_ALL; 40859243Sobrien break; 40959243Sobrien default: 410167465Smp *bufnext++ = LCHAR(c); 41159243Sobrien break; 41259243Sobrien } 41359243Sobrien } 41459243Sobrien *bufnext = EOS; 41559243Sobrien#ifdef DEBUG 416354195Sbrooks qprintf("patbuf=", patbuf); 41759243Sobrien#endif 41859243Sobrien 419167465Smp if ((err = glob1(patbuf, pglob, no_match)) != 0) { 420167465Smp xfree(patbuf); 42159243Sobrien return (err); 422167465Smp } 42359243Sobrien 42459243Sobrien /* 42559243Sobrien * If there was no match we are going to append the pattern 42659243Sobrien * if GLOB_NOCHECK was specified or if GLOB_NOMAGIC was specified 42759243Sobrien * and the pattern did not contain any magic characters 42859243Sobrien * GLOB_NOMAGIC is there just for compatibility with csh. 42959243Sobrien */ 43059243Sobrien if (pglob->gl_pathc == oldpathc && 43159243Sobrien ((flags & GLOB_NOCHECK) || 43259243Sobrien ((flags & GLOB_NOMAGIC) && !(pglob->gl_flags & GLOB_MAGCHAR)))) { 433167465Smp if (!(flags & GLOB_QUOTE)) 434167465Smp globextend(pattern, pglob); 435167465Smp else { 436167465Smp char *copy, *dest; 437167465Smp const char *src; 43859243Sobrien 439167465Smp /* copy pattern, interpreting quotes */ 440167465Smp copy = xmalloc(strlen(pattern) + 1); 441167465Smp dest = copy; 442167465Smp src = pattern; 443167465Smp while (*src != EOS) { 444316957Sdchagin /* Don't interpret quotes. The spec does not say we should do */ 445167465Smp if (*src == QUOTE) { 446167465Smp if (*++src == EOS) 447167465Smp --src; 44859243Sobrien } 449167465Smp *dest++ = *src++; 45059243Sobrien } 451167465Smp *dest = EOS; 452167465Smp globextend(copy, pglob); 453167465Smp xfree(copy); 45459243Sobrien } 455167465Smp xfree(patbuf); 456167465Smp return 0; 45759243Sobrien } 45859415Sobrien else if (!(flags & GLOB_NOSORT) && (pglob->gl_pathc != oldpathc)) 459167465Smp qsort(pglob->gl_pathv + pglob->gl_offs + oldpathc, 460167465Smp pglob->gl_pathc - oldpathc, sizeof(char *), compare); 461167465Smp xfree(patbuf); 46259243Sobrien return (0); 46359243Sobrien} 46459243Sobrien 46559243Sobrienstatic int 466167465Smpglob1(Char *pattern, glob_t *pglob, int no_match) 46759243Sobrien{ 468167465Smp struct strbuf pathbuf = strbuf_INIT; 469167465Smp int err; 47059243Sobrien 47159243Sobrien /* 47259243Sobrien * a null pathname is invalid -- POSIX 1003.1 sect. 2.4. 47359243Sobrien */ 47459243Sobrien if (*pattern == EOS) 47559243Sobrien return (0); 476167465Smp err = glob2(&pathbuf, pattern, pglob, no_match); 477167465Smp xfree(pathbuf.s); 478167465Smp return err; 47959243Sobrien} 48059243Sobrien 48159243Sobrien/* 48259243Sobrien * functions glob2 and glob3 are mutually recursive; there is one level 48359243Sobrien * of recursion for each segment in the pattern that contains one or 48459243Sobrien * more meta characters. 48559243Sobrien */ 48659243Sobrienstatic int 487167465Smpglob2(struct strbuf *pathbuf, const Char *pattern, glob_t *pglob, int no_match) 48859243Sobrien{ 48959243Sobrien struct stat sbuf; 49059243Sobrien int anymeta; 491167465Smp const Char *p; 492167465Smp size_t orig_len; 49359243Sobrien 49459243Sobrien /* 49559243Sobrien * loop over pattern segments until end of pattern or until segment with 49659243Sobrien * meta character found. 49759243Sobrien */ 49859243Sobrien anymeta = 0; 49959243Sobrien for (;;) { 50059243Sobrien if (*pattern == EOS) { /* end of pattern? */ 501167465Smp strbuf_terminate(pathbuf); 50259243Sobrien 503167465Smp if (Lstat(pathbuf->s, &sbuf)) 50459243Sobrien return (0); 50559243Sobrien 50659243Sobrien if (((pglob->gl_flags & GLOB_MARK) && 507167465Smp pathbuf->s[pathbuf->len - 1] != SEP) && 50859243Sobrien (S_ISDIR(sbuf.st_mode) 50959243Sobrien#ifdef S_IFLNK 51059243Sobrien || (S_ISLNK(sbuf.st_mode) && 511167465Smp (Stat(pathbuf->s, &sbuf) == 0) && 51259243Sobrien S_ISDIR(sbuf.st_mode)) 51359243Sobrien#endif 51459243Sobrien )) { 515167465Smp strbuf_append1(pathbuf, SEP); 516167465Smp strbuf_terminate(pathbuf); 51759243Sobrien } 51859243Sobrien ++pglob->gl_matchc; 519167465Smp globextend(pathbuf->s, pglob); 520167465Smp return 0; 52159243Sobrien } 52259243Sobrien 523167465Smp /* find end of next segment, tentatively copy to pathbuf */ 52459243Sobrien p = pattern; 525167465Smp orig_len = pathbuf->len; 52659243Sobrien while (*p != EOS && *p != SEP) { 52759243Sobrien if (ismeta(*p)) 52859243Sobrien anymeta = 1; 529167465Smp strbuf_append1(pathbuf, *p++); 53059243Sobrien } 53159243Sobrien 53259243Sobrien if (!anymeta) { /* no expansion, do next segment */ 53359243Sobrien pattern = p; 53459243Sobrien while (*pattern == SEP) 535167465Smp strbuf_append1(pathbuf, *pattern++); 53659243Sobrien } 537167465Smp else { /* need expansion, recurse */ 538167465Smp pathbuf->len = orig_len; 539231990Smp return (glob3(pathbuf, pattern, p, pattern, pglob, no_match)); 540167465Smp } 54159243Sobrien } 54259243Sobrien /* NOTREACHED */ 54359243Sobrien} 54459243Sobrien 545231990Smpstatic size_t 546231990SmpOne_Char_mbtowc(__Char *pwc, const Char *s, size_t n) 547231990Smp{ 548231990Smp#ifdef WIDE_STRINGS 549231990Smp char buf[MB_LEN_MAX], *p; 55059243Sobrien 551231990Smp if (n > MB_LEN_MAX) 552231990Smp n = MB_LEN_MAX; 553231990Smp p = buf; 554231990Smp while (p < buf + n && (*p++ = LCHAR(*s++)) != 0) 555231990Smp ; 556231990Smp return one_mbtowc(pwc, buf, n); 557231990Smp#else 558231990Smp *pwc = *s & CHAR; 559231990Smp return 1; 560231990Smp#endif 561231990Smp} 562231990Smp 56359243Sobrienstatic int 564167465Smpglob3(struct strbuf *pathbuf, const Char *pattern, const Char *restpattern, 565231990Smp const Char *pglobstar, glob_t *pglob, int no_match) 56659243Sobrien{ 56759243Sobrien DIR *dirp; 56859243Sobrien struct dirent *dp; 569231990Smp struct stat sbuf; 57059243Sobrien int err; 57159243Sobrien Char m_not = (pglob->gl_flags & GLOB_ALTNOT) ? M_ALTNOT : M_NOT; 572167465Smp size_t orig_len; 573231990Smp int globstar = 0; 574231990Smp int chase_symlinks = 0; 575231990Smp const Char *termstar = NULL; 57659243Sobrien 577167465Smp strbuf_terminate(pathbuf); 578231990Smp orig_len = pathbuf->len; 579231990Smp errno = err = 0; 58059243Sobrien 581231990Smp while (pglobstar < restpattern) { 582231990Smp __Char wc; 583231990Smp size_t width = One_Char_mbtowc(&wc, pglobstar, MB_LEN_MAX); 584231990Smp if ((pglobstar[0] & M_MASK) == M_ALL && 585231990Smp (pglobstar[width] & M_MASK) == M_ALL) { 586231990Smp globstar = 1; 587231990Smp chase_symlinks = (pglobstar[2 * width] & M_MASK) == M_ALL; 588231990Smp termstar = pglobstar + (2 + chase_symlinks) * width; 589231990Smp break; 590231990Smp } 591231990Smp pglobstar += width; 592231990Smp } 593231990Smp 594231990Smp if (globstar) { 595231990Smp err = pglobstar==pattern && termstar==restpattern ? 596231990Smp *restpattern == EOS ? 597231990Smp glob2(pathbuf, restpattern - 1, pglob, no_match) : 598231990Smp glob2(pathbuf, restpattern + 1, pglob, no_match) : 599231990Smp glob3(pathbuf, pattern, restpattern, termstar, pglob, no_match); 600231990Smp if (err) 601231990Smp return err; 602231990Smp pathbuf->len = orig_len; 603231990Smp strbuf_terminate(pathbuf); 604231990Smp } 605231990Smp 606231990Smp if (*pathbuf->s && (Lstat(pathbuf->s, &sbuf) || !S_ISDIR(sbuf.st_mode) 607231990Smp#ifdef S_IFLINK 608231990Smp && ((globstar && !chase_symlinks) || !S_ISLNK(sbuf.st_mode)) 609231990Smp#endif 610231990Smp )) 611231990Smp return 0; 612231990Smp 613167465Smp if (!(dirp = Opendir(pathbuf->s))) { 61459243Sobrien /* todo: don't call for ENOENT or ENOTDIR? */ 615167465Smp if ((pglob->gl_errfunc && (*pglob->gl_errfunc) (pathbuf->s, errno)) || 61659243Sobrien (pglob->gl_flags & GLOB_ERR)) 61759243Sobrien return (GLOB_ABEND); 61859243Sobrien else 61959243Sobrien return (0); 62059243Sobrien } 62159243Sobrien 62259243Sobrien /* search directory for matching names */ 62359243Sobrien while ((dp = readdir(dirp)) != NULL) { 62459243Sobrien /* initial DOT must be matched literally */ 62559243Sobrien if (dp->d_name[0] == DOT && *pattern != DOT) 626231990Smp if (!(pglob->gl_flags & GLOB_DOT) || !dp->d_name[1] || 627231990Smp (dp->d_name[1] == DOT && !dp->d_name[2])) 628231990Smp continue; /*unless globdot and not . or .. */ 629167465Smp pathbuf->len = orig_len; 630167465Smp strbuf_append(pathbuf, dp->d_name); 631167465Smp strbuf_terminate(pathbuf); 632231990Smp 633231990Smp if (globstar) { 634231990Smp#ifdef S_IFLNK 635231990Smp if (!chase_symlinks && 636231990Smp (Lstat(pathbuf->s, &sbuf) || S_ISLNK(sbuf.st_mode))) 637231990Smp continue; 638231990Smp#endif 639231990Smp if (match(pathbuf->s + orig_len, pattern, termstar, 640231990Smp (int)m_not) == no_match) 641231990Smp continue; 642231990Smp strbuf_append1(pathbuf, SEP); 643231990Smp strbuf_terminate(pathbuf); 644231990Smp if ((err = glob2(pathbuf, pglobstar, pglob, no_match)) != 0) 645231990Smp break; 646231990Smp } else { 647231990Smp if (match(pathbuf->s + orig_len, pattern, restpattern, 648231990Smp (int) m_not) == no_match) 649231990Smp continue; 650231990Smp if ((err = glob2(pathbuf, restpattern, pglob, no_match)) != 0) 651231990Smp break; 652231990Smp } 65359243Sobrien } 65459243Sobrien /* todo: check error from readdir? */ 655167465Smp closedir(dirp); 65659243Sobrien return (err); 65759243Sobrien} 65859243Sobrien 65959243Sobrien 66059243Sobrien/* 66159243Sobrien * Extend the gl_pathv member of a glob_t structure to accomodate a new item, 66259243Sobrien * add the new item, and update gl_pathc. 66359243Sobrien * 66459243Sobrien * This assumes the BSD realloc, which only copies the block when its size 66559243Sobrien * crosses a power-of-two boundary; for v7 realloc, this would cause quadratic 66659243Sobrien * behavior. 66759243Sobrien * 66859243Sobrien * Return 0 if new item added, error code if memory couldn't be allocated. 66959243Sobrien * 67059243Sobrien * Invariant of the glob_t structure: 67159243Sobrien * Either gl_pathc is zero and gl_pathv is NULL; or gl_pathc > 0 and 67259243Sobrien * gl_pathv points to (gl_offs + gl_pathc + 1) items. 67359243Sobrien */ 674167465Smpstatic void 675167465Smpglobextend(const char *path, glob_t *pglob) 67659243Sobrien{ 677145479Smp char **pathv; 678145479Smp int i; 679167465Smp size_t newsize; 68059243Sobrien 68159243Sobrien newsize = sizeof(*pathv) * (2 + pglob->gl_pathc + pglob->gl_offs); 682167465Smp pathv = xrealloc(pglob->gl_pathv, newsize); 68359243Sobrien 68459243Sobrien if (pglob->gl_pathv == NULL && pglob->gl_offs > 0) { 68559243Sobrien /* first time around -- clear initial gl_offs items */ 68659243Sobrien pathv += pglob->gl_offs; 68759243Sobrien for (i = pglob->gl_offs; --i >= 0;) 68859243Sobrien *--pathv = NULL; 68959243Sobrien } 69059243Sobrien pglob->gl_pathv = pathv; 69159243Sobrien 692167465Smp pathv[pglob->gl_offs + pglob->gl_pathc++] = strsave(path); 69359243Sobrien pathv[pglob->gl_offs + pglob->gl_pathc] = NULL; 69459243Sobrien} 69559243Sobrien 69659243Sobrien/* 697354195Sbrooks * pattern matching function for filenames. 69859243Sobrien */ 69959243Sobrienstatic int 700167465Smpmatch(const char *name, const Char *pat, const Char *patend, int m_not) 70159243Sobrien{ 70259243Sobrien int ok, negate_range; 703354195Sbrooks const Char *patNext; 704354195Sbrooks const char *nameNext, *nameStart, *nameEnd; 705167465Smp Char c; 70659243Sobrien 707354195Sbrooks patNext = pat; 708354195Sbrooks nameStart = nameNext = name; 709354195Sbrooks nameEnd = NULL; 710145479Smp 711354195Sbrooks while (pat < patend || *name) { 712354195Sbrooks size_t lwk, pwk; 713354195Sbrooks __Char wc, wk, wc1; 714354195Sbrooks 715145479Smp c = *pat; /* Only for M_MASK bits */ 716354195Sbrooks if (*name == EOS) 717354195Sbrooks nameEnd = name; 718354195Sbrooks 719354195Sbrooks pwk = One_Char_mbtowc(&wc, pat, MB_LEN_MAX); 720167465Smp lwk = one_mbtowc(&wk, name, MB_LEN_MAX); 72159243Sobrien switch (c & M_MASK) { 72259243Sobrien case M_ALL: 723354195Sbrooks while ((*(pat + pwk) & M_MASK) == M_ALL) { 724354195Sbrooks pat += pwk; 725354195Sbrooks pwk = One_Char_mbtowc(&wc, pat, MB_LEN_MAX); 726145479Smp } 727354195Sbrooks patNext = pat; 728354195Sbrooks nameNext = name + lwk; 729354195Sbrooks pat += pwk; 730354195Sbrooks continue; 73159243Sobrien case M_ONE: 732145479Smp if (*name == EOS) 733354195Sbrooks break; 734145479Smp name += lwk; 735354195Sbrooks pat += pwk; 736354195Sbrooks continue; 73759243Sobrien case M_SET: 73859243Sobrien ok = 0; 739145479Smp if (*name == EOS) 740354195Sbrooks break; 741354195Sbrooks pat += pwk; 742354195Sbrooks pwk = One_Char_mbtowc(&wc, pat, MB_LEN_MAX); 743145479Smp name += lwk; 744354195Sbrooks if ((negate_range = ((*pat & M_MASK) == m_not)) != 0) { 745354195Sbrooks pat += pwk; 746354195Sbrooks pwk = One_Char_mbtowc(&wc, pat, MB_LEN_MAX); 747354195Sbrooks } 748354195Sbrooks wc1 = wc; 749145479Smp while ((*pat & M_MASK) != M_END) { 75059243Sobrien if ((*pat & M_MASK) == M_RNG) { 751167465Smp __Char wc2; 752167465Smp 753354195Sbrooks pat += pwk; 754354195Sbrooks pwk = One_Char_mbtowc(&wc2, pat, MB_LEN_MAX); 755354195Sbrooks if (globcharcoll(wc1, wk, 0) <= 0 && 756145479Smp globcharcoll(wk, wc2, 0) <= 0) 75759243Sobrien ok = 1; 758145479Smp } else if (wc == wk) 75959243Sobrien ok = 1; 760354195Sbrooks pat += pwk; 761354195Sbrooks wc1 = wc; 762354195Sbrooks pwk = One_Char_mbtowc(&wc, pat, MB_LEN_MAX); 76359243Sobrien } 764354195Sbrooks pat += pwk; 765354195Sbrooks pwk = One_Char_mbtowc(&wc, pat, MB_LEN_MAX); 76659243Sobrien if (ok == negate_range) 767354195Sbrooks break; 768354195Sbrooks continue; 76959243Sobrien default: 770231990Smp if (*name == EOS || samecase(wk) != samecase(wc)) 771354195Sbrooks break; 772145479Smp name += lwk; 773354195Sbrooks pat += pwk; 774354195Sbrooks continue; 77559243Sobrien } 776354195Sbrooks if (nameNext != nameStart 777354195Sbrooks && (nameEnd == NULL || nameNext <= nameEnd)) { 778354195Sbrooks pat = patNext; 779354195Sbrooks name = nameNext; 780354195Sbrooks continue; 781354195Sbrooks } 782354195Sbrooks return 0; 78359243Sobrien } 784354195Sbrooks return 1; 78559243Sobrien} 78659243Sobrien 78759243Sobrien/* free allocated data belonging to a glob_t structure */ 78859243Sobrienvoid 789167465Smpglobfree(glob_t *pglob) 79059243Sobrien{ 791145479Smp int i; 792145479Smp char **pp; 79359243Sobrien 79459243Sobrien if (pglob->gl_pathv != NULL) { 79559243Sobrien pp = pglob->gl_pathv + pglob->gl_offs; 79659243Sobrien for (i = pglob->gl_pathc; i--; ++pp) 79759243Sobrien if (*pp) 798167465Smp xfree(*pp), *pp = NULL; 799167465Smp xfree(pglob->gl_pathv), pglob->gl_pathv = NULL; 80059243Sobrien } 80159243Sobrien} 802