1package sheet23import (4 "strings"56 "src.rest/cat/012/internal/formula"7 "src.rest/cat/012/internal/functions"8)910// Evaluation is lazy and recursive: a formula reading a dirty cell11// evaluates it first, so a chain of formulas (each row adding to the row12// above) recurses once per link. The parser caps how deeply one formula13// nests (formula.MaxDepth), but a chain can run through every cell of a14// sheet, two million links, which would take more than the goroutine's15// stack. So evaluation counts how deep it is (w.depth: cells and16// operators, nested), and a cell it reaches past maxEvalDepth is put off:17// the evaluation in progress is abandoned (its cells go back to dirty),18// the cell is evaluated on its own, from the top of the stack, and then19// what was abandoned is tried again, finding it done. Values come out as20// if evaluated in one go; a long chain costs about twice the work.21//22// Cells put off are "deferred" until they're evaluated: each depends on23// the one put off after it, so reaching one again is a cycle, as reaching24// a cell being evaluated is.2526// maxEvalDepth bounds evaluation's nesting, in cells and operators: about27// 30 MB of stack. A var so tests can lower it.28var maxEvalDepth = 1 << 162930// tooDeep abandons an evaluation that went past maxEvalDepth.31type tooDeep struct{}3233// evaluator is the state of one evaluate.34type evaluator struct {35 w *Workbook36 pending []loc // cells put off, each needed by the one before37 // stack holds the formulas being evaluated, outermost first, and38 // cycle the cells found to be part of a cycle: every formula on the39 // stack from the cell reached again up. Each of them is #REF!,40 // whatever its formula makes of the #REF! it read (IFERROR, COUNTIF),41 // as in Sheets, so a cycle's values don't depend on the order its42 // cells were evaluated in.43 stack []loc44 cycle map[loc]bool45}4647// evaluate computes the cells marked dirty in each sheet's calc. Cells48// are evaluated lazily in dependency order: reading a dirty cell49// evaluates it first. A cell that is reached again while it is still50// being evaluated is part of a cycle and becomes ERR. The state lives on51// the sheets, keyed by address as on one sheet, and each sheet's lookup52// is made once, so evaluating a formula allocates nothing for sheets.53func (w *Workbook) evaluate() {54 e := &evaluator{w: w, cycle: w.findCycles()}55 w.Circular = e.cycle != nil56 // Running aggregates shared by the recalculation (rangememo.go). A57 // cell put off abandons an extension part way: its checkpoints stop58 // at the last row it finished, and the next read goes on from there.59 memo := &aggMemo{w: w, m: map[aggKey]*runAgg{}}60 for _, s := range w.sheets {61 s.version++62 s.hidden.valid = false // values may have changed what the filter hides63 s.calcGet = w.recalcReader(s, e, memo)64 s.calcFmt, s.calcPaged = w.formatFrom(s), s.calcGet.Paged65 }66 for _, s := range w.sheets {67 for !e.sweep(s) {68 e.settle()69 }70 }71 for _, s := range w.sheets {72 s.calcGet.read, s.calcGet.memo = nil, nil73 s.calcGet.lib.Forget()74 s.calc, s.calcGet, s.calcFmt, s.calcPaged = nil, nil, nil, nil75 }76}7778// compute returns the value of the cell at a, evaluating it first if it's79// dirty. Every cell a formula reads comes through here: a SUM over 819280// cells makes 8192 calls. A plain cell's value is its entry's, never81// out of date, so it costs an index into the store; only rich cells82// look up their recalculation state.83func (e *evaluator) compute(s *Sheet, a Addr) Value {84 w := e.w85 c, v, _ := s.cells.peek(a)86 if c == nil { // plain or blank87 return v88 }89 switch st := s.calc[a]; {90 case st == visiting:91 e.inCycle(loc{s, a})92 return ErrRef93 case st == deferred:94 w.Circular = true95 return ErrRef96 case st != dirty:97 return c.Value98 case c.derived || c.spilled: // a pivot's or an array's result, set when it was computed99 s.calc[a] = done100 return c.Value101 case c.expr != nil && w.depth >= maxEvalDepth:102 s.calc[a] = deferred103 e.pending = append(e.pending, loc{s, a})104 panic(tooDeep{})105 }106 c.auto = Format{}107 switch {108 case c.Input == "":109 c.Value = Value{}110 case c.expr == nil && c.Format.Kind == FmtText:111 c.Value = Value{Kind: Text, Str: c.Input}112 case c.expr == nil:113 c.Value = Value{Kind: Text, Str: strings.TrimPrefix(c.Input, "'")}114 default:115 if n, lit := c.expr.(formula.Num); lit { // a number typed in116 c.Value = num(n.V)117 } else {118 e.formula(s, a, c)119 }120 }121 s.calc[a] = done122 s.cells.changed(a)123 return c.Value124}125126// formula evaluates the formula in c, at a, which may read other cells:127// it's visiting meanwhile.128func (e *evaluator) formula(s *Sheet, a Addr, c *Cell) {129 w := e.w130 s.calc[a] = visiting131 w.depth++132 expr := s.bound(a, c)133 outer, l := w.evaluating, loc{s, a}134 w.evaluating = l135 e.stack = append(e.stack, l)136 c.Value = functions.EvalCell(w.arith(expr), s.calcGet.lib, a)137 e.stack = e.stack[:len(e.stack)-1]138 arr := s.calcGet.lib.Spilled()139 if e.cycle[l] {140 c.Value, arr = ErrRef, nil141 }142 if arr != nil || s.spills != nil {143 w.noteSpill(s, a, c, arr)144 }145 w.evaluating = outer146 c.auto = functions.InferFormat(expr, s.calcFmt, s.calcPaged)147 w.depth--148}149150// inCycle notes that the formula at l, being evaluated, was reached151// again: it and the formulas it led to, up the stack, form a cycle.152func (e *evaluator) inCycle(l loc) {153 e.w.Circular = true154 if e.cycle == nil {155 e.cycle = map[loc]bool{}156 }157 for i := len(e.stack) - 1; i >= 0; i-- {158 e.cycle[e.stack[i]] = true159 if e.stack[i] == l {160 return161 }162 }163}164165// sweep evaluates s's dirty cells, reporting false if it went too deep166// and put off a cell.167func (e *evaluator) sweep(s *Sheet) (finished bool) {168 defer e.abandon(&finished)169 for a, st := range s.calc {170 if st == dirty {171 e.compute(s, a)172 }173 }174 return true175}176177// settle evaluates the cells put off, deepest first, putting off more on178// the way if need be.179func (e *evaluator) settle() {180 for len(e.pending) > 0 {181 top := e.pending[len(e.pending)-1]182 if top.s.calc[top.a] == deferred {183 top.s.calc[top.a] = dirty184 }185 if e.try(top) {186 e.pending = e.pending[:len(e.pending)-1]187 }188 }189}190191// try evaluates the cell at l, reporting false if it went too deep and192// put off a cell, having undone what it had started.193func (e *evaluator) try(l loc) (finished bool) {194 defer e.abandon(&finished)195 e.compute(l.s, l.a)196 return true197}198199// abandon, deferred, recovers from an evaluation that went too deep:200// the cells it was evaluating go back to dirty, those put off stay201// deferred, and finished is set false.202func (e *evaluator) abandon(finished *bool) {203 r := recover()204 if r == nil {205 return206 }207 if _, deep := r.(tooDeep); !deep {208 panic(r)209 }210 for _, s := range e.w.sheets {211 for a, st := range s.calc {212 if st == visiting {213 s.calc[a] = dirty214 }215 }216 s.calcGet.lib.Reset()217 }218 for _, p := range e.pending {219 p.s.calc[p.a] = deferred220 }221 e.w.depth = 0222 e.w.evaluating = loc{}223 e.stack = e.stack[:0]224 *finished = false225}