///|
let symbol_repr_to_id : Map[String, Int] = {}

///|
/// Creates a new `Symbol` from a string.
///
/// If the symbol already exists in the global symbol table, the existing symbol is returned.
/// This ensures that `Symbol`s with the same string representation are always identical.
pub fn Symbol::new(str : String) -> Symbol {
  if symbol_repr_to_id.get(str) is Some(id) {
    { id, repr: str }
  } else {
    let new_id = symbol_repr_to_id.length()
    symbol_repr_to_id[str] = new_id
    { id: new_id, repr: str }
  }
}

///|
pub impl Show for Symbol with output(self, logger) {
  logger.write_string(self.repr)
}

///|
pub impl Eq for Symbol with equal(self, other) {
  self.id == other.id
}

///|
pub impl Hash for Symbol with hash_combine(self, hasher) {
  hasher.combine_int(self.id)
}

///|
fn Position::new() -> Position {
  { line: 1, col: 1 }
}

///|
fn Position::next_line(self : Position) -> Unit {
  self.line += 1
  self.col = 1
}

///|
fn Lexer::new(input : StringView) -> Lexer {
  { input_iter: RevertableIter::new(input.iter()), pos: Position::new() }
}

///|
fn is_separator(c : Char) -> Bool {
  c.is_whitespace() || c == '(' || c == ')' || c == ';' || c == '"'
}

///|
fn Lexer::read_codepoint(self : Lexer, length : Int) -> Result[Char, String] {
  let hex = StringBuilder::new()
  for _ in 0.. hex.write_char(h)
      _ => return Err("Invalid unicode character literal")
    }
  }
  let codepoint = try! @string.parse_int(hex.to_string(), base=16)
  match codepoint.to_char() {
    Some(c) => {
      self.pos.col += length
      Ok(c)
    }
    None => Err("Invalid unicode codepoint")
  }
}

///|
fn Lexer::read_chars(self : Lexer, expected : String) -> Bool {
  let prev_col = self.pos.col
  let chars_taken = []
  for expected_c in expected {
    match self.input_iter.next() {
      Some(c) if c == expected_c => {
        chars_taken.push(c)
        self.pos.col += 1
      }
      maybe_c => {
        self.pos.col = prev_col
        if maybe_c is Some(c) {
          self.input_iter.revert(c)
        }
        for c in chars_taken.rev_iter() {
          self.input_iter.revert(c)
        }
        return false
      }
    }
  }
  true
}

///|
let char_constant_literals : FixedArray[(String, Char)] = [
  ("space", ' '),
  ("tab", '\t'),
  ("newline", '\n'),
  ("return", '\r'),
  ("backspace", '\b'),
  ("nul", '\u0000'),
]

///|
fn Lexer::read_char(self : Lexer) -> Result[Char, String] {
  guard self.input_iter.peek() is Some(c) else {
    return Err("Invalid character literal at end of input")
  }
  if c == 'u' {
    self.pos.col += 1
    self.input_iter.next() |> ignore
    return self.read_codepoint(4)
  }
  for pair in char_constant_literals {
    if self.read_chars(pair.0) {
      return Ok(pair.1)
    }
  }
  self.input_iter.next() |> ignore
  if c == '\n' {
    self.pos.next_line()
  } else {
    self.pos.col += 1
  }
  if self.input_iter.peek() is Some(c) && !is_separator(c) {
    Err("Invalid character literal")
  } else {
    Ok(c)
  }
}

///|
fn Lexer::read_hash(self : Lexer) -> Result[Token, String] {
  guard self.input_iter.next() is Some(c) else {
    return Err("Invalid token at end of input")
  }
  self.pos.col += 1
  match c {
    ';' => Ok(BlockCommentBegin)
    't' => Ok(Bool(true))
    'f' => Ok(Bool(false))
    '\\' => self.read_char().map(c => Char(c))
    _ => Err("Invalid token after '#'")
  }
}

