///|
pub(all) struct ParseError {
  message : String
  span : @source.Span
} derive(Eq, Debug)

///|
pub(all) struct ParseResult {
  design : @syntax.Design
  errors : Array[ParseError]
} derive(Debug)

///|
priv struct Cursor {
  tokens : Array[@lexer.Token]
  mut position : Int
  errors : Array[ParseError]
}

///|
fn Cursor::new(tokens : Array[@lexer.Token]) -> Cursor {
  { tokens, position: 0, errors: [] }
}

///|
fn Cursor::peek(self : Cursor) -> @lexer.Token {
  self.tokens[self.position]
}

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

///|
fn Cursor::at(self : Cursor, kind : @lexer.TokenKind) -> Bool {
  self.peek().kind == kind
}

///|
fn Cursor::consume(self : Cursor, kind : @lexer.TokenKind) -> @lexer.Token? {
  if self.at(kind) {
    Some(self.advance())
  } else {
    None
  }
}

///|
fn Cursor::error(self : Cursor, message : String) -> Unit {
  self.errors.push({ message, span: self.peek().span })
}

///|
fn Cursor::expect(
  self : Cursor,
  kind : @lexer.TokenKind,
  message : String,
) -> @lexer.Token {
  match self.consume(kind) {
    Some(token) => token
    None => {
      self.error(message)
      self.peek()
    }
  }
}

///|
fn Cursor::expect_identifier(self : Cursor) -> (@lexer.Token, String) {
  if self.at(@lexer.Identifier) {
    let token = self.advance()
    (token, token.lexeme)
  } else {
    self.error("expected identifier")
    (self.peek(), "")
  }
}

///|
fn Cursor::synchronize(self : Cursor) -> Unit {
  while !self.at(@lexer.Eof) &&
        !self.at(@lexer.Semicolon) &&
        !self.at(@lexer.KeywordEndmodule) &&
        !self.at(@lexer.KeywordModule) {
    ignore(self.advance())
  }
  if self.at(@lexer.Semicolon) {
    ignore(self.advance())
  }
}

///|
fn decimal_value(text : String) -> Int? {
  let chars = text.to_array()
  let mut index = 0
  let mut value = 0
  let mut valid = chars.length() > 0
  while index < chars.length() && valid {
    if chars[index] >= '0' && chars[index] <= '9' {
      value = value * 10 + chars[index].to_int() - '0'.to_int()
      index = index + 1
    } else {
      valid = false
    }
  }
  if valid {
    Some(value)
  } else {
    None
  }
}

///|
fn Cursor::parse_direction(self : Cursor) -> @syntax.Direction {
  if self.at(@lexer.KeywordInput) {
    ignore(self.advance())
    @syntax.Input
  } else if self.at(@lexer.KeywordOutput) {
    ignore(self.advance())
    @syntax.Output
  } else if self.at(@lexer.KeywordInout) {
    ignore(self.advance())
    @syntax.Inout
  } else {
    @syntax.Unspecified
  }
}

///|
fn Cursor::parse_net_type(self : Cursor) -> @syntax.NetType {
  if self.at(@lexer.KeywordWire) {
    ignore(self.advance())
    @syntax.Wire
  } else if self.at(@lexer.KeywordReg) {
    ignore(self.advance())
    @syntax.Reg
  } else {
    @syntax.Unspecified
  }
}

///|
fn Cursor::parse_range(self : Cursor) -> @syntax.Range? {
  if self.at(@lexer.LBracket) {
    let open = self.advance()
    let high = self.expect(@lexer.Number, "expected range bound")
    ignore(self.expect(@lexer.Colon, "expected ':' in range"))
    let low = self.expect(@lexer.Number, "expected range bound")
    let close = self.expect(@lexer.RBracket, "expected ']' after range")
    let msb = match decimal_value(high.lexeme) {
      Some(value) => value
      None => 0
    }
    let lsb = match decimal_value(low.lexeme) {
      Some(value) => value
      None => 0
    }
    Some(
      @syntax.Range::new(
        msb,
        lsb,
        @source.Span::new(open.span.start, close.span.end),
      ),
    )
  } else {
    None
  }
}

///|
fn Cursor::parse_ports(self : Cursor) -> Array[@syntax.Port] {
  let ports : Array[@syntax.Port] = []
  if self.consume(@lexer.LParen) is Some(_) {
    while !self.at(@lexer.RParen) && !self.at(@lexer.Eof) {
      let start = self.peek().span.start
      let direction = self.parse_direction()
      ignore(self.parse_net_type())
      let width = self.parse_range()
      let (name_token, name) = self.expect_identifier()
      let end = name_token.span.end
      ports.push(
        @syntax.Port::new(name, direction, width, @source.Span::new(start, end)),
      )
      if self.consume(@lexer.Comma) is None {
        break
      }
    }
    ignore(self.expect(@lexer.RParen, "expected ')' after port list"))
  }
  ports
}

