// Token types used by the lexer

///|
priv enum Token {
  Text(String) // Plain text
  Raw(String) // Content inside a raw/endraw block
  VarStart(Bool) // Start of a variable tag: {{ or {{- (with strip_left)
  VarEnd(Bool) // End of a variable tag: }} or -}}
  BlockStart(Bool) // Start of a control block: {% or {%- (with strip_left)
  BlockEnd(Bool) // End of a control block: %} or -%}
  Identifier(String) // Keywords or variable names
  StringLiteral(String)
  Literal(String) // Numeric, boolean, or null literal
  Operator(String) // Operators: ==, +, -, etc.
  Delimiter(Char) // Symbols: (, ), :, ., ,
  EOF // End of input
}

///|
priv struct TokenStream {
  tokens : Array[Token]
  spans : Array[SourceSpan]
}

///|
priv struct NamedBlockTag {
  next_index : Int
  strip_left : Bool
  strip_right : Bool
}

// Equality comparison for tokens

// Convert a token to its string representation (for debugging)

///|
//fn token_to_string(tok : Token) -> String {
//  match tok {
//    Text(s) => "Text(" + s + ")"
//    VarStart(strip) => "VarStart(" + strip.to_string() + ")"
//    VarEnd(strip) => "VarEnd(" + strip.to_string() + ")"
//    BlockStart(strip) => "BlockStart(" + strip.to_string() + ")"
//    BlockEnd(strip) => "BlockEnd(" + strip.to_string() + ")"
//    CommentStart => "CommentStart"
//    CommentEnd => "CommentEnd"
//    Identifier(s) => "Identifier(" + s + ")"
//    Literal(s) => "Literal(" + s + ")"
//    Operator(s) => "Operator(" + s + ")"          // ← 加上
//    Delimiter(c) => "Delimiter(" + c.to_string() + ")"  // ← 加上
//    EOF => "EOF"
//  }
//}

// Main lexer function: converts source string into a list of tokens

