/// 公式解析失败(语法错误、不支持的引用形式、超出 Excel 公式限制)。
/// 与求值产生的错误值(`XlError`)是两条独立通道。
pub suberror ParseError {
  /// 携带人类可读的错误原因。
  ParseError(String)
}

/// Excel 公式长度上限(UTF-16 码元,与 Excel 公式栏一致)。超限返回 ParseError。
pub let max_formula_length : Int = 8192

/// Excel 公式嵌套上限(括号、一元运算符、函数调用均计入)。超限返回 ParseError。
pub let max_nesting_depth : Int = 64

struct Parser {
  tokens : Array[Token]
  mut pos : Int
  mut depth : Int
}

fn enter_nested(p : Parser) -> Unit raise ParseError {
  if p.depth >= max_nesting_depth {
    raise ParseError("formula nesting exceeds 64 levels")
  }
  p.depth += 1
}

fn peek(p : Parser) -> Token? {
  p.tokens.get(p.pos)
}

fn expect(p : Parser, t : Token, what : String) -> Unit raise ParseError {
  match peek(p) {
    Some(x) if x == t => p.pos += 1
    _ => raise ParseError("expected " + what)
  }
}

fn bin_op(s : String) -> BinOp {
  match s {
    "+" => Add
    "-" => Sub
    "*" => Mul
    "/" => Div
    "^" => Pow
    "&" => Concat
    "=" => Eq
    "<>" => Ne
    "<" => Lt
    "<=" => Le
    ">" => Gt
    ">=" => Ge
    _ => Add
  }
}

fn looks_like_ref(name : String) -> Bool {
  let chars : Array[Char] = Array::from_iter(name.iter())
  let n = chars.length()
  let mut i = 0
  if i < n && chars[i] == '$' {
    i += 1
  }
  let ls = i
  while i < n && @value.is_ascii_letter(chars[i]) {
    i += 1
  }
  if i == ls || i - ls > 3 {
    return false
  }
  if i < n && chars[i] == '$' {
    i += 1
  }
  let ds = i
  while i < n && @value.is_ascii_digit(chars[i]) {
    i += 1
  }
  i > ds && i == n
}

/// 区域端点:单元格、整列(列序号)或整行(行序号)。
/// 只在 `:` 组合时用于区分三种区域形态,不进入 AST。
enum RngEnd {
  RngRef(@value.CellAddr)
  RngCol(Int)
  RngRow(Int)
}

/// 定义名称字符集:`[A-Za-z_][A-Za-z0-9_]*`(Excel 名称规则;不含 `$`、`.`)。
fn is_name_token(s : String) -> Bool {
  @value.valid_name_token(s)
}

/// 工作表名归一化(ASCII 大写)并校验合法性;非法表名在解析期即拒绝。
fn sheet_token(name : String) -> String raise ParseError {
  let up = @value.ascii_upper(name)
  if !@value.valid_sheet_name(up) {
    raise ParseError("invalid sheet name: " + name)
  }
  up
}

/// 把整数 token 还原为行序号(1..1048576);非整数或越界返回 None。
fn row_index(d : Double) -> Int? {
  if !(d >= 1.0 && d <= @value.max_row.to_double()) {
    return None
  }
  let r = d.trunc().to_int()
  if r.to_double() != d {
    return None
  }
  Some(r)
}

/// 解析 `!` 右侧的受限主引用:`A1` / 列字母 `A` / 整数行号 `2`。
/// 列字母与行号只有在后面紧跟 `:` 时才合法(由调用方检查)。
fn parse_sheet_primary(p : Parser) -> Expr raise ParseError {
  let t = match peek(p) {
    Some(t) => t
    None => raise ParseError("unexpected end of formula")
  }
  p.pos += 1
  match t {
    Ident(name) =>
      if looks_like_ref(name) {
        match @value.parse_addr(name) {
          Some(a) => Ref(a)
          None => raise ParseError("invalid cell reference: " + name)
        }
      } else {
        match @value.parse_column(name) {
          Some(_) => Name(@value.ascii_upper(name))
          None => raise ParseError("invalid sheet reference: " + name)
        }
      }
    Number(d) => match row_index(d) {
      Some(r) => Lit(@value.Num(r.to_double()))
      None => raise ParseError("invalid row reference in sheet range")
    }
    _ => raise ParseError("invalid sheet reference")
  }
}

