///|
priv enum TokenKind {
  Name(String)
  Number(Int64)
  Mark(String)
  End
}

///|
priv struct Token {
  kind : TokenKind
  position : Int32
}

///|
fn lex(text : String) -> Result[Array[Token], MonitorError] {
  if text.length() > 16384 {
    return Err(ResourceLimit("rule text exceeds 16384 code units"))
  }
  let chars = text.to_array()
  let result : Array[Token] = []
  let mut cursor = 0
  while cursor < chars.length() {
    let at = cursor
    let c = chars[cursor]
    if c == ' ' || c == '\t' || c == '\n' || c == '\r' {
      cursor += 1
      continue
    }
    if (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || c == '_' {
      let mut name = ""
      while cursor < chars.length() {
        let ch = chars[cursor]
        if !((ch >= 'a' && ch <= 'z') ||
          (ch >= 'A' && ch <= 'Z') ||
          (ch >= '0' && ch <= '9') ||
          ch == '_' ||
          ch == '.') {
          break
        }
        name += ch.to_string()
        cursor += 1
      }
      if !valid_identifier(name) {
        return Err(SyntaxError(at, "identifier exceeds 128 characters"))
      }
      result.push({ kind: Name(name), position: at, })
    } else if c >= '0' && c <= '9' {
      let mut number = 0L
      while cursor < chars.length() &&
            chars[cursor] >= '0' &&
            chars[cursor] <= '9' {
        let digit = (chars[cursor].to_int() - 48).to_int64()
        if number > (9223372036854775807L - digit) / 10L {
          return Err(SyntaxError(at, "integer overflow"))
        }
        number = number * 10L + digit
        cursor += 1
      }
      result.push({ kind: Number(number), position: at, })
    } else {
      let mut mark = c.to_string()
      cursor += 1
      if c == '-' && cursor < chars.length() && chars[cursor] == '>' {
        mark = "->"
        cursor += 1
      } else if c != '!' &&
        c != '&' &&
        c != '|' &&
        c != '(' &&
        c != ')' &&
        c != '[' &&
        c != ']' &&
        c != ',' {
        return Err(SyntaxError(at, "unexpected character " + c.to_string()))
      }
      result.push({ kind: Mark(mark), position: at, })
    }
  }
  result.push({ kind: End, position: chars.length(), })
  Ok(result)
}

///|
priv struct Parser {
  tokens : Array[Token]
  limits : Limits
  mut cursor : Int32
  mut built : Int32
}

///|
fn Parser::mark(self : Parser, expected : String) -> Bool {
  match self.tokens[self.cursor].kind {
    Mark(actual) if actual == expected => {
      self.cursor += 1
      true
    }
    _ => false
  }
}

///|
fn Parser::expect(
  self : Parser,
  expected : String,
) -> Result[Unit, MonitorError] {
  if self.mark(expected) {
    Ok(())
  } else {
    Err(SyntaxError(self.tokens[self.cursor].position, "expected " + expected))
  }
}

///|
fn Parser::number(self : Parser) -> Result[Int64, MonitorError] {
  match self.tokens[self.cursor].kind {
    Number(value) => {
      self.cursor += 1
      Ok(value)
    }
    _ =>
      Err(
        SyntaxError(
          self.tokens[self.cursor].position,
          "expected nonnegative integer",
        ),
      )
  }
}

///|
fn Parser::interval(self : Parser) -> Result[Interval, MonitorError] {
  match self.expect("[") {
    Err(e) => return Err(e)
    Ok(_) => ()
  }
  let lower = match self.number() {
    Err(e) => return Err(e)
    Ok(v) => v
  }
  match self.expect(",") {
    Err(e) => return Err(e)
    Ok(_) => ()
  }
  let upper = match self.number() {
    Err(e) => return Err(e)
    Ok(v) => v
  }
  match self.expect("]") {
    Err(e) => return Err(e)
    Ok(_) => ()
  }
  Interval::new(lower, upper)
}

///|
fn Parser::count(
  self : Parser,
  value : Formula,
) -> Result[Formula, MonitorError] {
  self.built += 1
  if self.built > self.limits.nodes {
    Err(ResourceLimit("parsed formula node budget"))
  } else {
    Ok(value)
  }
}

///|
fn Parser::prefix(
  self : Parser,
  depth : Int32,
) -> Result[Formula, MonitorError] {
  if depth > self.limits.depth {
    return Err(ResourceLimit("parser nesting depth"))
  }
  if self.mark("!") {
    let child = match self.prefix(depth + 1) {
      Err(e) => return Err(e)
      Ok(v) => v
    }
    return self.count(Not(child))
  }
  if self.mark("(") {
    let result = match self.expression(0, depth + 1) {
      Err(e) => return Err(e)
      Ok(v) => v
    }
    match self.expect(")") {
      Err(e) => return Err(e)
      Ok(_) => ()
    }
    return Ok(result)
  }
  let token = self.tokens[self.cursor]
  self.cursor += 1
  match token.kind {
    Name("true") => self.count(Constant(true))
    Name("false") => self.count(Constant(false))
    Name("previous") => {
      let child = match self.prefix(depth + 1) {
        Err(e) => return Err(e)
        Ok(v) => v
      }
      self.count(Previous(child))
    }
    Name("once") | Name("historically") => {
      let window = match self.interval() {
        Err(e) => return Err(e)
        Ok(v) => v
      }
      let child = match self.prefix(depth + 1) {
        Err(e) => return Err(e)
        Ok(v) => v
      }
      if token.kind is Name("once") {
        self.count(Once(window, child))
      } else {
        self.count(Historically(window, child))
      }
    }
    Name("since") =>
      Err(SyntaxError(token.position, "since requires a left operand"))
    Name(name) => self.count(Atom(name))
    _ => Err(SyntaxError(token.position, "expected a formula"))
  }
}

///|
fn Parser::expression(
  self : Parser,
  minimum : Int32,
  depth : Int32,
) -> Result[Formula, MonitorError] {
  let mut left = match self.prefix(depth) {
    Err(e) => return Err(e)
    Ok(v) => v
  }
  while true {
    let (precedence, operation) = match self.tokens[self.cursor].kind {
      Mark("->") => (1, "implies")
      Mark("|") => (2, "or")
      Mark("&") => (3, "and")
      Name("since") => (4, "since")
      _ => (0, "")
    }
    if precedence == 0 || precedence < minimum {
      break
    }
    self.cursor += 1
    let interval = if operation == "since" {
      match self.interval() {
        Err(e) => return Err(e)
        Ok(v) => Some(v)
      }
    } else {
      None
    }
    let next = if operation == "implies" { precedence } else { precedence + 1 }
    let right = match self.expression(next, depth + 1) {
      Err(e) => return Err(e)
      Ok(v) => v
    }
    let combined = match operation {
      "implies" => Implies(left, right)
      "or" => Or(left, right)
      "and" => And(left, right)
      _ => Since(interval.unwrap(), left, right)
    }
    left = match self.count(combined) {
      Err(e) => return Err(e)
      Ok(v) => v
    }
  }
  Ok(left)
}

///|
/// ASCII identifiers; character offsets in errors count Unicode scalar values.
/// Precedence: unary > since > & > | > ->. Implication associates to the right.
pub fn parse(
  text : String,
  limits~ : Limits = Limits::defaults(),
) -> Result[Formula, MonitorError] {
  let tokens = match lex(text) {
    Err(e) => return Err(e)
    Ok(v) => v
  }
  let parser = Parser::{ tokens, limits, cursor: 0, built: 0, }
  let result = match parser.expression(0, 1) {
    Err(e) => return Err(e)
    Ok(v) => v
  }
  if parser.tokens[parser.cursor].kind is End {
    match Plan::new([("parsed", result)], limits~) {
      Err(error) => Err(error)
      Ok(_) => Ok(result)
    }
  } else {
    Err(
      SyntaxError(
        parser.tokens[parser.cursor].position,
        "unexpected trailing token",
      ),
    )
  }
}