///|
fn Lexer::read_number(self : Lexer) -> Result[Token, String] {
  let num_str = StringBuilder::new()
  let mut has_dot = false
  let mut has_exp = false
  if self.input_iter.peek() is Some('-' | '+' as c) {
    self.input_iter.next() |> ignore
    self.pos.col += 1
    num_str.write_char(c)
  }
  while self.input_iter.next() is Some(c) {
    if is_separator(c) {
      self.input_iter.revert(c)
      break
    }
    self.pos.col += 1
    if c.is_ascii_digit() {
      num_str.write_char(c)
    } else if c == '.' {
      if has_dot || has_exp {
        return Err("Invalid number literal")
      }
      has_dot = true
      num_str.write_char(c)
    } else if c == 'e' || c == 'E' {
      if has_exp {
        return Err("Invalid number literal")
      }
      has_exp = true
      num_str.write_char(c)
      match self.input_iter.peek() {
        Some('+') | Some('-') => {
          let sign = self.input_iter.next().unwrap()
          self.pos.col += 1
          num_str.write_char(sign)
        }
        _ => ()
      }
    } else {
      return Err("Invalid number literal")
    }
  }
  let num_string = num_str.to_string()
  if num_string == "-" {
    return Ok(Symbol(Symbol::new("-")))
  }
  if num_string == "+" {
    return Ok(Symbol(Symbol::new("+")))
  }
  if has_dot || has_exp {
    Ok(Double(@string.parse_double(num_string))) catch {
      _ => Err("Invalid double literal")
    }
  } else {
    Ok(Int(@string.parse_int(num_string))) catch {
      _ => Err("Invalid integer literal")
    }
  }
}

///|
fn Lexer::read_indent(self : Lexer) -> String {
  let ident = StringBuilder::new()
  while self.input_iter.next() is Some(c) {
    if c.is_whitespace() || c == '(' || c == ')' {
      self.input_iter.revert(c)
      break
    } else {
      self.pos.col += 1
      ident.write_char(c)
    }
  }
  ident.to_string()
}

///|
fn Lexer::read_string(self : Lexer) -> Result[Token, String] {
  let str_builder = StringBuilder::new()
  while self.input_iter.next() is Some(c) {
    match c {
      '"' => {
        self.pos.col += 1
        return Ok(String(str_builder.to_string()))
      }
      '\n' => {
        self.pos.next_line()
        str_builder.write_char('\n')
      }
      '\\' => {
        guard self.input_iter.next() is Some(esc) else {
          return Err("Unterminated string literal")
        }
        self.pos.col += 1
        match esc {
          'n' => str_builder.write_char('\n')
          't' => str_builder.write_char('\t')
          'r' => str_builder.write_char('\r')
          'b' => str_builder.write_char('\b')
          'f' => str_builder.write_char('\f')
          '"' => str_builder.write_char('"')
          '\\' => str_builder.write_char('\\')
          'u' =>
            match self.read_codepoint(4) {
              Ok(c) => str_builder.write_char(c)
              Err(e) => return Err(e)
            }
          _ => return Err("Invalid escape sequence in string literal")
        }
      }
      _ => str_builder.write_char(c)
    }
  }
  Err("Unterminated string literal")
}

///|
fn Lexer::read_comment(self : Lexer) -> Unit {
  for ;; {
    match self.input_iter.next() {
      Some(c) if c != '\n' => continue
      _ => {
        self.pos.next_line()
        break
      }
    }
  }
}

///|
fn Lexer::tokenize(self : Lexer) -> Iter[Result[Token, ParseError]] {
  Iter::new(() => {
    for ;; {
      guard self.input_iter.next() is Some(c) else { break None }
      if c == '\n' {
        self.pos.next_line()
        continue
      }
      self.pos.col += 1
      let res = match c {
        ';' => {
          self.read_comment()
          continue
        }
        '#' => self.read_hash()
        '(' => Ok(OpenParen)
        ')' => Ok(CloseParen)
        '"' => self.read_string()
        _ if c.is_whitespace() => continue
        _ if c.is_ascii_digit() || c == '-' || c == '+' => {
          self.input_iter.revert(c)
          self.pos.col -= 1
          self.read_number()
        }
        _ => {
          self.input_iter.revert(c)
          self.pos.col -= 1
          Ok(Symbol(Symbol::new(self.read_indent())))
        }
      }
      match res {
        Ok(token) => break Some(Ok(token))
        Err(e) =>
          break Some(
            Err(
              ParseError(
                "\{e} at line \{self.pos.line}, column \{self.pos.col}",
              ),
            ),
          )
      }
    }
  })
}

