///|
pub(all) suberror ParseError {
  UnexpectedEof
  UnexpectedChar(pos~ : Int, Char)
  ExpectedRParen(pos~ : Int)
} derive(Show)

///|
pub enum Expr {
  Leaf(String)
  Node(String, Array[Expr])
} derive(Show, Eq)

///|
pub fn expr_leaf(name : String) -> Expr {
  Expr::Leaf(name)
}

///|
pub fn expr_node(op : String, children : Array[Expr]) -> Expr {
  Expr::Node(op, children)
}

///|
pub fn Expr::to_sexpr(self : Expr) -> String {
  match self {
    Leaf(name) => name
    Node(op, children) =>
      if children.is_empty() {
        "(\{op})"
      } else {
        let rendered = children.map(child => child.to_sexpr())
        let joined = rendered.join(" ")
        "(\{op} \{joined})"
      }
  }
}

///|
priv struct Parser {
  s : String
  mut i : Int
}

///|
fn Parser::new(s : String) -> Parser {
  Parser::{ s, i: 0 }
}

///|
fn Parser::len(self : Parser) -> Int {
  self.s.length()
}

///|
fn Parser::peek(self : Parser) -> Char? {
  self.s.get_char(self.i)
}

///|
fn Parser::next(self : Parser) -> Char? {
  match self.s.get_char(self.i) {
    None => None
    Some(c) => {
      self.i = self.i + 1
      Some(c)
    }
  }
}

///|
fn Parser::skip_ws(self : Parser) -> Unit {
  loop () {
    _ =>
      match self.peek() {
        Some(c) if c == ' ' || c == '\n' || c == '\t' || c == '\r' => {
          self.i = self.i + 1
          continue ()
        }
        _ => break ()
      }
  }
}

///|
fn Parser::parse_atom(self : Parser) -> Expr raise ParseError {
  let start = self.i
  loop () {
    _ =>
      match self.peek() {
        Some(c) if c == '(' ||
          c == ')' ||
          c == ' ' ||
          c == '\n' ||
          c == '\t' ||
          c == '\r' => break ()
        Some(_) => {
          self.i = self.i + 1
          continue ()
        }
        None => break ()
      }
  }
  if self.i == start {
    raise ParseError::UnexpectedEof
  }
  let token_view = try! self.s[start:self.i]
  Expr::Leaf(token_view.to_string())
}

///|
fn Parser::parse_list(self : Parser) -> Expr raise ParseError {
  self.skip_ws()
  let head = self.parse_expr()
  let op = match head {
    Expr::Leaf(name) => name
    _ => raise ParseError::UnexpectedChar(pos=self.i, ')')
  }
  let children : Array[Expr] = Array::new()
  loop () {
    _ => {
      self.skip_ws()
      match self.peek() {
        Some(')') => {
          ignore(self.next())
          break ()
        }
        None => raise ParseError::ExpectedRParen(pos=self.i)
        _ => {
          children.push(self.parse_expr())
          continue ()
        }
      }
    }
  }
  Expr::Node(op, children)
}

///|
fn Parser::parse_expr(self : Parser) -> Expr raise ParseError {
  self.skip_ws()
  match self.next() {
    Some('(') => self.parse_list()
    Some(')') => raise ParseError::UnexpectedChar(pos=self.i - 1, ')')
    Some(_) => {
      self.i = self.i - 1
      self.parse_atom()
    }
    None => raise ParseError::UnexpectedEof
  }
}

///|
pub fn parse_sexpr(s : String) -> Expr raise ParseError {
  let parser = Parser::new(s)
  let expr = parser.parse_expr()
  parser.skip_ws()
  if parser.i != parser.len() {
    let extra = match parser.peek() {
      Some(c) => c
      None => ' '
    }
    raise ParseError::UnexpectedChar(pos=parser.i, extra)
  }
  expr
}

///|
test "parse sexpr and roundtrip" {
  let expr = parse_sexpr("(add x (mul y z))")
  inspect(expr.to_sexpr(), content="(add x (mul y z))")
  let atom = parse_sexpr("foo")
  inspect(atom.to_sexpr(), content="foo")
}