| /* |
| * An implementation of what I call the "Sea of Stars" algorithm for |
| * POSIX fnmatch(). The basic idea is that we factor the pattern into |
| * a head component (which we match first and can reject without ever |
| * measuring the length of the string), an optional tail component |
| * (which only exists if the pattern contains at least one star), and |
| * an optional "sea of stars", a set of star-separated components |
| * between the head and tail. After the head and tail matches have |
| * been removed from the input string, the components in the "sea of |
| * stars" are matched sequentially by searching for their first |
| * occurrence past the end of the previous match. |
| * |
| * - Rich Felker, April 2012 |
| */ |
| |
| #include <string.h> |
| #include <fnmatch.h> |
| #include <stdlib.h> |
| #include <wchar.h> |
| #include <wctype.h> |
| #include "locale_impl.h" |
| |
| #define END 0 |
| #define UNMATCHABLE -2 |
| #define BRACKET -3 |
| #define QUESTION -4 |
| #define STAR -5 |
| |
| static int str_next(const char *str, size_t n, size_t *step) |
| { |
| if (!n) { |
| *step = 0; |
| return 0; |
| } |
| if (str[0] >= 128U) { |
| wchar_t wc; |
| int k = mbtowc(&wc, str, n); |
| if (k<0) { |
| *step = 1; |
| return -1; |
| } |
| *step = k; |
| return wc; |
| } |
| *step = 1; |
| return str[0]; |
| } |
| |
| static int pat_next(const char *pat, size_t m, size_t *step, int flags) |
| { |
| int esc = 0; |
| if (!m || !*pat) { |
| *step = 0; |
| return END; |
| } |
| *step = 1; |
| if (pat[0]=='\\' && pat[1] && !(flags & FNM_NOESCAPE)) { |
| *step = 2; |
| pat++; |
| esc = 1; |
| goto escaped; |
| } |
| if (pat[0]=='[') { |
| size_t k = 1; |
| if (k<m) if (pat[k] == '^' || pat[k] == '!') k++; |
| if (k<m) if (pat[k] == ']') k++; |
| for (; k<m && pat[k] && pat[k]!=']'; k++) { |
| if (k+1<m && pat[k+1] && pat[k]=='[' && (pat[k+1]==':' || pat[k+1]=='.' || pat[k+1]=='=')) { |
| int z = pat[k+1]; |
| k+=2; |
| if (k<m && pat[k]) k++; |
| while (k<m && pat[k] && (pat[k-1]!=z || pat[k]!=']')) k++; |
| if (k==m || !pat[k]) break; |
| } |
| } |
| if (k==m || !pat[k]) { |
| *step = 1; |
| return '['; |
| } |
| *step = k+1; |
| return BRACKET; |
| } |
| if (pat[0] == '*') |
| return STAR; |
| if (pat[0] == '?') |
| return QUESTION; |
| escaped: |
| if (pat[0] >= 128U) { |
| wchar_t wc; |
| int k = mbtowc(&wc, pat, m); |
| if (k<0) { |
| *step = 0; |
| return UNMATCHABLE; |
| } |
| *step = k + esc; |
| return wc; |
| } |
| return pat[0]; |
| } |
| |
| static int casefold(int k) |
| { |
| int c = towupper(k); |
| return c == k ? towlower(k) : c; |
| } |
| |
| static int match_bracket(const char *p, int k, int kfold) |
| { |
| wchar_t wc; |
| int inv = 0; |
| p++; |
| if (*p=='^' || *p=='!') { |
| inv = 1; |
| p++; |
| } |
| if (*p==']') { |
| if (k==']') return !inv; |
| p++; |
| } else if (*p=='-') { |
| if (k=='-') return !inv; |
| p++; |
| } |
| wc = p[-1]; |
| for (; *p != ']'; p++) { |
| if (p[0]=='-' && p[1]!=']') { |
| wchar_t wc2; |
| int l = mbtowc(&wc2, p+1, 4); |
| if (l < 0) return 0; |
| if (wc <= wc2) |
| if ((unsigned)k-wc <= wc2-wc || |
| (unsigned)kfold-wc <= wc2-wc) |
| return !inv; |
| p += l-1; |
| continue; |
| } |
| if (p[0]=='[' && (p[1]==':' || p[1]=='.' || p[1]=='=')) { |
| const char *p0 = p+2; |
| int z = p[1]; |
| p+=3; |
| while (p[-1]!=z || p[0]!=']') p++; |
| if (z == ':' && p-1-p0 < 16) { |
| char buf[16]; |
| memcpy(buf, p0, p-1-p0); |
| buf[p-1-p0] = 0; |
| if (iswctype(k, wctype(buf)) || |
| iswctype(kfold, wctype(buf))) |
| return !inv; |
| } |
| continue; |
| } |
| if (*p < 128U) { |
| wc = (unsigned char)*p; |
| } else { |
| int l = mbtowc(&wc, p, 4); |
| if (l < 0) return 0; |
| p += l-1; |
| } |
| if (wc==k || wc==kfold) return !inv; |
| } |
| return inv; |
| } |
| |
| static int fnmatch_internal(const char *pat, size_t m, const char *str, size_t n, int flags) |
| { |
| const char *p, *ptail, *endpat; |
| const char *s, *stail, *endstr; |
| size_t pinc, sinc, tailcnt=0; |
| int c, k, kfold; |
| |
| if (flags & FNM_PERIOD) { |
| if (*str == '.' && *pat != '.') |
| return FNM_NOMATCH; |
| } |
| for (;;) { |
| switch ((c = pat_next(pat, m, &pinc, flags))) { |
| case UNMATCHABLE: |
| return FNM_NOMATCH; |
| case STAR: |
| pat++; |
| m--; |
| break; |
| default: |
| k = str_next(str, n, &sinc); |
| if (k <= 0) |
| return (c==END) ? 0 : FNM_NOMATCH; |
| str += sinc; |
| n -= sinc; |
| kfold = flags & FNM_CASEFOLD ? casefold(k) : k; |
| if (c == BRACKET) { |
| if (!match_bracket(pat, k, kfold)) |
| return FNM_NOMATCH; |
| } else if (c != QUESTION && k != c && kfold != c) { |
| return FNM_NOMATCH; |
| } |
| pat+=pinc; |
| m-=pinc; |
| continue; |
| } |
| break; |
| } |
| |
| /* Compute real pat length if it was initially unknown/-1 */ |
| m = strnlen(pat, m); |
| endpat = pat + m; |
| |
| /* Find the last * in pat and count chars needed after it */ |
| for (p=ptail=pat; p<endpat; p+=pinc) { |
| switch (pat_next(p, endpat-p, &pinc, flags)) { |
| case UNMATCHABLE: |
| return FNM_NOMATCH; |
| case STAR: |
| tailcnt=0; |
| ptail = p+1; |
| break; |
| default: |
| tailcnt++; |
| break; |
| } |
| } |
| |
| /* Past this point we need not check for UNMATCHABLE in pat, |
| * because all of pat has already been parsed once. */ |
| |
| /* Compute real str length if it was initially unknown/-1 */ |
| n = strnlen(str, n); |
| endstr = str + n; |
| if (n < tailcnt) return FNM_NOMATCH; |
| |
| /* Find the final tailcnt chars of str, accounting for UTF-8. |
| * On illegal sequences we may get it wrong, but in that case |
| * we necessarily have a matching failure anyway. */ |
| for (s=endstr; s>str && tailcnt; tailcnt--) { |
| if (s[-1] < 128U || MB_CUR_MAX==1) s--; |
| else while ((unsigned char)*--s-0x80U<0x40 && s>str); |
| } |
| if (tailcnt) return FNM_NOMATCH; |
| stail = s; |
| |
| /* Check that the pat and str tails match */ |
| p = ptail; |
| for (;;) { |
| c = pat_next(p, endpat-p, &pinc, flags); |
| p += pinc; |
| if ((k = str_next(s, endstr-s, &sinc)) <= 0) { |
| if (c != END) return FNM_NOMATCH; |
| break; |
| } |
| s += sinc; |
| kfold = flags & FNM_CASEFOLD ? casefold(k) : k; |
| if (c == BRACKET) { |
| if (!match_bracket(p-pinc, k, kfold)) |
| return FNM_NOMATCH; |
| } else if (c != QUESTION && k != c && kfold != c) { |
| return FNM_NOMATCH; |
| } |
| } |
| |
| /* We're all done with the tails now, so throw them out */ |
| endstr = stail; |
| endpat = ptail; |
| |
| /* Match pattern components until there are none left */ |
| while (pat<endpat) { |
| p = pat; |
| s = str; |
| for (;;) { |
| c = pat_next(p, endpat-p, &pinc, flags); |
| p += pinc; |
| /* Encountering * completes/commits a component */ |
| if (c == STAR) { |
| pat = p; |
| str = s; |
| break; |
| } |
| k = str_next(s, endstr-s, &sinc); |
| if (!k) |
| return FNM_NOMATCH; |
| kfold = flags & FNM_CASEFOLD ? casefold(k) : k; |
| if (c == BRACKET) { |
| if (!match_bracket(p-pinc, k, kfold)) |
| break; |
| } else if (c != QUESTION && k != c && kfold != c) { |
| break; |
| } |
| s += sinc; |
| } |
| if (c == STAR) continue; |
| /* If we failed, advance str, by 1 char if it's a valid |
| * char, or past all invalid bytes otherwise. */ |
| k = str_next(str, endstr-str, &sinc); |
| if (k > 0) str += sinc; |
| else for (str++; str_next(str, endstr-str, &sinc)<0; str++); |
| } |
| |
| return 0; |
| } |
| |
| int fnmatch(const char *pat, const char *str, int flags) |
| { |
| const char *s, *p; |
| size_t inc; |
| int c; |
| if (flags & FNM_PATHNAME) for (;;) { |
| for (s=str; *s && *s!='/'; s++); |
| for (p=pat; (c=pat_next(p, -1, &inc, flags))!=END && c!='/'; p+=inc); |
| if (c!=*s && (!*s || !(flags & FNM_LEADING_DIR))) |
| return FNM_NOMATCH; |
| if (fnmatch_internal(pat, p-pat, str, s-str, flags)) |
| return FNM_NOMATCH; |
| if (!c) return 0; |
| str = s+1; |
| pat = p+inc; |
| } else if (flags & FNM_LEADING_DIR) { |
| for (s=str; *s; s++) { |
| if (*s != '/') continue; |
| if (!fnmatch_internal(pat, -1, str, s-str, flags)) |
| return 0; |
| } |
| } |
| return fnmatch_internal(pat, -1, str, -1, flags); |
| } |