///|
fn parse_aux(
  input_iter : RevertableIter[Result[Token, ParseError]],
) -> Sexp raise ParseError {
  fn next() raise ParseError {
    match input_iter.next() {
      Some(Ok(token)) => token
      Some(Err(e)) => raise e
      None => raise ParseError("Unexpected end of input")
    }
  }

  match next() {
    Bool(b) => Bool(b)
    Char(c) => Char(c)
    Int(i) => Int(i)
    Double(d) => Double(d)
    Symbol(s) => Symbol(s)
    String(s) => String(s)
    BlockCommentBegin => {
      parse_aux(input_iter) |> ignore
      parse_aux(input_iter)
    }
    OpenParen => {
      let elements = []
      for ;; {
        if input_iter.peek() is Some(Ok(CloseParen)) {
          input_iter.next() |> ignore
          break List(elements)
        }
        elements.push(parse_aux(input_iter))
      }
    }
    CloseParen => raise ParseError("Unexpected ')'")
  }
}

///|
/// Parses a single S-expression from the input string view.
///
/// # Errors
///
/// Returns `ParseError` if the input parses to more than one S-expression or if the syntax is invalid.
pub fn parse(input : StringView) -> Sexp raise ParseError {
  let lexer = Lexer::new(input)
  let input_iter = RevertableIter::new(lexer.tokenize())
  parse_aux(input_iter)
}

///|
/// Parses multiple S-expressions from the input string view.
///
/// Returns an array containing all parsed S-expressions.
pub fn parse_many(input : StringView) -> Array[Sexp] raise ParseError {
  let lexer = Lexer::new(input)
  let input_iter = RevertableIter::new(lexer.tokenize())
  let sexps = []
  for ;; {
    if input_iter.is_empty() {
      break sexps
    }
    sexps.push(parse_aux(input_iter))
  }
}

///|
pub impl Show for Sexp with output(self, logger) {
  match self {
    Symbol(s) => s.output(logger)
    String(s) => logger.write_string(s.escape())
    List(xs) => {
      logger.write_char('(')
      for i = 0; i < xs.length(); i = i + 1 {
        if i > 0 {
          logger.write_char(' ')
        }
        xs[i].output(logger)
      }
      logger.write_char(')')
    }
    Int(i) => logger.write_string(i.to_string())
    Double(d) => logger.write_string(d.to_string())
    Bool(b) => logger.write_string(if b { "#t" } else { "#f" })
    Char(c) =>
      // Scheme-like character representation
      logger..write_string("#\\").write_char(c)
  }
}

///|
/// Adds a key segment to the path, typically used when navigating a Map-like structure represented as an association list.
pub fn SexpPath::add_key(self : SexpPath, key : Symbol) -> SexpPath {
  Key(self, key)
}

///|
/// Adds an index segment to the path, used when navigating a list.
pub fn SexpPath::add_index(self : SexpPath, index : Int) -> SexpPath {
  Index(self, index)
}

///|
/// Adds a string key segment to the path by converting the string to a Symbol.
pub fn SexpPath::add_string_key(self : SexpPath, key : String) -> SexpPath {
  self.add_key(Symbol::new(key))
}

///|
pub impl Show for SexpPath with output(self, logger) {
  match self {
    Root => ()
    Key(Root, key) => key.output(logger)
    Index(Root, index) =>
      logger
      ..write_string("[")
      ..write_string(index.to_string())
      .write_string("]")
    Key(parent, key) =>
      logger..write_object(parent)..write_string(".").write_object(key)
    Index(parent, index) =>
      logger
      ..write_object(parent)
      ..write_string("[")
      ..write_string(index.to_string())
      .write_string("]")
  }
}

///|
/// Represents an error that occurred when converting an S-expression to a specific type.
/// Contains a message and the path to the element where the error occurred.
pub(all) suberror SexpError {
  SexpError(String, SexpPath)
}

///|
pub impl Show for SexpError with output(self, logger) {
  let SexpError(msg, path) = self
  logger
  ..write_string("SexpError at ")
  ..write_object(path)
  ..write_string(": ")
  .write_string(msg)
}

///|
/// Converts a value to an S-expression.
pub fn[T : ToSexp] to_sexp(value : T) -> Sexp {
  value.to_sexp()
}

///|
pub fn[T : FromSexp] from_sexp(sexp : Sexp) -> T raise SexpError {
  T::from_sexp(sexp, Root)
}