static bool flexMatch_debug;

static bool flexMatch(S pat, S s) {
  ret flexMatch(pat, s, null);
}

static bool flexMatch(S pat, S s, Matches m) {
  ret flexMatch(javaTok(pat), javaTok(unnull(s)), m);
}

static bool flexMatch(S pat, S s, Matches m, bool joinBrackets) {
  ret flexMatch(javaTok(pat), javaTok(unnull(s)), m, joinBrackets);
}

static bool flexMatch(L<S> tokpat, L<S> tokfull, Matches m) {
  ret flexMatch(tokpat, tokfull, m, true);
}

static bool flexMatch(L<S> tokpat, L<S> tokfull, Matches m, bool joinBrackets) {
  tokpat = codeTokens(joinBrackets ? joinBrackets(tokpat) : tokpat);
  for (int i = 0; i < l(tokpat); i++)
    if (eq(tokpat.get(i), "*"))
      tokpat.add(i++, "!*"); // insert single-token wildcard in front to avoid empty matches
  if (joinBrackets) tokfull = joinBrackets(tokfull);
  L<S> tok = codeTokens(tokfull);
  new BitSet bla;
  new BitSet bla2;
  if (!flexMatch_impl(tokpat, 0, tok, 0, bla, bla2)) ret false;
  if (m != null) {
    new L<S> l;
    for (int i = 1; i < l(tokfull); i += 2) {
      if (bla.get(i/2)) {
        int j = i;
        while (j < l(tokfull) && bla.get(j/2)) j += 2;
        l.add(join(subList(tokfull, i, j-1)));
        i = j-2;
      } else if (bla2.get(i/2))
        l.add(tokfull.get(i));
    }
    m.m = toStringArray(l);
  }
  ret true;
}

static bool flexMatch_impl(L<S> pat, int ipat, L<S> tok, int itok, BitSet bla, BitSet bla2) {
  if (flexMatch_debug)
    print("flexMatch pat=" + structure(subList(pat, ipat)) + " tok=" + structure(subList(tok, itok)) + " " + structure(bla));
  if (ipat >= l(pat))
    ret itok >= l(tok);
  S t = pat.get(ipat);
  
  if (eq(t, "*")) { // the flex wildcard (0 or more tokens)
    if (flexMatch_debug) print("Trying zero tokens");
    if (flexMatch_impl(pat, ipat+1, tok, itok, bla, bla2)) {
      if (flexMatch_debug) print("Success!");
      ret true;
    }
    
    bla.set(itok);
    if (itok < l(tok)) {
      if (flexMatch_debug) print("Trying one or more tokens");
      if (flexMatch_impl(pat, ipat, tok, itok+1, bla, bla2)) {
        if (flexMatch_debug) print("Success!");
        ret true; // success, leave mark
      }
    }
    
    if (flexMatch_debug) print("Failed * matching");
    bla.clear(itok); // fail, undo marking
    ret false;
  }
  if (itok >= l(tok)) {
    if (flexMatch_debug)
      print("too much pattern");
    ret false;
  }
  if (eq(t, "!*")) { // the single-token wildcard
    bla.set(itok);
    if (flexMatch_impl(pat, ipat+1, tok, itok+1, bla, bla2))
      ret true; // success, leave mark
    bla.clear(itok); // fail, undo marking
    ret false;
  }
  S realt = tok.get(itok);
  if (t.startsWith("(") && t.endsWith(")")) {
    // quick pre-check
    if (flexMatch_debug)
      print("flexMatch precheck " + t + " " + realt);
    if (!contains(t, realt)) false;
    // real check
    L<S> list = splitAt(dropFirstAndLast(t), "|");
    if (flexMatch_debug)
      print("flexMatch real check " + struct(list));
    if (!contains(list, realt)) false;
    bla2.set(itok);
  } else if (neq(realt, t)) {
    if (flexMatch_debug)
      print("mismatch");
    ret false;
  }
  
  // it is a token match. consume and proceed
  if (flexMatch_impl(pat, ipat+1, tok, itok+1, bla, bla2))
    true;
  else {
    bla2.clear(itok);
    false;
  }
}