///|
priv enum TokenKind {
  Eof
  Identifier(String)
  NullLiteral
  BoolLiteral(Bool)
  IntLiteral(String)
  UIntLiteral(String)
  DoubleLiteral(String)
  StringLiteral(String, Bool)
  BytesLiteral(String, Bool)
  LeftParen
  RightParen
  LeftBracket
  RightBracket
  LeftBrace
  RightBrace
  Comma
  Dot
  Colon
  Question
  OrOr
  AndAnd
  EqualEqual
  BangEqual
  Less
  LessEqual
  Greater
  GreaterEqual
  Plus
  Minus
  Star
  Slash
  Percent
  Bang
  In
} derive(Eq)

///|
fn TokenKind::label(self : TokenKind) -> String {
  match self {
    Eof => "end of input"
    Identifier(name) => "identifier(\{name})"
    NullLiteral => "null"
    BoolLiteral(value) => if value { "true" } else { "false" }
    IntLiteral(text) => "int(\{text})"
    UIntLiteral(text) => "uint(\{text})"
    DoubleLiteral(text) => "double(\{text})"
    StringLiteral(_, raw) => if raw { "raw string" } else { "string" }
    BytesLiteral(_, raw) => if raw { "raw bytes" } else { "bytes" }
    LeftParen => "("
    RightParen => ")"
    LeftBracket => "["
    RightBracket => "]"
    LeftBrace => "{"
    RightBrace => "}"
    Comma => ","
    Dot => "."
    Colon => ":"
    Question => "?"
    OrOr => "||"
    AndAnd => "&&"
    EqualEqual => "=="
    BangEqual => "!="
    Less => "<"
    LessEqual => "<="
    Greater => ">"
    GreaterEqual => ">="
    Plus => "+"
    Minus => "-"
    Star => "*"
    Slash => "/"
    Percent => "%"
    Bang => "!"
    In => "in"
  }
}

///|
priv struct Token {
  kind : TokenKind
  span : SourceSpan
}

///|
fn Token::label(self : Token) -> String {
  self.kind.label()
}

///|
priv struct Lexer {
  source : String
  mut index : Int
  mut line : Int
  mut column : Int
}

///|
fn Lexer::new(source : String) -> Lexer {
  { source, index: 0, line: 1, column: 1 }
}

///|
fn Lexer::at_end(self : Lexer) -> Bool {
  self.index >= self.source.length()
}

///|
fn Lexer::peek(self : Lexer) -> UInt16? {
  if self.at_end() {
    None
  } else {
    Some(self.source[self.index])
  }
}

///|
fn Lexer::peek_next(self : Lexer) -> UInt16? {
  if self.index + 1 >= self.source.length() {
    None
  } else {
    Some(self.source[self.index + 1])
  }
}

///|
fn Lexer::advance(self : Lexer) -> UInt16 {
  let value = self.source[self.index]
  self.index += 1
  if value == '\n' {
    self.line += 1
    self.column = 1
  } else {
    self.column += 1
  }
  value
}

///|
fn Lexer::take_if(self : Lexer, expected : UInt16) -> Bool {
  if self.peek() == Some(expected) {
    ignore(self.advance())
    true
  } else {
    false
  }
}

///|
fn Lexer::slice(self : Lexer, start : Int, end : Int) -> String {
  self.source[start:end].to_owned()
}

///|
fn Lexer::span_from(
  self : Lexer,
  start : Int,
  start_line : Int,
  start_column : Int,
) -> SourceSpan {
  SourceSpan::new(start~, end=self.index, line=start_line, column=start_column)
}

///|
fn is_ascii_letter(value : UInt16) -> Bool {
  (value >= 'a' && value <= 'z') || (value >= 'A' && value <= 'Z')
}

///|
fn is_ascii_digit(value : UInt16) -> Bool {
  value >= '0' && value <= '9'
}

///|
fn is_hex_digit(value : UInt16) -> Bool {
  is_ascii_digit(value) ||
  (value >= 'a' && value <= 'f') ||
  (value >= 'A' && value <= 'F')
}

///|
fn is_identifier_start(value : UInt16) -> Bool {
  value == '_' || is_ascii_letter(value)
}

///|
fn is_identifier_continue(value : UInt16) -> Bool {
  is_identifier_start(value) || is_ascii_digit(value)
}

