| 1 | package calc |
| 2 | |
| 3 | import "time" |
| 4 | |
| 5 | // ValueKind tags which field of a Value is live. KindEmpty is the zero |
| 6 | // value, so a Value nobody has set (e.g. env.CellValue's answer for a |
| 7 | // cell that has never been written) reads as empty, not as the number 0 — |
| 8 | // distinguishable from a cell that genuinely contains 0. Arithmetic and |
| 9 | // text coercion (toNumber, toStr) still give an empty cell the identity |
| 10 | // each context needs (0 for arithmetic, "" for concatenation), the same |
| 11 | // way Excel does; what an empty Value is NOT is silently indistinguishable |
| 12 | // from KindNum{Num: 0} to a function like COUNT that needs to tell them |
| 13 | // apart (task 8). |
| 14 | type ValueKind uint8 |
| 15 | |
| 16 | const ( |
| 17 | KindEmpty ValueKind = iota |
| 18 | KindNum |
| 19 | KindStr |
| 20 | KindBool |
| 21 | KindErr |
| 22 | ) |
| 23 | |
| 24 | // Value is a computed cell value. Cell values are IEEE doubles end to |
| 25 | // end — Num carries the number verbatim, with no rounding at this |
| 26 | // boundary; currency and other display formatting are a concern outside |
| 27 | // this package. Kind selects which field is meaningful: none for |
| 28 | // KindEmpty, Num for KindNum, Str for KindStr, Bool for KindBool, Err for |
| 29 | // KindErr. |
| 30 | type Value struct { |
| 31 | Kind ValueKind |
| 32 | Num float64 |
| 33 | Str string |
| 34 | Bool bool |
| 35 | Err ErrKind |
| 36 | } |
| 37 | |
| 38 | // CellKey identifies a cell by its stable row and column ids. It is the |
| 39 | // dependency graph's node key and the key Env looks values up by. |
| 40 | type CellKey struct { |
| 41 | RowID, ColID uint64 |
| 42 | } |
| 43 | |
| 44 | // Env supplies the two things Eval cannot know by itself: the current |
| 45 | // value of any cell a formula references, and the instant this |
| 46 | // recalculation pass is pinned to. One pass sees one instant — Now must |
| 47 | // return the same value on every call within a single Eval/Recalc walk, |
| 48 | // which is what makes a volatile function like NOW() or TODAY() |
| 49 | // deterministic within a pass (task 8 exercises this). |
| 50 | // |
| 51 | // Env is an interface, not a concrete type, so the dependency graph can |
| 52 | // hand Eval a view backed by its own cache and tests can hand it a plain |
| 53 | // map — and so that nothing in this package needs to import store or |
| 54 | // sheets to evaluate a formula. |
| 55 | type Env interface { |
| 56 | CellValue(k CellKey) Value |
| 57 | Now() time.Time |
| 58 | } |
| 59 | |
| 60 | // refKey turns a parsed reference's position into the id space Env is |
| 61 | // keyed by. Binding a reference to a stable id that survives insert and |
| 62 | // delete is task 10's job; until it exists, position IS the id — the AST |
| 63 | // carries 0-based row/column positions, so the id is simply position+1 |
| 64 | // (1-based, so 0 stays free as a reserved/unbound sentinel elsewhere in |
| 65 | // the system). Task 10's real binder can diverge ids from position after |
| 66 | // structural edits; nothing here assumes it never will. |
| 67 | func refKey(r *Ref) CellKey { |
| 68 | return CellKey{RowID: uint64(r.RowPos + 1), ColID: uint64(r.ColPos + 1)} |
| 69 | } |
| 70 | |
| 71 | // maxRangeCells caps how many cells a single Range expands to in |
| 72 | // rangeCells. The spec's own hard ceiling is 200,000 cells per tab (see |
| 73 | // spec §4.4's budgets), so no addressable range can cover more than |
| 74 | // that — this cap sits at exactly that ceiling. The realistic way to hit |
| 75 | // it is not a malformed reference but an ordinary whole-column formula — |
| 76 | // e.g. a SUM over A1:A200000 on a tab sized at its own cap — from a user |
| 77 | // who has no reason to know they've asked for every cell the tab has. |
| 78 | // Without this cap, that single formula's Range would synchronously |
| 79 | // materialize up to 200,000 CellKeys, twice over: once as call arguments |
| 80 | // when a range-taking function evaluates it (evalCallArg), and again as |
| 81 | // dependency-graph precedent edges every time SetFormula parses that same |
| 82 | // formula (collectRefs). This is rangeCells' fan-in counterpart to |
| 83 | // Recalc's MaxDirtyPerPass, which caps the symmetric fan-out case. |
| 84 | const maxRangeCells = 200_000 |
| 85 | |
| 86 | // rangeBounds normalizes a *Range's positions, handling a range written |
| 87 | // back-to-front (e.g. "A5:A1"). Shared by rangeCells below, which also |
| 88 | // materializes every cell, and by the lookup family (fn_lookup.go's |
| 89 | // boundedRangeBounds), which only need the four bounds to compute an |
| 90 | // offset or walk cells directly against env rather than through a |
| 91 | // flattened []CellKey — see fn_lookup.go's package doc comment for why |
| 92 | // VLOOKUP/INDEX/MATCH need the range's shape, not evalCallArg's flattened |
| 93 | // form. |
| 94 | func rangeBounds(rng *Range) (r0, r1, c0, c1 int) { |
| 95 | r0, r1 = rng.From.RowPos, rng.To.RowPos |
| 96 | c0, c1 = rng.From.ColPos, rng.To.ColPos |
| 97 | if r0 > r1 { |
| 98 | r0, r1 = r1, r0 |
| 99 | } |
| 100 | if c0 > c1 { |
| 101 | c0, c1 = c1, c0 |
| 102 | } |
| 103 | return |
| 104 | } |
| 105 | |
| 106 | // rangeCellCount reports how many cells a normalized range bounds covers, |
| 107 | // and whether that count is within maxRangeCells. decodeRef (token.go) |
| 108 | // accepts any int row or column, so a written reference can put r1-r0+1 |
| 109 | // or c1-c0+1 itself near the int range's own limit; multiplying two such |
| 110 | // spans together before checking them would overflow and could wrap |
| 111 | // around to a small or negative product, silently passing a pathological |
| 112 | // range through the cap it exists to enforce. So each span is checked |
| 113 | // against maxRangeCells individually — it alone already caps span sizes |
| 114 | // well below where their product could overflow — before they are ever |
| 115 | // multiplied. |
| 116 | func rangeCellCount(r0, r1, c0, c1 int) (count int, ok bool) { |
| 117 | rows := r1 - r0 + 1 |
| 118 | cols := c1 - c0 + 1 |
| 119 | if rows > maxRangeCells || cols > maxRangeCells { |
| 120 | return 0, false |
| 121 | } |
| 122 | count = rows * cols |
| 123 | return count, count <= maxRangeCells |
| 124 | } |
| 125 | |
| 126 | // rangeCells expands a Range into every CellKey it covers. Used both to |
| 127 | // fetch a function call argument's values and to build the dependency |
| 128 | // graph's precedent edges for a formula that reads a range. |
| 129 | // |
| 130 | // ok is false, with cells nil, when the range would exceed maxRangeCells — |
| 131 | // nothing is materialized in that case, mirroring Recalc's own cap: the |
| 132 | // caller decides how to report it rather than rangeCells silently |
| 133 | // truncating the range to some prefix of itself. |
| 134 | func rangeCells(rng *Range) (cells []CellKey, ok bool) { |
| 135 | r0, r1, c0, c1 := rangeBounds(rng) |
| 136 | count, ok := rangeCellCount(r0, r1, c0, c1) |
| 137 | if !ok { |
| 138 | return nil, false |
| 139 | } |
| 140 | out := make([]CellKey, 0, count) |
| 141 | for row := r0; row <= r1; row++ { |
| 142 | for col := c0; col <= c1; col++ { |
| 143 | out = append(out, CellKey{RowID: uint64(row + 1), ColID: uint64(col + 1)}) |
| 144 | } |
| 145 | } |
| 146 | return out, true |
| 147 | } |
| 148 | |
| 149 | // Eval walks n and returns its value under env. Errors are values, not Go |
| 150 | // errors: any error operand makes the whole expression that error, |
| 151 | // left-most operand wins when both sides are errors (see evalBinary). |
| 152 | func Eval(n Node, env Env) Value { |
| 153 | switch t := n.(type) { |
| 154 | case *Num: |
| 155 | return Value{Kind: KindNum, Num: t.V} |
| 156 | case *Str: |
| 157 | return Value{Kind: KindStr, Str: t.V} |
| 158 | case *Bool: |
| 159 | return Value{Kind: KindBool, Bool: t.V} |
| 160 | case *Ref: |
| 161 | return env.CellValue(refKey(t)) |
| 162 | case *Range: |
| 163 | // A bare range is not a scalar. Excel accepts one outside a |
| 164 | // function only via implicit intersection with the evaluating |
| 165 | // cell's own row/column, which this engine does not implement; |
| 166 | // reject the same way Excel does when intersection finds |
| 167 | // nothing. |
| 168 | return Value{Kind: KindErr, Err: ErrValue} |
| 169 | case *Unary: |
| 170 | return evalUnary(t, env) |
| 171 | case *Binary: |
| 172 | return evalBinary(t, env) |
| 173 | case *Call: |
| 174 | return evalCall(t, env) |
| 175 | } |
| 176 | return Value{Kind: KindErr, Err: ErrValue} |
| 177 | } |
| 178 | |
| 179 | // evalUnary handles the only unary operator the parser produces: negation |
| 180 | // (see parse.go's parseUnary and translate.go's Render doc comment). |
| 181 | func evalUnary(t *Unary, env Env) Value { |
| 182 | x := Eval(t.X, env) |
| 183 | if x.Kind == KindErr { |
| 184 | return x |
| 185 | } |
| 186 | num, errKind := toNumber(x) |
| 187 | if errKind != ErrNone { |
| 188 | return Value{Kind: KindErr, Err: errKind} |
| 189 | } |
| 190 | return Value{Kind: KindNum, Num: -num} |
| 191 | } |
| 192 | |
amadan