// ============================================================
// MoonbitJinja — Parser
// ============================================================

///|
priv struct VarPath {
  parts : Array[String]
}

///|
priv struct Call {
  name : String
  args : Array[Expr]
  kwargs : Map[String, Expr]
}

///|
priv struct MacroParam {
  name : String
  default : Expr?
}

// ==================== Operators ====================

///|
priv enum BinOp {
  Add
  Sub
  Mul
  Div
  FloorDiv
  Mod
  Pow
  Concat
  Eq
  Ne
  Lt
  Le
  Gt
  Ge
  And
  Or
  In
  NotIn
} derive(Eq)

///|
fn op_to_binop(op : String) -> BinOp? {
  match op {
    "+" => Some(BinOp::Add)
    "-" => Some(BinOp::Sub)
    "*" => Some(BinOp::Mul)
    "/" => Some(BinOp::Div)
    "//" => Some(BinOp::FloorDiv)
    "%" => Some(BinOp::Mod)
    "**" => Some(BinOp::Pow)
    "~" => Some(BinOp::Concat)
    "==" => Some(BinOp::Eq)
    "!=" => Some(BinOp::Ne)
    "<" => Some(BinOp::Lt)
    "<=" => Some(BinOp::Le)
    ">" => Some(BinOp::Gt)
    ">=" => Some(BinOp::Ge)
    "and" => Some(BinOp::And)
    "or" => Some(BinOp::Or)
    "in" => Some(BinOp::In)
    "not in" => Some(BinOp::NotIn)
    _ => None
  }
}

///|
fn precedence(op : BinOp) -> Int {
  match op {
    BinOp::Pow => 80
    BinOp::Mul | BinOp::Div | BinOp::FloorDiv | BinOp::Mod => 70
    BinOp::Add | BinOp::Sub | BinOp::Concat => 60
    BinOp::Lt | BinOp::Le | BinOp::Gt | BinOp::Ge | BinOp::In | BinOp::NotIn =>
      50
    BinOp::Eq | BinOp::Ne => 40
    BinOp::And => 30
    BinOp::Or => 20
  }
}

///|
priv enum UnOp {
  Not
  Neg
  Pos
}

// ==================== AST ====================

///|
priv enum Expr {
  TextNode(String, Bool, Bool)
  RawText(String)
  Var(VarPath)
  Literal(Value)
  ListLiteral(Array[Expr])
  MapLiteral(Array[(String, Expr)])
  Unary(UnOp, Expr)
  Binary(Expr, BinOp, Expr)
  Conditional(Expr, Expr, Expr?)
  Index(Expr, Expr)
  TestCall(Expr, String, Bool, Array[Expr], Map[String, Expr])
  FunctionCall(Call)
  FilterChain(Expr, Array[Call])
  IfBlock(Expr, Array[Expr], Array[Expr])
  ForBlock(String, Expr, Array[Expr], Array[Expr])
  IncludeNode(String, Bool)
  BlockNode(String, Array[Expr])
  SetStmt(String, Expr)
  WithBlock(Map[String, Expr], Array[Expr])
  MacroDef(String, Array[MacroParam], Array[Expr])
  CallBlock(Call, Array[Expr])
  ImportNode(String, String)
  FromImportNode(String, Array[String])
  ExtendsNode(String)
  Break
  Continue
}

// 顶层模板（用于继承支持）

///|
priv struct Template {
  parent : String?
  prefix : Array[Expr]
  body : Array[Expr]
}

///|
fn is_block_start(t : Token) -> Bool {
  match t {
    BlockStart(_) => true
    _ => false
  }
}

///|
fn is_block_end(t : Token) -> Bool {
  match t {
    BlockEnd(_) => true
    _ => false
  }
}

///|
fn is_var_end(t : Token) -> Bool {
  match t {
    VarEnd(_) => true
    _ => false
  }
}

///|
///调试用，
fn parse_fail(
  _i : Ref[Int],
  _tokens : Array[Token],
  _len : Int,
  msg : String,
) -> String raise JinjaError {
  //let from = if i.val >= 3 { i.val - 3 } else { 0 }
  //let to = if i.val + 3 < len { i.val + 3 } else { len - 1 }

  // 收集并拼成一行
  //let near : Array[String] = []
  //for k in from..=to {
  //  near.push(token_to_string(tokens[k]))
  //}
  ////println("PARSE ERROR at index=\{i.val}")
  ////println("NEAR TOKENS: [" + near.join(", ") + "]")
  raise ParseError(msg + " at token " + _i.val.to_string())
}

// ==================== Parsing Entry ====================

///|
fn parse(
  stream : TokenStream,
  max_depth? : Int = 256,
  enable_macros? : Bool = true,
  enable_multi_template? : Bool = true,
  enable_loop_controls? : Bool = true,
) -> Template raise JinjaError {
  let tokens = stream.tokens
  let i : Ref[Int] = { val: 0 }
  let len = tokens.length()
  try {
    validate_parse_depth(tokens, max_depth)
    let tpl = parse_template(tokens, i, len)
    validate_control_flow(tpl.body, 0)
    validate_unique_blocks(tpl.body, Map([]))
    validate_features(
      tpl, enable_macros, enable_multi_template, enable_loop_controls,
    )
    tpl
  } catch {
    ParseError(message) => {
      let span = stream.spans[if i.val < stream.spans.length() {
          i.val
        } else {
          stream.spans.length() - 1
        }]
      raise ParseError(
        message +
        " at " +
        span.line.to_string() +
        ":" +
        span.column.to_string() +
        " (bytes " +
        span.start.to_string() +
        ".." +
        span.end.to_string() +
        ")",
      )
    }
    error => raise error
  }
}

