///|
priv struct Parser {
  tokens : Array[Token]
  mut cursor : Int
}

///|
fn Parser::new(tokens : Array[Token]) -> Parser {
  { tokens, cursor: 0 }
}

///|
fn Parser::current(self : Parser) -> Token {
  self.tokens[self.cursor]
}

///|
fn Parser::at_end(self : Parser) -> Bool {
  self.current().kind is Eof
}

///|
fn Parser::advance(self : Parser) -> Token {
  let token = self.current()
  if !self.at_end() {
    self.cursor = self.cursor + 1
  }
  token
}

///|
fn[T] Parser::fail_here(
  self : Parser,
  code : String,
  message : String,
  hint? : String,
) -> T raise RuleFailure {
  raise RuleFailure(
    Diagnostic::new(Parse, code, message, self.current().span, hint?),
  )
}

///|
fn Parser::consume_right_paren(self : Parser) -> Token raise RuleFailure {
  if self.current().kind is RightParen {
    return self.advance()
  }
  self.fail_here(
    "P003",
    "expected `)`",
    hint="Close the parenthesized expression.",
  )
}

///|
fn Parser::consume_right_bracket(self : Parser) -> Token raise RuleFailure {
  if self.current().kind is RightBracket {
    return self.advance()
  }
  self.fail_here(
    "P004",
    "expected `]`",
    hint="Close the array or index expression.",
  )
}

///|
fn Parser::parse(self : Parser) -> Expr raise RuleFailure {
  let expression = self.parse_or()
  if !self.at_end() {
    self.fail_here(
      "P001",
      "unexpected token after the expression",
      hint="Remove the token or join it with a supported operator.",
    )
  }
  expression
}

///|
fn Parser::parse_or(self : Parser) -> Expr raise RuleFailure {
  let mut left = self.parse_and()
  while self.current().kind is TokenKind::Or {
    self.advance() |> ignore
    let right = self.parse_and()
    let span = left.span().merge(right.span())
    left = Binary(left, BinaryOp::Or, right, span)
  }
  left
}

///|
fn Parser::parse_and(self : Parser) -> Expr raise RuleFailure {
  let mut left = self.parse_equality()
  while self.current().kind is TokenKind::And {
    self.advance() |> ignore
    let right = self.parse_equality()
    let span = left.span().merge(right.span())
    left = Binary(left, BinaryOp::And, right, span)
  }
  left
}

///|
fn Parser::parse_equality(self : Parser) -> Expr raise RuleFailure {
  let mut left = self.parse_comparison()
  while true {
    let operator = match self.current().kind {
      EqualEqual => Some(BinaryOp::Equal)
      BangEqual => Some(BinaryOp::NotEqual)
      _ => None
    }
    guard operator is Some(op) else { break }
    self.advance() |> ignore
    let right = self.parse_comparison()
    let span = left.span().merge(right.span())
    left = Binary(left, op, right, span)
  }
  left
}

///|
fn Parser::parse_comparison(self : Parser) -> Expr raise RuleFailure {
  let mut left = self.parse_term()
  while true {
    let operator = match self.current().kind {
      TokenKind::Less => Some(BinaryOp::Less)
      TokenKind::LessEqual => Some(BinaryOp::LessEqual)
      TokenKind::Greater => Some(BinaryOp::Greater)
      TokenKind::GreaterEqual => Some(BinaryOp::GreaterEqual)
      TokenKind::In => Some(BinaryOp::In)
      _ => None
    }
    guard operator is Some(op) else { break }
    self.advance() |> ignore
    let right = self.parse_term()
    let span = left.span().merge(right.span())
    left = Binary(left, op, right, span)
  }
  left
}

///|
fn Parser::parse_term(self : Parser) -> Expr raise RuleFailure {
  let mut left = self.parse_factor()
  while true {
    let operator = match self.current().kind {
      Plus => Some(BinaryOp::Add)
      Minus => Some(BinaryOp::Subtract)
      _ => None
    }
    guard operator is Some(op) else { break }
    self.advance() |> ignore
    let right = self.parse_factor()
    let span = left.span().merge(right.span())
    left = Binary(left, op, right, span)
  }
  left
}

///|
fn Parser::parse_factor(self : Parser) -> Expr raise RuleFailure {
  let mut left = self.parse_unary()
  while true {
    let operator = match self.current().kind {
      Star => Some(BinaryOp::Multiply)
      Slash => Some(BinaryOp::Divide)
      Percent => Some(BinaryOp::Remainder)
      _ => None
    }
    guard operator is Some(op) else { break }
    self.advance() |> ignore
    let right = self.parse_unary()
    let span = left.span().merge(right.span())
    left = Binary(left, op, right, span)
  }
  left
}