///|
fn is_reserved_identifier(value : String) -> Bool {
  match value {
    "as"
    | "break"
    | "const"
    | "continue"
    | "else"
    | "for"
    | "function"
    | "if"
    | "import"
    | "let"
    | "loop"
    | "package"
    | "namespace"
    | "return"
    | "var"
    | "void"
    | "while" => true
    _ => false
  }
}

///|
fn Lexer::skip_layout(self : Lexer) -> Unit {
  for ;; {
    match self.peek() {
      Some(' ' | '\t' | '\r' | '\n' | '\f') => ignore(self.advance())
      Some('/') =>
        if self.peek_next() == Some('/') {
          ignore(self.advance())
          ignore(self.advance())
          while self.peek() is Some(value) && value != '\n' {
            ignore(self.advance())
          }
        } else {
          break
        }
      _ => break
    }
  }
}

///|
fn Lexer::identifier(
  self : Lexer,
  start : Int,
  start_line : Int,
  start_column : Int,
) -> Token raise ParseError {
  while self.peek() is Some(value) && is_identifier_continue(value) {
    ignore(self.advance())
  }
  let text = self.slice(start, self.index)
  let span = self.span_from(start, start_line, start_column)
  if is_reserved_identifier(text) {
    raise ParseError(
      code="CEL-LEX-RESERVED",
      message="reserved identifier '\{text}' cannot be used",
      span~,
    )
  }
  let kind = match text {
    "null" => NullLiteral
    "true" => BoolLiteral(true)
    "false" => BoolLiteral(false)
    "in" => In
    _ => Identifier(text)
  }
  { kind, span }
}

///|
fn Lexer::number(
  self : Lexer,
  start : Int,
  start_line : Int,
  start_column : Int,
) -> Token raise ParseError {
  let mut is_double = false
  if self.source[start] == '0' && self.peek() is Some('x' | 'X') {
    ignore(self.advance())
    let digits_start = self.index
    while self.peek() is Some(value) && is_hex_digit(value) {
      ignore(self.advance())
    }
    if self.index == digits_start {
      raise ParseError(
        code="CEL-LEX-NUMBER",
        message="hexadecimal literal requires at least one digit",
        span=self.span_from(start, start_line, start_column),
      )
    }
  } else {
    while self.peek() is Some(value) && is_ascii_digit(value) {
      ignore(self.advance())
    }
    if self.peek() == Some('.') &&
      self.peek_next() is Some(next) &&
      is_ascii_digit(next) {
      is_double = true
      ignore(self.advance())
      while self.peek() is Some(value) && is_ascii_digit(value) {
        ignore(self.advance())
      }
    }
    if self.peek() is Some('e' | 'E') {
      is_double = true
      ignore(self.advance())
      if self.peek() is Some('+' | '-') {
        ignore(self.advance())
      }
      let exponent_start = self.index
      while self.peek() is Some(value) && is_ascii_digit(value) {
        ignore(self.advance())
      }
      if self.index == exponent_start {
        raise ParseError(
          code="CEL-LEX-NUMBER",
          message="numeric exponent requires at least one digit",
          span=self.span_from(start, start_line, start_column),
        )
      }
    }
  }
  let unsigned = if !is_double && self.peek() is Some('u' | 'U') {
    ignore(self.advance())
    true
  } else {
    false
  }
  if self.peek() is Some(value) && is_identifier_continue(value) {
    raise ParseError(
      code="CEL-LEX-NUMBER",
      message="invalid character after numeric literal",
      span=self.span_from(start, start_line, start_column),
    )
  }
  let text = self.slice(start, self.index)
  let span = self.span_from(start, start_line, start_column)
  let kind = if is_double {
    DoubleLiteral(text)
  } else if unsigned {
    UIntLiteral(text)
  } else {
    IntLiteral(text)
  }
  { kind, span }
}

///|
fn Lexer::quoted(
  self : Lexer,
  start : Int,
  start_line : Int,
  start_column : Int,
  quote : UInt16,
  content_start : Int,
  bytes : Bool,
  raw : Bool,
) -> Token raise ParseError {
  let mut escaped = false
  for ;; {
    match self.peek() {
      None =>
        raise ParseError(
          code="CEL-LEX-STRING",
          message="unterminated quoted literal",
          span=self.span_from(start, start_line, start_column),
        )
      Some('\n' | '\r') =>
        raise ParseError(
          code="CEL-LEX-STRING",
          message="single-line quoted literal cannot contain a newline",
          span=self.span_from(start, start_line, start_column),
        )
      Some(value) => {
        ignore(self.advance())
        if !raw && !escaped && value == '\\' {
          escaped = true
        } else if !escaped && value == quote {
          let content = self.slice(content_start, self.index - 1)
          let span = self.span_from(start, start_line, start_column)
          let kind = if bytes {
            BytesLiteral(content, raw)
          } else {
            StringLiteral(content, raw)
          }
          return { kind, span }
        } else {
          escaped = false
        }
      }
    }
  }
}