///|
fn Cursor::parse_declaration(self : Cursor) -> Array[@syntax.Signal] {
  let start = self.peek().span.start
  let net_type = self.parse_net_type()
  let width = self.parse_range()
  let signals : Array[@syntax.Signal] = []
  while !self.at(@lexer.Semicolon) && !self.at(@lexer.Eof) {
    let (name_token, name) = self.expect_identifier()
    signals.push(
      @syntax.Signal::new(
        name,
        net_type,
        width,
        @source.Span::new(start, name_token.span.end),
      ),
    )
    if self.consume(@lexer.Comma) is None {
      break
    }
  }
  ignore(self.expect(@lexer.Semicolon, "expected ';' after declaration"))
  signals
}

///|
fn precedence(kind : @lexer.TokenKind) -> Int? {
  match kind {
    @lexer.LogicalOr => Some(1)
    @lexer.LogicalAnd => Some(2)
    @lexer.BitOr => Some(3)
    @lexer.BitXor => Some(4)
    @lexer.BitAnd => Some(5)
    @lexer.EqualEqual | @lexer.NotEqual => Some(6)
    @lexer.Less | @lexer.LessEqual | @lexer.Greater | @lexer.GreaterEqual =>
      Some(7)
    @lexer.Plus | @lexer.Minus => Some(8)
    @lexer.Star | @lexer.Slash | @lexer.Percent => Some(9)
    _ => None
  }
}

///|
fn operator_text(kind : @lexer.TokenKind) -> String {
  match kind {
    @lexer.LogicalOr => "||"
    @lexer.LogicalAnd => "&&"
    @lexer.BitOr => "|"
    @lexer.BitXor => "^"
    @lexer.BitAnd => "&"
    @lexer.EqualEqual => "=="
    @lexer.NotEqual => "!="
    @lexer.Less => "<"
    @lexer.LessEqual => "<="
    @lexer.Greater => ">"
    @lexer.GreaterEqual => ">="
    @lexer.Plus => "+"
    @lexer.Minus => "-"
    @lexer.Star => "*"
    @lexer.Slash => "/"
    @lexer.Percent => "%"
    _ => "?"
  }
}

///|
fn Cursor::parse_primary(self : Cursor) -> @syntax.Expression {
  let token = self.peek()
  if self.at(@lexer.Identifier) {
    ignore(self.advance())
    let base = @syntax.Expression::name(token.lexeme, token.span)
    if self.consume(@lexer.LBracket) is Some(_) {
      let index = self.parse_expression(0)
      let close = self.expect(@lexer.RBracket, "expected ']' after index")
      @syntax.Expression::Index(
        base,
        index,
        @source.Span::new(token.span.start, close.span.end),
      )
    } else {
      base
    }
  } else if self.at(@lexer.Number) {
    ignore(self.advance())
    @syntax.Expression::number(token.lexeme, token.span)
  } else if self.at(@lexer.StringLiteral) {
    ignore(self.advance())
    @syntax.Expression::string(token.lexeme, token.span)
  } else if self.at(@lexer.LParen) {
    let open = self.advance()
    let expression = self.parse_expression(0)
    let close = self.expect(@lexer.RParen, "expected ')' after expression")
    @syntax.Expression::Unary(
      "group",
      expression,
      @source.Span::new(open.span.start, close.span.end),
    )
  } else if self.at(@lexer.Minus) ||
    self.at(@lexer.Plus) ||
    self.at(@lexer.LogicalNot) ||
    self.at(@lexer.BitNot) {
    ignore(self.advance())
    let inner = self.parse_primary()
    @syntax.Expression::Unary(
      token.lexeme,
      inner,
      @source.Span::new(token.span.start, inner.span().end),
    )
  } else {
    self.error("expected expression")
    ignore(self.advance())
    @syntax.Expression::Unknown(token.span)
  }
}

///|
fn Cursor::parse_expression(self : Cursor, minimum : Int) -> @syntax.Expression {
  let mut left = self.parse_primary()
  while precedence(self.peek().kind) is Some(priority) && priority >= minimum {
    let operator = self.advance()
    let right = self.parse_expression(priority + 1)
    let span = @source.Span::new(left.span().start, right.span().end)
    left = @syntax.Expression::binary(
      left,
      operator_text(operator.kind),
      right,
      span,
    )
  }
  left
}

