[fusl] clang-format 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;
+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);
-}
+  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);
+}