/// 解析 `Sheet!` 之后的引用;区域(含整列/整行)由外层 `:` 组合完成。
fn parse_sheet_qualified(p : Parser, sheet : String) -> Expr raise ParseError {
  let inner = parse_sheet_primary(p)
  match inner {
    Ref(_) => Sheet(sheet, inner)
    _ => {
      if peek(p) != Some(Colon) {
        raise ParseError("expected ':' after sheet-qualified reference")
      }
      Sheet(sheet, inner)
    }
  }
}

/// 区域端点规范化:行、列各自升序,并清除绝对引用标记(区域在值层面无绝对性)。
fn normalize_pair(
  a : @value.CellAddr,
  b : @value.CellAddr,
) -> (@value.CellAddr, @value.CellAddr) {
  let lo : @value.CellAddr = {
    row: if a.row < b.row { a.row } else { b.row },
    col: if a.col < b.col { a.col } else { b.col },
    abs_row: false,
    abs_col: false,
  }
  let hi : @value.CellAddr = {
    row: if a.row > b.row { a.row } else { b.row },
    col: if a.col > b.col { a.col } else { b.col },
    abs_row: false,
    abs_col: false,
  }
  (lo, hi)
}

fn whole_cols(c1 : Int, c2 : Int) -> Expr {
  if c1 <= c2 {
    WholeCols(c1, c2)
  } else {
    WholeCols(c2, c1)
  }
}

fn whole_rows(r1 : Int, r2 : Int) -> Expr {
  if r1 <= r2 {
    WholeRows(r1, r2)
  } else {
    WholeRows(r2, r1)
  }
}

fn rng_end(e : Expr) -> RngEnd? {
  match e {
    Ref(a) => Some(RngRef(a))
    Name(s) => match @value.parse_column(s) {
      Some(c) => Some(RngCol(c))
      None => None
    }
    Lit(v) => match v {
      @value.Value::Num(d) => match row_index(d) {
        Some(r) => Some(RngRow(r))
        None => None
      }
      _ => None
    }
    _ => None
  }
}

fn sheet_end(e : Expr) -> (String, RngEnd)? {
  match e {
    Sheet(s, inner) => match rng_end(inner) {
      Some(re) => Some((s, re))
      None => None
    }
    _ => None
  }
}

/// `:` 组合:单元格区域、整列区域(`A:B` / `Sheet!A:B`)、整行区域(`2:3` / `Sheet!2:3`)。
/// 3D 表名区域、跨表区域与其它组合一律解析期拒绝。
fn combine_range(lhs : Expr, rhs : Expr) -> Expr raise ParseError {
  match (rng_end(lhs), rng_end(rhs)) {
    (Some(RngRef(a)), Some(RngRef(b))) => {
      let (lo, hi) = normalize_pair(a, b)
      Range(lo, hi)
    }
    (Some(RngCol(c1)), Some(RngCol(c2))) => whole_cols(c1, c2)
    (Some(RngRow(r1)), Some(RngRow(r2))) => whole_rows(r1, r2)
    _ =>
      match (sheet_end(lhs), rng_end(rhs)) {
        (Some((s, RngRef(a))), Some(RngRef(b))) => {
          let (lo, hi) = normalize_pair(a, b)
          Sheet(s, Range(lo, hi))
        }
        (Some((s, RngCol(c1))), Some(RngCol(c2))) => Sheet(s, whole_cols(c1, c2))
        (Some((s, RngRow(r1))), Some(RngRow(r2))) => Sheet(s, whole_rows(r1, r2))
        _ =>
          match (sheet_end(lhs), sheet_end(rhs)) {
            (Some((s1, RngRef(a))), Some((s2, RngRef(b)))) => {
              if s1 != s2 {
                raise ParseError("3D references are not supported: " + s1 + ":" + s2)
              }
              let (lo, hi) = normalize_pair(a, b)
              Sheet(s1, Range(lo, hi))
            }
            _ => raise ParseError("range endpoints must be cell references")
          }
      }
  }
}

