text: /*
   * 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 "locale_impl.h"
  #include <fnmatch.h>
  #include <stdlib.h>
  #include <string.h>
  #include <wchar.h>
  #include <wctype.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);
  }
  