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 6259243Sobrien#undef Char 6359243Sobrien#undef QUOTE 6459243Sobrien#undef TILDE 6559243Sobrien#undef META 6659243Sobrien#undef ismeta 6759243Sobrien#undef Strchr 6859243Sobrien 6959243Sobrien#ifndef S_ISDIR 7059243Sobrien#define S_ISDIR(a) (((a) & S_IFMT) == S_IFDIR) 7159243Sobrien#endif 7259243Sobrien 7359243Sobrien#if !defined(S_ISLNK) && defined(S_IFLNK) 7459243Sobrien#define S_ISLNK(a) (((a) & S_IFMT) == S_IFLNK) 7559243Sobrien#endif 7659243Sobrien 7759243Sobrien#if !defined(S_ISLNK) && !defined(lstat) 7859243Sobrien#define lstat stat 7959243Sobrien#endif 8059243Sobrien 8159243Sobrientypedef unsigned short Char; 8259243Sobrien 83167465Smpstatic int glob1 (Char *, glob_t *, int); 84167465Smpstatic int glob2 (struct strbuf *, const Char *, glob_t *, int); 85167465Smpstatic int glob3 (struct strbuf *, const Char *, const Char *, 86232633Smp const Char *, glob_t *, int); 87167465Smpstatic void globextend (const char *, glob_t *); 88167465Smpstatic int match (const char *, const Char *, const Char *, 89167465Smp int); 90167465Smpstatic int compare (const void *, const void *); 91167465Smpstatic DIR *Opendir (const char *); 9259243Sobrien#ifdef S_IFLNK 93167465Smpstatic int Lstat (const char *, struct stat *); 9459243Sobrien#endif 95167465Smpstatic int Stat (const char *, struct stat *sb); 96167465Smpstatic Char *Strchr (Char *, int); 9759243Sobrien#ifdef DEBUG 98167465Smpstatic void qprintf (const Char *); 9959243Sobrien#endif 10059243Sobrien 10159243Sobrien#define DOLLAR '$' 10259243Sobrien#define DOT '.' 10359243Sobrien#define EOS '\0' 10459243Sobrien#define LBRACKET '[' 10559243Sobrien#define NOT '!' 10659243Sobrien#define ALTNOT '^' 10759243Sobrien#define QUESTION '?' 10859243Sobrien#define QUOTE '\\' 10959243Sobrien#define RANGE '-' 11059243Sobrien#define RBRACKET ']' 11159243Sobrien#define SEP '/' 11259243Sobrien#define STAR '*' 11359243Sobrien#define TILDE '~' 11459243Sobrien#define UNDERSCORE '_' 11559243Sobrien 11659243Sobrien#define M_META 0x8000 11759243Sobrien#define M_PROTECT 0x4000 11859243Sobrien#define M_MASK 0xffff 11959243Sobrien#define M_ASCII 0x00ff 12059243Sobrien 121167465Smp#define LCHAR(c) ((c)&M_ASCII) 12259243Sobrien#define META(c) ((c)|M_META) 12359243Sobrien#define M_ALL META('*') 12459243Sobrien#define M_END META(']') 12559243Sobrien#define M_NOT META('!') 12659243Sobrien#define M_ALTNOT META('^') 12759243Sobrien#define M_ONE META('?') 12859243Sobrien#define M_RNG META('-') 12959243Sobrien#define M_SET META('[') 13059243Sobrien#define ismeta(c) (((c)&M_META) != 0) 13159243Sobrien 13259243Sobrienint 133167465Smpglobcharcoll(__Char c1, __Char c2, int cs) 13459243Sobrien{ 135167465Smp#if defined(NLS) && defined(LC_COLLATE) && defined(HAVE_STRCOLL) 136167465Smp# if defined(WIDE_STRINGS) 137145479Smp wchar_t s1[2], s2[2]; 138145479Smp 139145479Smp if (c1 == c2) 140145479Smp return (0); 141145479Smp if (cs) { 142145479Smp c1 = towlower(c1); 143145479Smp c2 = towlower(c2); 144145479Smp } else { 145145479Smp /* This should not be here, but I'll rather leave it in than engage in 146145479Smp a LC_COLLATE flamewar about a shell I don't use... */ 147145479Smp if (iswlower(c1) && iswupper(c2)) 148145479Smp return (1); 149145479Smp if (iswupper(c1) && iswlower(c2)) 150145479Smp return (-1); 151145479Smp } 152145479Smp s1[0] = c1; 153145479Smp s2[0] = c2; 154145479Smp s1[1] = s2[1] = '\0'; 155145479Smp return wcscoll(s1, s2); 156167465Smp# else /* not WIDE_STRINGS */ 15759243Sobrien char s1[2], s2[2]; 15859243Sobrien 15959243Sobrien if (c1 == c2) 16059243Sobrien return (0); 16159415Sobrien /* 16259415Sobrien * From kevin lyda <kevin@suberic.net>: 16359415Sobrien * strcoll does not guarantee case sorting, so we pre-process now: 16459415Sobrien */ 165131962Smp if (cs) { 166131962Smp c1 = islower(c1) ? c1 : tolower(c1); 167131962Smp c2 = islower(c2) ? c2 : tolower(c2); 168131962Smp } else { 169131962Smp if (islower(c1) && isupper(c2)) 170131962Smp return (1); 171145479Smp if (isupper(c1) && islower(c2)) 172145479Smp return (-1); 173131962Smp } 17459243Sobrien s1[0] = c1; 17559243Sobrien s2[0] = c2; 17659243Sobrien s1[1] = s2[1] = '\0'; 17759243Sobrien return strcoll(s1, s2); 178145479Smp# endif 17959243Sobrien#else 18059243Sobrien return (c1 - c2); 18159243Sobrien#endif 18259243Sobrien} 18359243Sobrien 18459243Sobrien/* 18559243Sobrien * Need to dodge two kernel bugs: 18659243Sobrien * opendir("") != opendir(".") 18759243Sobrien * NAMEI_BUG: on plain files trailing slashes are ignored in some kernels. 18859243Sobrien * POSIX specifies that they should be ignored in directories. 18959243Sobrien */ 19059243Sobrien 19159243Sobrienstatic DIR * 192167465SmpOpendir(const char *str) 19359243Sobrien{ 19459243Sobrien#if defined(hpux) || defined(__hpux) 19559243Sobrien struct stat st; 19659243Sobrien#endif 19759243Sobrien 19859243Sobrien if (!*str) 19959243Sobrien return (opendir(".")); 20059243Sobrien#if defined(hpux) || defined(__hpux) 20159243Sobrien /* 20259243Sobrien * Opendir on some device files hangs, so avoid it 20359243Sobrien */ 204167465Smp if (stat(str, &st) == -1 || !S_ISDIR(st.st_mode)) 20559243Sobrien return NULL; 20659243Sobrien#endif 207167465Smp return opendir(str); 20859243Sobrien} 20959243Sobrien 21059243Sobrien#ifdef S_IFLNK 21159243Sobrienstatic int 212167465SmpLstat(const char *fn, struct stat *sb) 21359243Sobrien{ 214167465Smp int st; 21559243Sobrien 216167465Smp st = lstat(fn, sb); 21759243Sobrien# ifdef NAMEI_BUG 218167465Smp if (*fn != 0 && strend(fn)[-1] == '/' && !S_ISDIR(sb->st_mode)) 219167465Smp st = -1; 22059243Sobrien# endif /* NAMEI_BUG */ 221167465Smp return st; 22259243Sobrien} 22359243Sobrien#else 22459243Sobrien#define Lstat Stat 22559243Sobrien#endif /* S_IFLNK */ 22659243Sobrien 22759243Sobrienstatic int 228167465SmpStat(const char *fn, struct stat *sb) 22959243Sobrien{ 230167465Smp int st; 23159243Sobrien 232167465Smp st = stat(fn, sb); 23359243Sobrien#ifdef NAMEI_BUG 234167465Smp if (*fn != 0 && strend(fn)[-1] == '/' && !S_ISDIR(sb->st_mode)) 235167465Smp st = -1; 23659243Sobrien#endif /* NAMEI_BUG */ 237167465Smp return st; 23859243Sobrien} 23959243Sobrien 24059243Sobrienstatic Char * 241167465SmpStrchr(Char *str, int ch) 24259243Sobrien{ 24359243Sobrien do 24459243Sobrien if (*str == ch) 24559243Sobrien return (str); 24659243Sobrien while (*str++); 24759243Sobrien return (NULL); 24859243Sobrien} 24959243Sobrien 25059243Sobrien#ifdef DEBUG 25159243Sobrienstatic void 252167465Smpqprintf(const Char *s) 25359243Sobrien{ 254167465Smp const Char *p; 25559243Sobrien 25659243Sobrien for (p = s; *p; p++) 25759243Sobrien printf("%c", *p & 0xff); 25859243Sobrien printf("\n"); 25959243Sobrien for (p = s; *p; p++) 26059243Sobrien printf("%c", *p & M_PROTECT ? '"' : ' '); 26159243Sobrien printf("\n"); 26259243Sobrien for (p = s; *p; p++) 26359243Sobrien printf("%c", *p & M_META ? '_' : ' '); 26459243Sobrien printf("\n"); 26559243Sobrien} 26659243Sobrien#endif /* DEBUG */ 26759243Sobrien 26859243Sobrienstatic int 269167465Smpcompare(const void *p, const void *q) 27059243Sobrien{ 271167465Smp#if defined(NLS) && defined(HAVE_STRCOLL) 272167465Smp return (strcoll(*(char *const *) p, *(char *const *) q)); 27359243Sobrien#else 274167465Smp return (strcmp(*(char *const *) p, *(char *const *) q)); 275167465Smp#endif /* NLS && HAVE_STRCOLL */ 27659243Sobrien} 27759243Sobrien 27859243Sobrien/* 27959243Sobrien * The main glob() routine: compiles the pattern (optionally processing 28059243Sobrien * quotes), calls glob1() to do the real pattern matching, and finally 28159243Sobrien * sorts the list (unless unsorted operation is requested). Returns 0 28259243Sobrien * if things went well, nonzero if errors occurred. It is not an error 28359243Sobrien * to find no matches. 28459243Sobrien */ 28559243Sobrienint 286167465Smpglob(const char *pattern, int flags, int (*errfunc) (const char *, int), 287167465Smp glob_t *pglob) 28859243Sobrien{ 28959243Sobrien int err, oldpathc; 290167465Smp Char *bufnext, m_not; 291167465Smp const unsigned char *patnext; 29259243Sobrien int c, not; 293167465Smp Char *qpatnext, *patbuf; 29459243Sobrien int no_match; 29559243Sobrien 296145479Smp patnext = (const unsigned char *) pattern; 29759243Sobrien if (!(flags & GLOB_APPEND)) { 29859243Sobrien pglob->gl_pathc = 0; 29959243Sobrien pglob->gl_pathv = NULL; 30059243Sobrien if (!(flags & GLOB_DOOFFS)) 30159243Sobrien pglob->gl_offs = 0; 30259243Sobrien } 30359243Sobrien pglob->gl_flags = flags & ~GLOB_MAGCHAR; 30459243Sobrien pglob->gl_errfunc = errfunc; 30559243Sobrien oldpathc = pglob->gl_pathc; 30659243Sobrien pglob->gl_matchc = 0; 30759243Sobrien 30859243Sobrien if (pglob->gl_flags & GLOB_ALTNOT) { 30959243Sobrien not = ALTNOT; 31059243Sobrien m_not = M_ALTNOT; 31159243Sobrien } 31259243Sobrien else { 31359243Sobrien not = NOT; 31459243Sobrien m_not = M_NOT; 31559243Sobrien } 31659243Sobrien 317167465Smp patbuf = xmalloc((strlen(pattern) + 1) * sizeof(*patbuf)); 31859243Sobrien bufnext = patbuf; 31959243Sobrien 32059243Sobrien no_match = *patnext == not; 32159243Sobrien if (no_match) 32259243Sobrien patnext++; 32359243Sobrien 32459243Sobrien if (flags & GLOB_QUOTE) { 32559243Sobrien /* Protect the quoted characters */ 326167465Smp while ((c = *patnext++) != EOS) { 327145479Smp#ifdef WIDE_STRINGS 328145479Smp int len; 329145479Smp 330145479Smp len = mblen((const char *)(patnext - 1), MB_LEN_MAX); 331145479Smp if (len == -1) 332232633Smp TCSH_IGNORE(mblen(NULL, 0)); 333195609Smp else if (len > 1) { 334145479Smp *bufnext++ = (Char) c; 335145479Smp while (--len != 0) 336145479Smp *bufnext++ = (Char) (*patnext++ | M_PROTECT); 337145479Smp } else 338145479Smp#endif /* WIDE_STRINGS */ 33959243Sobrien if (c == QUOTE) { 34059243Sobrien if ((c = *patnext++) == EOS) { 34159243Sobrien c = QUOTE; 34259243Sobrien --patnext; 34359243Sobrien } 34459243Sobrien *bufnext++ = (Char) (c | M_PROTECT); 34559243Sobrien } 34659243Sobrien else 34759243Sobrien *bufnext++ = (Char) c; 348145479Smp } 34959243Sobrien } 350167465Smp else 351167465Smp while ((c = *patnext++) != EOS) 35259243Sobrien *bufnext++ = (Char) c; 35359243Sobrien *bufnext = EOS; 35459243Sobrien 35559243Sobrien bufnext = patbuf; 35659243Sobrien qpatnext = patbuf; 35759243Sobrien while ((c = *qpatnext++) != EOS) { 35859243Sobrien switch (c) { 35959243Sobrien case LBRACKET: 36059243Sobrien c = *qpatnext; 36159243Sobrien if (c == not) 36259243Sobrien ++qpatnext; 36359243Sobrien if (*qpatnext == EOS || 36459243Sobrien Strchr(qpatnext + 1, RBRACKET) == NULL) { 36559243Sobrien *bufnext++ = LBRACKET; 36659243Sobrien if (c == not) 36759243Sobrien --qpatnext; 36859243Sobrien break; 36959243Sobrien } 37059243Sobrien pglob->gl_flags |= GLOB_MAGCHAR; 37159243Sobrien *bufnext++ = M_SET; 37259243Sobrien if (c == not) 37359243Sobrien *bufnext++ = m_not; 37459243Sobrien c = *qpatnext++; 37559243Sobrien do { 376167465Smp *bufnext++ = LCHAR(c); 37759243Sobrien if (*qpatnext == RANGE && 37859243Sobrien (c = qpatnext[1]) != RBRACKET) { 37959243Sobrien *bufnext++ = M_RNG; 380167465Smp *bufnext++ = LCHAR(c); 38159243Sobrien qpatnext += 2; 38259243Sobrien } 38359243Sobrien } while ((c = *qpatnext++) != RBRACKET); 38459243Sobrien *bufnext++ = M_END; 38559243Sobrien break; 38659243Sobrien case QUESTION: 38759243Sobrien pglob->gl_flags |= GLOB_MAGCHAR; 38859243Sobrien *bufnext++ = M_ONE; 38959243Sobrien break; 39059243Sobrien case STAR: 39159243Sobrien pglob->gl_flags |= GLOB_MAGCHAR; 392232633Smp /* collapse adjacent stars to one [or three if globstar], 393232633Smp * to avoid exponential behavior 39459243Sobrien */ 395232633Smp if (bufnext == patbuf || bufnext[-1] != M_ALL || 396232633Smp ((flags & GLOB_STAR) != 0 && 397232633Smp (bufnext - 1 == patbuf || bufnext[-2] != M_ALL || 398232633Smp bufnext - 2 == patbuf || bufnext[-3] != M_ALL))) 39959243Sobrien *bufnext++ = M_ALL; 40059243Sobrien break; 40159243Sobrien default: 402167465Smp *bufnext++ = LCHAR(c); 40359243Sobrien break; 40459243Sobrien } 40559243Sobrien } 40659243Sobrien *bufnext = EOS; 40759243Sobrien#ifdef DEBUG 40859243Sobrien qprintf(patbuf); 40959243Sobrien#endif 41059243Sobrien 411167465Smp if ((err = glob1(patbuf, pglob, no_match)) != 0) { 412167465Smp xfree(patbuf); 41359243Sobrien return (err); 414167465Smp } 41559243Sobrien 41659243Sobrien /* 41759243Sobrien * If there was no match we are going to append the pattern 41859243Sobrien * if GLOB_NOCHECK was specified or if GLOB_NOMAGIC was specified 41959243Sobrien * and the pattern did not contain any magic characters 42059243Sobrien * GLOB_NOMAGIC is there just for compatibility with csh. 42159243Sobrien */ 42259243Sobrien if (pglob->gl_pathc == oldpathc && 42359243Sobrien ((flags & GLOB_NOCHECK) || 42459243Sobrien ((flags & GLOB_NOMAGIC) && !(pglob->gl_flags & GLOB_MAGCHAR)))) { 425167465Smp if (!(flags & GLOB_QUOTE)) 426167465Smp globextend(pattern, pglob); 427167465Smp else { 428167465Smp char *copy, *dest; 429167465Smp const char *src; 43059243Sobrien 431167465Smp /* copy pattern, interpreting quotes */ 432167465Smp copy = xmalloc(strlen(pattern) + 1); 433167465Smp dest = copy; 434167465Smp src = pattern; 435167465Smp while (*src != EOS) { 436167465Smp if (*src == QUOTE) { 437167465Smp if (*++src == EOS) 438167465Smp --src; 43959243Sobrien } 440167465Smp *dest++ = *src++; 44159243Sobrien } 442167465Smp *dest = EOS; 443167465Smp globextend(copy, pglob); 444167465Smp xfree(copy); 44559243Sobrien } 446167465Smp xfree(patbuf); 447167465Smp return 0; 44859243Sobrien } 44959415Sobrien else if (!(flags & GLOB_NOSORT) && (pglob->gl_pathc != oldpathc)) 450167465Smp qsort(pglob->gl_pathv + pglob->gl_offs + oldpathc, 451167465Smp pglob->gl_pathc - oldpathc, sizeof(char *), compare); 452167465Smp xfree(patbuf); 45359243Sobrien return (0); 45459243Sobrien} 45559243Sobrien 45659243Sobrienstatic int 457167465Smpglob1(Char *pattern, glob_t *pglob, int no_match) 45859243Sobrien{ 459167465Smp struct strbuf pathbuf = strbuf_INIT; 460167465Smp int err; 46159243Sobrien 46259243Sobrien /* 46359243Sobrien * a null pathname is invalid -- POSIX 1003.1 sect. 2.4. 46459243Sobrien */ 46559243Sobrien if (*pattern == EOS) 46659243Sobrien return (0); 467167465Smp err = glob2(&pathbuf, pattern, pglob, no_match); 468167465Smp xfree(pathbuf.s); 469167465Smp return err; 47059243Sobrien} 47159243Sobrien 47259243Sobrien/* 47359243Sobrien * functions glob2 and glob3 are mutually recursive; there is one level 47459243Sobrien * of recursion for each segment in the pattern that contains one or 47559243Sobrien * more meta characters. 47659243Sobrien */ 47759243Sobrienstatic int 478167465Smpglob2(struct strbuf *pathbuf, const Char *pattern, glob_t *pglob, int no_match) 47959243Sobrien{ 48059243Sobrien struct stat sbuf; 48159243Sobrien int anymeta; 482167465Smp const Char *p; 483167465Smp size_t orig_len; 48459243Sobrien 48559243Sobrien /* 48659243Sobrien * loop over pattern segments until end of pattern or until segment with 48759243Sobrien * meta character found. 48859243Sobrien */ 48959243Sobrien anymeta = 0; 49059243Sobrien for (;;) { 49159243Sobrien if (*pattern == EOS) { /* end of pattern? */ 492167465Smp strbuf_terminate(pathbuf); 49359243Sobrien 494167465Smp if (Lstat(pathbuf->s, &sbuf)) 49559243Sobrien return (0); 49659243Sobrien 49759243Sobrien if (((pglob->gl_flags & GLOB_MARK) && 498167465Smp pathbuf->s[pathbuf->len - 1] != SEP) && 49959243Sobrien (S_ISDIR(sbuf.st_mode) 50059243Sobrien#ifdef S_IFLNK 50159243Sobrien || (S_ISLNK(sbuf.st_mode) && 502167465Smp (Stat(pathbuf->s, &sbuf) == 0) && 50359243Sobrien S_ISDIR(sbuf.st_mode)) 50459243Sobrien#endif 50559243Sobrien )) { 506167465Smp strbuf_append1(pathbuf, SEP); 507167465Smp strbuf_terminate(pathbuf); 50859243Sobrien } 50959243Sobrien ++pglob->gl_matchc; 510167465Smp globextend(pathbuf->s, pglob); 511167465Smp return 0; 51259243Sobrien } 51359243Sobrien 514167465Smp /* find end of next segment, tentatively copy to pathbuf */ 51559243Sobrien p = pattern; 516167465Smp orig_len = pathbuf->len; 51759243Sobrien while (*p != EOS && *p != SEP) { 51859243Sobrien if (ismeta(*p)) 51959243Sobrien anymeta = 1; 520167465Smp strbuf_append1(pathbuf, *p++); 52159243Sobrien } 52259243Sobrien 52359243Sobrien if (!anymeta) { /* no expansion, do next segment */ 52459243Sobrien pattern = p; 52559243Sobrien while (*pattern == SEP) 526167465Smp strbuf_append1(pathbuf, *pattern++); 52759243Sobrien } 528167465Smp else { /* need expansion, recurse */ 529167465Smp pathbuf->len = orig_len; 530232633Smp return (glob3(pathbuf, pattern, p, pattern, pglob, no_match)); 531167465Smp } 53259243Sobrien } 53359243Sobrien /* NOTREACHED */ 53459243Sobrien} 53559243Sobrien 536232633Smpstatic size_t 537232633SmpOne_Char_mbtowc(__Char *pwc, const Char *s, size_t n) 538232633Smp{ 539232633Smp#ifdef WIDE_STRINGS 540232633Smp char buf[MB_LEN_MAX], *p; 54159243Sobrien 542232633Smp if (n > MB_LEN_MAX) 543232633Smp n = MB_LEN_MAX; 544232633Smp p = buf; 545232633Smp while (p < buf + n && (*p++ = LCHAR(*s++)) != 0) 546232633Smp ; 547232633Smp return one_mbtowc(pwc, buf, n); 548232633Smp#else 549232633Smp *pwc = *s & CHAR; 550232633Smp return 1; 551232633Smp#endif 552232633Smp} 553232633Smp 55459243Sobrienstatic int 555167465Smpglob3(struct strbuf *pathbuf, const Char *pattern, const Char *restpattern, 556232633Smp const Char *pglobstar, glob_t *pglob, int no_match) 55759243Sobrien{ 55859243Sobrien DIR *dirp; 55959243Sobrien struct dirent *dp; 560232633Smp struct stat sbuf; 56159243Sobrien int err; 56259243Sobrien Char m_not = (pglob->gl_flags & GLOB_ALTNOT) ? M_ALTNOT : M_NOT; 563167465Smp size_t orig_len; 564232633Smp int globstar = 0; 565232633Smp int chase_symlinks = 0; 566232633Smp const Char *termstar = NULL; 56759243Sobrien 568167465Smp strbuf_terminate(pathbuf); 569232633Smp orig_len = pathbuf->len; 570232633Smp errno = err = 0; 57159243Sobrien 572232633Smp while (pglobstar < restpattern) { 573232633Smp __Char wc; 574232633Smp size_t width = One_Char_mbtowc(&wc, pglobstar, MB_LEN_MAX); 575232633Smp if ((pglobstar[0] & M_MASK) == M_ALL && 576232633Smp (pglobstar[width] & M_MASK) == M_ALL) { 577232633Smp globstar = 1; 578232633Smp chase_symlinks = (pglobstar[2 * width] & M_MASK) == M_ALL; 579232633Smp termstar = pglobstar + (2 + chase_symlinks) * width; 580232633Smp break; 581232633Smp } 582232633Smp pglobstar += width; 583232633Smp } 584232633Smp 585232633Smp if (globstar) { 586232633Smp err = pglobstar==pattern && termstar==restpattern ? 587232633Smp *restpattern == EOS ? 588232633Smp glob2(pathbuf, restpattern - 1, pglob, no_match) : 589232633Smp glob2(pathbuf, restpattern + 1, pglob, no_match) : 590232633Smp glob3(pathbuf, pattern, restpattern, termstar, pglob, no_match); 591232633Smp if (err) 592232633Smp return err; 593232633Smp pathbuf->len = orig_len; 594232633Smp strbuf_terminate(pathbuf); 595232633Smp } 596232633Smp 597232633Smp if (*pathbuf->s && (Lstat(pathbuf->s, &sbuf) || !S_ISDIR(sbuf.st_mode) 598232633Smp#ifdef S_IFLINK 599232633Smp && ((globstar && !chase_symlinks) || !S_ISLNK(sbuf.st_mode)) 600232633Smp#endif 601232633Smp )) 602232633Smp return 0; 603232633Smp 604167465Smp if (!(dirp = Opendir(pathbuf->s))) { 60559243Sobrien /* todo: don't call for ENOENT or ENOTDIR? */ 606167465Smp if ((pglob->gl_errfunc && (*pglob->gl_errfunc) (pathbuf->s, errno)) || 60759243Sobrien (pglob->gl_flags & GLOB_ERR)) 60859243Sobrien return (GLOB_ABEND); 60959243Sobrien else 61059243Sobrien return (0); 61159243Sobrien } 61259243Sobrien 61359243Sobrien /* search directory for matching names */ 61459243Sobrien while ((dp = readdir(dirp)) != NULL) { 61559243Sobrien /* initial DOT must be matched literally */ 61659243Sobrien if (dp->d_name[0] == DOT && *pattern != DOT) 617232633Smp if (!(pglob->gl_flags & GLOB_DOT) || !dp->d_name[1] || 618232633Smp (dp->d_name[1] == DOT && !dp->d_name[2])) 619232633Smp continue; /*unless globdot and not . or .. */ 620167465Smp pathbuf->len = orig_len; 621167465Smp strbuf_append(pathbuf, dp->d_name); 622167465Smp strbuf_terminate(pathbuf); 623232633Smp 624232633Smp if (globstar) { 625232633Smp#ifdef S_IFLNK 626232633Smp if (!chase_symlinks && 627232633Smp (Lstat(pathbuf->s, &sbuf) || S_ISLNK(sbuf.st_mode))) 628232633Smp continue; 629232633Smp#endif 630232633Smp if (match(pathbuf->s + orig_len, pattern, termstar, 631232633Smp (int)m_not) == no_match) 632232633Smp continue; 633232633Smp strbuf_append1(pathbuf, SEP); 634232633Smp strbuf_terminate(pathbuf); 635232633Smp if ((err = glob2(pathbuf, pglobstar, pglob, no_match)) != 0) 636232633Smp break; 637232633Smp } else { 638232633Smp if (match(pathbuf->s + orig_len, pattern, restpattern, 639232633Smp (int) m_not) == no_match) 640232633Smp continue; 641232633Smp if ((err = glob2(pathbuf, restpattern, pglob, no_match)) != 0) 642232633Smp break; 643232633Smp } 64459243Sobrien } 64559243Sobrien /* todo: check error from readdir? */ 646167465Smp closedir(dirp); 64759243Sobrien return (err); 64859243Sobrien} 64959243Sobrien 65059243Sobrien 65159243Sobrien/* 65259243Sobrien * Extend the gl_pathv member of a glob_t structure to accomodate a new item, 65359243Sobrien * add the new item, and update gl_pathc. 65459243Sobrien * 65559243Sobrien * This assumes the BSD realloc, which only copies the block when its size 65659243Sobrien * crosses a power-of-two boundary; for v7 realloc, this would cause quadratic 65759243Sobrien * behavior. 65859243Sobrien * 65959243Sobrien * Return 0 if new item added, error code if memory couldn't be allocated. 66059243Sobrien * 66159243Sobrien * Invariant of the glob_t structure: 66259243Sobrien * Either gl_pathc is zero and gl_pathv is NULL; or gl_pathc > 0 and 66359243Sobrien * gl_pathv points to (gl_offs + gl_pathc + 1) items. 66459243Sobrien */ 665167465Smpstatic void 666167465Smpglobextend(const char *path, glob_t *pglob) 66759243Sobrien{ 668145479Smp char **pathv; 669145479Smp int i; 670167465Smp size_t newsize; 67159243Sobrien 67259243Sobrien newsize = sizeof(*pathv) * (2 + pglob->gl_pathc + pglob->gl_offs); 673167465Smp pathv = xrealloc(pglob->gl_pathv, newsize); 67459243Sobrien 67559243Sobrien if (pglob->gl_pathv == NULL && pglob->gl_offs > 0) { 67659243Sobrien /* first time around -- clear initial gl_offs items */ 67759243Sobrien pathv += pglob->gl_offs; 67859243Sobrien for (i = pglob->gl_offs; --i >= 0;) 67959243Sobrien *--pathv = NULL; 68059243Sobrien } 68159243Sobrien pglob->gl_pathv = pathv; 68259243Sobrien 683167465Smp pathv[pglob->gl_offs + pglob->gl_pathc++] = strsave(path); 68459243Sobrien pathv[pglob->gl_offs + pglob->gl_pathc] = NULL; 68559243Sobrien} 68659243Sobrien 68759243Sobrien/* 68859243Sobrien * pattern matching function for filenames. Each occurrence of the * 68959243Sobrien * pattern causes a recursion level. 69059243Sobrien */ 69159243Sobrienstatic int 692167465Smpmatch(const char *name, const Char *pat, const Char *patend, int m_not) 69359243Sobrien{ 69459243Sobrien int ok, negate_range; 695167465Smp Char c; 69659243Sobrien 69759243Sobrien while (pat < patend) { 698145479Smp size_t lwk; 699167465Smp __Char wc, wk; 700145479Smp 701145479Smp c = *pat; /* Only for M_MASK bits */ 702167465Smp pat += One_Char_mbtowc(&wc, pat, MB_LEN_MAX); 703167465Smp lwk = one_mbtowc(&wk, name, MB_LEN_MAX); 70459243Sobrien switch (c & M_MASK) { 70559243Sobrien case M_ALL: 706232633Smp while (pat < patend && (*pat & M_MASK) == M_ALL) /* eat consecutive '*' */ 707232633Smp pat += One_Char_mbtowc(&wc, pat, MB_LEN_MAX); 70859243Sobrien if (pat == patend) 709232633Smp return (1); 710232633Smp while (!match(name, pat, patend, m_not)) { 711145479Smp if (*name == EOS) 712232633Smp return (0); 713145479Smp name += lwk; 714167465Smp lwk = one_mbtowc(&wk, name, MB_LEN_MAX); 715145479Smp } 716232633Smp return (1); 71759243Sobrien case M_ONE: 718145479Smp if (*name == EOS) 71959243Sobrien return (0); 720145479Smp name += lwk; 72159243Sobrien break; 72259243Sobrien case M_SET: 72359243Sobrien ok = 0; 724145479Smp if (*name == EOS) 72559243Sobrien return (0); 726145479Smp name += lwk; 72759243Sobrien if ((negate_range = ((*pat & M_MASK) == m_not)) != 0) 72859243Sobrien ++pat; 729145479Smp while ((*pat & M_MASK) != M_END) { 730167465Smp pat += One_Char_mbtowc(&wc, pat, MB_LEN_MAX); 73159243Sobrien if ((*pat & M_MASK) == M_RNG) { 732167465Smp __Char wc2; 733167465Smp 734145479Smp pat++; 735167465Smp pat += One_Char_mbtowc(&wc2, pat, MB_LEN_MAX); 736145479Smp if (globcharcoll(wc, wk, 0) <= 0 && 737145479Smp globcharcoll(wk, wc2, 0) <= 0) 73859243Sobrien ok = 1; 739145479Smp } else if (wc == wk) 74059243Sobrien ok = 1; 74159243Sobrien } 742167465Smp pat += One_Char_mbtowc(&wc, pat, MB_LEN_MAX); 74359243Sobrien if (ok == negate_range) 74459243Sobrien return (0); 74559243Sobrien break; 74659243Sobrien default: 747232633Smp if (*name == EOS || samecase(wk) != samecase(wc)) 748232633Smp return (0); 749145479Smp name += lwk; 75059243Sobrien break; 75159243Sobrien } 75259243Sobrien } 75359243Sobrien return (*name == EOS); 75459243Sobrien} 75559243Sobrien 75659243Sobrien/* free allocated data belonging to a glob_t structure */ 75759243Sobrienvoid 758167465Smpglobfree(glob_t *pglob) 75959243Sobrien{ 760145479Smp int i; 761145479Smp char **pp; 76259243Sobrien 76359243Sobrien if (pglob->gl_pathv != NULL) { 76459243Sobrien pp = pglob->gl_pathv + pglob->gl_offs; 76559243Sobrien for (i = pglob->gl_pathc; i--; ++pp) 76659243Sobrien if (*pp) 767167465Smp xfree(*pp), *pp = NULL; 768167465Smp xfree(pglob->gl_pathv), pglob->gl_pathv = NULL; 76959243Sobrien } 77059243Sobrien} 771