// Parser: tokens -> AST.
//
// Recursive descent. Supports `{% if %}`/`{% else %}`/`{% endif %}` and
// `{% for x in xs %}`/`{% endfor %}`. Other tags are parsed but deferred.

///|
priv struct P {
  tokens : Array[Token]
  mut i : Int
  mut parent : String
}

///|
fn P::peek(self : P) -> Token {
  if self.i < self.tokens.length() {
    self.tokens[self.i]
  } else {
    Text("")
  }
}

///|
fn P::advance(self : P) -> Unit {
  self.i = self.i + 1
}

///|
/// The leading keyword of a tag. `"if x > 1"` -> `"if"`.
fn tag_keyword(t : String) -> String {
  let chars = t.trim().to_array()
  let mut j = 0
  while j < chars.length() && chars[j] != ' ' {
    j = j + 1
  }
  t[0:j].to_owned()
}

///|
/// The text after the leading keyword. `"if x"` -> `"x"`.
fn tag_rest(t : String) -> String {
  let chars = t.trim().to_array()
  let n = chars.length()
  let mut j = 0
  while j < n && chars[j] != ' ' {
    j = j + 1
  }
  if j < n {
    t[j:n].trim().to_owned()
  } else {
    ""
  }
}

///|
/// Split a `for` header `"x in expr"` into `("x", "expr")`.
fn split_for_header(s : String) -> (String, String) {
  let chars = s.to_array()
  let n = chars.length()
  let mut j = 0
  while j + 3 < n {
    if chars[j] == ' ' &&
      chars[j + 1] == 'i' &&
      chars[j + 2] == 'n' &&
      chars[j + 3] == ' ' {
      return (s[0:j].trim().to_owned(), s[j + 4:n].trim().to_owned())
    }
    j = j + 1
  }
  (s.trim().to_owned(), "")
}

///|
/// Strip surrounding double quotes from a string (`"base"` -> `base`).
fn strip_quotes(s : String) -> String {
  let t = s.trim().to_owned()
  let chars = t.to_array()
  let n = chars.length()
  if n >= 2 && chars[0] == '"' && chars[n - 1] == '"' {
    t[1:n - 1].to_owned()
  } else {
    t
  }
}

///|
/// Parse tokens into AST nodes and the `extends` parent name ("" if none).
pub fn parse(tokens : Array[Token]) -> (Array[Node], String) {
  let p = P::{ tokens, i: 0, parent: "" }
  let nodes = p.parse_block([])
  (nodes, p.parent)
}

///|
/// Parse a block until a stop keyword (`endif`/`else`/`endfor`) is peeked, or EOF.
/// The stop tag itself is NOT consumed (the caller handles it).
fn P::parse_block(self : P, stop : Array[String]) -> Array[Node] {
  let nodes : Array[Node] = []
  while self.i < self.tokens.length() {
    match self.peek() {
      Text(s) => {
        nodes.push(Text(s))
        self.advance()
      }
      Variable(e) => {
        nodes.push(Output(parse_expr(e)))
        self.advance()
      }
      Tag(t) => {
        let kw = tag_keyword(t)
        if stop.contains(kw) {
          return nodes
        }
        self.advance()
        match kw {
          "if" => nodes.push(self.parse_if(t))
          "for" => nodes.push(self.parse_for(t))
          "block" => nodes.push(self.parse_block_tag(t))
          "extends" =>
            // parse_block already advanced past the tag
            self.parent = strip_quotes(tag_rest(t))
          "include" => nodes.push(Include(strip_quotes(tag_rest(t))))
          "set" => nodes.push(parse_set_tag(t))
          _ => () // unknown tag: ignore for now
        }
      }
    }
  }
  nodes
}

///|
fn P::parse_if(self : P, tag : String) -> Node {
  let cond = parse_expr(tag_rest(tag))
  let then_branch = self.parse_block(["elif", "else", "endif"])
  self.parse_if_tail(cond, then_branch)
}

///|
/// Parse the tail of an `if`: `elif` chains, `else`, or `endif`.
fn P::parse_if_tail(self : P, cond : Expr, then_branch : Array[Node]) -> Node {
  match self.peek() {
    Tag(t) => {
      let kw = tag_keyword(t)
      if kw == "elif" {
        self.advance()
        let elif_cond = parse_expr(tag_rest(t))
        let elif_then = self.parse_block(["elif", "else", "endif"])
        let nested = self.parse_if_tail(elif_cond, elif_then)
        If(cond, then_branch, [nested])
      } else if kw == "else" {
        self.advance()
        let eb = self.parse_block(["endif"])
        self.advance()
        If(cond, then_branch, eb)
      } else if kw == "endif" {
        self.advance()
        If(cond, then_branch, [])
      } else {
        If(cond, then_branch, [])
      }
    }
    _ => If(cond, then_branch, [])
  }
}

///|
fn P::parse_for(self : P, tag : String) -> Node {
  let header = split_for_header(tag_rest(tag))
  let iter = parse_expr(header.1)
  let body = self.parse_block(["else", "endfor"])
  let empty_body = match self.peek() {
    Tag(t) =>
      if tag_keyword(t) == "else" {
        self.advance()
        let nodes = self.parse_block(["endfor"])
        self.advance() // consume endfor
        nodes
      } else {
        self.advance() // consume endfor
        []
      }
    _ => []
  }
  For(header.0, iter, body, empty_body)
}

///|
fn P::parse_block_tag(self : P, tag : String) -> Node {
  let name = tag_rest(tag)
  let body = self.parse_block(["endblock"])
  self.advance() // consume endblock
  Block(name, body)
}

///|
/// Parse `{% set name = expr %}`.
fn parse_set_tag(tag : String) -> Node {
  let rest = tag_rest(tag)
  let chars = rest.to_array()
  let n = chars.length()
  let mut eq = -1
  let mut k = 0
  while k < n && eq < 0 {
    if chars[k] == '=' {
      eq = k
    }
    k = k + 1
  }
  if eq > 0 {
    let name = rest[0:eq].trim().to_owned()
    let expr_str = rest[eq + 1:n].trim().to_owned()
    Set(name, parse_expr(expr_str))
  } else {
    Text("") // malformed set
  }
}