///|
/// A lexical unit before trivia is attached: a significant token or trivia.
pub(all) enum RawTokenKind {
  Significant(TokenKind)
  Whitespace
  Newline
  LineComment
  BlockComment
  DocComment
} derive(Eq, Debug)

///|
pub(all) struct RawToken {
  kind : RawTokenKind
  lexeme : String
  span : Span
} derive(Eq, Debug)

///|
/// Position in the source. Columns count code points, as elm-syntax does: the
/// low half of a surrogate pair does not add a column.
priv struct Cursor {
  text : String
  mut pos : Int
  mut line : Int
  mut column : Int
}

///|
fn Cursor::new(text : String) -> Cursor {
  { text, pos: 0, line: 1, column: 1, }
}

///|
/// Code unit `ahead` units after the cursor, or -1 at the end.
fn Cursor::at(self : Cursor, ahead? : Int = 0) -> Int {
  let i = self.pos + ahead
  if i < self.text.length() {
    self.text.code_unit_at(i).to_int()
  } else {
    -1
  }
}

///|
/// The code point at the cursor and its width in code units (a surrogate pair
/// is one code point, two units), or `(-1, 0)` at the end.
fn Cursor::code_point(self : Cursor) -> (Int, Int) {
  let c = self.at()
  if c >= 0xD800 && c <= 0xDBFF {
    let low = self.at(ahead=1)
    if low >= 0xDC00 && low <= 0xDFFF {
      return (0x10000 + ((c - 0xD800) << 10) + (low - 0xDC00), 2)
    }
  }
  (c, if c < 0 { 0 } else { 1 })
}

///|
/// Whether the code point at the cursor satisfies `predicate`.
fn Cursor::code_point_is(self : Cursor, predicate : (Char) -> Bool) -> Bool {
  let (cp, width) = self.code_point()
  width > 0 && predicate(Int::unsafe_to_char(cp))
}

///|
fn Cursor::done(self : Cursor) -> Bool {
  self.pos >= self.text.length()
}

///|
fn Cursor::position(self : Cursor) -> Position {
  { offset: self.pos, line: self.line, column: self.column, }
}

///|
/// Move one code unit forward, tracking lines and columns. Does nothing at
/// the end of the input.
fn Cursor::advance(self : Cursor) -> Unit {
  if self.done() {
    return
  }
  let c = self.at()
  if c == '\n'.to_int() {
    self.line += 1
    self.column = 1
  } else if !(c >= 0xDC00 && c <= 0xDFFF && self.after_high_surrogate()) {
    // The low half of a surrogate pair adds no column; a lone surrogate is
    // one character.
    self.column += 1
  }
  self.pos += 1
}

