1package sheet23import "slices"45// spillsIntoItself finds whether the array at a would spill over a cell6// its formula reads, other than a itself, directly or through other7// formulas and the arrays they spill: spilling would change what8// computed it, a circular dependency, whose values would depend on the9// order cells were computed in. It returns why, or "", and the other10// arrays on the way, which are part of the cycle and give way too.11//12// It walks the formulas that read the area's cells, and those that read13// them or what they spill, looking for the anchor: the cells a14// recalculation after the spill would visit anyway. An array blocked by15// a cycle counts as spilling over the cells it needs, so the arrays of16// a cycle stay blocked together whichever was computed first.17//18// A region whose table is in area gives way to the array19// (regionsGiveWay), so what reads it by name reads #REF! once the array20// spills, whatever the array holds: the walk doesn't follow it, or the21// array would be blocked or not by whether the region's rows arrived22// before it spilled. A formula reading the table's cells, though, leads23// the walk from each of them, those outside area too: spilling empties24// them, the anchor showing #REF!, which may make the array smaller and25// free the region, spilling again once it's sent its rows, without26// end. The table is the one shown or, blocked by arrays alone, the one27// it needs, so the array is blocked either way (regionMoved has it28// checked again).29func (s *Sheet) spillsIntoItself(a Addr, area Rect) (string, []loc) {30 if area.From == area.To {31 return "", nil32 }33 look := s.wb.readerLookup()34 look.named = slices.DeleteFunc(look.named, func(nu namedUsers) bool { return nu.region && nu.s == s && overlaps(nu.r, area) })35 w := &spillWalk{look: look, target: loc{s, a}, seen: map[loc]bool{{s, a}: true}, parent: -1}36 if w.cells(s, area, a, loc{}, true) {37 return circular(w.origin), nil38 }39 for _, r := range s.regions.list {40 if t, ok := s.heldByArrays(r); ok && overlaps(t, area) && w.cells(s, t, a, loc{}, true) {41 return "Circular dependency: the array would spill over " + r.Name + "'s table, whose cells its formula reads", nil42 }43 }44 for i := 0; i < len(w.queue); i++ {45 u := w.queue[i]46 w.origin, w.parent = w.nodes[i].from, i47 // An array's cells first, so a cycle through them is found as48 // one, and the array blocked with it, rather than through the49 // anchor alone.50 if sp := u.s.spills[u.a]; sp != nil && sp.walked() {51 w.cells(u.s, sp.area, u.a, u, false)52 }53 if !w.found {54 w.look.each(u, w.visitVia(loc{}))55 }56 if w.found {57 return circular(w.origin), w.arrays()58 }59 }60 return "", nil61}6263// spillCycle is spillsIntoItself for the array at a, whose spill was64// old, holding it blocked once a cycle has blocked it twice in the65// recalculation, freed between. Arrays whose sizes follow what they read66// can go around a cycle without settling: blocked, one shows #REF!,67// which the other reads, and its smaller array frees the first, which68// spills and blocks it again. Held, they end blocked together, as they69// are when the cycle is found in one go, whichever came first.70func (s *Sheet) spillCycle(a Addr, area Rect, old *spill) (string, []loc) {71 l, w := loc{s, a}, s.wb72 why, cycle := s.spillsIntoItself(a, area)73 blocked := old != nil && old.circular74 checked := w.checkedCycle(l)75 switch {76 case why != "" && (!blocked || !checked):77 w.noteCycle(l)78 case why == "" && blocked && w.spillCycles[l] >= 2:79 why = old.why80 }81 return why, cycle82}8384// checkedCycle reports whether the array at l was checked for a cycle85// already in the recalculation, and notes that it has been.86func (w *Workbook) checkedCycle(l loc) bool {87 if _, ok := w.spillCycles[l]; ok {88 return true89 }90 if w.spillCycles == nil {91 w.spillCycles = map[loc]int{}92 }93 w.spillCycles[l] = 094 return false95}9697// cycleMoved reports whether the arrays are to be checked again, the98// array whose spill was old found blocked by a cycle (circ) or not: a99// cycle through arrays began or ended at it, which may take in or let go100// of others, or it is blocked still, the first time in the101// recalculation: something changed on the way around its cycle, as a102// formula typed reading another array's cells, which may have closed a103// cycle through another array, which isn't computed again for it.104func (w *Workbook) cycleMoved(circ bool, old *spill) bool {105 switch was := old != nil && old.circular; {106 case circ != was:107 return true108 case circ && !w.spillRechecked:109 w.spillRechecked = true110 return true111 }112 return false113}114115// blockedMoved reports whether the arrays are to be checked again, an116// array whose spill was old found blocked over area by something other117// than a cycle: counted as spilling over the cells it needs (walked), it118// may close or open a cycle through arrays that read them, when it's119// blocked over other cells, or blocked still, the first time in the120// recalculation: a formula on the way around a cycle through it may121// have changed, which the others aren't computed again for, as in122// cycleMoved.123func (w *Workbook) blockedMoved(old *spill, area Rect) bool {124 switch {125 case old == nil || old.why == "" || old.area != area:126 return true127 case !w.spillRechecked:128 w.spillRechecked = true129 return true130 }131 return false132}133134// noteCycle counts the array at l found blocked by a cycle, from spilling135// or not, in the recalculation.136func (w *Workbook) noteCycle(l loc) {137 if w.spillCycles == nil {138 w.spillCycles = map[loc]int{}139 }140 w.spillCycles[l]++141}142143// spillWalk is the state of spillsIntoItself: the formulas reached, in144// the order found, each with how it was reached.145type spillWalk struct {146 look readerLookup147 target loc148 seen map[loc]bool149 queue []loc150 nodes []walkNode151 origin Addr // the cell of the area the walk is on152 parent int // the node the walk is on, -1 at the start153 via loc // the array whose cells the walk is on, if any154 found bool155 last int // the node the target was reached from156}157158// walkNode is how the walk reached a formula: from which cell of the159// area, from which node, and through the cells of which array.160type walkNode struct {161 from Addr162 parent int163 via loc164}165166// visitVia returns what the walk does with each formula it reaches167// through the cells of the array via (none when zero).168func (w *spillWalk) visitVia(via loc) func(loc) {169 w.via = via170 return w.visit171}172173func (w *spillWalk) visit(u loc) {174 switch {175 case w.found:176 case u == w.target:177 w.found, w.last = true, len(w.nodes)178 w.nodes = append(w.nodes, walkNode{w.origin, w.parent, w.via})179 case !w.seen[u]:180 w.seen[u] = true181 w.queue = append(w.queue, u)182 w.nodes = append(w.nodes, walkNode{w.origin, w.parent, w.via})183 }184}185186// cells visits the formulas reading the cells of area on s other than187// skip, the cells of the array via, and reports whether one leads to188// the target. At the start, each cell is its own origin.189func (w *spillWalk) cells(s *Sheet, area Rect, skip Addr, via loc, start bool) bool {190 visit := w.visitVia(via)191 for row := area.From.Row; row <= area.To.Row; row++ {192 for col := area.From.Col; col <= area.To.Col; col++ {193 at := Addr{Col: col, Row: row}194 if at == skip {195 continue196 }197 if start {198 w.origin = at199 }200 if w.look.each(loc{s, at}, visit); w.found {201 return true202 }203 }204 }205 return false206}207208// arrays are the arrays whose cells the path to the target went209// through.210func (w *spillWalk) arrays() []loc {211 var out []loc212 for i := w.last; i >= 0; i = w.nodes[i].parent {213 if v := w.nodes[i].via; v.s != nil {214 out = append(out, v)215 }216 }217 return out218}219220func circular(at Addr) string {221 return "Circular dependency: the array would spill into " + at.String() + ", which its formula reads"222}223224// recheckArrays returns every array's anchor but l's, spilling or225// blocked by a cycle, to compute again: a cycle through arrays that226// begins or ends at l may take in or let go of others, which checking227// each again finds, whichever order they're in.228func (w *Workbook) recheckArrays(l loc) []loc {229 var out []loc230 for _, s := range w.sheets {231 for b, sp := range s.spills {232 if (loc{s, b}) != l && (sp.why == "" || sp.circular) {233 sp.stale = true234 out = append(out, loc{s, b})235 }236 }237 }238 return out239}240241// recheckCircular returns the anchors of the arrays blocked by a cycle,242// to compute again, when an array stops spilling or spills over other243// cells: the cycle may have gone through its cells, and the arrays244// found it blocked in the same pass, before it changed, which nothing245// they read may tell them.246func (w *Workbook) recheckCircular() []loc {247 if w.circArrays <= 0 {248 return nil249 }250 var out []loc251 for _, s := range w.sheets {252 for b, sp := range s.spills {253 if sp.circular {254 sp.stale = true255 out = append(out, loc{s, b})256 }257 }258 }259 return out260}261262// forgetSpill drops the anchor at a's spill for good, its formula263// computing one value or none, returning the cells that changed. When264// blocked, it counted as spilling over the cells it needed (walked), so265// the arrays blocked by a cycle are checked again.266func (s *Sheet) forgetSpill(a Addr) []loc {267 old := s.spills[a]268 changed := s.dropSpill(a)269 if old != nil && old.why != "" {270 changed = append(changed, s.wb.recheckCircular()...)271 }272 return changed273}274275// blockCircular blocks the arrays at l, part of a cycle with another,276// and returns the cells that changed, with the anchors, to compute277// again, finding the cycle themselves.278func blockCircular(arrays []loc) []loc {279 var changed []loc280 for _, l := range arrays {281 sp := l.s.spills[l.a]282 if sp == nil || sp.circular {283 continue284 }285 area := sp.area286 changed = append(changed, l.s.dropSpill(l.a)...)287 l.s.setSpill(l.a, &spill{area: area, why: "Circular dependency through another array", circular: true})288 l.s.wb.noteCycle(l)289 changed = append(changed, l)290 }291 return changed292}293294// walked reports whether spillsIntoItself follows the cells of the295// array: spilled, or blocked, over the cells it needs, what it would296// spill over given room. A blocked array whose size follows what it297// reads may be blocked or free by whether another spills into its298// inputs, and that other by whether it spills: counted as spilling,299// the two are blocked together, as when the cycle is found in one go,300// rather than by the order they were computed in. The cells of an array301// too big for max-cells aren't walked.302func (sp *spill) walked() bool {303 if sp.why == "" || sp.circular {304 return true305 }306 return (sp.area.To.Row-sp.area.From.Row+1)*(sp.area.To.Col-sp.area.From.Col+1) <= MaxCells()307}