///|
priv enum RegexAtom {
  Literal(UInt16)
  Any
}

///|
priv enum RegexRepeat {
  Once
  ZeroOrOne
  ZeroOrMore
  OneOrMore
}

///|
priv struct RegexPiece {
  atom : RegexAtom
  repeat : RegexRepeat
}

///|
priv struct BoundedRegex {
  anchored_start : Bool
  anchored_end : Bool
  pieces : Array[RegexPiece]
}

///|
fn regex_error(message : String, span : SourceSpan) -> Unit raise EvalError {
  raise InvalidArgument(message="invalid matches pattern: \{message}", span~)
}

///|
fn escaped_regex_atom(
  pattern : String,
  index : Int,
  span : SourceSpan,
) -> (RegexAtom, Int) raise EvalError {
  if index + 1 >= pattern.length() {
    regex_error("trailing escape", span)
    abort("unreachable")
  }
  let escaped = pattern[index + 1]
  let value = match escaped {
    'n' => '\n'.to_uint().to_uint16()
    'r' => '\r'.to_uint().to_uint16()
    't' => '\t'.to_uint().to_uint16()
    '\\' => '\\'.to_uint().to_uint16()
    '.' => '.'.to_uint().to_uint16()
    '^' => '^'.to_uint().to_uint16()
    '$' => '$'.to_uint().to_uint16()
    '*' => '*'.to_uint().to_uint16()
    '+' => '+'.to_uint().to_uint16()
    '?' => '?'.to_uint().to_uint16()
    other => other
  }
  (RegexAtom::Literal(value), index + 2)
}

///|
fn regex_atom(
  pattern : String,
  index : Int,
  span : SourceSpan,
) -> (RegexAtom, Int) raise EvalError {
  match pattern[index] {
    '.' => (RegexAtom::Any, index + 1)
    '\\' => escaped_regex_atom(pattern, index, span)
    '(' | ')' | '[' | ']' | '{' | '}' | '|' => {
      regex_error(
        "groups, classes, ranges, and alternation are not supported", span,
      )
      abort("unreachable")
    }
    '*' | '+' | '?' => {
      regex_error("quantifier has no preceding atom", span)
      abort("unreachable")
    }
    value => (RegexAtom::Literal(value), index + 1)
  }
}

///|
fn regex_repeat(pattern : String, index : Int) -> (RegexRepeat, Int) {
  if index >= pattern.length() {
    return (RegexRepeat::Once, index)
  }
  match pattern[index] {
    '?' => (RegexRepeat::ZeroOrOne, index + 1)
    '*' => (RegexRepeat::ZeroOrMore, index + 1)
    '+' => (RegexRepeat::OneOrMore, index + 1)
    _ => (RegexRepeat::Once, index)
  }
}

///|
fn compile_bounded_regex(
  pattern : String,
  span : SourceSpan,
) -> BoundedRegex raise EvalError {
  let anchored_start = pattern.length() > 0 && pattern[0] == '^'
  let mut stop = pattern.length()
  let anchored_end = stop > 0 &&
    pattern[stop - 1] == '$' &&
    (stop < 2 || pattern[stop - 2] != '\\')
  if anchored_end {
    stop = stop - 1
  }
  let pieces : Array[RegexPiece] = []
  let mut index = if anchored_start { 1 } else { 0 }
  while index < stop {
    let (atom, after_atom) = regex_atom(pattern, index, span)
    let (repeat, next) = regex_repeat(pattern, after_atom)
    if next > stop {
      regex_error("quantifier follows the end anchor", span)
      abort("unreachable")
    }
    if next < stop &&
      (pattern[next] == '*' || pattern[next] == '+' || pattern[next] == '?') {
      regex_error("stacked quantifiers are not supported", span)
      abort("unreachable")
    }
    pieces.push({ atom, repeat })
    index = next
  }
  { anchored_start, anchored_end, pieces }
}

///|
fn RegexAtom::accepts(self : RegexAtom, code_unit : UInt16) -> Bool {
  match self {
    RegexAtom::Any => true
    RegexAtom::Literal(expected) => expected == code_unit
  }
}

///|
fn empty_positions(length : Int) -> Array[Bool] {
  Array::make(length + 1, false)
}

///|
fn advance_once(
  atom : RegexAtom,
  value : String,
  current : Array[Bool],
) -> Array[Bool] {
  let next = empty_positions(value.length())
  for position = 0; position < value.length(); position = position + 1 {
    if current[position] && atom.accepts(value[position]) {
      next[position + 1] = true
    }
  }
  next
}

///|
fn advance_optional(
  atom : RegexAtom,
  value : String,
  current : Array[Bool],
) -> Array[Bool] {
  let next = current.copy()
  for position = 0; position < value.length(); position = position + 1 {
    if current[position] && atom.accepts(value[position]) {
      next[position + 1] = true
    }
  }
  next
}

///|
fn advance_repeated(
  atom : RegexAtom,
  value : String,
  current : Array[Bool],
  require_one : Bool,
) -> Array[Bool] {
  let next = if require_one {
    empty_positions(value.length())
  } else {
    current.copy()
  }
  for start = 0; start <= value.length(); start = start + 1 {
    if !current[start] {
      continue
    }
    let mut position = start
    while position < value.length() && atom.accepts(value[position]) {
      position = position + 1
      next[position] = true
    }
  }
  next
}

///|
fn RegexPiece::advance(
  self : RegexPiece,
  value : String,
  current : Array[Bool],
) -> Array[Bool] {
  match self.repeat {
    RegexRepeat::Once => advance_once(self.atom, value, current)
    RegexRepeat::ZeroOrOne => advance_optional(self.atom, value, current)
    RegexRepeat::ZeroOrMore =>
      advance_repeated(self.atom, value, current, false)
    RegexRepeat::OneOrMore => advance_repeated(self.atom, value, current, true)
  }
}

///|
fn BoundedRegex::matches_from(
  self : BoundedRegex,
  value : String,
  start : Int,
) -> Bool {
  let mut positions = empty_positions(value.length())
  positions[start] = true
  for piece in self.pieces {
    positions = piece.advance(value, positions)
    if !positions.any(value => value) {
      return false
    }
  }
  if self.anchored_end {
    positions[value.length()]
  } else {
    positions.any(value => value)
  }
}

///|
fn BoundedRegex::matches(self : BoundedRegex, value : String) -> Bool {
  if self.anchored_start {
    return self.matches_from(value, 0)
  }
  for start = 0; start <= value.length(); start = start + 1 {
    if self.matches_from(value, start) {
      return true
    }
  }
  false
}

///|
fn bounded_regex_matches(
  value : String,
  pattern : String,
  span : SourceSpan,
) -> Bool raise EvalError {
  compile_bounded_regex(pattern, span).matches(value)
}