///|
fn Cursor::advance_by(self : Cursor, n : Int) -> Unit {
  for _ in 0.. Bool {
  for i in 0.. String {
  self.text.unsafe_substring(start~, end=self.pos)
}

///|
fn is_ascii_digit_code(c : Int) -> Bool {
  c >= '0'.to_int() && c <= '9'.to_int()
}

///|
fn is_hex_digit_code(c : Int) -> Bool {
  is_ascii_digit_code(c) ||
  (c >= 'a'.to_int() && c <= 'f'.to_int()) ||
  (c >= 'A'.to_int() && c <= 'F'.to_int())
}

///|
fn is_symbol_char(c : Int) -> Bool {
  match c {
    '+'
    | '-'
    | '/'
    | '*'
    | '='
    | '.'
    | '<'
    | '>'
    | ':'
    | '&'
    | '|'
    | '^'
    | '?' => true
    _ => false
  }
}

///|
/// Tokens made of symbol characters, longest first so that the longest known
/// prefix of a run wins.
let symbol_tokens : Array[String] = [
  "", "", "==", "/=", "::", "++", "<|", "|>", "||", "<=", ">=", "|=", "|.",
  "//", "<<", ">>", "&&", "->", "..", "+", "*", "^", "<", ">", "/", "-", "=", ".",
  ":", "|",
]

///|
/// The dialect's extra operator symbols plus the standard ones, longest first.
/// Empty symbols are ignored: they would match without moving the cursor.
fn symbols_of(dialect : @dialect.Dialect) -> Array[String] {
  let extra = dialect.operator_symbols.filter(s => s != "")
  if extra.is_empty() {
    return symbol_tokens
  }
  let all = [..extra, ..symbol_tokens]
  all.sort_by((a, b) => b.length().compare(a.length()))
  all
}

///|
fn symbol_kind(symbol : String) -> TokenKind {
  match symbol {
    "=" => Equals
    "." => Dot
    ".." => DotDot
    ":" => Colon
    "|" => Pipe
    "->" => Arrow
    op => Operator(op)
  }
}

///|
fn keyword_of(name : String, dialect : @dialect.Dialect) -> KeywordKind? {
  match name {
    "module" => Some(Module)
    "exposing" => Some(Exposing)
    "import" => Some(Import)
    "as" => Some(As)
    "type" => Some(Type)
    "if" => Some(If)
    "then" => Some(Then)
    "else" => Some(Else)
    "let" => Some(Let)
    "in" => Some(In)
    "case" => Some(Case)
    "of" => Some(Of)
    "port" => Some(Port)
    "where" => Some(Where)
    _ if dialect.reserved_words.contains(name) => Some(Custom(name))
    _ => None
  }
}

///|
/// Skip a block comment starting at `{-`, including nested block comments.
/// Returns whether the comment was closed.
fn skip_block_comment(cursor : Cursor) -> Bool {
  let mut depth = 0
  while !cursor.done() {
    if cursor.starts_with("{-") {
      depth += 1
      cursor.advance_by(2)
    } else if cursor.starts_with("-}") {
      depth -= 1
      cursor.advance_by(2)
      if depth == 0 {
        return true
      }
    } else {
      cursor.advance()
    }
  }
  false
}

///|
/// Skip a quoted literal body up to and including `close`. Backslash escapes
/// one code unit. Returns whether it was closed; a line break ends an
/// unclosed single-line literal.
fn skip_quoted(cursor : Cursor, close : String, multiline : Bool) -> Bool {
  while !cursor.done() {
    if cursor.starts_with(close) {
      cursor.advance_by(close.length())
      return true
    }
    let c = cursor.at()
    // A single-line literal ends before an unescaped line break, LF or CRLF,
    // so its span never ends inside a CRLF.
    let line_break = (ahead : Int) => {
      cursor.at(ahead~) == '\n'.to_int() ||
      (
        cursor.at(ahead~) == '\r'.to_int() &&
        cursor.at(ahead=ahead + 1) == '\n'.to_int()
      )
    }
    if !multiline && line_break(0) {
      return false
    } else if c == '\\'.to_int() {
      // An escaped line break is an unknown escape (as in elm make), not the
      // end of the literal; a CRLF is taken whole, so no span ends inside it.
      let crlf = cursor.at(ahead=1) == '\r'.to_int() &&
        cursor.at(ahead=2) == '\n'.to_int()
      cursor.advance_by(if crlf { 3 } else { 2 })
    } else {
      cursor.advance()
    }
  }
  false
}

///|
/// Skip up to and including `close`, with no escapes (GLSL blocks). Returns
/// whether `close` was found.
fn skip_until(cursor : Cursor, close : String) -> Bool {
  while !cursor.done() {
    if cursor.starts_with(close) {
      cursor.advance_by(close.length())
      return true
    }
    cursor.advance()
  }
  false
}

///|
/// Skip a number: decimal or `0x` hexadecimal integer, or a float with an
/// optional fraction and exponent. Returns whether it is a float.
fn skip_number(cursor : Cursor) -> Bool {
  if cursor.starts_with("0x") && is_hex_digit_code(cursor.at(ahead=2)) {
    cursor.advance_by(2)
    while is_hex_digit_code(cursor.at()) {
      cursor.advance()
    }
    return false
  }
  while is_ascii_digit_code(cursor.at()) {
    cursor.advance()
  }
  let mut float = false
  if cursor.at() == '.'.to_int() && is_ascii_digit_code(cursor.at(ahead=1)) {
    float = true
    cursor.advance()
    while is_ascii_digit_code(cursor.at()) {
      cursor.advance()
    }
  }
  let e = cursor.at()
  if e == 'e'.to_int() || e == 'E'.to_int() {
    let sign = cursor.at(ahead=1)
    let digits_at = if sign == '+'.to_int() || sign == '-'.to_int() {
      2
    } else {
      1
    }
    if is_ascii_digit_code(cursor.at(ahead=digits_at)) {
      float = true
      cursor.advance_by(digits_at)
      while is_ascii_digit_code(cursor.at()) {
        cursor.advance()
      }
    }
  }
  float
}

///|
/// Split Elm source into significant tokens and trivia. Diagnostics:
/// `KR-SCAN-001` unterminated block comment, `KR-SCAN-002` malformed doc
/// comment, `KR-SCAN-003` a character Elm does not allow here, `KR-SCAN-004`
/// an unterminated string, char or GLSL literal.
pub fn lex_raw(
  source : SourceText,
  dialect? : @dialect.Dialect = @dialect.Dialect::elm_0_19_1(),
) -> Result[Array[RawToken], ScanErrorList] {
  let symbols = symbols_of(dialect)
  let cursor = Cursor::new(source.text)
  let tokens : Array[RawToken] = []
  let diagnostics = []
  while !cursor.done() {
    let start = cursor.position()
    let c = cursor.at()
    let kind : RawTokenKind? = if c == ' '.to_int() {
      while cursor.at() == ' '.to_int() {
        cursor.advance()
      }
      Some(Whitespace)
    } else if c == '\r'.to_int() && cursor.at(ahead=1) != '\n'.to_int() {
      // A lone carriage return is whitespace, as in elm make and elm-syntax.
      cursor.advance()
      Some(Whitespace)
    } else if c == '\n'.to_int() || cursor.starts_with("\r\n") {
      cursor.advance_by(if c == '\n'.to_int() { 1 } else { 2 })
      Some(Newline)
    } else if cursor.starts_with("--") {
      while !cursor.done() &&
            cursor.at() != '\n'.to_int() &&
            cursor.at() != '\r'.to_int() {
        cursor.advance()
      }
      Some(LineComment)
    } else if cursor.starts_with("{-|") {
      if !skip_block_comment(cursor) {
        diagnostics.push(
          malformed_doc_comment({ start, end: cursor.position(), }),
        )
      }
      Some(DocComment)
    } else if cursor.starts_with("{-") {
      if !skip_block_comment(cursor) {
        diagnostics.push(
          unterminated_block_comment({ start, end: cursor.position(), }),
        )
      }
      Some(BlockComment)
    } else if cursor.starts_with("[glsl|") {
      cursor.advance_by(6)
      if !skip_until(cursor, "|]") {
        diagnostics.push(unterminated_glsl({ start, end: cursor.position(), }))
      }
      Some(Significant(Glsl))
    } else if cursor.starts_with("\"\"\"") {
      cursor.advance_by(3)
      if !skip_quoted(cursor, "\"\"\"", true) {
        diagnostics.push(
          unterminated_multiline_string({ start, end: cursor.position(), }),
        )
      }
      Some(Significant(StringLiteral))
    } else if c == '"'.to_int() {
      cursor.advance()
      if !skip_quoted(cursor, "\"", false) {
        diagnostics.push(
          unterminated_string({ start, end: cursor.position(), }),
        )
      }
      Some(Significant(StringLiteral))
    } else if c == '\''.to_int() {
      cursor.advance()
      if !skip_quoted(cursor, "'", false) {
        diagnostics.push(unterminated_char({ start, end: cursor.position(), }))
      }
      Some(Significant(CharLiteral))
    } else if is_ascii_digit_code(c) {
      Some(
        Significant(if skip_number(cursor) { FloatLiteral } else { IntLiteral }),
      )
    } else if cursor.code_point_is(is_lower_start) ||
      (
        cursor.code_point_is(is_upper_start) &&
        !(dialect.has(TitlecaseNameStart) && cursor.code_point_is(is_titlecase))
      ) ||
      (
        dialect.has(NonAsciiDigitInName) &&
        cursor.code_point_is(is_non_ascii_number)
      ) {
      // With non-ascii-digit-in-name, a name stops before a non-ASCII number,
      // and the rest lexes as a separate name that the parser rejects, as
      // elm make does.
      let digits_end = dialect.has(NonAsciiDigitInName)
      let mut first = true
      while cursor.code_point_is(is_name_part) &&
            !(digits_end && !first && cursor.code_point_is(is_non_ascii_number)) {
        cursor.advance_by(cursor.code_point().1)
        first = false
      }
      match keyword_of(cursor.slice(start.offset), dialect) {
        Some(k) => Some(Significant(Keyword(k)))
        None => Some(Significant(Identifier))
      }
    } else if is_symbol_char(c) {
      match symbols.search_by(s => cursor.starts_with(s)) {
        Some(i) => {
          let symbol = symbols[i]
          cursor.advance_by(symbol.length())
          Some(Significant(symbol_kind(symbol)))
        }
        None => {
          cursor.advance()
          diagnostics.push(invalid_sequence({ start, end: cursor.position(), }))
          None
        }
      }
    } else {
      let punctuation : TokenKind? = match c {
        '(' => Some(LParen)
        ')' => Some(RParen)
        '[' => Some(LBracket)
        ']' => Some(RBracket)
        '{' => Some(LBrace)
        '}' => Some(RBrace)
        ',' => Some(Comma)
        '\\' => Some(Backslash)
        '_' => Some(Underscore)
        _ => None
      }
      match punctuation {
        Some(p) => {
          cursor.advance()
          Some(Significant(p))
        }
        None => {
          // A surrogate pair is one character (two code units); a lone
          // surrogate is one unit.
          let (_, width) = cursor.code_point()
          cursor.advance_by(width)
          let span = { start, end: cursor.position(), }
          diagnostics.push(
            match c {
              '\t' => tab_character(span)
              ';' => unexpected_semicolon(span)
              '`' => unexpected_character(span)
              _ if c < 0x80 => invalid_sequence(span)
              _ => unexpected_character(span)
            },
          )
          None
        }
      }
    }
    if kind is Some(k) {
      tokens.push({
        kind: k,
        lexeme: cursor.slice(start.offset),
        span: { start, end: cursor.position(), },
      })
    }
  }
  if diagnostics.is_empty() {
    Ok(tokens)
  } else {
    Err({ diagnostics, })
  }
}

///|
/// Whether the code unit before the cursor is a high surrogate.
fn Cursor::after_high_surrogate(self : Cursor) -> Bool {
  if self.pos == 0 {
    return false
  }
  let prev = self.text.code_unit_at(self.pos - 1).to_int()
  prev >= 0xD800 && prev <= 0xDBFF
}