| 1 | package calc |
| 2 | |
| 3 | import "strconv" |
| 4 | |
| 5 | // Translate offsets every relative reference in n by (dRow, dCol) and |
| 6 | // returns a new tree. Absolute components are untouched — that is the whole |
| 7 | // meaning of the dollar sign. |
| 8 | // |
| 9 | // This is the pass stable row and column identity does NOT remove. Ids make |
| 10 | // insert and delete free; copy and fill are positional by definition, so the |
| 11 | // offset has to be applied at paste time. See spec section 4.2. |
| 12 | func Translate(n Node, dRow, dCol int) Node { |
| 13 | switch t := n.(type) { |
| 14 | case *Ref: |
| 15 | out := *t |
| 16 | if !out.AbsRow { |
| 17 | out.RowPos += dRow |
| 18 | } |
| 19 | if !out.AbsCol { |
| 20 | out.ColPos += dCol |
| 21 | } |
| 22 | return &out |
| 23 | case *Range: |
| 24 | return &Range{ |
| 25 | From: Translate(t.From, dRow, dCol).(*Ref), |
| 26 | To: Translate(t.To, dRow, dCol).(*Ref), |
| 27 | } |
| 28 | case *Binary: |
| 29 | return &Binary{Op: t.Op, |
| 30 | Left: Translate(t.Left, dRow, dCol), |
| 31 | Right: Translate(t.Right, dRow, dCol)} |
| 32 | case *Unary: |
| 33 | return &Unary{Op: t.Op, X: Translate(t.X, dRow, dCol)} |
| 34 | case *Call: |
| 35 | args := make([]Node, len(t.Args)) |
| 36 | for i, a := range t.Args { |
| 37 | args[i] = Translate(a, dRow, dCol) |
| 38 | } |
| 39 | return &Call{Name: t.Name, Args: args} |
| 40 | default: |
| 41 | return n // Num, Str, Bool have no references |
| 42 | } |
| 43 | } |
| 44 | |
| 45 | // TranslateChecked is Translate plus the bounds check its callers cannot |
| 46 | // perform afterwards, and the reason it exists is that Render is happy to |
| 47 | // render a reference that does not exist. |
| 48 | // |
| 49 | // A relative reference can be offset off the top or the left of the grid: |
| 50 | // =A1 copied one column left has nowhere to point, and Excel writes #REF! |
| 51 | // there. Ours did something worse. ColLabel(-1) returns the EMPTY STRING |
| 52 | // and RowPos+1 is 0, so Translate followed by Render turned `=A1` into `=1` |
| 53 | // — a formula replaced by the number one, which reads as a value somebody |
| 54 | // typed and is the quiet kind of wrong nothing downstream can detect. |
| 55 | // |
| 56 | // So the check belongs beside the translation rather than at the call site: |
| 57 | // the caller has the source text and the offset, not the tree, and by the |
| 58 | // time it has a string again the evidence is gone. |
| 59 | // |
| 60 | // ok is false if ANY reference landed off-grid, including one nested in a |
| 61 | // range or a call's argument. The tree is still returned, for a caller that |
| 62 | // wants to report which part failed; nothing should render it. |
| 63 | func TranslateChecked(n Node, dRow, dCol int) (Node, bool) { |
| 64 | out := Translate(n, dRow, dCol) |
| 65 | return out, onGrid(out) |
| 66 | } |
| 67 | |
| 68 | // maxSheetRows and maxSheetCols are the spreadsheet grid's own extent — |
| 69 | // 1,048,576 rows and 16,384 columns (XFD), which is what Excel and |
| 70 | // LibreOffice both stop at and what XLSX can represent. |
| 71 | // |
| 72 | // They are here rather than in the sheets package because they are a |
| 73 | // property of the FORMAT, not of this deployment's window: a formula |
| 74 | // translated past XFD is not a reference we happen not to store, it is |
| 75 | // one that cannot be written down. Excel answers #REF! and so must we. |
| 76 | const ( |
| 77 | maxSheetRows = 1 << 20 |
| 78 | maxSheetCols = 16384 |
| 79 | ) |
| 80 | |
| 81 | // onGrid reports whether every reference in n lands inside the |
| 82 | // spreadsheet grid — not merely at a non-negative position. It walks the same shapes Translate does, and deliberately in the |
| 83 | // same order, so a node type added to one and not the other is a compile |
| 84 | // error in Translate and a silently unchecked branch here — which is why |
| 85 | // the default case returns true only for the leaf types that hold no |
| 86 | // reference at all. |
| 87 | func onGrid(n Node) bool { |
| 88 | switch t := n.(type) { |
| 89 | case *Ref: |
| 90 | // Both ends. The first version checked only >= 0, so copying |
| 91 | // =XFD1 one column right rendered =XFE1 — a column label the |
| 92 | // parser will happily read back and no spreadsheet can hold. |
| 93 | // Caught by the branch review. |
| 94 | return t.RowPos >= 0 && t.ColPos >= 0 && |
| 95 | t.RowPos < maxSheetRows && t.ColPos < maxSheetCols |
| 96 | case *Range: |
| 97 | return onGrid(t.From) && onGrid(t.To) |
| 98 | case *Binary: |
| 99 | return onGrid(t.Left) && onGrid(t.Right) |
| 100 | case *Unary: |
| 101 | return onGrid(t.X) |
| 102 | case *Call: |
| 103 | for _, a := range t.Args { |
| 104 | if !onGrid(a) { |
| 105 | return false |
| 106 | } |
| 107 | } |
| 108 | return true |
| 109 | default: |
| 110 | return true // Num, Str, Bool have no references |
| 111 | } |
| 112 | } |
| 113 | |
| 114 | // Render is the inverse of Parse for the node shapes Parse can produce: |
| 115 | // numbers, strings (re-quoted with `"` doubled), booleans, references and |
| 116 | // ranges (with both absolute markers preserved in position), unary minus, |
| 117 | // binary operators, and upper-cased function calls. It does not reproduce |
| 118 | // the source's original whitespace or its exact parenthesisation — a |
| 119 | // redundant paren the source didn't need is never replayed — but for every |
| 120 | // tree Parse can produce, Parse(Render(n)) reproduces a tree equal to n: |
| 121 | // Render inserts parentheses wherever precedence or associativity would |
| 122 | // otherwise regroup the expression, the mirror of the precedence-climbing |
| 123 | // parser above. This is also what the formula bar shows, so both |
| 124 | // guarantees matter beyond the tests: a Render that dropped a "$" would |
| 125 | // silently turn an absolute reference into a relative one the next time it |
| 126 | // was copied, and a Render that dropped a needed paren would silently |
| 127 | // change the value a cell computes. |
| 128 | func Render(n Node) string { |
| 129 | switch t := n.(type) { |
| 130 | case *Num: |
| 131 | return strconv.FormatFloat(t.V, 'g', -1, 64) |
| 132 | case *Str: |
| 133 | return `"` + quoteStr(t.V) + `"` |
| 134 | case *Bool: |
| 135 | if t.V { |
| 136 | return "TRUE" |
| 137 | } |
| 138 | return "FALSE" |
| 139 | case *Ref: |
| 140 | return renderRef(t) |
| 141 | case *Range: |
| 142 | return renderRef(t.From) + ":" + renderRef(t.To) |
| 143 | case *Unary: |
| 144 | return t.Op + renderOperand(t.X, precUnary, false) |
| 145 | case *Binary: |
| 146 | p := binaryPrec(t.Op) |
| 147 | return renderOperand(t.Left, p, false) + t.Op + renderOperand(t.Right, p, true) |
| 148 | case *Call: |
| 149 | args := make([]string, len(t.Args)) |
| 150 | for i, a := range t.Args { |
| 151 | args[i] = Render(a) |
| 152 | } |
| 153 | return t.Name + "(" + joinComma(args) + ")" |
| 154 | default: |
| 155 | return "" |
| 156 | } |
| 157 | } |
| 158 | |
| 159 | // Precedence levels, loosest to tightest, matching Parse's grammar |
| 160 | // (comparison, concat, additive, term, power, then unary — see the |
| 161 | // precedence note on Parse). Atoms (numbers, strings, refs, ranges, |
| 162 | // calls) never need parenthesising as anyone's child, so they sort above |
| 163 | // even unary. |
| 164 | const ( |
| 165 | precComparison = iota + 1 |
| 166 | precConcat |
| 167 | precAdditive |
| 168 | precTerm |
| 169 | precPower |
| 170 | precUnary |
| 171 | precAtom |
| 172 | ) |
| 173 | |
| 174 | // binaryPrec maps a Binary's operator to its precedence level. |
| 175 | func binaryPrec(op string) int { |
| 176 | switch op { |
| 177 | case "=", "<>", "<", "<=", ">", ">=": |
| 178 | return precComparison |
| 179 | case "&": |
| 180 | return precConcat |
| 181 | case "+", "-": |
| 182 | return precAdditive |
| 183 | case "*", "/": |
| 184 | return precTerm |
| 185 | case "^": |
| 186 | return precPower |
| 187 | default: |
| 188 | return precAtom |
| 189 | } |
| 190 | } |
| 191 | |
| 192 | // nodePrec reports the precedence level a node binds at when it appears as |
| 193 | // someone else's operand: a Binary's by its operator, a Unary's fixed at |
| 194 | // precUnary (it parses tighter than any binary operator but looser than |
| 195 | // nothing — see the -2^2 = 4 note on Parse), everything else at precAtom. |
| 196 | func nodePrec(n Node) int { |
| 197 | switch t := n.(type) { |
| 198 | case *Binary: |
| 199 | return binaryPrec(t.Op) |
| 200 | case *Unary: |
| 201 | return precUnary |
| 202 | default: |
| 203 | return precAtom |
| 204 | } |
| 205 | } |
| 206 | |
| 207 | // renderOperand renders n as a child sitting in a slot of precedence |
| 208 | // parentPrec, adding parentheses exactly when omitting them would let the |
| 209 | // child regroup under re-parsing: when it binds strictly looser than the |
| 210 | // parent, or when it binds at exactly the parent's precedence on the side |
| 211 | // associativity doesn't protect (see samePrecedenceNeedsParens). |
| 212 | func renderOperand(n Node, parentPrec int, isRight bool) string { |
| 213 | cp := nodePrec(n) |
| 214 | needParens := cp < parentPrec || (cp == parentPrec && samePrecedenceNeedsParens(parentPrec, isRight)) |
| 215 | s := Render(n) |
| 216 | if needParens { |
| 217 | return "(" + s + ")" |
| 218 | } |
| 219 | return s |
| 220 | } |
| 221 | |
| 222 | // samePrecedenceNeedsParens decides, for a child at exactly its parent's |
| 223 | // precedence, whether it still needs parens to reparse into the same tree. |
| 224 | // Every level Parse builds is left-associative except ^, so a |
| 225 | // left-associative parent needs parens around a same-precedence RIGHT |
| 226 | // child (8-(3-1) must keep its parens: "8-3-1" reparses as (8-3)-1), while |
| 227 | // the right-associative power needs them around a same-precedence LEFT |
| 228 | // child instead ((2^3)^2 must keep its parens: "2^3^2" reparses as |
| 229 | // 2^(3^2)). The unary slot (parentPrec == precUnary, always called with |
| 230 | // isRight == false) falls into the left-associative branch, which is also |
| 231 | // the answer it wants: chained unary minus ("--A1") never needs parens. |
| 232 | func samePrecedenceNeedsParens(parentPrec int, isRight bool) bool { |
| 233 | if parentPrec == precPower { |
| 234 | return !isRight |
| 235 | } |
| 236 | return isRight |
| 237 | } |
| 238 | |
| 239 | // renderRef reproduces a single reference's A1 text, including whichever |
| 240 | // dollar signs are set: neither ($A1 has one, A$1 has the other, $A$1 has |
| 241 | // both), matching how decodeRef reads them back. |
| 242 | func renderRef(r *Ref) string { |
| 243 | s := "" |
| 244 | if r.AbsCol { |
| 245 | s += "$" |
| 246 | } |
| 247 | s += ColLabel(r.ColPos) |
| 248 | if r.AbsRow { |
| 249 | s += "$" |
| 250 | } |
| 251 | s += strconv.Itoa(r.RowPos + 1) |
| 252 | return s |
| 253 | } |
| 254 | |
| 255 | // quoteStr doubles embedded double quotes, the inverse of lexString's |
| 256 | // unescaping. |
| 257 | func quoteStr(s string) string { |
| 258 | out := make([]byte, 0, len(s)) |
| 259 | for i := 0; i < len(s); i++ { |
| 260 | if s[i] == '"' { |
| 261 | out = append(out, '"', '"') |
| 262 | continue |
| 263 | } |
| 264 | out = append(out, s[i]) |
| 265 | } |
| 266 | return string(out) |
| 267 | } |
| 268 | |
| 269 | func joinComma(parts []string) string { |
| 270 | out := "" |
| 271 | for i, p := range parts { |
| 272 | if i > 0 { |
| 273 | out += "," |
| 274 | } |
| 275 | out += p |
| 276 | } |
| 277 | return out |
| 278 | } |
| 279 | |
amadan