///|
fn Lexer::prefixed_quote(
  self : Lexer,
  start : Int,
  start_line : Int,
  start_column : Int,
) -> Token? raise ParseError {
  let first = self.source[start]
  let mut bytes = false
  let mut raw = false
  if first == 'b' || first == 'B' {
    bytes = true
  } else if first == 'r' || first == 'R' {
    raw = true
  } else {
    return None
  }
  if self.peek() is Some('b' | 'B') && raw {
    bytes = true
    ignore(self.advance())
  } else if self.peek() is Some('r' | 'R') && bytes {
    raw = true
    ignore(self.advance())
  }
  match self.peek() {
    Some('\'' | '"') as found => {
      let quote = found.unwrap()
      ignore(self.advance())
      Some(
        self.quoted(
          start,
          start_line,
          start_column,
          quote,
          self.index,
          bytes,
          raw,
        ),
      )
    }
    _ => None
  }
}

///|
fn Lexer::next_token(self : Lexer) -> Token raise ParseError {
  self.skip_layout()
  let start = self.index
  let start_line = self.line
  let start_column = self.column
  if self.at_end() {
    return {
      kind: Eof,
      span: SourceSpan::new(
        start~,
        end=start,
        line=start_line,
        column=start_column,
      ),
    }
  }
  let first = self.advance()
  if is_ascii_digit(first) {
    return self.number(start, start_line, start_column)
  }
  if is_identifier_start(first) {
    if first is ('b' | 'B' | 'r' | 'R') {
      match self.prefixed_quote(start, start_line, start_column) {
        Some(token) => return token
        None => ()
      }
    }
    return self.identifier(start, start_line, start_column)
  }
  if first is ('\'' | '"') {
    return self.quoted(
      start,
      start_line,
      start_column,
      first,
      self.index,
      false,
      false,
    )
  }
  let kind = match first {
    '(' => LeftParen
    ')' => RightParen
    '[' => LeftBracket
    ']' => RightBracket
    '{' => LeftBrace
    '}' => RightBrace
    ',' => Comma
    '.' => Dot
    ':' => Colon
    '?' => Question
    '+' => Plus
    '-' => Minus
    '*' => Star
    '%' => Percent
    '/' => Slash
    '!' => if self.take_if('=') { BangEqual } else { Bang }
    '=' =>
      if self.take_if('=') {
        EqualEqual
      } else {
        raise ParseError(
          code="CEL-LEX-CHAR",
          message="assignment is not part of CEL; use '==' for equality",
          span=self.span_from(start, start_line, start_column),
        )
      }
    '<' => if self.take_if('=') { LessEqual } else { Less }
    '>' => if self.take_if('=') { GreaterEqual } else { Greater }
    '&' =>
      if self.take_if('&') {
        AndAnd
      } else {
        raise ParseError(
          code="CEL-LEX-CHAR",
          message="expected '&&'",
          span=self.span_from(start, start_line, start_column),
        )
      }
    '|' =>
      if self.take_if('|') {
        OrOr
      } else {
        raise ParseError(
          code="CEL-LEX-CHAR",
          message="expected '||'",
          span=self.span_from(start, start_line, start_column),
        )
      }
    _ =>
      raise ParseError(
        code="CEL-LEX-CHAR",
        message="unexpected character at source offset \{start}",
        span=self.span_from(start, start_line, start_column),
      )
  }
  { kind, span: self.span_from(start, start_line, start_column) }
}

///|
fn lex(source : String) -> Array[Token] raise ParseError {
  let lexer = Lexer::new(source)
  let tokens : Array[Token] = []
  for ;; {
    let token = lexer.next_token()
    let done = token.kind == Eof
    tokens.push(token)
    if done {
      break
    }
  }
  tokens
}

///|
pub fn lex_labels(source : String) -> Array[String] raise ParseError {
  lex(source).map(token => token.label())
}