///|
priv struct Parser {
  tokens : Array[Token]
  source : String
  mut index : Int
  mut next_id : Int
}

///|
fn Parser::new(tokens : Array[Token], source : String) -> Parser {
  { tokens, source, index: 0, next_id: 1 }
}

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

///|
fn Parser::previous(self : Parser) -> Token {
  self.tokens[self.index - 1]
}

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

///|
fn Parser::advance(self : Parser) -> Token {
  if !self.at_end() {
    self.index += 1
  }
  self.tokens[self.index - 1]
}

///|
fn Parser::new_id(self : Parser) -> Int {
  let id = self.next_id
  self.next_id += 1
  id
}

///|
fn Parser::check(self : Parser, expected : TokenKind) -> Bool {
  self.current().kind == expected
}

///|
fn Parser::take(self : Parser, expected : TokenKind) -> Bool {
  if self.check(expected) {
    ignore(self.advance())
    true
  } else {
    false
  }
}

///|
fn Parser::fail(self : Parser, code : String, message : String) -> ParseError {
  ParseError(code~, message~, span=self.current().span)
}

///|
fn Parser::expect(
  self : Parser,
  expected : TokenKind,
  description : String,
) -> Token raise ParseError {
  if self.check(expected) {
    self.advance()
  } else {
    raise self.fail(
      "CEL-PARSE-EXPECTED",
      "expected \{description}, found \{self.current().label()}",
    )
  }
}

///|
fn Parser::expect_identifier(
  self : Parser,
  context : String,
) -> (String, Token) raise ParseError {
  match self.current().kind {
    Identifier(name) => {
      let token = self.advance()
      (name, token)
    }
    _ =>
      raise self.fail(
        "CEL-PARSE-IDENTIFIER",
        "expected identifier \{context}, found \{self.current().label()}",
      )
  }
}

///|
fn Parser::parse(self : Parser) -> ParsedExpr raise ParseError {
  let root = self.conditional()
  if !self.at_end() {
    raise self.fail(
      "CEL-PARSE-TRAILING",
      "unexpected trailing token \{self.current().label()}",
    )
  }
  { source: self.source, root }
}

///|
fn Parser::conditional(self : Parser) -> Expr raise ParseError {
  let condition = self.logical_or()
  if !self.take(Question) {
    return condition
  }
  let when_true = self.logical_or()
  ignore(self.expect(Colon, "':' in conditional expression"))
  let when_false = self.conditional()
  let span = condition.span.merge(when_false.span)
  Expr::conditional(self.new_id(), span, condition, when_true, when_false)
}

///|
fn Parser::logical_or(self : Parser) -> Expr raise ParseError {
  let mut expression = self.logical_and()
  while self.take(OrOr) {
    let right = self.logical_and()
    expression = Expr::binary(
      self.new_id(),
      expression.span.merge(right.span),
      BinaryOp::Or,
      expression,
      right,
    )
  }
  expression
}

///|
fn Parser::logical_and(self : Parser) -> Expr raise ParseError {
  let mut expression = self.relation()
  while self.take(AndAnd) {
    let right = self.relation()
    expression = Expr::binary(
      self.new_id(),
      expression.span.merge(right.span),
      BinaryOp::And,
      expression,
      right,
    )
  }
  expression
}

///|
fn relation_operator(kind : TokenKind) -> BinaryOp? {
  match kind {
    EqualEqual => Some(BinaryOp::Equal)
    BangEqual => Some(BinaryOp::NotEqual)
    Less => Some(BinaryOp::Less)
    LessEqual => Some(BinaryOp::LessEqual)
    Greater => Some(BinaryOp::Greater)
    GreaterEqual => Some(BinaryOp::GreaterEqual)
    In => Some(BinaryOp::In)
    _ => None
  }
}

///|
fn Parser::relation(self : Parser) -> Expr raise ParseError {
  let mut expression = self.addition()
  while relation_operator(self.current().kind) is Some(operator) {
    ignore(self.advance())
    let right = self.addition()
    expression = Expr::binary(
      self.new_id(),
      expression.span.merge(right.span),
      operator,
      expression,
      right,
    )
  }
  expression
}

///|
fn addition_operator(kind : TokenKind) -> BinaryOp? {
  match kind {
    Plus => Some(BinaryOp::Add)
    Minus => Some(BinaryOp::Subtract)
    _ => None
  }
}

///|
fn Parser::addition(self : Parser) -> Expr raise ParseError {
  let mut expression = self.multiplication()
  while addition_operator(self.current().kind) is Some(operator) {
    ignore(self.advance())
    let right = self.multiplication()
    expression = Expr::binary(
      self.new_id(),
      expression.span.merge(right.span),
      operator,
      expression,
      right,
    )
  }
  expression
}

///|
fn multiplication_operator(kind : TokenKind) -> BinaryOp? {
  match kind {
    Star => Some(BinaryOp::Multiply)
    Slash => Some(BinaryOp::Divide)
    Percent => Some(BinaryOp::Modulo)
    _ => None
  }
}