///|
fn Cursor::parse_assignment(self : Cursor, start : Int) -> @syntax.Statement {
  let target = self.parse_expression(0)
  let nonblocking = if self.consume(@lexer.NonBlockingAssign) is Some(_) {
    true
  } else {
    ignore(self.expect(@lexer.Equal, "expected assignment operator"))
    false
  }
  let value = self.parse_expression(0)
  let end = self.expect(@lexer.Semicolon, "expected ';' after assignment")
  @syntax.Statement::Assignment(
    target,
    value,
    nonblocking,
    @source.Span::new(start, end.span.end),
  )
}

///|
fn Cursor::parse_block(self : Cursor) -> @syntax.Statement {
  let start = self.expect(@lexer.KeywordBegin, "expected 'begin'")
  let statements : Array[@syntax.Statement] = []
  while !self.at(@lexer.KeywordEnd) && !self.at(@lexer.Eof) {
    statements.push(self.parse_statement())
  }
  let end = self.expect(@lexer.KeywordEnd, "expected 'end'")
  @syntax.Statement::Block(
    statements,
    @source.Span::new(start.span.start, end.span.end),
  )
}

///|
fn Cursor::parse_if(self : Cursor) -> @syntax.Statement {
  let start = self.expect(@lexer.KeywordIf, "expected 'if'")
  ignore(self.expect(@lexer.LParen, "expected '(' after if"))
  let condition = self.parse_expression(0)
  ignore(self.expect(@lexer.RParen, "expected ')' after if condition"))
  let then_branch = self.parse_statement()
  let else_branch = if self.consume(@lexer.KeywordElse) is Some(_) {
    Some(self.parse_statement())
  } else {
    None
  }
  @syntax.Statement::If(
    condition,
    then_branch,
    else_branch,
    @source.Span::new(start.span.start, then_branch.span().end),
  )
}

///|
fn Cursor::parse_case(self : Cursor) -> @syntax.Statement {
  let start = self.expect(@lexer.KeywordCase, "expected 'case'")
  ignore(self.expect(@lexer.LParen, "expected '(' after case"))
  let expression = self.parse_expression(0)
  ignore(self.expect(@lexer.RParen, "expected ')' after case expression"))
  let arms : Array[@syntax.CaseArm] = []
  while !self.at(@lexer.KeywordEndcase) && !self.at(@lexer.Eof) {
    let arm_start = self.peek().span.start
    let choices : Array[@syntax.Expression] = []
    if self.consume(@lexer.KeywordDefault) is Some(_) {
      ignore(self.expect(@lexer.Colon, "expected ':' after default"))
    } else {
      choices.push(self.parse_expression(0))
      ignore(self.expect(@lexer.Colon, "expected ':' after case choice"))
    }
    let body = self.parse_statement()
    arms.push({
      choices,
      body,
      span: @source.Span::new(arm_start, body.span().end),
    })
  }
  let end = self.expect(@lexer.KeywordEndcase, "expected 'endcase'")
  @syntax.Statement::Case(
    expression,
    arms,
    @source.Span::new(start.span.start, end.span.end),
  )
}

///|
fn Cursor::parse_statement(self : Cursor) -> @syntax.Statement {
  if self.at(@lexer.KeywordBegin) {
    self.parse_block()
  } else if self.at(@lexer.KeywordIf) {
    self.parse_if()
  } else if self.at(@lexer.KeywordCase) {
    self.parse_case()
  } else if self.at(@lexer.Semicolon) {
    @syntax.Statement::Empty(self.advance().span)
  } else if self.at(@lexer.Identifier) {
    self.parse_assignment(self.peek().span.start)
  } else {
    let token = self.advance()
    self.error("unexpected token in statement")
    self.synchronize()
    @syntax.Statement::Unknown(token.span)
  }
}

///|
fn Cursor::parse_continuous_assign(self : Cursor) -> @syntax.ContinuousAssign {
  let start = self.expect(@lexer.KeywordAssign, "expected 'assign'")
  let target = self.parse_expression(0)
  ignore(self.expect(@lexer.Equal, "expected '=' after assign target"))
  let value = self.parse_expression(0)
  let end = self.expect(@lexer.Semicolon, "expected ';' after assign")
  @syntax.ContinuousAssign::new(
    target,
    value,
    @source.Span::new(start.span.start, end.span.end),
  )
}

