///|
pub(all) enum MatchType {
  Is
  Contains
  Matches
} derive(Eq, Debug)

///|
pub(all) enum Comparator {
  Octet
  AsciiCasemap
} derive(Eq, Debug)

///|
priv struct Budget {
  limits : Limits
  mut steps : Int
  mut comparisons : Int
}

///|
fn Budget::step(self : Budget, span : Span) -> Unit raise SieveError {
  if self.steps >= self.limits.steps {
    fail("limit.steps", "execution step budget exhausted", span)
  }
  self.steps += 1
}

///|
fn Budget::compare(
  self : Budget,
  n : Int,
  span : Span,
) -> Unit raise SieveError {
  if n < 0 || n > self.limits.comparisons - self.comparisons {
    fail("limit.comparisons", "matching budget exhausted", span)
  }
  self.comparisons += n
}

///|
fn new_budget(limits : Limits) -> Budget {
  { limits, steps: 0, comparisons: 0 }
}

///|
fn fold_char(c : Char, comparator : Comparator) -> Char {
  match comparator {
    Octet => c
    AsciiCasemap => c.to_ascii_lowercase()
  }
}

///|
priv enum PatternUnit {
  Exact(Char)
  One
  Many
}

///|
fn glob_units(pattern : String, comparator : Comparator) -> Array[PatternUnit] {
  let chars = pattern.to_array()
  let out : Array[PatternUnit] = []
  let mut i = 0
  while i < chars.length() {
    match chars[i] {
      '\\' if i + 1 < chars.length() => {
        i += 1
        out.push(Exact(fold_char(chars[i], comparator)))
      }
      '*' => out.push(Many)
      '?' => out.push(One)
      c => out.push(Exact(fold_char(c, comparator)))
    }
    i += 1
  }
  out
}

///|
fn compare_text(
  value : String,
  key : String,
  mode : MatchType,
  comparator : Comparator,
  budget : Budget,
  span : Span,
) -> Bool raise SieveError {
  budget.step(span)
  if value.length() > budget.limits.string_chars ||
    key.length() > budget.limits.string_chars {
    fail("limit.string", "matching input exceeds limit", span)
  }
  let text = value.to_array()
  let pattern = key.to_array()
  match mode {
    Is => {
      if text.length() != pattern.length() {
        return false
      }
      budget.compare(text.length(), span)
      for i = 0; i < text.length(); i = i + 1 {
        if fold_char(text[i], comparator) != fold_char(pattern[i], comparator) {
          return false
        }
      }
      true
    }
    Contains => {
      if pattern.is_empty() {
        return true
      }
      if pattern.length() > text.length() {
        return false
      }
      for start = 0
          start <= text.length() - pattern.length()
          start = start + 1 {
        let mut same = true
        for j = 0; j < pattern.length(); j = j + 1 {
          budget.compare(1, span)
          if fold_char(text[start + j], comparator) !=
            fold_char(pattern[j], comparator) {
            same = false
            break
          }
        }
        if same {
          return true
        }
      }
      false
    }
    Matches => {
      let units = glob_units(key, comparator)
      let width = text.length() + 1
      if units.length() + 1 >
        (budget.limits.comparisons - budget.comparisons) / width {
        fail(
          "limit.comparisons", "glob table exceeds remaining matching budget", span,
        )
      }
      budget.compare(width * (units.length() + 1), span)
      let mut previous = Array::make(width, false)
      previous[0] = true
      for unit in units {
        let current = Array::make(width, false)
        match unit {
          Many => {
            current[0] = previous[0]
            for j = 1; j < width; j = j + 1 {
              current[j] = previous[j] || current[j - 1]
            }
          }
          One =>
            for j = 1; j < width; j = j + 1 {
              current[j] = previous[j - 1]
            }
          Exact(c) =>
            for j = 1; j < width; j = j + 1 {
              current[j] = previous[j - 1] &&
                fold_char(text[j - 1], comparator) == c
            }
        }
        previous = current
      }
      previous[text.length()]
    }
  }
}

///|
pub fn match_text(
  value : String,
  key : String,
  mode : MatchType,
  comparator? : Comparator = AsciiCasemap,
  limits? : Limits = Limits::default(),
) -> Bool raise SieveError {
  limits.check()
  compare_text(value, key, mode, comparator, new_budget(limits), origin())
}