1package sheet23import (4 "slices"56 "src.rest/cat/012/internal/formula"7)89// Cycles are found from the formulas as written, as Sheets and Excel10// find them, before a recalculation evaluates anything: a formula is11// part of a cycle when what it references (cells, ranges, names, tables,12// regions, other sheets) leads back to it, whether or not evaluating it13// reads that far: an IF branch not taken, a range read that stops at an14// error, INDEX reading one cell of its range. Evaluation meeting a cell15// it is evaluating finds the cycles it walks (evaluate.go), but only16// those, so what the cells of a cycle it didn't walk showed depended on17// the order they were evaluated in. Every cell of a cycle is #REF!.18//19// Only the formulas to recalculate are looked at: a cycle through one of20// them runs through formulas that read it, which recalculate too.21//22// The graph's nodes are those formulas, each leading to the formulas it23// references. A range leads to the formulas in it through a segment tree24// over each column's formulas, whose nodes lead to their halves, so a25// range costs the logarithm of the formulas in its columns rather than26// their number, and a column of running totals over computed cells27// stays linear. Tarjan's algorithm finds the strongly connected28// components; the formulas of a component with more than one node, or29// that reference themselves, are a cycle's. The graph's buffers are kept30// for the next recalculation, up to maxCycleKeep formulas.3132// maxCycleKeep is the most formulas whose graph's buffers are kept.33const maxCycleKeep = 1 << 163435// cycleGraph is the graph of the formulas to recalculate: formulas are36// nodes 0 to formulas-1, in sheet order and by column and row within a37// sheet, and segment nodes follow. The edges leaving node v are38// edges[start[v]:start[v+1]].39type cycleGraph struct {40 w *Workbook41 formulas int3242 sheets []cycleSheet43 keys []uint64 // each sheet's formulas' keys, sorted44 cols []cycleCol // each sheet's columns holding formulas, in order45 last *cycleSheet46 start []int3247 edges []int3248 tarjan49}5051// cycleSheet is a sheet's formulas in the graph: keys[from:to] (column in52// the high half, row in the low), which are nodes from to to, and its53// columns, cols[col0:col1].54type cycleSheet struct {55 s *Sheet56 from, to int3257 col0, col1 int3258}5960// cycleCol is a column's formulas: keys[from:from+m], and the node of its61// segment tree's first inner node (the tree has m-1).62type cycleCol struct {63 col int64 from, m int3265 seg int3266}6768func cycleKey(a Addr) uint64 { return uint64(a.Col)<<32 | uint64(uint32(a.Row)) }6970func keyAddr(k uint64) Addr { return Addr{Col: int(k >> 32), Row: int(uint32(k))} }7172// findCycles returns the formulas to recalculate, dirty in each sheet's73// calc, that are part of a cycle, or nil when none is.74func (w *Workbook) findCycles() map[loc]bool {75 g := w.cycles76 if g == nil {77 g = &cycleGraph{w: w}78 }79 var cycle map[loc]bool80 if g.collect() {81 g.link()82 cycle = g.components()83 }84 g.reset()85 w.cycles = nil86 if cap(g.keys) <= maxCycleKeep {87 w.cycles = g88 }89 return cycle90}9192// reset empties the graph for the next recalculation, keeping its93// buffers.94func (g *cycleGraph) reset() {95 clear(g.sheets)96 g.sheets, g.keys, g.cols, g.start, g.edges = g.sheets[:0], g.keys[:0], g.cols[:0], g.start[:0], g.edges[:0]97 g.formulas, g.last = 0, nil98 g.tarjan = tarjan{index: g.index[:0], low: g.low[:0], on: g.on[:0], stack: g.stack[:0], path: g.path[:0], next: g.next[:0]}99}100101// collect gathers the formulas to recalculate, reporting whether a102// cycle may run through them: not when there are none, or when each103// references only cells before it, row by row, as a column of running104// totals or a chain down a column does, since then no reference leads105// back.106func (g *cycleGraph) collect() bool {107 back := true108 for _, s := range g.w.sheets {109 from := len(g.keys)110 for a, st := range s.calc {111 if c := s.cells.richAt(a); st == dirty && c != nil && c.expr != nil && !c.derived && !c.spilled && readsCells(c) {112 g.keys = append(g.keys, cycleKey(a))113 back = back && readsBefore(c, a)114 }115 }116 if len(g.keys) > from {117 g.sheets = append(g.sheets, cycleSheet{s: s, from: int32(from), to: int32(len(g.keys))})118 }119 }120 g.formulas = int32(len(g.keys))121 if back {122 return false123 }124 for _, cs := range g.sheets {125 slices.Sort(g.keys[cs.from:cs.to])126 }127 seg := g.formulas128 for i := range g.sheets {129 cs := &g.sheets[i]130 cs.col0 = int32(len(g.cols))131 for j := cs.from; j < cs.to; j++ {132 col := int(g.keys[j] >> 32)133 if len(g.cols) == int(cs.col0) || g.cols[len(g.cols)-1].col != col {134 g.cols = append(g.cols, cycleCol{col: col, from: j})135 }136 g.cols[len(g.cols)-1].m++137 }138 cs.col1 = int32(len(g.cols))139 for c := cs.col0; c < cs.col1; c++ {140 g.cols[c].seg = seg141 seg += max(g.cols[c].m-1, 0)142 }143 }144 g.start = slices.Grow(g.start, int(seg)+1)[:seg+1]145 return true146}147148// readsBefore reports whether the formula c, at a, references only149// cells of its own sheet before a, row by row.150func readsBefore(c *Cell, a Addr) bool {151 if len(c.xrefs) > 0 || len(c.names) > 0 {152 return false153 }154 for _, r := range c.refs {155 if !before(r, a) {156 return false157 }158 }159 for _, r := range c.ranges {160 if !before(r.To, a) {161 return false162 }163 }164 return true165}166167// readsCells reports whether the formula c references anything.168func readsCells(c *Cell) bool {169 return len(c.refs) > 0 || len(c.ranges) > 0 || len(c.xrefs) > 0 || len(c.names) > 0170}171172// link writes the edges: each formula's to what it references, then173// each segment node's to its halves.174func (g *cycleGraph) link() {175 for _, cs := range g.sheets {176 for j := cs.from; j < cs.to; j++ {177 g.start[j] = int32(len(g.edges))178 g.references(cs.s, keyAddr(g.keys[j]))179 }180 }181 v := g.formulas182 for _, col := range g.cols {183 for p := int32(1); p < col.m; p++ {184 g.start[v] = int32(len(g.edges))185 g.edges = append(g.edges, col.node(2*p), col.node(2*p+1))186 v++187 }188 }189 g.start[v] = int32(len(g.edges))190}191192// node is the node at position p of the column's segment tree: an inner193// node below m, a formula from m on.194func (col cycleCol) node(p int32) int32 {195 if p >= col.m {196 return col.from + p - col.m197 }198 return col.seg + p - 1199}200201// references adds the edges from the formula at a on s to the formulas202// it references. One naming a name, a table or a region is bound first,203// as evaluating it is, so a table's row (Sales[@Price]) leads to that204// row alone.205func (g *cycleGraph) references(s *Sheet, a Addr) {206 c := s.cells.richAt(a)207 if len(c.names) > 0 {208 formula.WalkRefs(s.bound(a, c),209 func(sheet string, r Addr) { g.cell(g.w.resolve(s, sheet), r) },210 func(sheet string, r Rect) { g.rect(g.w.resolve(s, sheet), r) })211 return212 }213 for _, r := range c.refs {214 g.cell(s, r)215 }216 for _, r := range c.ranges {217 g.rect(s, r)218 }219 for _, x := range c.xrefs {220 g.rect(g.w.byKey[x.key], x.r)221 }222}223224// sheet is t's formulas in the graph, if it has any.225func (g *cycleGraph) sheet(t *Sheet) (*cycleSheet, bool) {226 if g.last != nil && g.last.s == t {227 return g.last, true228 }229 for i := range g.sheets {230 if g.sheets[i].s == t {231 g.last = &g.sheets[i]232 return g.last, true233 }234 }235 return nil, false236}237238// cell adds an edge to the formula at a on t, if it is one.239func (g *cycleGraph) cell(t *Sheet, a Addr) {240 if cs, ok := g.sheet(t); ok {241 if i, found := slices.BinarySearch(g.keys[cs.from:cs.to], cycleKey(a)); found {242 g.edges = append(g.edges, cs.from+int32(i))243 }244 }245}246247// rect adds edges to the formulas of r on t: in each of its columns, to248// the fewest segment nodes that cover them.249func (g *cycleGraph) rect(t *Sheet, r Rect) {250 cs, ok := g.sheet(t)251 switch {252 case !ok:253 return254 case r.From == r.To:255 g.cell(t, r.From)256 return257 }258 cols := g.cols[cs.col0:cs.col1]259 c0, _ := slices.BinarySearchFunc(cols, r.From.Col, func(c cycleCol, col int) int { return c.col - col })260 for _, col := range cols[c0:] {261 if col.col > r.To.Col {262 break263 }264 keys := g.keys[col.from : col.from+col.m]265 lo, _ := slices.BinarySearch(keys, cycleKey(Addr{Col: col.col, Row: r.From.Row}))266 hi, _ := slices.BinarySearch(keys, cycleKey(Addr{Col: col.col, Row: r.To.Row})+1)267 for lp, hp := int32(lo)+col.m, int32(hi)+col.m; lp < hp; lp, hp = lp/2, hp/2 {268 if lp&1 == 1 {269 g.edges = append(g.edges, col.node(lp))270 lp++271 }272 if hp&1 == 1 {273 hp--274 g.edges = append(g.edges, col.node(hp))275 }276 }277 }278}279280// components runs Tarjan's algorithm from each formula, without281// recursion, and returns the formulas in cycles.282func (g *cycleGraph) components() map[loc]bool {283 n := len(g.start) - 1284 g.index = slices.Grow(g.index, n)[:n]285 g.low = slices.Grow(g.low, n)[:n]286 g.on = slices.Grow(g.on, n)[:n]287 clear(g.index)288 for v := range g.formulas {289 if g.index[v] == 0 {290 g.visit(v)291 }292 }293 return g.cycle294}295296// tarjan is the state of Tarjan's algorithm: each node's index, from 1297// (0 while unvisited), and lowest index reached, the nodes on the stack,298// the path being followed, with the next edge of each, and the formulas299// found in cycles.300type tarjan struct {301 index, low []int32302 on []bool303 stack, path []int32304 next []int32305 count int32306 cycle map[loc]bool307}308309func (g *cycleGraph) push(v int32) {310 g.count++311 g.index[v], g.low[v] = g.count, g.count312 g.stack = append(g.stack, v)313 g.on[v] = true314 g.path = append(g.path, v)315 g.next = append(g.next, g.start[v])316}317318func (g *cycleGraph) visit(root int32) {319 g.push(root)320 for len(g.path) > 0 {321 top := len(g.path) - 1322 v := g.path[top]323 if e := g.next[top]; e < g.start[v+1] {324 g.next[top]++325 switch u := g.edges[e]; {326 case g.index[u] == 0:327 g.push(u)328 case g.on[u]:329 g.low[v] = min(g.low[v], g.index[u])330 }331 continue332 }333 g.path, g.next = g.path[:top], g.next[:top]334 if top > 0 {335 p := g.path[top-1]336 g.low[p] = min(g.low[p], g.low[v])337 }338 if g.low[v] == g.index[v] {339 g.pop(v)340 }341 }342}343344// pop takes the component rooted at v off the stack, keeping its345// formulas when it is a cycle.346func (g *cycleGraph) pop(v int32) {347 i := len(g.stack) - 1348 for g.stack[i] != v {349 i--350 }351 comp := g.stack[i:]352 g.stack = g.stack[:i]353 for _, u := range comp {354 g.on[u] = false355 }356 if len(comp) == 1 && !slices.Contains(g.edges[g.start[v]:g.start[v+1]], v) {357 return358 }359 if g.cycle == nil {360 g.cycle = map[loc]bool{}361 }362 for _, u := range comp {363 if u < g.formulas {364 g.cycle[g.loc(u)] = true365 }366 }367}368369// loc is the cell of the formula node v.370func (g *cycleGraph) loc(v int32) loc {371 for _, cs := range g.sheets {372 if v < cs.to {373 return loc{cs.s, keyAddr(g.keys[v])}374 }375 }376 panic("sheet: no formula node")377}