///|
fn Parser::parse_unary(self : Parser) -> Expr raise RuleFailure {
  match self.current().kind {
    Bang => {
      let start = self.advance().span
      let operand = self.parse_unary()
      Unary(UnaryOp::Not, operand, start.merge(operand.span()))
    }
    Minus => {
      let start = self.advance().span
      let operand = self.parse_unary()
      Unary(UnaryOp::Negate, operand, start.merge(operand.span()))
    }
    _ => self.parse_postfix()
  }
}

///|
fn Parser::parse_postfix(self : Parser) -> Expr raise RuleFailure {
  let mut expression = self.parse_primary()
  while true {
    match self.current().kind {
      Dot => {
        self.advance() |> ignore
        let name_token = self.current()
        guard name_token.kind is Identifier(name) else {
          self.fail_here("P005", "expected a field name after `.`")
        }
        self.advance() |> ignore
        expression = Member(
          expression,
          name,
          expression.span().merge(name_token.span),
        )
      }
      QuestionDot => {
        self.advance() |> ignore
        let name_token = self.current()
        guard name_token.kind is Identifier(name) else {
          self.fail_here("P009", "expected a field name after `?.`")
        }
        self.advance() |> ignore
        expression = OptionalMember(
          expression,
          name,
          expression.span().merge(name_token.span),
        )
      }
      LeftBracket => {
        self.advance() |> ignore
        let index = self.parse_or()
        let closing = self.consume_right_bracket()
        expression = Index(
          expression,
          index,
          expression.span().merge(closing.span),
        )
      }
      QuestionLeftBracket => {
        self.advance() |> ignore
        let index = self.parse_or()
        let closing = self.consume_right_bracket()
        expression = OptionalIndex(
          expression,
          index,
          expression.span().merge(closing.span),
        )
      }
      _ => break
    }
  }
  expression
}

///|
fn Parser::parse_arguments(
  self : Parser,
  opening : Span,
) -> (Array[Expr], Span) raise RuleFailure {
  let arguments = []
  if self.current().kind is RightParen {
    let closing = self.advance()
    return (arguments, opening.merge(closing.span))
  }
  while true {
    arguments.push(self.parse_or())
    if self.current().kind is Comma {
      self.advance() |> ignore
      continue
    }
    let closing = self.consume_right_paren()
    return (arguments, opening.merge(closing.span))
  } nobreak {
    self.fail_here("P007", "failed to parse function arguments")
  }
}

///|
fn Parser::parse_array(self : Parser, opening : Span) -> Expr raise RuleFailure {
  let values = []
  if self.current().kind is RightBracket {
    let closing = self.advance()
    return ArrayLiteral(values, opening.merge(closing.span))
  }
  while true {
    values.push(self.parse_or())
    if self.current().kind is Comma {
      self.advance() |> ignore
      continue
    }
    let closing = self.consume_right_bracket()
    return ArrayLiteral(values, opening.merge(closing.span))
  } nobreak {
    self.fail_here("P008", "failed to parse array literal")
  }
}

///|
fn Parser::parse_primary(self : Parser) -> Expr raise RuleFailure {
  let token = self.advance()
  match token.kind {
    True => Literal(Json::boolean(true), token.span)
    False => Literal(Json::boolean(false), token.span)
    Null => Literal(Json::null(), token.span)
    Number(text) => {
      let value = @string.parse_double(text) catch {
        _ =>
          raise RuleFailure(
            Diagnostic::new(Parse, "P006", "invalid number literal", token.span),
          )
      }
      Literal(Json::number(value, repr=text), token.span)
    }
    StringLiteral(value) => Literal(Json::string(value), token.span)
    Identifier(name) =>
      if self.current().kind is LeftParen {
        let opening = self.advance()
        let (arguments, span) = self.parse_arguments(
          token.span.merge(opening.span),
        )
        Call(name, arguments, span)
      } else {
        Variable(name, token.span)
      }
    LeftParen => {
      let expression = self.parse_or()
      self.consume_right_paren() |> ignore
      expression
    }
    LeftBracket => self.parse_array(token.span)
    Eof =>
      raise RuleFailure(
        Diagnostic::new(Parse, "P002", "expected an expression", token.span),
      )
    _ =>
      raise RuleFailure(
        Diagnostic::new(Parse, "P002", "expected an expression", token.span),
      )
  }
}

///|
fn parse_program(source : String) -> Program raise RuleFailure {
  let parser = Parser::new(lex(source))
  let root = parser.parse()
  let (node_count, ast_depth) = root.metrics()
  { root, source, node_count, ast_depth }
}