///|
fn validate_features(
  template : Template,
  enable_macros : Bool,
  enable_multi_template : Bool,
  enable_loop_controls : Bool,
) -> Unit raise JinjaError {
  if !enable_multi_template && template.parent is Some(_) {
    raise ParseError("Template inheritance is disabled")
  }
  validate_node_features(
    template.body,
    enable_macros,
    enable_multi_template,
    enable_loop_controls,
  )
}

///|
fn validate_node_features(
  nodes : Array[Expr],
  enable_macros : Bool,
  enable_multi_template : Bool,
  enable_loop_controls : Bool,
) -> Unit raise JinjaError {
  for node in nodes {
    match node {
      MacroDef(_, _, _) | CallBlock(_, _) if !enable_macros =>
        raise ParseError("Macros are disabled")
      IncludeNode(_, _) | ImportNode(_, _) | FromImportNode(_, _) if !enable_multi_template =>
        raise ParseError("Multi-template features are disabled")
      Break | Continue if !enable_loop_controls =>
        raise ParseError("Loop controls are disabled")
      IfBlock(_, then_body, else_body) => {
        validate_node_features(
          then_body, enable_macros, enable_multi_template, enable_loop_controls,
        )
        validate_node_features(
          else_body, enable_macros, enable_multi_template, enable_loop_controls,
        )
      }
      ForBlock(_, _, body, else_body) => {
        validate_node_features(
          body, enable_macros, enable_multi_template, enable_loop_controls,
        )
        validate_node_features(
          else_body, enable_macros, enable_multi_template, enable_loop_controls,
        )
      }
      BlockNode(_, body)
      | WithBlock(_, body)
      | MacroDef(_, _, body)
      | CallBlock(_, body) =>
        validate_node_features(
          body, enable_macros, enable_multi_template, enable_loop_controls,
        )
      _ => ()
    }
  }
}

///|
fn validate_parse_depth(
  tokens : Array[Token],
  max_depth : Int,
) -> Unit raise JinjaError {
  if max_depth <= 0 {
    raise ParseError("Parser nesting limit must be positive")
  }
  let mut delimiter_depth = 0
  let mut block_depth = 0
  let mut unary_depth = 0
  for index, token in tokens {
    match token {
      Delimiter('(') | Delimiter('[') | Delimiter('{') => {
        delimiter_depth += 1
        unary_depth = 0
      }
      Delimiter(')') | Delimiter(']') | Delimiter('}') => {
        delimiter_depth -= 1
        unary_depth = 0
      }
      Operator("not") | Operator("+") | Operator("-") => unary_depth += 1
      BlockStart(_) =>
        match peek(tokens, index + 1) {
          Identifier("if")
          | Identifier("for")
          | Identifier("with")
          | Identifier("block")
          | Identifier("macro")
          | Identifier("call") => block_depth += 1
          Identifier("endif")
          | Identifier("endfor")
          | Identifier("endwith")
          | Identifier("endblock")
          | Identifier("endmacro")
          | Identifier("endcall") => block_depth -= 1
          _ => ()
        }
      _ => unary_depth = 0
    }
    if delimiter_depth > max_depth ||
      block_depth > max_depth ||
      unary_depth > max_depth {
      raise ParseError("Template parser nesting limit exceeded")
    }
  }
}

///|
fn parse_template(
  tokens : Array[Token],
  i : Ref[Int],
  len : Int,
) -> Template raise JinjaError {
  let mut parent : String? = None
  let parsed = parse_expr_list(tokens, i, len)
  let prefix : Array[Expr] = []
  let body : Array[Expr] = []
  let mut saw_extends = false
  for node in parsed {
    match node {
      ExtendsNode(name) =>
        match parent {
          Some(_) => raise ParseError("A template can only extend one parent")
          None => {
            parent = Some(name)
            saw_extends = true
          }
        }
      _ => {
        if !saw_extends {
          prefix.push(node)
        }
        body.push(node)
      }
    }
  }
  if parent is None {
    prefix.clear()
  }
  // Template 是 struct；用记录字面量的“具名”写法，避免字段顺序陷阱
  let tpl : Template = { parent, prefix, body }
  return tpl
}

// 只返回 extends 文件名

///|
fn parse_extends_header(
  tokens : Array[Token],
  i : Ref[Int],
  _len : Int,
) -> String raise JinjaError {
  // 消费 BlockStart
  match tokens[i.val] {
    BlockStart(_) => i.val += 1
    _ => raise ParseError("Expected '{%' before extends")
  }

  // "extends"
  match tokens[i.val] {
    Identifier(id) => {
      if id != "extends" {
        ignore(parse_fail(i, tokens, _len, "Expected 'extends'"))
      }
      i.val += 1
    }
    _ => ignore(parse_fail(i, tokens, _len, "Expected 'extends'"))
  }

  // 字面量文件名
  let filename = match tokens[i.val] {
    StringLiteral(s) => {
      i.val += 1
      s
    }
    _ => raise ParseError("Expected file name after 'extends'")
  }

  // 结束 "%}"（strip/非 strip 都接受）
  match tokens[i.val] {
    BlockEnd(_) => i.val += 1
    _ => raise ParseError("Expected '%}' after extends")
  }
  filename
}

