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

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

///|
fn Parser::advance(self : Parser) -> Token {
  let token = self.current()
  if self.position + 1 < self.tokens.length() {
    self.position = self.position + 1
  }
  token
}

///|
fn Parser::skip_newlines(self : Parser) -> Unit {
  while self.current().kind is Newline {
    ignore(self.advance())
  }
}

///|
fn parse_error(token : Token, code : String, message : String) -> Diagnostic {
  { code, message, span: token.span }
}

///|
/// Parse a complete FlipSpec document.
pub fn parse(source : String) -> Result[Policy, Diagnostic] {
  let tokens = match lex(source) {
    Ok(value) => value
    Err(error) => return Err(error)
  }
  let parser = Parser::{ tokens, position: 0 }
  parser.skip_newlines()
  if !(parser.current().kind is KeywordSpec) {
    return Err(
      parse_error(
        parser.current(),
        "E_EXPECTED_SPEC",
        "document must start with 'spec '",
      ),
    )
  }
  ignore(parser.advance())
  let name = match parser.advance().kind {
    Word(value) => value
    other =>
      return Err(
        parse_error(
          parser.tokens[parser.position - 1],
          "E_EXPECTED_NAME",
          "expected spec name, found \{token_name(other)}",
        ),
      )
  }
  match parser.consume_line_end() {
    Some(error) => return Err(error)
    None => ()
  }
  let features : Array[Feature] = []
  parser.skip_newlines()
  while parser.current().kind is KeywordFeature {
    match parser.parse_feature() {
      Ok(item) => features.push(item)
      Err(error) => return Err(error)
    }
    parser.skip_newlines()
  }
  if !(parser.current().kind is KeywordGoal) {
    return Err(
      parse_error(
        parser.current(),
        "E_EXPECTED_GOAL",
        "expected a 'goal' statement after features",
      ),
    )
  }
  ignore(parser.advance())
  let goal = match parser.parse_or() {
    Ok(value) => value
    Err(error) => return Err(error)
  }
  match parser.consume_line_end() {
    Some(error) => return Err(error)
    None => ()
  }
  parser.skip_newlines()
  if !(parser.current().kind is End) {
    return Err(
      parse_error(
        parser.current(),
        "E_TRAILING_INPUT",
        "unexpected content after goal",
      ),
    )
  }
  let result = Policy::{ name, features, goal }
  let validation = result.validate()
  if validation.length() > 0 {
    Err(validation[0])
  } else {
    Ok(result)
  }
}

///|
fn Parser::consume_line_end(self : Parser) -> Diagnostic? {
  match self.current().kind {
    Newline => {
      ignore(self.advance())
      None
    }
    End => None
    other =>
      Some(
        parse_error(
          self.current(),
          "E_EXPECTED_LINE_END",
          "expected end of line, found \{token_name(other)}",
        ),
      )
  }
}

///|
fn Parser::parse_feature(self : Parser) -> Result[Feature, Diagnostic] {
  ignore(self.advance())
  let name_token = self.advance()
  let name = match name_token.kind {
    Word(value) => value
    other =>
      return Err(
        parse_error(
          name_token,
          "E_EXPECTED_FEATURE_NAME",
          "expected feature name, found \{token_name(other)}",
        ),
      )
  }
  if !(self.current().kind is Assign) {
    return Err(
      parse_error(
        self.current(),
        "E_EXPECTED_ASSIGN",
        "expected '=' after feature name",
      ),
    )
  }
  ignore(self.advance())
  let current = match self.parse_value() {
    Ok(value) => value
    Err(error) => return Err(error)
  }
  if !(self.current().kind is KeywordIn) {
    return Err(
      parse_error(
        self.current(),
        "E_EXPECTED_IN",
        "expected 'in' before feature domain",
      ),
    )
  }
  ignore(self.advance())
  let domain = match self.parse_domain() {
    Ok(value) => value
    Err(error) => return Err(error)
  }
  let mut cost = 1
  let mut locked = false
  if self.current().kind is KeywordCost {
    ignore(self.advance())
    let cost_token = self.advance()
    match cost_token.kind {
      Number(value) if value >= 0 => cost = value
      Number(_) =>
        return Err(
          parse_error(
            cost_token, "E_NEGATIVE_COST", "feature cost cannot be negative",
          ),
        )
      other =>
        return Err(
          parse_error(
            cost_token,
            "E_EXPECTED_COST",
            "expected non-negative integer cost, found \{token_name(other)}",
          ),
        )
    }
  }
  if self.current().kind is KeywordLocked {
    ignore(self.advance())
    locked = true
  }
  match self.consume_line_end() {
    Some(error) => return Err(error)
    None => ()
  }
  Ok({ name, current, domain, cost, locked })
}

