1package formula23import (4 "fmt"5 "strconv"6 "strings"78 "src.rest/cat/012/internal/numfmt"9)1011// Binding powers, lowest to highest, following Sheets' precedence.12var infixPower = map[string]int{13 "#OR#": 10, "#AND#": 10,14 "=": 30, "<>": 30, "<": 30, ">": 30, "<=": 30, ">=": 30,15 "&": 35,16 "+": 40, "-": 40,17 "*": 50, "/": 50,18 "^": 70,19}2021// Negation binds tighter than ^, so -2^2 is 4 as in Sheets and Excel.22const (23 notPower = 2024 unaryPower = 7525 percentPower = 8026)2728// MaxDepth is how deeply a formula may nest: parentheses, function calls29// and prefix operators each open a level (an operator of higher30// precedence may add one or two). Excel allows 64 nested functions; this31// is far more than a formula written by hand needs, and it bounds the32// recursion of everything that walks a formula (the parser, printer,33// evaluator and reference rewriting), so a pathological file fails to34// parse rather than exhausting the stack.35const MaxDepth = 10243637type parser struct {38 src string // the formula without its "=", for names' original spelling39 toks []token40 pos int41 funcs Funcs42 depth int // of expr calls, see MaxDepth43 // locals are the names LET and LAMBDA calls being parsed have bound,44 // innermost last, as upper-case keys.45 locals []string46}4748// Parse parses a formula, finding the functions it calls with funcs. src49// may start with "=", as typed in a cell; error positions are relative to50// src.51func Parse(src string, funcs Funcs) (Node, error) {52 body := strings.TrimPrefix(src, "=")53 offset := len(src) - len(body)54 toks, err := lex(body)55 if err != nil {56 return nil, shift(err, offset, src)57 }58 p := &parser{src: body, toks: toks, funcs: funcs}59 n, err := p.expr(0)60 if err == nil && p.peek().kind != tokEOF {61 err = &ParseError{Pos: p.peek().pos, Msg: "Unexpected " + p.peek().text}62 }63 if err != nil {64 return nil, shift(err, offset, src)65 }66 return n, nil67}6869func shift(err error, offset int, src string) error {70 if pe, ok := err.(*ParseError); ok {71 pe.Pos += offset72 pe.src = src73 }74 return err75}7677func (p *parser) peek() token { return p.toks[p.pos] }7879func (p *parser) next() token {80 t := p.toks[p.pos]81 if t.kind != tokEOF {82 p.pos++83 }84 return t85}8687func (p *parser) isOp(op string) bool {88 t := p.peek()89 return t.kind == tokOp && t.text == op90}9192// expr parses an expression whose operators bind tighter than minPower.93// Every level of nesting passes through here, so here it's counted.94func (p *parser) expr(minPower int) (Node, error) {95 if p.depth >= MaxDepth {96 return nil, &ParseError{Pos: p.peek().pos, Msg: fmt.Sprintf("Formula is nested too deeply (more than %d levels)", MaxDepth)}97 }98 p.depth++99 n, err := p.climb(minPower)100 p.depth--101 return n, err102}103104// climb parses by precedence climbing: a prefix, then infix and postfix105// operators binding tighter than minPower.106func (p *parser) climb(minPower int) (Node, error) {107 left, err := p.prefix()108 if err != nil {109 return nil, err110 }111 for {112 if p.isOp("%") && percentPower > minPower {113 p.next()114 left = Unary{Op: "%", X: left}115 continue116 }117 t := p.peek()118 power, ok := infixPower[t.text]119 if t.kind != tokOp || !ok || power <= minPower {120 return left, nil121 }122 p.next()123 right, err := p.expr(power)124 if err != nil {125 return nil, err126 }127 left = Binary{Op: t.text, L: left, R: right}128 }129}130131func (p *parser) prefix() (Node, error) {132 t := p.next()133 switch t.kind {134 case tokNum:135 if r, ok := p.lines(t, ""); ok {136 return r, nil137 }138 v, err := strconv.ParseFloat(numfmt.Entered(t.text), 64)139 if err != nil {140 return nil, &ParseError{Pos: t.pos, Msg: "Invalid number " + t.text}141 }142 return Num{v}, nil143 case tokStr:144 return Str{t.text}, nil145 case tokIdent:146 return p.ident(t, "")147 case tokSheet:148 ref := p.next()149 if r, ok := p.lines(ref, t.text); ok {150 return r, nil151 }152 if ref.kind != tokIdent {153 return nil, &ParseError{Pos: ref.pos, Msg: "Expected a cell after " + QuoteSheet(t.text) + "!"}154 }155 return p.ident(ref, t.text)156 case tokTable:157 return tableRef(t.text, t.pos)158 case tokFunc:159 return p.call(t)160 case tokRefErr:161 return RefErr{}, nil162 case tokOp:163 return p.prefixOp(t)164 case tokEOF:165 return nil, &ParseError{Pos: t.pos, Msg: "Formula is incomplete"}166 }167 return nil, &ParseError{Pos: t.pos, Msg: "Unexpected " + t.text}168}169170// prefixOp parses what starts with an operator: a parenthesized171// expression, or a prefix + - or #NOT#.172func (p *parser) prefixOp(t token) (Node, error) {173 switch t.text {174 case "(":175 n, err := p.expr(0)176 if err != nil {177 return nil, err178 }179 if !p.isOp(")") {180 return nil, &ParseError{Pos: p.peek().pos, Msg: "Missing )"}181 }182 p.next()183 return n, nil184 case "{":185 return p.array(t)186 case "+", "-", "#NOT#":187 power := unaryPower188 if t.text == "#NOT#" {189 power = notPower190 }191 x, err := p.expr(power)192 if err != nil {193 return nil, err194 }195 return Unary{Op: t.text, X: x}, nil196 }197 return nil, &ParseError{Pos: t.pos, Msg: "Unexpected " + t.text}198}199200// ident parses a reference, a range, a boolean or a name. sheet is the201// sheet the reference was qualified with, if any.202func (p *parser) ident(t token, sheet string) (Node, error) {203 if r, ok := p.lines(t, sheet); ok {204 return r, nil205 }206 a, abs, isRef := ParseRef(t.text)207 if !isRef {208 if sheet != "" {209 return nil, &ParseError{Pos: t.pos, Msg: "Expected a cell after " + QuoteSheet(sheet) + "!"}210 }211 switch t.text {212 case "TRUE":213 return Bool{true}, nil214 case "FALSE":215 return Bool{false}, nil216 }217 // Names match case-insensitively but print as written.218 written := p.src[t.pos : t.pos+len(t.text)]219 if p.bound(t.text) {220 return Local{written}, nil221 }222 return Name{written}, nil223 }224 if !p.isOp(":") && !p.isOp("..") {225 return Ref{a, abs, sheet}, nil226 }227 sep := p.next()228 end := p.next()229 // The second corner may repeat the sheet: Sheet2!A1:Sheet2!B3.230 if end.kind == tokSheet {231 if SheetKey(end.text) != SheetKey(sheet) {232 return nil, &ParseError{Pos: end.pos, Msg: "A range can't span sheets"}233 }234 end = p.next()235 }236 b, bAbs, ok := ParseRef(end.text)237 if end.kind != tokIdent || !ok {238 return nil, &ParseError{Pos: end.pos, Msg: "Expected a cell after " + sep.text}239 }240 r := NewRange(a, b, abs, bAbs)241 r.Sheet = sheet242 return r, nil243}244245// lines parses whole columns (A:C, $A:$A) or rows (2:5), starting at t,246// if that's what comes.247func (p *parser) lines(t token, sheet string) (Range, bool) {248 if !p.isOp(":") || t.kind != tokIdent && t.kind != tokNum {249 return Range{}, false250 }251 end := p.toks[p.pos+1]252 if end.kind == tokSheet && SheetKey(end.text) == SheetKey(sheet) && p.pos+2 < len(p.toks) {253 end = p.toks[p.pos+2]254 }255 if end.kind != tokIdent && end.kind != tokNum {256 return Range{}, false257 }258 r, abs, ok := ParseLines(t.text, end.text)259 if !ok {260 return Range{}, false261 }262 for p.next() != end {263 }264 return Range{r, abs, sheet}, true265}266267// NewRange builds a normalized range from two corners as written. Each268// absolute marker stays with its column or row, so $B1:A$2 becomes A1:$B$2.269func NewRange(a, b Addr, aAbs, bAbs Abs) Range {270 swap := func(bit Abs) {271 aAbs, bAbs = aAbs&^bit|bAbs&bit, bAbs&^bit|aAbs&bit272 }273 if a.Col > b.Col {274 a.Col, b.Col = b.Col, a.Col275 swap(AbsCol)276 }277 if a.Row > b.Row {278 a.Row, b.Row = b.Row, a.Row279 swap(AbsRow)280 }281 return Range{Rect{a, b}, [2]Abs{aAbs, bAbs}, ""}282}283284// call parses a function call, with or without parentheses (@PI), and285// checks its number of arguments. A name LET or LAMBDA bound, followed286// by arguments, calls the LAMBDA it stands for.287func (p *parser) call(t token) (Node, error) {288 if p.bound(t.text) && p.isOp("(") {289 p.next()290 args, err := p.args(t.text, BindNone)291 if err != nil {292 return nil, err293 }294 return Invoke{Fn: Local{p.src[t.pos : t.pos+len(t.text)]}, Args: args}, nil295 }296 fn, ok := p.funcs(t.text)297 if !ok {298 return nil, &ParseError{Pos: t.pos, Msg: "Unknown function " + t.text}299 }300 sig := fn.Signature()301 n := Call{Fn: fn}302 if p.isOp("(") {303 p.next()304 scope := len(p.locals)305 args, err := p.args(sig.Name, sig.Binds)306 p.locals = p.locals[:scope]307 if err != nil {308 return nil, err309 }310 n.Args = args311 }312 if !sig.accepts(len(n.Args)) {313 return nil, &ParseError{Pos: t.pos, Msg: fmt.Sprintf("Wrong number of arguments to %s(%s)", sig.Name, sig.Args)}314 }315 if err := checkBinds(sig, n.Args, t.pos); err != nil {316 return nil, err317 }318 if sig.Binds == BindLambda && p.isOp("(") {319 p.next()320 args, err := p.args(sig.Name, BindNone)321 if err != nil {322 return nil, err323 }324 return Invoke{Fn: n, Args: args}, nil325 }326 return n, nil327}328329// args parses a call's arguments after its "(", through the ")". An330// argument may be left out: F(a, , c) or F(a, ). With binds, the names331// the call binds are declared as they come (see declares).332func (p *parser) args(name string, binds Binding) ([]Node, error) {333 if p.isOp(")") {334 p.next()335 return nil, nil336 }337 var args []Node338 for {339 if decl, ok := p.declares(binds, len(args)); ok {340 args = append(args, decl)341 p.next()342 p.locals = append(p.locals, strings.ToUpper(decl.Name))343 } else if p.isOp(",") || p.isOp(";") || p.isOp(")") {344 args = append(args, Empty{})345 } else {346 arg, err := p.expr(0)347 if err != nil {348 return nil, err349 }350 args = append(args, arg)351 }352 sep := p.next()353 switch {354 case sep.kind == tokOp && sep.text == ")":355 return args, nil356 case sep.kind != tokOp || (sep.text != "," && sep.text != ";"):357 return nil, &ParseError{Pos: sep.pos, Msg: "Expected , or ) in " + name}358 }359 }360}361362// declares reports whether argument i of a call binding names with binds363// is a name it declares: a plain name, not a cell, followed by a comma364// (the last argument is the expression, never a name).365func (p *parser) declares(binds Binding, i int) (Local, bool) {366 if binds == BindNone || binds == BindLet && i%2 == 1 {367 return Local{}, false368 }369 t, sep := p.peek(), p.toks[min(p.pos+1, len(p.toks)-1)]370 if t.kind != tokIdent || sep.kind != tokOp || sep.text != "," && sep.text != ";" {371 return Local{}, false372 }373 if _, _, isRef := ParseRef(t.text); isRef || t.text == "TRUE" || t.text == "FALSE" {374 return Local{}, false375 }376 return Local{p.src[t.pos : t.pos+len(t.text)]}, true377}378379// bound reports whether a LET or LAMBDA being parsed binds the name key.380func (p *parser) bound(key string) bool {381 for _, l := range p.locals {382 if l == key {383 return true384 }385 }386 return false387}388389// checkBinds checks that a LET or LAMBDA names what it binds: LET takes390// pairs of a name and a value before its expression (its signature391// counts them), LAMBDA names before its expression.392func checkBinds(sig Signature, args []Node, pos int) error {393 if sig.Binds == BindNone || len(args) == 0 {394 return nil395 }396 for i, a := range args[:len(args)-1] {397 if sig.Binds == BindLet && i%2 == 1 {398 continue399 }400 if _, ok := a.(Local); !ok {401 return &ParseError{Pos: pos, Msg: fmt.Sprintf("Argument %d of %s must be a name, like x or total", i+1, sig.Name)}402 }403 }404 return nil405}406407// array parses an array literal after its "{": elements separated by ","408// in a row and rows by ";", through the "}".409func (p *parser) array(open token) (Node, error) {410 if p.isOp("}") {411 return nil, &ParseError{Pos: open.pos, Msg: "An array needs at least one value"}412 }413 rows := [][]Node{nil}414 for {415 e, err := p.expr(0)416 if err != nil {417 return nil, err418 }419 rows[len(rows)-1] = append(rows[len(rows)-1], e)420 sep := p.next()421 switch {422 case sep.kind == tokOp && sep.text == "}":423 return Array{rows}, nil424 case sep.kind == tokOp && sep.text == ",":425 case sep.kind == tokOp && sep.text == ";":426 rows = append(rows, nil)427 default:428 return nil, &ParseError{Pos: sep.pos, Msg: "Expected , ; or } in an array"}429 }430 }431}432433// accepts reports whether a call may pass n arguments.434func (s Signature) accepts(n int) bool {435 return n >= s.Min && (s.Max < 0 || n <= s.Max) && (s.Step <= 0 || (n-s.Min)%s.Step == 0)436}