// ==================== Core Helpers ====================

///|
fn peek(tokens : Array[Token], i : Int) -> Token {
  if i < tokens.length() {
    tokens[i]
  } else {
    EOF
  }
}

///|
fn advance(i : Ref[Int]) -> Unit {
  i.val += 1
}

///|
fn is_delim(tok : Token, ch : Char) -> Bool {
  match tok {
    Delimiter(c) => c == ch
    _ => false
  }
}

///|
fn expect_delim(
  tokens : Array[Token],
  i : Ref[Int],
  ch : Char,
  what : String,
) -> Unit raise JinjaError {
  if i.val >= tokens.length() || !is_delim(tokens[i.val], ch) {
    raise ParseError(what)
  }
  i.val += 1
}

// ==================== Value Conversion ====================

///|
fn str_to_int(s : String) -> Int {
  let chars = s.to_array()
  let mut result = 0
  let mut sign = 1
  let mut start = 0
  if chars.length() > 0 && chars[0] == '-' {
    sign = -1
    start = 1
  }
  for i in start.. Value {
  if lit == "true" {
    return BoolValue(true)
  }
  if lit == "false" {
    return BoolValue(false)
  }
  if lit == "null" {
    return Null
  }
  let chars = lit.to_array()
  let mut all_digits = true
  let mut decimal_points = 0
  for c in chars {
    if c == '.' {
      decimal_points += 1
    } else if !('0' <= c && c <= '9') {
      all_digits = false
      break
    }
  }
  if all_digits && decimal_points == 0 {
    return IntValue(str_to_int(lit))
  }
  if all_digits && decimal_points == 1 {
    let parts = lit.split(".").to_array()
    if parts.length() == 2 {
      let whole = str_to_int(parts[0].to_owned()).to_double()
      let fraction_text = parts[1].to_owned()
      let mut divisor = 1.0
      for _ in fraction_text {
        divisor *= 10.0
      }
      return DoubleValue(
        whole + str_to_int(fraction_text).to_double() / divisor,
      )
    }
  }
  return StrValue(lit)
}

// ==================== Expression Parsers ====================

///|
fn parse_expr(
  tokens : Array[Token],
  i : Ref[Int],
  len : Int,
) -> Expr raise JinjaError {
  let value = parse_binary_expr(tokens, i, len, 1)
  match peek(tokens, i.val) {
    Identifier("if") => {
      i.val += 1
      let condition = parse_binary_expr(tokens, i, len, 1)
      let fallback = match peek(tokens, i.val) {
        Identifier("else") => {
          i.val += 1
          Some(parse_expr(tokens, i, len))
        }
        _ => None
      }
      Conditional(value, condition, fallback)
    }
    _ => value
  }
}

///|
fn parse_binary_expr(
  tokens : Array[Token],
  i : Ref[Int],
  len : Int,
  min_prec : Int,
) -> Expr raise JinjaError {
  let mut left = parse_unary_or_primary(tokens, i, len)
  while true {
    let tok = peek(tokens, i.val)
    match tok {
      Identifier("is") => {
        if 50 < min_prec {
          break
        }
        i.val += 1
        let negated = match peek(tokens, i.val) {
          Operator("not") => {
            i.val += 1
            true
          }
          _ => false
        }
        let name = match peek(tokens, i.val) {
          Identifier(name) => {
            i.val += 1
            name
          }
          _ => raise ParseError("Expected test name after 'is'")
        }
        let (args, kwargs) = if is_delim(peek(tokens, i.val), '(') {
          parse_call_args(tokens, i, len)
        } else {
          ([], Map([]))
        }
        left = TestCall(left, name, negated, args, kwargs)
      }
      Identifier("in") => {
        if 50 < min_prec {
          break
        }
        i.val += 1
        let right = parse_binary_expr(tokens, i, len, 51)
        left = Binary(left, BinOp::In, right)
      }
      Operator("not") =>
        match peek(tokens, i.val + 1) {
          Identifier("in") => {
            if 50 < min_prec {
              break
            }
            i.val += 2
            let right = parse_binary_expr(tokens, i, len, 51)
            left = Binary(left, BinOp::NotIn, right)
          }
          _ => break
        }
      Operator(op_str) => {
        let maybe = op_to_binop(op_str)
        match maybe {
          None => break
          Some(binop) => {
            let prec = precedence(binop)
            if prec < min_prec {
              break
            }
            advance(i)
            let right = parse_binary_expr(tokens, i, len, prec + 1)
            left = Expr::Binary(left, binop, right)
          }
        }
      }
      _ => break
    }
  }
  return left
}

///|
fn parse_unary_or_primary(
  tokens : Array[Token],
  i : Ref[Int],
  len : Int,
) -> Expr raise JinjaError {
  let base = match peek(tokens, i.val) {
    Operator("not") => {
      i.val += 1
      Expr::Unary(UnOp::Not, parse_unary_or_primary(tokens, i, len))
    }
    Operator("-") => {
      i.val += 1
      Expr::Unary(UnOp::Neg, parse_unary_or_primary(tokens, i, len))
    }
    Operator("+") => {
      i.val += 1
      Expr::Unary(UnOp::Pos, parse_unary_or_primary(tokens, i, len))
    }
    _ => parse_primary(tokens, i, len)
  }
  parse_postfix(tokens, i, len, base)
}

///|
fn parse_call_args(
  tokens : Array[Token],
  i : Ref[Int],
  len : Int,
) -> (Array[Expr], Map[String, Expr]) raise JinjaError {
  expect_delim(tokens, i, '(', "Expected '(' after filter name")
  let args : Array[Expr] = []
  let kwargs : Map[String, Expr] = Map([])
  let mut saw_keyword = false
  // 空实参 ()
  if is_delim(peek(tokens, i.val), ')') {
    i.val += 1
    return (args, kwargs)
  }
  while true {
    match (peek(tokens, i.val), peek(tokens, i.val + 1)) {
      (Identifier(name), Operator("=")) => {
        if kwargs.contains(name) {
          raise ParseError("Duplicate keyword argument: " + name)
        }
        i.val += 2
        kwargs[name] = parse_expr(tokens, i, len)
        saw_keyword = true
      }
      _ => {
        if saw_keyword {
          raise ParseError(
            "Positional arguments cannot follow keyword arguments",
          )
        }
        args.push(parse_expr(tokens, i, len))
      }
    }
    if is_delim(peek(tokens, i.val), ',') {
      i.val += 1
      if is_delim(peek(tokens, i.val), ')') {
        break
      }
      continue
    }
    break
  }
  expect_delim(tokens, i, ')', "Expected ')' to close argument list")
  (args, kwargs)
}

///|
fn parse_postfix(
  tokens : Array[Token],
  i : Ref[Int],
  len : Int,
  base0 : Expr,
) -> Expr raise JinjaError {
  let mut base = base0
  let filters : Array[Call] = []
  while i.val < len {
    match tokens[i.val] {
      Delimiter('[') => {
        i.val += 1
        let index = parse_expr(tokens, i, len)
        expect_delim(tokens, i, ']', "Expected ']' to close index")
        base = Expr::Index(base, index)
      }
      Operator(op) => {
        if op != "|" {
          break
        } // ← 只在分支体里判断
        i.val += 1 // 吃掉 '|'
        let fname = match tokens[i.val] {
          Identifier(s) => {
            i.val += 1
            s
          }
          _ => raise ParseError("Expected filter name after '|'")
        }
        let (args, kwargs) = if is_delim(tokens[i.val], '(') {
          parse_call_args(tokens, i, len)
        } else {
          ([], Map([]))
        }
        let call : Call = { name: fname, args, kwargs }
        filters.push(call)
      }
      _ => break
    }
  }
  if filters.length() > 0 {
    Expr::FilterChain(base, filters)
  } else {
    base
  }
}

///|
fn parse_primary(
  tokens : Array[Token],
  i : Ref[Int],
  len : Int,
) -> Expr raise JinjaError {
  let tok = peek(tokens, i.val)
  match tok {
    Text(s) => {
      let strip_left = if i.val > 0 {
        match tokens[i.val - 1] {
          VarEnd(true) | BlockEnd(true) => true // ← 左边看 End(true)
          _ => false
        }
      } else {
        false
      }
      let strip_right = if i.val + 1 < len {
        match tokens[i.val + 1] {
          VarStart(true) | BlockStart(true) => true // ← 右边看 Start(true)
          _ => false
        }
      } else {
        false
      }
      i.val += 1
      Expr::TextNode(s, strip_left, strip_right)
    }
    Raw(s) => {
      i.val += 1
      Expr::RawText(s)
    }
    Identifier(first) => {
      i.val += 1
      let parts : Array[String] = Array::new()
      parts.push(first)
      while i.val + 1 < len {
        if is_delim(tokens[i.val], '.') {
          match tokens[i.val + 1] {
            Identifier(seg) => {
              i.val += 2
              parts.push(seg)
              continue
            }
            _ => raise ParseError("Expected identifier after '.'")
          }
        }
        break
      }
      if is_delim(peek(tokens, i.val), '(') {
        let (args, kwargs) = parse_call_args(tokens, i, len)
        return Expr::FunctionCall({ name: parts.join("."), args, kwargs })
      }
      let a : VarPath = { parts, }
      Expr::Var(a)
    }
    Literal(raw) => {
      i.val += 1
      let v = to_value_from_token_lit(raw)
      Expr::Literal(v)
    }
    StringLiteral(value) => {
      i.val += 1
      Expr::Literal(StrValue(value))
    }
    Delimiter('[') => {
      i.val += 1
      let values : Array[Expr] = []
      while !is_delim(peek(tokens, i.val), ']') {
        values.push(parse_expr(tokens, i, len))
        if is_delim(peek(tokens, i.val), ',') {
          i.val += 1
          if is_delim(peek(tokens, i.val), ']') {
            break
          }
        } else {
          break
        }
      }
      expect_delim(tokens, i, ']', "Expected ']' to close list literal")
      Expr::ListLiteral(values)
    }
    Delimiter('{') => {
      i.val += 1
      let entries : Array[(String, Expr)] = []
      while !is_delim(peek(tokens, i.val), '}') {
        let key = match peek(tokens, i.val) {
          StringLiteral(key) | Identifier(key) => {
            i.val += 1
            key
          }
          _ => raise ParseError("Expected string or identifier map key")
        }
        expect_delim(tokens, i, ':', "Expected ':' after map key")
        entries.push((key, parse_expr(tokens, i, len)))
        if is_delim(peek(tokens, i.val), ',') {
          i.val += 1
          if is_delim(peek(tokens, i.val), '}') {
            break
          }
        } else {
          break
        }
      }
      expect_delim(tokens, i, '}', "Expected '}' to close map literal")
      Expr::MapLiteral(entries)
    }
    Delimiter('(') => {
      i.val += 1
      let e = parse_expr(tokens, i, len)
      expect_delim(tokens, i, ')', "Expected ')'")
      e
    }
    _ => raise ParseError("Unsupported token in primary")
  }
}

// ==================== Expression Lists ====================

///|
//fn debug_token_at(tokens : Array[Token], len : Int, idx : Int) -> String {
//  if idx < 0 || idx >= len {
//    ""
//  } else {
//    token_to_string(tokens[idx])
//  }
//}

///|
fn parse_expr_list(
  tokens : Array[Token],
  i : Ref[Int],
  len : Int,
) -> Array[Expr] raise JinjaError {
  let out : Array[Expr] = Array::new()
  while i.val < len {
    let cur = tokens[i.val]
    match cur {
      EOF => return out
      VarStart(_) => {
        i.val += 1
        let e = parse_expr(tokens, i, len)
        if i.val >= len || !is_var_end(tokens[i.val]) {
          raise ParseError("Expected '}}' to close variable tag")
        }
        i.val += 1
        out.push(e)
      }
      BlockStart(_) => {
        // lookahead：这些交给外层块解析器处理
        if i.val + 1 < len {
          match tokens[i.val + 1] {
            Identifier(id) =>
              if id == "endif" ||
                id == "endfor" ||
                id == "endwith" ||
                id == "endblock" ||
                id == "endmacro" ||
                id == "endcall" ||
                id == "else" ||
                id == "elif" {
                return out
              }
            _ => ()
          }
        }
        if i.val + 1 >= len {
          raise ParseError("Unexpected EOF inside block")
        }
        match tokens[i.val + 1] {
          Identifier(id) =>
            if id == "if" {
              let e = parse_if_block(tokens, i, len)
              out.push(e)
            } else if id == "for" {
              let e = parse_for_block(tokens, i, len)
              out.push(e)
            } else if id == "with" {
              let e = parse_with_block(tokens, i, len)
              out.push(e)
            } else if id == "include" {
              let e = parse_include(tokens, i, len)
              out.push(e)
            } else if id == "block" {
              let e = parse_block(tokens, i, len)
              out.push(e)
            } else if id == "set" {
              let e = parse_set_block(tokens, i, len)
              out.push(e)
            } else if id == "macro" {
              out.push(parse_macro_block(tokens, i, len))
            } else if id == "call" {
              out.push(parse_call_block(tokens, i, len))
            } else if id == "import" {
              out.push(parse_import(tokens, i, len))
            } else if id == "from" {
              out.push(parse_from_import(tokens, i, len))
            } else if id == "extends" {
              out.push(ExtendsNode(parse_extends_header(tokens, i, len)))
            } else if id == "break" {
              // 期望：BlockStart(_), Identifier("break"), BlockEnd(_)
              i.val += 1 // {%
              i.val += 1 // break
              if i.val >= len || !is_block_end(tokens[i.val]) {
                raise ParseError("Expected '%}' after break")
              }
              i.val += 1
              out.push(Expr::Break)
            } else if id == "continue" {
              i.val += 1 // {%
              i.val += 1 // continue
              if i.val >= len || !is_block_end(tokens[i.val]) {
                raise ParseError("Expected '%}' after continue")
              }
              i.val += 1
              out.push(Expr::Continue)
            } else {
              raise ParseError("Unknown block tag")
            }
          _ => raise ParseError("Expected block identifier after '{%'")
        }
      }
      _ => {
        let e = parse_primary(tokens, i, len)
        out.push(e)
      }
    }
  }
  out
}

// ==================== Block Parsers ====================

///|
fn parse_if_block(
  tokens : Array[Token],
  i : Ref[Int],
  len : Int,
) -> Expr raise JinjaError {
  // 进入 "{% if"
  match tokens[i.val] {
    BlockStart(_) => i.val += 1
    _ => ignore(parse_fail(i, tokens, len, "Expected '{%' before if"))
  }
  match tokens[i.val] {
    Identifier(id) => {
      if id != "if" {
        ignore(parse_fail(i, tokens, len, "Expected 'if'"))
      }
      i.val += 1
    }
    _ => ignore(parse_fail(i, tokens, len, "Expected 'if'"))
  }
  let cond = parse_expr(tokens, i, len)
  if i.val >= len || !is_block_end(tokens[i.val]) {
    ignore(parse_fail(i, tokens, len, "Expected '%}' after if condition"))
  }
  i.val += 1
  let then_body = parse_expr_list(tokens, i, len)
  let else_body = parse_if_remainder(tokens, i, len)

  // 结束：endif
  match tokens[i.val] {
    BlockStart(_) => i.val += 1
    _ => ignore(parse_fail(i, tokens, len, "Expected '{%' before endif"))
  }
  match tokens[i.val] {
    Identifier(id) => {
      if id != "endif" {
        ignore(parse_fail(i, tokens, len, "Expected 'endif'"))
      }
      i.val += 1
    }
    _ => ignore(parse_fail(i, tokens, len, "Expected 'endif'"))
  }
  if i.val >= len || !is_block_end(tokens[i.val]) {
    ignore(parse_fail(i, tokens, len, "Expected '%}' after endif"))
  }
  i.val += 1
  Expr::IfBlock(cond, then_body, else_body)
}

///|
fn parse_if_remainder(
  tokens : Array[Token],
  i : Ref[Int],
  len : Int,
) -> Array[Expr] raise JinjaError {
  if i.val + 1 >= len || !is_block_start(tokens[i.val]) {
    return []
  }
  match tokens[i.val + 1] {
    Identifier("else") => {
      i.val += 2
      if i.val >= len || !is_block_end(tokens[i.val]) {
        ignore(parse_fail(i, tokens, len, "Expected '%}' after else"))
      }
      i.val += 1
      parse_expr_list(tokens, i, len)
    }
    Identifier("elif") => {
      i.val += 2
      let cond = parse_expr(tokens, i, len)
      if i.val >= len || !is_block_end(tokens[i.val]) {
        ignore(parse_fail(i, tokens, len, "Expected '%}' after elif condition"))
      }
      i.val += 1
      let body = parse_expr_list(tokens, i, len)
      let remainder = parse_if_remainder(tokens, i, len)
      [Expr::IfBlock(cond, body, remainder)]
    }
    _ => []
  }
}

///|
fn parse_for_block(
  tokens : Array[Token],
  i : Ref[Int],
  len : Int,
) -> Expr raise JinjaError {
  match tokens[i.val] {
    BlockStart(_) => i.val += 1
    _ => ignore(parse_fail(i, tokens, len, "Expected '{%' before for"))
  }
  match tokens[i.val] {
    Identifier(id) => {
      if id != "for" {
        ignore(parse_fail(i, tokens, len, "Expected 'for'"))
      }
      i.val += 1
    }
    _ => ignore(parse_fail(i, tokens, len, "Expected 'for'"))
  }
  let loop_var = match tokens[i.val] {
    Identifier(n) => {
      i.val += 1
      n
    }
    _ => parse_fail(i, tokens, len, "Expected loop variable")
  }
  match tokens[i.val] {
    Identifier(id) => {
      if id != "in" {
        ignore(parse_fail(i, tokens, len, "Expected 'in' in for"))
      }
      i.val += 1
    }
    _ => ignore(parse_fail(i, tokens, len, "Expected 'in' in for"))
  }
  let iterable = parse_expr(tokens, i, len)
  if i.val >= len || !is_block_end(tokens[i.val]) {
    ignore(parse_fail(i, tokens, len, "Expected '%}' after for header"))
  }
  i.val += 1

  let body = parse_expr_list(tokens, i, len)
  let mut else_body : Array[Expr] = []
  if i.val + 1 < len && is_block_start(tokens[i.val]) {
    match tokens[i.val + 1] {
      Identifier("else") => {
        i.val += 2
        if i.val >= len || !is_block_end(tokens[i.val]) {
          ignore(parse_fail(i, tokens, len, "Expected '%}' after else"))
        }
        i.val += 1
        else_body = parse_expr_list(tokens, i, len)
      }
      _ => ()
    }
  }

  // "{% endfor %}"
  match tokens[i.val] {
    BlockStart(_) => i.val += 1
    _ => ignore(parse_fail(i, tokens, len, "Expected '{%' before endfor"))
  }
  match tokens[i.val] {
    Identifier(id) => {
      if id != "endfor" {
        ignore(parse_fail(i, tokens, len, "Expected 'endfor'"))
      }
      i.val += 1
    }
    _ => ignore(parse_fail(i, tokens, len, "Expected 'endfor'"))
  }
  if i.val >= len || !is_block_end(tokens[i.val]) {
    ignore(parse_fail(i, tokens, len, "Expected '%}' after endfor"))
  }
  i.val += 1
  Expr::ForBlock(loop_var, iterable, body, else_body)
}

///|
fn parse_include(
  tokens : Array[Token],
  i : Ref[Int],
  _len : Int,
) -> Expr raise JinjaError {
  match tokens[i.val] {
    BlockStart(_) => i.val += 1
    _ => raise ParseError("Expected '{%' before include")
  }
  match tokens[i.val] {
    Identifier(id) => {
      if id != "include" {
        raise ParseError("Expected 'include'")
      }
      i.val += 1
    }
    _ => raise ParseError("Expected 'include'")
  }
  let filename = match tokens[i.val] {
    StringLiteral(s) => {
      i.val += 1
      s
    }
    _ => raise ParseError("Expected filename in include")
  }
  let mut with_context = true
  match peek(tokens, i.val) {
    Identifier("without") => {
      i.val += 1
      match peek(tokens, i.val) {
        Identifier("context") => i.val += 1
        _ => raise ParseError("Expected 'context' after 'without'")
      }
      with_context = false
    }
    Identifier("with") => {
      i.val += 1
      match peek(tokens, i.val) {
        Identifier("context") => i.val += 1
        _ => raise ParseError("Expected 'context' after 'with'")
      }
    }
    _ => ()
  }
  match tokens[i.val] {
    BlockEnd(_) => i.val += 1
    _ => raise ParseError("Expected '%}' after include")
  }
  Expr::IncludeNode(filename, with_context)
}

///|
fn parse_block(
  tokens : Array[Token],
  i : Ref[Int],
  len : Int,
) -> Expr raise JinjaError {
  match tokens[i.val] {
    BlockStart(_) => i.val += 1
    _ => raise ParseError("Expected '{%' before block")
  }
  match tokens[i.val] {
    Identifier(id) => {
      if id != "block" {
        raise ParseError("Expected 'block'")
      }
      i.val += 1
    }
    _ => raise ParseError("Expected 'block'")
  }
  let name = match tokens[i.val] {
    Identifier(n) => {
      i.val += 1
      n
    }
    _ => raise ParseError("Expected block name")
  }
  if i.val >= len || !is_block_end(tokens[i.val]) {
    raise ParseError("Expected '%}' after block")
  }
  i.val += 1
  let body = parse_expr_list(tokens, i, len)
  match tokens[i.val] {
    BlockStart(_) => i.val += 1
    _ => raise ParseError("Expected '{%' before endblock")
  }
  match tokens[i.val] {
    Identifier(id) => {
      if id != "endblock" {
        raise ParseError("Expected 'endblock'")
      }
      i.val += 1
    }
    _ => raise ParseError("Expected 'endblock'")
  }
  if i.val >= len || !is_block_end(tokens[i.val]) {
    raise ParseError("Expected '%}' after endblock")
  }
  i.val += 1
  Expr::BlockNode(name, body)
}

///|
fn parse_set_block(
  tokens : Array[Token],
  i : Ref[Int],
  len : Int,
) -> Expr raise JinjaError {
  match tokens[i.val] {
    BlockStart(_) => i.val += 1
    _ => raise ParseError("Expected '{%' before set")
  }
  match tokens[i.val] {
    Identifier(id) => {
      if id != "set" {
        raise ParseError("Expected 'set'")
      }
      i.val += 1
    }
    _ => raise ParseError("Expected 'set'")
  }
  let name = match tokens[i.val] {
    Identifier(n) => {
      i.val += 1
      n
    }
    _ => raise ParseError("Expected var name")
  }
  match tokens[i.val] {
    Operator(op) => {
      if op != "=" {
        raise ParseError("Expected '=' after var name")
      }
      i.val += 1
    }
    _ => raise ParseError("Expected '=' after var name")
  }
  let value = parse_expr(tokens, i, len)
  if i.val >= len || !is_block_end(tokens[i.val]) {
    raise ParseError("Expected '%}' after set")
  }
  i.val += 1
  Expr::SetStmt(name, value)
}

///|
fn parse_with_block(
  tokens : Array[Token],
  i : Ref[Int],
  len : Int,
) -> Expr raise JinjaError {
  // "{% with"
  match tokens[i.val] {
    BlockStart(_) => i.val += 1
    _ => raise ParseError("Expected '{%' before with")
  }
  match tokens[i.val] {
    Identifier(id) => {
      if id != "with" {
        raise ParseError("Expected 'with'")
      }
      i.val += 1
    }
    _ => raise ParseError("Expected 'with'")
  }
  let assigns : Map[String, Expr] = Map([])
  while true {
    // name
    let name = match tokens[i.val] {
      Identifier(n) => {
        i.val += 1
        n
      }
      _ => raise ParseError("Expected var name in 'with'")
    }
    // "="
    match tokens[i.val] {
      Operator(op) => {
        if op != "=" {
          raise ParseError("Expected '=' after var name")
        }
        i.val += 1
      }
      _ => raise ParseError("Expected '=' after var name")
    }
    // value expr
    let value = parse_expr(tokens, i, len)
    assigns[name] = value

    // ',' 继续，或 '%}' 结束
    if i.val < len {
      match tokens[i.val] {
        Delimiter(',') => {
          i.val += 1
          continue
        }
        BlockEnd(_) => {
          i.val += 1
          break
        }
        _ => raise ParseError("Expected ',' or '%}' in with")
      }
    } else {
      raise ParseError("Unexpected EOF in with")
    }
  }
  let body = parse_expr_list(tokens, i, len)

  // "{% endwith %}"
  match tokens[i.val] {
    BlockStart(_) => i.val += 1
    _ => raise ParseError("Expected '{%' before endwith")
  }
  match tokens[i.val] {
    Identifier(id) => {
      if id != "endwith" {
        raise ParseError("Expected 'endwith'")
      }
      i.val += 1
    }
    _ => raise ParseError("Expected 'endwith'")
  }
  if i.val >= len || !is_block_end(tokens[i.val]) {
    raise ParseError("Expected '%}' after endwith")
  }
  i.val += 1
  Expr::WithBlock(assigns, body)
}

///|
fn expect_block_end(
  tokens : Array[Token],
  i : Ref[Int],
  message : String,
) -> Unit raise JinjaError {
  match peek(tokens, i.val) {
    BlockEnd(_) => i.val += 1
    _ => raise ParseError(message)
  }
}

///|
fn parse_end_tag(
  tokens : Array[Token],
  i : Ref[Int],
  name : String,
) -> Unit raise JinjaError {
  match peek(tokens, i.val) {
    BlockStart(_) => i.val += 1
    _ => raise ParseError("Expected '{%' before " + name)
  }
  match peek(tokens, i.val) {
    Identifier(actual) if actual == name => i.val += 1
    _ => raise ParseError("Expected '" + name + "'")
  }
  expect_block_end(tokens, i, "Expected '%}' after " + name)
}

///|
fn parse_macro_block(
  tokens : Array[Token],
  i : Ref[Int],
  len : Int,
) -> Expr raise JinjaError {
  i.val += 2 // BlockStart, macro
  let name = match peek(tokens, i.val) {
    Identifier(name) => {
      i.val += 1
      name
    }
    _ => raise ParseError("Expected macro name")
  }
  expect_delim(tokens, i, '(', "Expected '(' after macro name")
  let params : Array[MacroParam] = []
  let param_names : Map[String, Bool] = Map([])
  let mut saw_default = false
  if !is_delim(peek(tokens, i.val), ')') {
    while true {
      let param_name = match peek(tokens, i.val) {
        Identifier(name) => {
          i.val += 1
          name
        }
        _ => raise ParseError("Expected macro parameter")
      }
      if param_names.contains(param_name) {
        raise ParseError("Duplicate macro parameter: " + param_name)
      }
      param_names[param_name] = true
      let default = match peek(tokens, i.val) {
        Operator("=") => {
          i.val += 1
          saw_default = true
          Some(parse_expr(tokens, i, len))
        }
        _ => {
          if saw_default {
            raise ParseError(
              "Required macro parameters cannot follow default parameters",
            )
          }
          None
        }
      }
      params.push({ name: param_name, default })
      match peek(tokens, i.val) {
        Delimiter(',') => i.val += 1
        Delimiter(')') => break
        _ => raise ParseError("Expected ',' or ')' in macro parameters")
      }
    }
  }
  expect_delim(tokens, i, ')', "Expected ')' after macro parameters")
  expect_block_end(tokens, i, "Expected '%}' after macro declaration")
  let body = parse_expr_list(tokens, i, len)
  parse_end_tag(tokens, i, "endmacro")
  MacroDef(name, params, body)
}

///|
fn parse_call_block(
  tokens : Array[Token],
  i : Ref[Int],
  len : Int,
) -> Expr raise JinjaError {
  i.val += 2 // BlockStart, call
  let call = match parse_expr(tokens, i, len) {
    FunctionCall(call) => call
    _ => raise ParseError("call expects a macro invocation")
  }
  expect_block_end(tokens, i, "Expected '%}' after call")
  let body = parse_expr_list(tokens, i, len)
  parse_end_tag(tokens, i, "endcall")
  CallBlock(call, body)
}

///|
fn parse_import(
  tokens : Array[Token],
  i : Ref[Int],
  _len : Int,
) -> Expr raise JinjaError {
  i.val += 2 // BlockStart, import
  let filename = match peek(tokens, i.val) {
    StringLiteral(filename) => {
      i.val += 1
      filename
    }
    _ => raise ParseError("Expected template name after import")
  }
  match peek(tokens, i.val) {
    Identifier("as") => i.val += 1
    _ => raise ParseError("Expected 'as' in import")
  }
  let import_name = match peek(tokens, i.val) {
    Identifier(import_name) => {
      i.val += 1
      import_name
    }
    _ => raise ParseError("Expected namespace after import as")
  }
  expect_block_end(tokens, i, "Expected '%}' after import")
  ImportNode(filename, import_name)
}

///|
fn parse_from_import(
  tokens : Array[Token],
  i : Ref[Int],
  _len : Int,
) -> Expr raise JinjaError {
  i.val += 2 // BlockStart, from
  let filename = match peek(tokens, i.val) {
    StringLiteral(filename) => {
      i.val += 1
      filename
    }
    _ => raise ParseError("Expected template name after from")
  }
  match peek(tokens, i.val) {
    Identifier("import") => i.val += 1
    _ => raise ParseError("Expected 'import' after template name")
  }
  let names : Array[String] = []
  while true {
    match peek(tokens, i.val) {
      Identifier(name) => {
        names.push(name)
        i.val += 1
      }
      _ => raise ParseError("Expected macro name in from import")
    }
    match peek(tokens, i.val) {
      Delimiter(',') => i.val += 1
      BlockEnd(_) => break
      _ => raise ParseError("Expected ',' or '%}' in from import")
    }
  }
  expect_block_end(tokens, i, "Expected '%}' after from import")
  FromImportNode(filename, names)
}

///|
fn validate_control_flow(
  nodes : Array[Expr],
  loop_depth : Int,
) -> Unit raise JinjaError {
  for node in nodes {
    match node {
      Break | Continue if loop_depth == 0 =>
        raise ParseError("break and continue are only valid inside a for loop")
      IfBlock(_, then_body, else_body) => {
        validate_control_flow(then_body, loop_depth)
        validate_control_flow(else_body, loop_depth)
      }
      ForBlock(_, _, body, else_body) => {
        validate_control_flow(body, loop_depth + 1)
        validate_control_flow(else_body, loop_depth)
      }
      BlockNode(_, body) | WithBlock(_, body) =>
        validate_control_flow(body, loop_depth)
      MacroDef(_, _, body) | CallBlock(_, body) =>
        validate_control_flow(body, 0)
      ExtendsNode(_) =>
        raise ParseError("extends is only valid at template top level")
      _ => ()
    }
  }
}

///|
fn validate_unique_blocks(
  nodes : Array[Expr],
  names : Map[String, Bool],
) -> Unit raise JinjaError {
  for node in nodes {
    match node {
      BlockNode(name, body) => {
        if names.contains(name) {
          raise ParseError("Duplicate block: " + name)
        }
        names[name] = true
        validate_unique_blocks(body, names)
      }
      IfBlock(_, then_body, else_body) => {
        validate_unique_blocks(then_body, names)
        validate_unique_blocks(else_body, names)
      }
      ForBlock(_, _, body, else_body) => {
        validate_unique_blocks(body, names)
        validate_unique_blocks(else_body, names)
      }
      WithBlock(_, body) | MacroDef(_, _, body) | CallBlock(_, body) =>
        validate_unique_blocks(body, names)
      _ => ()
    }
  }
}