///|
fn Cursor::parse_always(self : Cursor) -> @syntax.AlwaysBlock {
  let start = self.expect(@lexer.KeywordAlways, "expected 'always'")
  let sensitivity : Array[@syntax.Sensitivity] = []
  if self.consume(@lexer.At) is Some(_) {
    ignore(self.expect(@lexer.LParen, "expected '(' after @"))
    while !self.at(@lexer.RParen) && !self.at(@lexer.Eof) {
      let item_start = self.peek().span.start
      let edge = if self.consume(@lexer.KeywordPosedge) is Some(_) {
        @syntax.Posedge
      } else if self.consume(@lexer.KeywordNegedge) is Some(_) {
        @syntax.Negedge
      } else {
        @syntax.Any
      }
      let expression = if self.at(@lexer.Star) {
        let token = self.advance()
        @syntax.Expression::Unknown(token.span)
      } else {
        self.parse_primary()
      }
      sensitivity.push({
        edge,
        expression,
        span: @source.Span::new(item_start, expression.span().end),
      })
      if self.at(@lexer.Identifier) && self.peek().lexeme == "or" {
        ignore(self.advance())
      } else if self.consume(@lexer.Comma) is Some(_) {
        ()
      } else if !self.at(@lexer.RParen) {
        self.error("expected sensitivity separator")
        ignore(self.advance())
      }
    }
    ignore(self.expect(@lexer.RParen, "expected ')' after sensitivity list"))
  }
  let body = self.parse_statement()
  @syntax.AlwaysBlock::{
    sensitivity,
    body,
    span: @source.Span::new(start.span.start, body.span().end),
  }
}

///|
fn Cursor::parse_instance(self : Cursor) -> @syntax.Instance {
  let module_token = self.advance()
  let (_, instance_name) = self.expect_identifier()
  let connections : Array[@syntax.Connection] = []
  if self.consume(@lexer.LParen) is Some(_) {
    while !self.at(@lexer.RParen) && !self.at(@lexer.Eof) {
      let start = self.peek().span.start
      let port_name = if self.consume(@lexer.Dot) is Some(_) {
        let (_, name) = self.expect_identifier()
        ignore(self.expect(@lexer.LParen, "expected '(' after named port"))
        Some(name)
      } else {
        None
      }
      let expression = self.parse_expression(0)
      let end = expression.span().end
      if port_name is Some(_) {
        ignore(
          self.expect(@lexer.RParen, "expected ')' after named connection"),
        )
      }
      connections.push({
        port_name,
        expression,
        span: @source.Span::new(start, end),
      })
      if self.consume(@lexer.Comma) is None {
        break
      }
    }
    ignore(self.expect(@lexer.RParen, "expected ')' after instance"))
  }
  let end = self.expect(@lexer.Semicolon, "expected ';' after instance")
  @syntax.Instance::{
    module_name: module_token.lexeme,
    instance_name,
    connections,
    span: @source.Span::new(module_token.span.start, end.span.end),
  }
}

///|
fn Cursor::parse_module(self : Cursor) -> @syntax.Module {
  let start = self.expect(@lexer.KeywordModule, "expected 'module'")
  let (_, name) = self.expect_identifier()
  let ports = self.parse_ports()
  ignore(self.expect(@lexer.Semicolon, "expected ';' after module header"))
  let signals : Array[@syntax.Signal] = []
  let items : Array[@syntax.ModuleItem] = []
  while !self.at(@lexer.KeywordEndmodule) &&
        !self.at(@lexer.Eof) &&
        !self.at(@lexer.KeywordModule) {
    if self.at(@lexer.KeywordWire) || self.at(@lexer.KeywordReg) {
      for signal in self.parse_declaration() {
        signals.push(signal)
      }
    } else if self.at(@lexer.KeywordAssign) {
      items.push(@syntax.Assign(self.parse_continuous_assign()))
    } else if self.at(@lexer.KeywordAlways) {
      items.push(@syntax.Always(self.parse_always()))
    } else if self.at(@lexer.Identifier) &&
      self.tokens[self.position + 1].kind is @lexer.Identifier {
      items.push(@syntax.Instance(self.parse_instance()))
    } else if self.at(@lexer.Identifier) ||
      self.at(@lexer.KeywordBegin) ||
      self.at(@lexer.KeywordIf) {
      items.push(@syntax.Statement(self.parse_statement()))
    } else {
      self.error("unexpected token in module")
      self.synchronize()
    }
  }
  let end = if self.at(@lexer.KeywordEndmodule) {
    self.advance().span.end
  } else {
    self.error("expected 'endmodule'")
    self.peek().span.end
  }
  @syntax.Module::new(
    name,
    ports,
    signals,
    items,
    @source.Span::new(start.span.start, end),
  )
}

///|
pub fn parse(file : @source.SourceFile) -> ParseResult {
  let state = Cursor::new(@lexer.lex(file))
  let modules : Array[@syntax.Module] = []
  while !state.at(@lexer.Eof) {
    if state.at(@lexer.KeywordModule) {
      modules.push(state.parse_module())
    } else {
      state.error("expected module declaration")
      ignore(state.advance())
    }
  }
  { design: @syntax.Design::new(modules), errors: state.errors }
}