fn parse_prefix(p : Parser) -> Expr raise ParseError {
  let t = match peek(p) {
    Some(t) => t
    None => raise ParseError("unexpected end of formula")
  }
  p.pos += 1
  match t {
    Number(d) => Lit(@value.Num(d))
    Str(s) => Lit(@value.Text(s))
    BoolLit(b) => Lit(@value.Bool(b))
    ErrLit(e) => Lit(@value.Err(e))
    LParen => {
      enter_nested(p)
      let e = parse_expr(p, 0)
      expect(p, RParen, "')'")
      p.depth -= 1
      e
    }
    Op("-") => {
      enter_nested(p)
      let e = parse_expr(p, 60)
      p.depth -= 1
      Unary(Neg, e)
    }
    Op("+") => {
      enter_nested(p)
      let e = parse_expr(p, 60)
      p.depth -= 1
      Unary(Pos, e)
    }
    Ident(name) => {
      if peek(p) == Some(Bang) {
        p.pos += 1
        let sheet = sheet_token(name)
        parse_sheet_qualified(p, sheet)
      } else if peek(p) == Some(LParen) {
        p.pos += 1
        enter_nested(p)
        let args : Array[Expr] = []
        if peek(p) != Some(RParen) {
          while true {
            args.push(parse_expr(p, 0))
            if peek(p) == Some(Comma) {
              p.pos += 1
            } else {
              break
            }
          }
        }
        expect(p, RParen, "')'")
        p.depth -= 1
        Call(@value.ascii_upper(name), args)
      } else if looks_like_ref(name) {
        match @value.parse_addr(name) {
          Some(a) => Ref(a)
          None => raise ParseError("invalid cell reference: " + name)
        }
      } else if is_name_token(name) {
        Name(@value.ascii_upper(name))
      } else {
        raise ParseError("invalid reference or name: " + name)
      }
    }
    SheetName(raw) => {
      let sheet = sheet_token(raw)
      if peek(p) != Some(Bang) {
        raise ParseError("expected '!' after sheet name")
      }
      p.pos += 1
      parse_sheet_qualified(p, sheet)
    }
    _ => raise ParseError("unexpected token in formula")
  }
}

fn parse_expr(p : Parser, min_bp : Int) -> Expr raise ParseError {
  let mut lhs = parse_prefix(p)
  while true {
    let t = match peek(p) {
      Some(t) => t
      None => break
    }
    match t {
      Percent => {
        if 70 < min_bp {
          break
        }
        p.pos += 1
        lhs = Unary(Percent, lhs)
      }
      Colon => {
        if 80 < min_bp {
          break
        }
        p.pos += 1
        let rhs = parse_prefix(p)
        lhs = combine_range(lhs, rhs)
      }
      Op(s) => {
        let lbp = match s {
          "=" | "<>" | "<" | "<=" | ">" | ">=" => 10
          "&" => 20
          "+" | "-" => 30
          "*" | "/" => 40
          "^" => 50
          _ => -1
        }
        if lbp < 0 || lbp < min_bp {
          break
        }
        p.pos += 1
        let rhs = parse_expr(p, lbp + 1)
        lhs = Binary(bin_op(s), lhs, rhs)
      }
      _ => break
    }
  }
  lhs
}

/// 解析公式源码为 AST(前导 `=` 可有可无)。Pratt 解析,Excel 优先级,全部二元运算符左结合。
/// 超过 8192 字符或 64 层嵌套、语法错误、不支持的引用形式均抛 ParseError。
pub fn parse(input : String) -> Expr raise ParseError {
  if input.length() > max_formula_length {
    raise ParseError("formula exceeds 8192 characters")
  }
  let toks = lex(input)
  if toks.length() == 0 {
    raise ParseError("empty formula")
  }
  let p : Parser = { tokens: toks, pos: 0, depth: 0 }
  let e = parse_expr(p, 0)
  if p.pos != toks.length() {
    raise ParseError("unexpected trailing tokens in formula")
  }
  e
}