///|
fn Parser::parse_domain(self : Parser) -> Result[Array[Value], Diagnostic] {
  if !(self.current().kind is LeftBracket) {
    return Err(
      parse_error(
        self.current(),
        "E_EXPECTED_DOMAIN",
        "expected '[' to start feature domain",
      ),
    )
  }
  ignore(self.advance())
  let values : Array[Value] = []
  if self.current().kind is RightBracket {
    return Err(
      parse_error(
        self.current(),
        "E_EMPTY_DOMAIN",
        "feature domain cannot be empty",
      ),
    )
  }
  while true {
    match self.parse_value() {
      Ok(value) => values.push(value)
      Err(error) => return Err(error)
    }
    match self.current().kind {
      Comma => ignore(self.advance())
      RightBracket => {
        ignore(self.advance())
        break
      }
      other =>
        return Err(
          parse_error(
            self.current(),
            "E_EXPECTED_DOMAIN_SEPARATOR",
            "expected ',' or ']', found \{token_name(other)}",
          ),
        )
    }
  }
  Ok(values)
}

///|
fn Parser::parse_value(self : Parser) -> Result[Value, Diagnostic] {
  let token = self.advance()
  match token.kind {
    Number(value) => Ok(Integer(value))
    Quoted(value) => Ok(Text(value))
    KeywordTrue => Ok(Boolean(true))
    KeywordFalse => Ok(Boolean(false))
    other =>
      Err(
        parse_error(
          token,
          "E_EXPECTED_VALUE",
          "expected integer, boolean, or quoted text, found \{token_name(other)}",
        ),
      )
  }
}

///|
fn Parser::parse_or(self : Parser) -> Result[Expr, Diagnostic] {
  let mut left = match self.parse_and() {
    Ok(value) => value
    Err(error) => return Err(error)
  }
  while self.current().kind is KeywordOr {
    ignore(self.advance())
    let right = match self.parse_and() {
      Ok(value) => value
      Err(error) => return Err(error)
    }
    left = Or(left, right)
  }
  Ok(left)
}

///|
fn Parser::parse_and(self : Parser) -> Result[Expr, Diagnostic] {
  let mut left = match self.parse_unary() {
    Ok(value) => value
    Err(error) => return Err(error)
  }
  while self.current().kind is KeywordAnd {
    ignore(self.advance())
    let right = match self.parse_unary() {
      Ok(value) => value
      Err(error) => return Err(error)
    }
    left = And(left, right)
  }
  Ok(left)
}

///|
fn Parser::parse_unary(self : Parser) -> Result[Expr, Diagnostic] {
  if self.current().kind is KeywordNot {
    ignore(self.advance())
    return match self.parse_unary() {
      Ok(value) => Ok(Not(value))
      Err(error) => Err(error)
    }
  }
  self.parse_primary()
}

///|
fn Parser::parse_primary(self : Parser) -> Result[Expr, Diagnostic] {
  if self.current().kind is LeftParen {
    ignore(self.advance())
    let inner = match self.parse_or() {
      Ok(value) => value
      Err(error) => return Err(error)
    }
    if !(self.current().kind is RightParen) {
      return Err(
        parse_error(self.current(), "E_EXPECTED_RPAREN", "expected ')'"),
      )
    }
    ignore(self.advance())
    return Ok(inner)
  }
  if self.current().kind is KeywordPresent {
    ignore(self.advance())
    if !(self.current().kind is LeftParen) {
      return Err(
        parse_error(
          self.current(),
          "E_EXPECTED_LPAREN",
          "expected '(' after 'present'",
        ),
      )
    }
    ignore(self.advance())
    let name_token = self.advance()
    let name = match name_token.kind {
      Word(value) => value
      other =>
        return Err(
          parse_error(
            name_token,
            "E_EXPECTED_FEATURE_NAME",
            "expected feature name, found \{token_name(other)}",
          ),
        )
    }
    if !(self.current().kind is RightParen) {
      return Err(
        parse_error(
          self.current(),
          "E_EXPECTED_RPAREN",
          "expected ')' after feature name",
        ),
      )
    }
    ignore(self.advance())
    return Ok(Present(name))
  }
  match self.current().kind {
    KeywordTrue => {
      ignore(self.advance())
      return Ok(Constant(Yes))
    }
    KeywordFalse => {
      ignore(self.advance())
      return Ok(Constant(No))
    }
    _ => ()
  }
  let name_token = self.advance()
  let name = match name_token.kind {
    Word(value) => value
    other =>
      return Err(
        parse_error(
          name_token,
          "E_EXPECTED_EXPRESSION",
          "expected comparison or parenthesized expression, found \{token_name(other)}",
        ),
      )
  }
  let operator_token = self.current()
  let operator = match operator_token.kind {
    EqualEqual => {
      ignore(self.advance())
      Equal
    }
    BangEqual => {
      ignore(self.advance())
      NotEqual
    }
    LessToken => {
      ignore(self.advance())
      Less
    }
    LessEqualToken => {
      ignore(self.advance())
      LessEqual
    }
    GreaterToken => {
      ignore(self.advance())
      Greater
    }
    GreaterEqualToken => {
      ignore(self.advance())
      GreaterEqual
    }
    KeywordAnd | KeywordOr | RightParen | Newline | End =>
      return Ok(Compare(name, Equal, Boolean(true)))
    other =>
      return Err(
        parse_error(
          operator_token,
          "E_EXPECTED_OPERATOR",
          "expected comparison operator after '\{name}', found \{token_name(other)}",
        ),
      )
  }
  match self.parse_value() {
    Ok(value) => Ok(Compare(name, operator, value))
    Err(error) => Err(error)
  }
}