//// The wildcard retry algorithm must agree with exhaustive small-pattern
//// matching, including overlapping wildcard retries. HTTP E2E cannot cover
//// this combinatorial space or reliably catch exponential work regressions.

import albedo/harness/cache_ttl
import gleam/list
import gleam/string
import gleeunit/should

fn words(alphabet: List(String), length: Int) -> List(String) {
  case length {
    0 -> [""]
    _ -> {
      let shorter = words(alphabet, length - 1)
      list.append(
        [""],
        list.flat_map(alphabet, fn(head) {
          list.map(shorter, fn(tail) { head <> tail })
        }),
      )
    }
  }
}

// An intentionally exhaustive oracle for bounded inputs; the production
// matcher must not explore both branches recursively on long inputs.
fn exhaustive(pattern: List(String), value: List(String)) -> Bool {
  case pattern, value {
    [], [] -> True
    ["*", ..rest], _ ->
      exhaustive(rest, value)
      || case value {
        [_, ..tail] -> exhaustive(pattern, tail)
        [] -> False
      }
    [head, ..rest], [letter, ..tail] -> head == letter && exhaustive(rest, tail)
    _, _ -> False
  }
}

pub fn wildcard_retry_agrees_with_exhaustive_matching_test() -> Nil {
  list.each(words(["a", "b", "*"], 5), fn(pattern) {
    list.each(words(["a", "b"], 4), fn(value) {
      cache_ttl.matches_glob(pattern, value)
      |> should.equal(exhaustive(
        string.to_graphemes(pattern),
        string.to_graphemes(value),
      ))
    })
  })
}

pub fn repeated_wildcards_fail_without_exponential_backtracking_test() -> Nil {
  let pattern = string.repeat("*a", 24) <> "b"
  cache_ttl.matches_glob(pattern, string.repeat("a", 48))
  |> should.be_false
}

pub fn wildcard_matches_unicode_graphemes_and_only_star_is_special_test() -> Nil {
  cache_ttl.matches_glob("É*👩‍💻?", "éclair👩‍💻?") |> should.be_true
  cache_ttl.matches_glob("é*", "éclair") |> should.be_true
  cache_ttl.matches_glob("a?", "ab") |> should.be_false
  cache_ttl.matches_glob("[ab]", "a") |> should.be_false
}