| 1 | package calc |
| 2 | |
| 3 | // MaxDirtyPerPass caps how many cells a single Recalc will touch. One |
| 4 | // edit to a cell feeding a whole-column formula can transitively dirty |
| 5 | // thousands of dependents; past the cap Recalc stops without evaluating |
| 6 | // anything and just reports how many cells it would have touched, so the |
| 7 | // caller can tell the client to refetch its viewport instead of shipping |
| 8 | // (and the client diffing) an enormous delta. |
| 9 | // |
| 10 | // Exported so a caller that needs to decide up front whether a pass will |
| 11 | // run — Task 10's handle, deciding whether to attempt a synchronous |
| 12 | // dirty-forward recompute at all — can check against the same number |
| 13 | // Recalc enforces, rather than keeping a second copy of it. |
| 14 | const MaxDirtyPerPass = 5000 |
| 15 | |
| 16 | // Graph holds the precedent/dependent edges between formula cells and a |
| 17 | // cache of their last computed value. It is what turns "this cell |
| 18 | // changed" into "recompute exactly the cells that read it, transitively, |
| 19 | // and nothing else." A Graph is not safe for concurrent use — callers |
| 20 | // serialize edits and recalculation passes, the same discipline a single |
| 21 | // pass seeing a single Now() already requires. |
| 22 | type Graph struct { |
| 23 | formulas map[CellKey]Node |
| 24 | precedents map[CellKey]map[CellKey]struct{} // cell -> cells its formula reads |
| 25 | dependents map[CellKey]map[CellKey]struct{} // cell -> cells that read it |
| 26 | cache map[CellKey]Value |
| 27 | cached map[CellKey]bool // cache presence, since a cached zero Value is a real answer |
| 28 | color map[CellKey]cellColor |
| 29 | } |
| 30 | |
| 31 | // cellColor marks a cell's state during one evaluation walk, the standard |
| 32 | // three-colour cycle check: white (unvisited), grey (on the current |
| 33 | // recursion stack), black (finished). A node re-entered while grey is a |
| 34 | // cycle. |
| 35 | type cellColor uint8 |
| 36 | |
| 37 | const ( |
| 38 | white cellColor = iota |
| 39 | grey |
| 40 | black |
| 41 | ) |
| 42 | |
| 43 | // NewGraph returns an empty graph with no formulas. |
| 44 | func NewGraph() *Graph { |
| 45 | return &Graph{ |
| 46 | formulas: make(map[CellKey]Node), |
| 47 | precedents: make(map[CellKey]map[CellKey]struct{}), |
| 48 | dependents: make(map[CellKey]map[CellKey]struct{}), |
| 49 | cache: make(map[CellKey]Value), |
| 50 | cached: make(map[CellKey]bool), |
| 51 | } |
| 52 | } |
| 53 | |
| 54 | // SetFormula installs (or replaces) the formula at key, rewiring |
| 55 | // precedent and dependent edges to match the references the new formula |
| 56 | // actually contains. The cell's cached value is dropped; nothing |
| 57 | // recomputes until Recalc or Value asks for it. |
| 58 | func (g *Graph) SetFormula(key CellKey, n Node) { |
| 59 | if old, ok := g.precedents[key]; ok { |
| 60 | for p := range old { |
| 61 | delete(g.dependents[p], key) |
| 62 | } |
| 63 | } |
| 64 | refs := collectRefs(n) |
| 65 | prec := make(map[CellKey]struct{}, len(refs)) |
| 66 | for _, r := range refs { |
| 67 | prec[r] = struct{}{} |
| 68 | if g.dependents[r] == nil { |
| 69 | g.dependents[r] = make(map[CellKey]struct{}) |
| 70 | } |
| 71 | g.dependents[r][key] = struct{}{} |
| 72 | } |
| 73 | g.formulas[key] = n |
| 74 | g.precedents[key] = prec |
| 75 | delete(g.cache, key) |
| 76 | delete(g.cached, key) |
| 77 | } |
| 78 | |
| 79 | // collectRefs walks n and returns the CellKey of every cell it reads — |
| 80 | // every *Ref directly, every cell a *Range covers, recursively through |
| 81 | // binary, unary and call nodes. This is what SetFormula uses to build |
| 82 | // precedent/dependent edges. |
| 83 | // |
| 84 | // A *Range over maxRangeCells is left untracked here rather than adding |
| 85 | // hundreds of thousands of edges for one formula. This is safe, not just |
| 86 | // cheap: evalCallArg applies the exact same cap to the same Range when |
| 87 | // the formula actually evaluates, turning it into a single #REF! |
| 88 | // argument (see maxRangeCells) — so a formula with an untracked range |
| 89 | // never reads live data from that range in the first place. There is no |
| 90 | // stale-but-plausible value for a missing edge to fail to invalidate; |
| 91 | // the formula is #REF! until its Range shrinks under the cap, at which |
| 92 | // point re-parsing it (SetFormula) tracks it again. |
| 93 | func collectRefs(n Node) []CellKey { |
| 94 | var out []CellKey |
| 95 | var walk func(Node) |
| 96 | walk = func(n Node) { |
| 97 | switch t := n.(type) { |
| 98 | case *Ref: |
| 99 | out = append(out, refKey(t)) |
| 100 | case *Range: |
| 101 | if cells, ok := rangeCells(t); ok { |
| 102 | out = append(out, cells...) |
| 103 | } |
| 104 | case *Binary: |
| 105 | walk(t.Left) |
| 106 | walk(t.Right) |
| 107 | case *Unary: |
| 108 | walk(t.X) |
| 109 | case *Call: |
| 110 | for _, a := range t.Args { |
| 111 | walk(a) |
| 112 | } |
| 113 | } |
| 114 | } |
| 115 | walk(n) |
| 116 | return out |
| 117 | } |
| 118 | |
| 119 | // TransitiveDependents returns every cell reachable from origin by |
| 120 | // following dependent edges — the set that could change because origin |
| 121 | // did. origin itself is never included by this walk (callers that also |
| 122 | // need to recompute a changed formula cell's own value add it |
| 123 | // separately; see Recalc). |
| 124 | // |
| 125 | // Exported so a caller that needs to know WHICH cells a change affects — |
| 126 | // Task 10's handle, deciding which cells' persisted cache rows to |
| 127 | // rewrite after a Set or during Open's crash recovery — can ask Graph |
| 128 | // directly rather than re-deriving the same edges. Recalc itself |
| 129 | // deliberately returns only a touched count (it feeds the recalc |
| 130 | // marker's derived-count field, §4.3 — not a cell list), and this is |
| 131 | // the one walk this package already gets right, including everything |
| 132 | // SetFormula/collectRefs capped when the edges were built; a second, |
| 133 | // hand-written copy of it elsewhere would be exactly the kind of |
| 134 | // duplicated truth this project's own review history keeps finding. |
| 135 | func (g *Graph) TransitiveDependents(origin CellKey) map[CellKey]struct{} { |
| 136 | seen := make(map[CellKey]struct{}) |
| 137 | queue := []CellKey{origin} |
| 138 | for len(queue) > 0 { |
| 139 | cur := queue[0] |
| 140 | queue = queue[1:] |
| 141 | for dep := range g.dependents[cur] { |
| 142 | if _, ok := seen[dep]; ok { |
| 143 | continue |
| 144 | } |
| 145 | seen[dep] = struct{}{} |
| 146 | queue = append(queue, dep) |
| 147 | } |
| 148 | } |
| 149 | return seen |
| 150 | } |
| 151 | |
| 152 | // Clear removes key's formula, its cached value, and its precedent |
| 153 | // edges, exactly as SetFormula's replacement prologue does — but installs |
| 154 | // nothing new. It is what a blanked cell uses: SetFormula only knows how |
| 155 | // to install or replace a formula, and a cell with no content is neither. |
| 156 | // |
| 157 | // Dependents of key are left untouched: a cell that reads key still |
| 158 | // depends on it after key goes blank (env.CellValue(key) now answers |
| 159 | // empty rather than key no longer mattering to anything that reads it). |
| 160 | func (g *Graph) Clear(key CellKey) { |
| 161 | if old, ok := g.precedents[key]; ok { |
| 162 | for p := range old { |
| 163 | delete(g.dependents[p], key) |
| 164 | } |
| 165 | } |
| 166 | delete(g.formulas, key) |
| 167 | delete(g.precedents, key) |
| 168 | delete(g.cache, key) |
| 169 | delete(g.cached, key) |
| 170 | } |
| 171 | |
| 172 | // CachedValue returns key's last computed value and true, or a zero |
| 173 | // Value and false if nothing has been computed (or seeded) for it yet. |
| 174 | // It never evaluates — a read-only peek at state Recalc, Value or |
| 175 | // SeedCache already established, for a caller (Task 10's handle) that |
| 176 | // needs to read back what a Recalc pass just computed for several cells |
| 177 | // without re-walking each one. |
| 178 | func (g *Graph) CachedValue(key CellKey) (Value, bool) { |
| 179 | return g.cache[key], g.cached[key] |
| 180 | } |
| 181 | |
| 182 | // SeedCache installs v as key's cached value directly, without |
| 183 | // evaluating anything, as though a prior pass had already computed it. |
| 184 | // |
| 185 | // Task 10's handle uses this at Open to restore each cell's |
| 186 | // last-known-good value, decrypted from its stored cache, before |
| 187 | // deciding which cells (if any) are actually stale and need a real |
| 188 | // Recalc. Without it, every formula cell would read as uncomputed after |
| 189 | // a fresh Open — SetFormula always drops any existing cache — turning an |
| 190 | // ordinary restart into a full-tab recompute instead of the targeted |
| 191 | // dirty-forward one crash recovery actually needs. |
| 192 | // |
| 193 | // What the caller owes: Graph does no checking of its own here — no |
| 194 | // verification against key's installed formula (or that one even |
| 195 | // exists), and no version bookkeeping at all, because versioning is not |
| 196 | // a concept this package has; it lives entirely in the store package |
| 197 | // that calls this. It is safe in Task 10's own use because buildHandle |
| 198 | // only ever seeds a value it just decrypted from that SAME cell's own |
| 199 | // stored cache, immediately followed by the CacheVersion/InputVersion |
| 200 | // check that decides whether a real Recalc is still owed. A caller that |
| 201 | // seeds a value NOT actually derived from key's current formula — or |
| 202 | // skips that staleness check afterward — gets a Graph that will hand |
| 203 | // CachedValue's answer back indefinitely, no differently from a value |
| 204 | // Recalc legitimately computed. Seed only a value you can vouch is |
| 205 | // key's true current answer as of the moment you call this, and treat |
| 206 | // it as provisional until whatever staleness check your caller relies |
| 207 | // on has run. |
| 208 | func (g *Graph) SeedCache(key CellKey, v Value) { |
| 209 | g.cache[key] = v |
| 210 | g.cached[key] = true |
| 211 | } |
| 212 | |
amadan