/// 公式解析失败(语法错误、不支持的引用形式、超出 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
}

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(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 {
        raise ParseError("defined names are not supported: " + name)
      }
    }
    _ => 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)
        match (lhs, rhs) {
          (Ref(a), Ref(b)) => {
            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,
            }
            lhs = Range(lo, hi)
          }
          _ => raise ParseError("range endpoints must be cell references")
        }
      }
      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
}