Add a "fork" of musl as //fusl.

fusl/src/regex/fnmatch.c

+/*
+ * 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);
+}