///|
fn Parser::multiplication(self : Parser) -> Expr raise ParseError {
  let mut expression = self.unary()
  while multiplication_operator(self.current().kind) is Some(operator) {
    ignore(self.advance())
    let right = self.unary()
    expression = Expr::binary(
      self.new_id(),
      expression.span.merge(right.span),
      operator,
      expression,
      right,
    )
  }
  expression
}

///|
fn Parser::unary(self : Parser) -> Expr raise ParseError {
  if self.take(Bang) {
    let operator_span = self.previous().span
    let operand = self.unary()
    return Expr::unary(
      self.new_id(),
      operator_span.merge(operand.span),
      UnaryOp::Not,
      operand,
    )
  }
  if self.take(Minus) {
    let operator_span = self.previous().span
    let operand = self.unary()
    return Expr::unary(
      self.new_id(),
      operator_span.merge(operand.span),
      UnaryOp::Negate,
      operand,
    )
  }
  self.postfix()
}

///|
fn Parser::arguments(
  self : Parser,
) -> (Array[Expr], SourceSpan) raise ParseError {
  let open = self.expect(LeftParen, "'('")
  let args : Array[Expr] = []
  if !self.check(RightParen) {
    for ;; {
      args.push(self.conditional())
      if !self.take(Comma) {
        break
      }
      if self.check(RightParen) {
        break
      }
    }
  }
  let close = self.expect(RightParen, "')'")
  (args, open.span.merge(close.span))
}

///|
fn Parser::postfix(self : Parser) -> Expr raise ParseError {
  let mut expression = self.primary()
  for ;; {
    if self.take(Dot) {
      let (name, name_token) = self.expect_identifier("after '.'")
      if self.check(LeftParen) {
        let (args, call_span) = self.arguments()
        expression = Expr::receiver_call(
          self.new_id(),
          expression.span.merge(call_span),
          expression,
          name,
          args,
        )
      } else {
        expression = Expr::select(
          self.new_id(),
          expression.span.merge(name_token.span),
          expression,
          name,
        )
      }
      continue
    }
    if self.take(LeftBracket) {
      let index = self.conditional()
      let close = self.expect(RightBracket, "']'")
      expression = Expr::index(
        self.new_id(),
        expression.span.merge(close.span),
        expression,
        index,
      )
      continue
    }
    break
  }
  expression
}

///|
fn Parser::primary(self : Parser) -> Expr raise ParseError {
  let token = self.current()
  match token.kind {
    NullLiteral
    | BoolLiteral(_)
    | IntLiteral(_)
    | UIntLiteral(_)
    | DoubleLiteral(_)
    | StringLiteral(_, _)
    | BytesLiteral(_, _) => {
      ignore(self.advance())
      Expr::literal(self.new_id(), token.span, literal_from_token(token))
    }
    Identifier(name) => {
      ignore(self.advance())
      if self.check(LeftParen) {
        let (args, call_span) = self.arguments()
        Expr::call(self.new_id(), token.span.merge(call_span), name, args)
      } else {
        Expr::identifier(self.new_id(), token.span, name)
      }
    }
    LeftParen => {
      ignore(self.advance())
      let expression = self.conditional()
      ignore(self.expect(RightParen, "')'"))
      expression
    }
    LeftBracket => self.list_literal()
    LeftBrace => self.map_literal()
    _ =>
      raise self.fail(
        "CEL-PARSE-PRIMARY",
        "expected expression, found \{self.current().label()}",
      )
  }
}

///|
fn Parser::list_literal(self : Parser) -> Expr raise ParseError {
  let open = self.expect(LeftBracket, "'['")
  let items : Array[Expr] = []
  if !self.check(RightBracket) {
    for ;; {
      items.push(self.conditional())
      if !self.take(Comma) {
        break
      }
      if self.check(RightBracket) {
        break
      }
    }
  }
  let close = self.expect(RightBracket, "']'")
  Expr::list(self.new_id(), open.span.merge(close.span), items)
}

///|
fn Parser::map_literal(self : Parser) -> Expr raise ParseError {
  let open = self.expect(LeftBrace, "'{'")
  let entries : Array[MapExprEntry] = []
  if !self.check(RightBrace) {
    for ;; {
      let key = self.conditional()
      ignore(self.expect(Colon, "':' between map key and value"))
      let value = self.conditional()
      entries.push({ key, value, span: key.span.merge(value.span) })
      if !self.take(Comma) {
        break
      }
      if self.check(RightBrace) {
        break
      }
    }
  }
  let close = self.expect(RightBrace, "'}'")
  Expr::map(self.new_id(), open.span.merge(close.span), entries)
}

///|
/// Parse one CEL expression into a source-aware abstract syntax tree.
pub fn parse(source : StringView) -> ParsedExpr raise ParseError {
  let owned_source = source.to_owned()
  Parser::new(lex(owned_source), owned_source).parse()
}