| 1 | package calc |
| 2 | |
| 3 | import "time" |
| 4 | |
| 5 | // Recalc propagates a change at origin to every cell that transitively |
| 6 | // depends on it, evaluates each of those exactly once, and returns how |
| 7 | // many cells it touched. origin's own new value is expected to already |
| 8 | // be in env (e.g. a literal the user just typed) unless origin itself is |
| 9 | // a formula cell — an edit to a formula's own text — in which case origin |
| 10 | // is recomputed too. |
| 11 | // |
| 12 | // Past MaxDirtyPerPass, Recalc evaluates nothing and returns the count it |
| 13 | // would have touched; see the constant's comment for why. |
| 14 | func (g *Graph) Recalc(origin CellKey, env Env) int { |
| 15 | dirty := g.TransitiveDependents(origin) |
| 16 | if _, hasFormula := g.formulas[origin]; hasFormula { |
| 17 | dirty[origin] = struct{}{} |
| 18 | } |
| 19 | if len(dirty) > MaxDirtyPerPass { |
| 20 | return len(dirty) |
| 21 | } |
| 22 | g.color = make(map[CellKey]cellColor, len(dirty)) |
| 23 | genv := &graphEnv{g: g, base: env, dirty: dirty} |
| 24 | for k := range dirty { |
| 25 | genv.CellValue(k) |
| 26 | } |
| 27 | return len(dirty) |
| 28 | } |
| 29 | |
| 30 | // Value returns key's current value, evaluating it — and, recursively, |
| 31 | // whatever it depends on — from scratch. Unlike Recalc, it does not trust |
| 32 | // any existing cache: it is the ad-hoc "what is this cell right now" |
| 33 | // query (and the one TestCycleDetection uses), not the incremental fast |
| 34 | // path an edit takes. |
| 35 | // |
| 36 | // Cycle detection is the colour mark during this walk: a formula cell |
| 37 | // re-entered while still grey — still mid-evaluation lower in the same |
| 38 | // call stack — resolves to #CIRCULAR! instead of recursing forever. |
| 39 | func (g *Graph) Value(key CellKey, env Env) Value { |
| 40 | g.color = make(map[CellKey]cellColor) |
| 41 | genv := &graphEnv{g: g, base: env} |
| 42 | return genv.CellValue(key) |
| 43 | } |
| 44 | |
| 45 | // graphEnv is the Env Eval sees while the graph drives an evaluation. It |
| 46 | // intercepts CellValue for any cell the graph itself manages (one with a |
| 47 | // formula) and defers to base for everything else — a raw input cell, or |
| 48 | // any cell this graph has never heard of. |
| 49 | type graphEnv struct { |
| 50 | g *Graph |
| 51 | base Env |
| 52 | // dirty scopes a Recalc pass: a formula cell outside this set is |
| 53 | // assumed unaffected by the change and its existing cached value is |
| 54 | // reused as-is, so a clean precedent is never recomputed (and never |
| 55 | // inflates Recalc's touched count). nil means no such assumption |
| 56 | // applies — Value's every-cell-fresh walk. |
| 57 | dirty map[CellKey]struct{} |
| 58 | } |
| 59 | |
| 60 | func (e *graphEnv) Now() time.Time { return e.base.Now() } |
| 61 | |
| 62 | func (e *graphEnv) CellValue(k CellKey) Value { |
| 63 | n, isFormula := e.g.formulas[k] |
| 64 | if !isFormula { |
| 65 | return e.base.CellValue(k) |
| 66 | } |
| 67 | if e.dirty != nil { |
| 68 | if _, inPass := e.dirty[k]; !inPass && e.g.cached[k] { |
| 69 | return e.g.cache[k] // clean precedent: unaffected, last value still holds |
| 70 | } |
| 71 | } |
| 72 | switch e.g.color[k] { |
| 73 | case black: |
| 74 | return e.g.cache[k] |
| 75 | case grey: |
| 76 | return Value{Kind: KindErr, Err: ErrCircular} |
| 77 | } |
| 78 | e.g.color[k] = grey |
| 79 | v := Eval(n, e) |
| 80 | e.g.color[k] = black |
| 81 | e.g.cache[k] = v |
| 82 | e.g.cached[k] = true |
| 83 | return v |
| 84 | } |
| 85 | |
amadan