///|
fn tokenize(source : String) -> TokenStream raise JinjaError {
  let tokens : Ref[Array[Token]] = { val: [] }
  let starts : Ref[Array[Int]] = { val: [] }
  let ends : Ref[Array[Int]] = { val: [] }
  let chars = source.to_array()
  let i : Ref[Int] = { val: 0 }
  let len = chars.length()
  if len == 0 {
    return {
      tokens: [EOF],
      spans: [
        { start: 0, end: 0, line: 1, column: 1, end_line: 1, end_column: 1 },
      ],
    }
  }
  while i.val < len {
    let curr = chars[i.val]
    //println("tokenize: index=\{i.val}, char='\{curr}'")

    // === Handle {{ (expression start) ===
    if i.val + 1 < len && curr == '{' && chars[i.val + 1] == '{' {
      let strip_right = i.val + 2 < len && chars[i.val + 2] == '-'
      push_token(
        tokens,
        starts,
        ends,
        VarStart(strip_right),
        i.val,
        i.val + (if strip_right { 3 } else { 2 }),
      )
      //println("Detected VarStart (strip=\{strip_right}) at index \{i.val}")
      i.val += if strip_right { 3 } else { 2 }
      parse_expr_content(chars, i, tokens, starts, ends)
      continue
    }

    // === Handle {% (block start) ===
    if i.val + 1 < len && curr == '{' && chars[i.val + 1] == '%' {
      match match_named_block_tag(chars, i.val, "raw") {
        Some(opening) =>
          match find_named_block_tag(chars, opening.next_index, "endraw") {
            Some((content_end, closing)) => {
              let raw_chars : Array[Char] = []
              for index in opening.next_index.. tokens.val[last] = Text(trim_ws_end(text))
                  _ => ()
                }
              }
              push_token(
                tokens,
                starts,
                ends,
                Raw(raw_text),
                i.val,
                closing.next_index,
              )
              i.val = closing.next_index
              if closing.strip_right {
                while i.val < len && is_tag_ws(chars[i.val]) {
                  i.val += 1
                }
              }
              continue
            }
            None =>
              raise LexerError(
                lexer_message(chars, i.val, "Unterminated raw block"),
              )
          }
        None => ()
      }
      let strip_right = i.val + 2 < len && chars[i.val + 2] == '-'
      push_token(
        tokens,
        starts,
        ends,
        BlockStart(strip_right),
        i.val,
        i.val + (if strip_right { 3 } else { 2 }),
      )
      //println("Detected BlockStart (strip=\{strip_right}) at index \{i.val}")
      i.val += if strip_right { 3 } else { 2 }
      parse_block_content(chars, i, tokens, starts, ends)
      continue
    }

    // === Handle {# (comment start) ===
    if i.val + 1 < len && curr == '{' && chars[i.val + 1] == '#' {
      //println("Detected CommentStart at index \{i.val}")
      let strip_left = i.val + 2 < len && chars[i.val + 2] == '-'
      if strip_left && !tokens.val.is_empty() {
        let last = tokens.val.length() - 1
        match tokens.val[last] {
          Text(text) => tokens.val[last] = Text(trim_ws_end(text))
          _ => ()
        }
      }
      i.val += if strip_left { 3 } else { 2 }
      let strip_right = skip_comment_block(chars, i)
      if strip_right {
        while i.val < len && is_tag_ws(chars[i.val]) {
          i.val += 1
        }
      }
      continue
    }

    // === Fallback: Text block ===
    let start = i.val
    while i.val < len {
      let c = chars[i.val]
      if c == '{' && i.val + 1 < len {
        let peek = chars[i.val + 1]
        if peek == '{' || peek == '%' || peek == '#' {
          break
        }
      }
      i.val += 1
    }
    if start < i.val {
      let text_chars : Array[Char] = []
      for k in start.. Unit {
  tokens.val.push(token)
  starts.val.push(start)
  ends.val.push(end)
}

///|
fn build_source_spans(
  chars : Array[Char],
  starts : Array[Int],
  ends : Array[Int],
) -> Array[SourceSpan] {
  let byte_offsets : Array[Int] = [0]
  let lines : Array[Int] = [1]
  let columns : Array[Int] = [1]
  for char in chars {
    byte_offsets.push(byte_offsets.last().unwrap_or(0) + utf8_char_size(char))
    if char == '\n' {
      lines.push(lines.last().unwrap_or(1) + 1)
      columns.push(1)
    } else {
      lines.push(lines.last().unwrap_or(1))
      columns.push(columns.last().unwrap_or(1) + 1)
    }
  }
  let spans : Array[SourceSpan] = []
  for index in 0.. Int {
  let codepoint = char.to_int()
  if codepoint <= 0x7f {
    1
  } else if codepoint <= 0x7ff {
    2
  } else if codepoint <= 0xffff {
    3
  } else {
    4
  }
}

///|
fn is_tag_ws(char : Char) -> Bool {
  char == ' ' || char == '\t' || char == '\n' || char == '\r'
}

///|
/// Returns the first character after a simple `{% name %}` tag.
fn match_named_block_tag(
  chars : Array[Char],
  start : Int,
  name : String,
) -> NamedBlockTag? {
  if start + 1 >= chars.length() ||
    chars[start] != '{' ||
    chars[start + 1] != '%' {
    return None
  }
  let mut index = start + 2
  let strip_left = index < chars.length() && chars[index] == '-'
  if strip_left {
    index += 1
  }
  while index < chars.length() && is_tag_ws(chars[index]) {
    index += 1
  }
  let name_chars = name.to_array()
  for char in name_chars {
    if index >= chars.length() || chars[index] != char {
      return None
    }
    index += 1
  }
  while index < chars.length() && is_tag_ws(chars[index]) {
    index += 1
  }
  let strip_right = index < chars.length() && chars[index] == '-'
  if strip_right {
    index += 1
  }
  if index + 1 < chars.length() &&
    chars[index] == '%' &&
    chars[index + 1] == '}' {
    Some({ next_index: index + 2, strip_left, strip_right })
  } else {
    None
  }
}

///|
fn find_named_block_tag(
  chars : Array[Char],
  start : Int,
  name : String,
) -> (Int, NamedBlockTag)? {
  let mut index = start
  while index + 1 < chars.length() {
    if chars[index] == '{' && chars[index + 1] == '%' {
      match match_named_block_tag(chars, index, name) {
        Some(tag) => return Some((index, tag))
        None => ()
      }
    }
    index += 1
  }
  None
}

// 通用的 block / expression 内容解析函数

///|
fn parse_expr_content(
  chars : Array[Char],
  i : Ref[Int],
  tokens : Ref[Array[Token]],
  starts : Ref[Array[Int]],
  ends : Ref[Array[Int]],
) -> Unit raise JinjaError {
  parse_tag_content(chars, i, tokens, starts, ends, "}}")
}

///|
fn parse_block_content(
  chars : Array[Char],
  i : Ref[Int],
  tokens : Ref[Array[Token]],
  starts : Ref[Array[Int]],
  ends : Ref[Array[Int]],
) -> Unit raise JinjaError {
  parse_tag_content(chars, i, tokens, starts, ends, "%}")
}

// 跳过注释块 {# ... #}

///|
fn skip_comment_block(
  chars : Array[Char],
  i : Ref[Int],
) -> Bool raise JinjaError {
  while i.val + 1 < chars.length() {
    if chars[i.val] == '#' && chars[i.val + 1] == '}' {
      let strip_right = i.val > 0 && chars[i.val - 1] == '-'
      i.val += 2
      return strip_right
    }
    i.val += 1
  }
  raise LexerError(lexer_message(chars, i.val, "Unterminated comment block"))
}

// 通用 tag 内内容解析函数（支持 expression 和 block）

///|
fn parse_tag_content(
  chars : Array[Char],
  i : Ref[Int],
  tokens : Ref[Array[Token]],
  starts : Ref[Array[Int]],
  ends : Ref[Array[Int]],
  end_marker : String,
) -> Unit raise JinjaError {
  let len = chars.length()
  //println("parse_tag_content start at index \{i.val}, char = \{chars[i.val]}")
  while i.val < len {
    // 跳过空白字符
    while i.val < len &&
          (chars[i.val] == ' ' || chars[i.val] == '\n' || chars[i.val] == '\t') {
      i.val += 1
    }
    if i.val >= len {
      break
    }

    // ==== 新增：优先匹配 "-%}" / "-}}" （当前位置是 '-'）====
    if i.val + 2 < len &&
      chars[i.val] == '-' &&
      chars[i.val + 1].to_int() == end_marker[0].to_int() &&
      chars[i.val + 2].to_int() == end_marker[1].to_int() {
      // 这是 strip-left 的结束
      let token_start = i.val
      push_token(
        tokens,
        starts,
        ends,
        if end_marker == "}}" {
          VarEnd(true)
        } else {
          BlockEnd(true)
        },
        token_start,
        token_start + 3,
      )
      i.val += 3 // 消费 "-%}" 或 "-}}"
      return // 结束当前 tag
    }

    // ==== 原有：匹配 "%}" / "}}" （当前位置是 end_marker[0]）====
    if i.val + 1 < len &&
      chars[i.val].to_int() == end_marker[0].to_int() &&
      chars[i.val + 1].to_int() == end_marker[1].to_int() {
      // 是否有 strip-left（前一位是 '-'）
      let strip_left = i.val > 0 && chars[i.val - 1] == '-'
      if strip_left {
        push_token(
          tokens,
          starts,
          ends,
          if end_marker == "}}" {
            VarEnd(true)
          } else {
            BlockEnd(true)
          },
          i.val,
          i.val + 2,
        )
        i.val += 2
      } else {
        push_token(
          tokens,
          starts,
          ends,
          if end_marker == "}}" {
            VarEnd(false)
          } else {
            BlockEnd(false)
          },
          i.val,
          i.val + 2,
        )
        i.val += 2 // 普通 "%}" / "}}"
      }
      return
    }

    //  正常匹配 token 分支
    let c = chars[i.val]
    match c {
      // 标识符
      'a'..='z' | 'A'..='Z' | '_' => {
        let token_start = i.val
        let (ident, next_i) = parse_identifier(chars, i.val)
        //println("Parsed Identifier: \{ident}")
        if ident == "and" || ident == "or" || ident == "not" {
          push_token(tokens, starts, ends, Operator(ident), token_start, next_i)
        } else if ident == "true" || ident == "false" || ident == "null" {
          push_token(tokens, starts, ends, Literal(ident), token_start, next_i)
        } else {
          push_token(
            tokens,
            starts,
            ends,
            Identifier(ident),
            token_start,
            next_i,
          )
        }
        i.val = next_i
      }

      // 字面量（字符串或数字）
      '0'..='9' | '"' | '\'' => {
        let token_start = i.val
        let (lit, next_i, is_string) = parse_literal(chars, i.val)
        //println("Parsed Literal: \{lit}")
        push_token(
          tokens,
          starts,
          ends,
          if is_string {
            StringLiteral(lit)
          } else {
            Literal(lit)
          },
          token_start,
          next_i,
        )
        i.val = next_i
      }

      // 操作符
      '=' | '!' | '<' | '>' | '+' | '-' | '*' | '/' | '%' | '|' | '~' => {
        let token_start = i.val
        let (op, next_i) = parse_operator(chars, i.val)
        //println("Parsed Operator: \{op}")
        push_token(tokens, starts, ends, Operator(op), token_start, next_i)
        i.val = next_i
      }

      // 符号
      '(' | ')' | '[' | ']' | '{' | '}' | ':' | '.' | ',' => {
        //println("Parsed Delimiter: \{c}")
        push_token(tokens, starts, ends, Delimiter(c), i.val, i.val + 1)
        i.val += 1
      }

      // 其他非法字符
      _ =>
        //println("Unexpected character: \{c}")
        raise LexerError(
          lexer_message(chars, i.val, "Unexpected character in tag"),
        )
    }
    if i.val < len {
      //println("No end marker at index \{i.val}, char = \{chars[i.val]}")
    }
  }
  raise LexerError(lexer_message(chars, i.val, "Unterminated tag content"))
}

///|
fn lexer_message(chars : Array[Char], index : Int, message : String) -> String {
  let mut line = 1
  let mut column = 1
  let stop = if index < chars.length() { index } else { chars.length() }
  for offset in 0.. (String, Int) raise JinjaError {
  let mut j = i
  let len = chars.length()
  if j >= len {
    raise LexerError(
      lexer_message(
        chars, i, "Unexpected end of input while parsing identifier",
      ),
    )
  }
  let start = i
  let s = []
  while j < len &&
        (
          ('a' <= chars[j] && chars[j] <= 'z') ||
          ('A' <= chars[j] && chars[j] <= 'Z') ||
          ('0' <= chars[j] && chars[j] <= '9') ||
          chars[j] == '_'
        ) {
    j += 1
  }
  for k in start.. (String, Int, Bool) raise JinjaError {
  let len = chars.length()
  let mut j = i
  let s : Array[Char] = []
  if j >= len {
    raise LexerError(
      lexer_message(chars, i, "Unexpected end of input while parsing literal"),
    )
  }

  // 字符串字面量
  if chars[j] == '"' || chars[j] == '\'' {
    let quote = chars[j]
    j += 1
    while j < len {
      if chars[j] == '\\' && j + 1 < len {
        let escaped = match chars[j + 1] {
          'n' => '\n'
          'r' => '\r'
          't' => '\t'
          '\\' => '\\'
          '"' => '"'
          '\'' => '\''
          other => other
        }
        s.push(escaped)
        j += 2
      } else if chars[j] == quote {
        return (String::from_array(s), j + 1, true)
      } else {
        s.push(chars[j])
        j += 1
      }
    }
    raise LexerError(lexer_message(chars, j, "Unterminated string literal"))
  }

  while j < len && '0' <= chars[j] && chars[j] <= '9' {
    s.push(chars[j])
    j += 1
  }
  if j + 1 < len &&
    chars[j] == '.' &&
    '0' <= chars[j + 1] &&
    chars[j + 1] <= '9' {
    s.push('.')
    j += 1
    while j < len && '0' <= chars[j] && chars[j] <= '9' {
      s.push(chars[j])
      j += 1
    }
  }
  return (String::from_array(s), j, false)
}

///|
fn parse_operator(
  chars : Array[Char],
  i : Int,
) -> (String, Int) raise JinjaError {
  let len = chars.length()
  if i >= len {
    raise LexerError(
      lexer_message(chars, i, "Unexpected end of input while parsing operator"),
    )
  }

  // 两字符操作符
  if i + 1 < len {
    let two = String::from_array([chars[i], chars[i + 1]])
    if ["==", "!=", ">=", "<=", "//", "**"].contains(two) {
      return (two, i + 2)
    }
  }

  // 单字符操作符
  return (chars[i].to_string(), i + 1)
}