1// Package formula is the formula language: A1 references and ranges,2// sheet names in references, the lexer and Pratt parser, the syntax tree,3// the printer that writes trees back in Sheets' spelling, and the4// rewriting of references when cells are copied, moved, inserted or5// deleted. It knows nothing of cells or values: the engine evaluates the6// trees, and tells the parser which functions exist.7package formula89// Node is a parsed formula expression: one of the types below.10type Node any1112type (13 Num struct{ V float64 }14 Str struct{ V string }15 Bool struct{ V bool }16 // Ref is a cell reference. Sheet is the sheet name as written before17 // the "!" (Sheet2!A1), or "" for the formula's own sheet.18 Ref struct {19 Addr Addr20 Abs Abs21 Sheet string22 }23 // Range is kept normalized (Rect.From is the top-left corner); Abs24 // holds the absolute markers of Rect.From and Rect.To.25 Range struct {26 Rect Rect27 Abs [2]Abs28 Sheet string29 }30 RefErr struct{} // a reference to deleted cells: #REF!31 Name struct{ Name string } // a named range as spelled in the formula32 Empty struct{} // an omitted argument, as in XLOOKUP(a, b, c, , 1)33 Unary struct {34 Op string // "-", "+", "%" (postfix) or "#NOT#"35 X Node36 }37 Binary struct {38 Op string39 L, R Node40 }41 Call struct {42 Fn Func43 Args []Node44 }45 // Array is an array literal, {1,2;3,4}: rows of elements separated46 // by ";", elements by ",". An element may itself be a range or an47 // array, as {A1:A3,B1:B3} joins two columns.48 Array struct{ Rows [][]Node }49 // Local is a name LET or LAMBDA binds, used within that call, as in50 // LET(total, SUM(A:A), total*2). Named ranges never replace it.51 Local struct{ Name string }52 // Invoke calls what Fn computes to, a LAMBDA, with Args:53 // LAMBDA(x, x*2)(3), or f(3) where LET bound f to a LAMBDA.54 Invoke struct {55 Fn Node56 Args []Node57 }58)5960// Func is a function a formula can call. The parser checks calls against61// its signature; what a call computes is up to the engine, which62// recovers its own type from Call.Fn.63type Func interface {64 Signature() Signature65}6667// Signature is how a function is called.68type Signature struct {69 Name string // canonical, upper case70 Args string // shown to users, e.g. "value1, [value2, ...]"71 Min int72 Max int // -1 for variadic73 // Step > 0 means arguments after Min come in groups of Step, like74 // SUMIFS' (range, criterion) pairs.75 Step int76 // Binds says which arguments name values for the rest of the call,77 // as LET's and LAMBDA's do.78 Binds Binding79}8081// Binding is how a function's arguments bind names (Local).82type Binding uint88384const (85 BindNone Binding = iota86 // BindLet: LET(name1, value1, [name2, value2, ...], expression),87 // each name bound for the arguments after it.88 BindLet89 // BindLambda: LAMBDA([name, ...], expression), the names bound in90 // the expression.91 BindLambda92)9394// Funcs finds a function by its upper-case name or alias.95type Funcs func(name string) (Func, bool)9697// EachChild calls fn with every expression directly inside n: operands,98// arguments and array elements.99func EachChild(n Node, fn func(Node)) {100 switch n := n.(type) {101 case Unary:102 fn(n.X)103 case Binary:104 fn(n.L)105 fn(n.R)106 case Call:107 for _, a := range n.Args {108 fn(a)109 }110 case Array:111 for _, row := range n.Rows {112 for _, e := range row {113 fn(e)114 }115 }116 case Invoke:117 fn(n.Fn)118 for _, a := range n.Args {119 fn(a)120 }121 }122}123124// WalkNames calls fn for every name in n. It walks the tree itself125// rather than through EachChild, as every formula entered is walked.126func WalkNames(n Node, fn func(Name)) {127 switch n := n.(type) {128 case Name:129 fn(n)130 case Unary:131 WalkNames(n.X, fn)132 case Binary:133 WalkNames(n.L, fn)134 WalkNames(n.R, fn)135 case Call:136 for _, a := range n.Args {137 WalkNames(a, fn)138 }139 case Array, Invoke:140 EachChild(n, func(k Node) { WalkNames(k, fn) })141 }142}143144// WalkRefs calls fn for every single-cell reference and range in n, with145// the sheet it was qualified with ("" for the formula's own sheet).146func WalkRefs(n Node, ref func(string, Addr), rng func(string, Rect)) {147 switch n := n.(type) {148 case Ref:149 ref(n.Sheet, n.Addr)150 case Range:151 rng(n.Sheet, n.Rect)152 case Unary:153 WalkRefs(n.X, ref, rng)154 case Binary:155 WalkRefs(n.L, ref, rng)156 WalkRefs(n.R, ref, rng)157 case Call:158 for _, a := range n.Args {159 WalkRefs(a, ref, rng)160 }161 case Array, Invoke:162 EachChild(n, func(k Node) { WalkRefs(k, ref, rng) })163 }164}