///|
/// Rewrite strategy shared by term-dictionary expanding queries. Expansion is
/// deterministic and capped to keep adversarial patterns bounded.
pub(all) enum MultiTermRewrite {
  ScoringBoolean
  ConstantScore
} derive(Eq, @debug.Debug)

///|
priv enum MultiTermPredicate {
  Prefix(String)
  Wildcard(String)
  Regex(@string.Regex)
  Fuzzy(String, Int, Bool)
  LexicographicRange(String?, Bool, String?, Bool)
}

///|
priv struct MultiTermWeight {
  field_id : FieldId
  predicate : MultiTermPredicate
  rewrite : MultiTermRewrite
  max_expansions : Int
  statistics : SearchStatistics
}

///|
fn bounded_expansion_limit(max_expansions : Int) -> Int {
  guard max_expansions > 0 else {
    abort("multi-term expansion limit must be positive")
  }
  max_expansions
}

///|
fn string_chars(text : String) -> Array[Char] {
  let chars : Array[Char] = []
  for ch in text {
    chars.push(ch)
  }
  chars
}

///|
/// Unicode-scalar glob matcher. `*` matches zero or more scalars and `?`
/// matches exactly one. A backslash quotes the next scalar.
fn wildcard_matches(pattern : String, text : String) -> Bool {
  let raw = string_chars(pattern)
  let pattern_chars : Array[Char] = []
  let quoted : Array[Bool] = []
  let mut index = 0
  while index < raw.length() {
    if raw[index] == '\\' && index + 1 < raw.length() {
      pattern_chars.push(raw[index + 1])
      quoted.push(true)
      index += 2
    } else {
      pattern_chars.push(raw[index])
      quoted.push(false)
      index += 1
    }
  }
  let value = string_chars(text)
  let mut previous = Array::make(value.length() + 1, false)
  previous[0] = true
  for pattern_index in 0.. Int {
  let left_chars = string_chars(left)
  let right_chars = string_chars(right)
  if (left_chars.length() - right_chars.length()).abs() > limit {
    return limit + 1
  }
  let mut previous : Array[Int] = []
  for index in 0..<=right_chars.length() {
    previous.push(index)
  }
  for left_index in 1..<=left_chars.length() {
    let current = Array::make(right_chars.length() + 1, 0)
    current[0] = left_index
    let mut row_minimum = current[0]
    for right_index in 1..<=right_chars.length() {
      let substitution = previous[right_index - 1] +
        (if left_chars[left_index - 1] == right_chars[right_index - 1] {
          0
        } else {
          1
        })
      let deletion = previous[right_index] + 1
      let insertion = current[right_index - 1] + 1
      current[right_index] = substitution.min(deletion.min(insertion))
      row_minimum = row_minimum.min(current[right_index])
    }
    if row_minimum > limit {
      return limit + 1
    }
    previous = current
  }
  previous[right_chars.length()]
}

///|
fn range_matches(
  text : String,
  lower : String?,
  lower_inclusive : Bool,
  upper : String?,
  upper_inclusive : Bool,
) -> Bool {
  let lower_ok = match lower {
    None => true
    Some(bound) => {
      let order = query_term_text_compare(text, bound)
      order > 0 || (lower_inclusive && order == 0)
    }
  }
  let upper_ok = match upper {
    None => true
    Some(bound) => {
      let order = query_term_text_compare(text, bound)
      order < 0 || (upper_inclusive && order == 0)
    }
  }
  lower_ok && upper_ok
}

///|
/// Byte-lexicographic order shared with the on-disk term dictionary. MoonBit's
/// generic String comparison is shortlex and therefore unsuitable here.
fn query_term_text_compare(left : String, right : String) -> Int {
  let left_bytes = @utf8.encode(left)
  let right_bytes = @utf8.encode(right)
  let common = left_bytes.length().min(right_bytes.length())
  for index in 0.. Bool {
  match predicate {
    Prefix(prefix) => text.has_prefix(prefix)
    Wildcard(pattern) => wildcard_matches(pattern, text)
    Regex(regex) => regex.execute(text) is Some(_)
    Fuzzy(expected, distance, transpositions) => {
      // The portable baseline uses Levenshtein. `transpositions` is retained
      // in the public contract for a future Damerau rewrite.
      ignore(transpositions)
      bounded_levenshtein(expected, text, distance) <= distance
    }
    LexicographicRange(lower, lower_inclusive, upper, upper_inclusive) =>
      range_matches(text, lower, lower_inclusive, upper, upper_inclusive)
  }
}

///|
fn MultiTermWeight::expanded_terms(
  self : MultiTermWeight,
  segment : Segment,
) -> Array[Term] {
  let matches : Array[Term] = []
  let candidates = match self.predicate {
    Prefix(prefix) =>
      segment.term_dictionary().terms_with_prefix(self.field_id, prefix)
    _ => segment.terms()
  }
  for term in candidates {
    if term.field_id == self.field_id &&
      predicate_matches(self.predicate, term.text) {
      matches.push(term)
      if matches.length() >= self.max_expansions {
        break
      }
    }
  }
  matches
}

///|
impl Weight for MultiTermWeight with fn scorer(self, segment) {
  let clauses : Array[BooleanClause] = []
  for term in self.expanded_terms(segment) {
    let child : &Query = TermQuery::new(term)
    let rewritten : &Query = match self.rewrite {
      ScoringBoolean => child
      ConstantScore => ConstantScoreQuery::new(child, 1.0)
    }
    clauses.push(BooleanClause::new(Should, rewritten))
  }
  Query::weight(BooleanQuery::new(clauses), self.statistics).scorer(segment)
}

///|
pub struct PrefixQuery {
  field_id : FieldId
  prefix : String
  rewrite : MultiTermRewrite
  max_expansions : Int
}

///|
pub fn PrefixQuery::new(field_id : FieldId, prefix : String) -> PrefixQuery {
  { field_id, prefix, rewrite: ConstantScore, max_expansions: 1024 }
}

///|
pub fn PrefixQuery::with_rewrite(
  self : PrefixQuery,
  rewrite : MultiTermRewrite,
  max_expansions : Int,
) -> PrefixQuery {
  {
    field_id: self.field_id,
    prefix: self.prefix,
    rewrite,
    max_expansions: bounded_expansion_limit(max_expansions),
  }
}

///|
pub impl Query for PrefixQuery with fn weight(self, statistics) {
  MultiTermWeight::{
    field_id: self.field_id,
    predicate: Prefix(self.prefix),
    rewrite: self.rewrite,
    max_expansions: self.max_expansions,
    statistics,
  }
  as &Weight
}

///|
pub struct WildcardQuery {
  field_id : FieldId
  pattern : String
  rewrite : MultiTermRewrite
  max_expansions : Int
}

///|
pub fn WildcardQuery::new(
  field_id : FieldId,
  pattern : String,
) -> WildcardQuery {
  { field_id, pattern, rewrite: ConstantScore, max_expansions: 1024 }
}

///|
pub fn WildcardQuery::with_rewrite(
  self : WildcardQuery,
  rewrite : MultiTermRewrite,
  max_expansions : Int,
) -> WildcardQuery {
  {
    field_id: self.field_id,
    pattern: self.pattern,
    rewrite,
    max_expansions: bounded_expansion_limit(max_expansions),
  }
}

///|
pub impl Query for WildcardQuery with fn weight(self, statistics) {
  MultiTermWeight::{
    field_id: self.field_id,
    predicate: Wildcard(self.pattern),
    rewrite: self.rewrite,
    max_expansions: self.max_expansions,
    statistics,
  }
  as &Weight
}

///|
pub struct RegexQuery {
  field_id : FieldId
  pattern : String
  regex : @string.Regex
  rewrite : MultiTermRewrite
  max_expansions : Int
}

///|
pub fn RegexQuery::new(
  field_id : FieldId,
  pattern : String,
) -> RegexQuery raise {
  {
    field_id,
    pattern,
    regex: @string.Regex("^(?:" + pattern + ")$"),
    rewrite: ConstantScore,
    max_expansions: 1024,
  }
}

///|
pub fn RegexQuery::pattern(self : RegexQuery) -> String {
  self.pattern
}

///|
pub impl Query for RegexQuery with fn weight(self, statistics) {
  MultiTermWeight::{
    field_id: self.field_id,
    predicate: Regex(self.regex),
    rewrite: self.rewrite,
    max_expansions: self.max_expansions,
    statistics,
  }
  as &Weight
}

///|
pub struct FuzzyQuery {
  field_id : FieldId
  text : String
  max_distance : Int
  transpositions : Bool
  max_expansions : Int
}

///|
pub fn FuzzyQuery::new(
  field_id : FieldId,
  text : String,
  max_distance : Int,
) -> FuzzyQuery {
  guard max_distance >= 0 && max_distance <= 2 else {
    abort("fuzzy distance must be between zero and two")
  }
  { field_id, text, max_distance, transpositions: false, max_expansions: 256 }
}

///|
pub impl Query for FuzzyQuery with fn weight(self, statistics) {
  MultiTermWeight::{
    field_id: self.field_id,
    predicate: Fuzzy(self.text, self.max_distance, self.transpositions),
    rewrite: ScoringBoolean,
    max_expansions: self.max_expansions,
    statistics,
  }
  as &Weight
}

///|
/// Lexicographic term range for analyzed or keyword terms. Typed numeric/date
/// ranges continue to use `RangeQuery`.
pub struct TermRangeQuery {
  field_id : FieldId
  lower : String?
  lower_inclusive : Bool
  upper : String?
  upper_inclusive : Bool
  max_expansions : Int
}

///|
pub fn TermRangeQuery::new(
  field_id : FieldId,
  lower : String?,
  lower_inclusive : Bool,
  upper : String?,
  upper_inclusive : Bool,
) -> TermRangeQuery {
  {
    field_id,
    lower,
    lower_inclusive,
    upper,
    upper_inclusive,
    max_expansions: 1024,
  }
}

///|
pub impl Query for TermRangeQuery with fn weight(self, statistics) {
  MultiTermWeight::{
    field_id: self.field_id,
    predicate: LexicographicRange(
      self.lower,
      self.lower_inclusive,
      self.upper,
      self.upper_inclusive,
    ),
    rewrite: ConstantScore,
    max_expansions: self.max_expansions,
    statistics,
  }
  as &Weight
}