1package sheet23import (4 "cmp"5 "errors"6 "fmt"7 "maps"8 "slices"910 "src.rest/cat/012/internal/functions"11)1213// Spills, as Sheets' array results: a formula computing an array (its14// anchor) shows the first value and spills the rest into the cells to15// its right and below. Those are spilled cells, derived like a pivot's16// results: owned by the anchor, rewritten outside the undo history17// whenever it recomputes, refused by Set, constants to formulas reading18// them, values to copies and exports, and never saved (the file keeps19// the anchor's formula). Formatting a spilled cell keeps the formatting20// and the anchor spills its value into it again.21//22// Spills are written after each evaluation pass: the formulas reading23// spilled cells that changed are then recalculated, which may spill24// again (a FILTER of a SORT), up to maxSpillPasses. When the cells an25// array needs aren't empty, the anchor shows #REF! and says which cell26// is in the way; changing that cell has the anchor try again.2728// A spilled cell's note, like its formatting, belongs to the cell: one29// that had a note before an array spilled into it keeps it, but SetNote30// refuses spilled cells, as it refuses a pivot's results.3132// spill is what an anchor spills, or would.33type spill struct {34 area Rect // the cells it covers, the anchor first; when blocked, those it needs35 why string // why the anchor shows #REF! instead, or ""36 // circular is set when it's blocked by a cycle through its cells37 // (spillblock.go).38 circular bool39 // arr and auto are the array written and its format, so the same40 // array computed again isn't written again, unless stale says a cell41 // of area changed since.42 arr *functions.Array43 auto Format44 stale bool45}4647// ErrSpillEdit is what typing into a spilled cell says: its value48// belongs to the formula that spilled it.49var ErrSpillEdit = errors.New("That cell holds part of an array result: edit the formula it spills from")5051// maxSpillPasses bounds the passes that spill arrays and recalculate what52// reads them, so arrays reading each other can't loop.53const maxSpillPasses = 645455// spillWork is the arrays computed in an evaluation pass, by anchor,56// with the value each anchor's formula computed.57type spillWork map[loc]pendingSpill5859type pendingSpill struct {60 arr *functions.Array // nil when the formula computed one value61 v Value // what the anchor showed formulas read meanwhile62 top Value // what the formula computed, the array's first value63}6465// noteSpill records what the formula of c, at a on s, computed (top,66// and arr, nil for one value), when it spills or did. An array blocked67// before keeps showing #REF! until spilling finds it free, so formulas68// reading it don't see it come and go while it stays blocked.69//70//go:noinline71func (w *Workbook) noteSpill(s *Sheet, a Addr, c *Cell, arr *functions.Array) {72 l, top := loc{s, a}, c.Value73 sp := s.spills[a]74 if arr == nil && sp == nil {75 return76 }77 if arr != nil && sp != nil && sp.why != "" {78 c.Value = ErrRef79 }80 if w.spillWork == nil {81 w.spillWork = spillWork{}82 }83 w.spillWork[l] = pendingSpill{arr, c.Value, top}84}8586// settleSpills writes the arrays evaluated, then recalculates what reads87// the cells that changed, until nothing spills anew. It returns the88// sheets whose pivots to refresh: stale, and those whose source a spill89// changed.90func (w *Workbook) settleSpills(stale []*Sheet) []*Sheet {91 defer func() { w.spillCycles, w.spillRechecked = nil, false }()92 for pass := 0; len(w.spillWork) > 0; pass++ {93 var changed, anchors []loc94 for _, l := range w.spillOrder() {95 cells, moved := l.s.applySpill(l.a, w.spillWork[l])96 changed = append(changed, cells...)97 if moved {98 anchors = append(anchors, l)99 }100 }101 w.spillWork = nil102 if len(changed) == 0 && len(anchors) == 0 {103 break104 }105 if pass == maxSpillPasses {106 w.Circular = true107 break108 }109 w.affectedBy(changed, anchors, false)110 for _, s := range w.stalePivots() {111 if !slices.Contains(stale, s) {112 stale = append(stale, s)113 }114 }115 w.evaluate()116 }117 return stale118}119120// spillOrder is the anchors of spillWork in the order they spill: by121// sheet, then row by row, so when two arrays need the same cells, the122// first one written in that order gets them.123func (w *Workbook) spillOrder() []loc {124 order := slices.Collect(maps.Keys(w.spillWork))125 slices.SortFunc(order, func(x, y loc) int {126 return cmp.Or(cmp.Compare(w.Index(x.s), w.Index(y.s)), cmp.Compare(x.a.Row, y.a.Row), cmp.Compare(x.a.Col, y.a.Col))127 })128 return order129}130131// applySpill writes what the anchor at a computed, returning the cells132// that changed and whether the anchor's own value did (it shows #REF!133// when blocked).134func (s *Sheet) applySpill(a Addr, p pendingSpill) ([]loc, bool) {135 c := s.cells.get(a)136 if c == nil || !c.IsFormula() || p.arr == nil {137 return s.forgetSpill(a), false138 }139 area, why, later := s.spillArea(a, p.arr)140 var cycle []loc141 circ := false142 old := s.spills[a]143 if why == "" {144 // Checked each time the anchor is computed: a formula typed since145 // it spilled may lead from its cells back to it.146 why, cycle = s.spillCycle(a, area, old)147 circ = why != ""148 }149 if why == "" && len(later) == 0 && old != nil && old.why == "" && !old.stale && old.auto == c.auto && sameArray(old.arr, p.arr) {150 return nil, false // written already, and nothing has changed in its way151 }152 var changed []loc153 if s.wb.cycleMoved(circ, old) {154 changed = s.wb.recheckArrays(loc{s, a})155 }156 if why != "" {157 if !circ && s.wb.blockedMoved(old, area) {158 changed = append(changed, s.wb.recheckArrays(loc{s, a})...)159 }160 changed = append(changed, s.dropSpill(a)...)161 s.setSpill(a, &spill{area: area, why: why, circular: circ})162 c.Value = ErrRef163 return append(changed, blockCircular(cycle)...), p.v != ErrRef164 }165 for _, b := range later {166 // b's array gives way, and b is computed again to find itself167 // blocked by this one.168 changed = append(append(changed, s.dropSpill(b)...), loc{s, b})169 }170 changed = append(changed, s.regionsGiveWay(area)...)171 if old != nil && old.why == "" {172 changed = append(changed, s.clearSpilled(old.area, area)...)173 }174 if old != nil && old.area != area {175 changed = append(changed, s.wb.recheckCircular()...)176 }177 s.setSpill(a, &spill{area: area, arr: p.arr, auto: c.auto})178 c.Value = p.top179 for r := range area.To.Row - a.Row + 1 {180 for col := range area.To.Col - a.Col + 1 {181 if r == 0 && col == 0 {182 continue183 }184 at := Addr{Col: a.Col + col, Row: a.Row + r}185 if s.writeSpilled(at, p.arr.At(r, col), c.auto) {186 changed = append(changed, loc{s, at})187 }188 }189 }190 return changed, p.v != p.top191}192193// spillArea is where the array computed at a goes, or why it can't: past194// the sheet's edge, past max-cells, or over a cell that isn't empty.195// Blank entries past the array's data aren't spilled, so a whole column196// read as an array spills what it holds.197//198// When two arrays need the same cells, the one whose anchor comes first,199// row by row, gets them, whichever spilled first: later lists the200// anchors whose arrays give way to this one. So what spills doesn't201// depend on the order formulas were typed or computed in, and a file202// opens as it was saved.203func (s *Sheet) spillArea(a Addr, arr *functions.Array) (area Rect, why string, later []Addr) {204 rows, cols := arr.Rows, arr.Cols205 if arr.Fill.Kind == Empty {206 rows, cols = min(rows, max(arr.DRows, 1)), min(cols, max(arr.DCols, 1))207 }208 area = Rect{From: a, To: Addr{Col: a.Col + cols - 1, Row: a.Row + rows - 1}}209 switch {210 case area.To.Row >= MaxRows || area.To.Col >= MaxCols:211 area.To = Addr{Col: min(area.To.Col, MaxCols-1), Row: min(area.To.Row, MaxRows-1)}212 return area, "Array result was not expanded because it would go past the edge of the sheet", nil213 case rows*cols > MaxCells():214 return area, fmt.Sprintf("Array result was not expanded because it would write more cells than max-cells allows (%d)", MaxCells()), nil215 }216 if ms := s.MergesIn(area); len(ms) > 0 {217 return area, "Array result was not expanded because it would overwrite merged cells in " + ms[0].String(), nil218 }219 if at, blocked := s.arraysInTheWay(a, area, &later); blocked {220 return area, "Array result was not expanded because it would overwrite data in " + at.String(), nil221 }222 old := s.spills[a]223 for at := range s.cells.anyKeysIn(area) {224 if at == a || !s.cells.filledAt(at) {225 continue226 }227 if s.cells.derivedAt(at) == slotSpill {228 if old != nil && old.why == "" && old.area.Contains(at) {229 continue230 }231 if _, ok := s.SpillAnchor(at); ok || s.regionCell(at) {232 continue // an array's, found above, or a region's, which gives way233 }234 }235 return area, "Array result was not expanded because it would overwrite data in " + at.String(), nil236 }237 return area, "", later238}239240// arraysInTheWay finds the other arrays spilled over area, where the241// array at a would go, blank cells of theirs included, as Sheets keeps242// an array's whole range: it reports a cell of one whose anchor comes243// before a, which blocks it, and adds to later those whose anchors come244// after.245func (s *Sheet) arraysInTheWay(a Addr, area Rect, later *[]Addr) (Addr, bool) {246 if n := len(s.spills); n == 0 || n == 1 && s.spills[a] != nil {247 return Addr{}, false248 }249 var at Addr250 blocked := false251 for row := area.From.Row; row <= area.To.Row && !blocked; row++ {252 for col := area.From.Col; col <= area.To.Col && !blocked; col++ {253 cell := Addr{Col: col, Row: row}254 s.spillAt.readers(cell, func(b Addr) {255 switch sp := s.spills[b]; {256 case b == a || sp == nil || sp.why != "" || blocked:257 case b.Row < a.Row || b.Row == a.Row && b.Col < a.Col:258 at, blocked = cell, true259 case !slices.Contains(*later, b):260 *later = append(*later, b)261 }262 })263 }264 }265 return at, blocked266}267268// writeSpilled makes the cell at a show v as a spilled cell, keeping its269// formatting and note, and reports whether it changed.270func (s *Sheet) writeSpilled(a Addr, v Value, auto Format) bool {271 was, l, kind := s.cells.derivedOf(a)272 spilled := kind == slotSpill273 if v.Kind == Empty {274 if !spilled {275 return false276 }277 s.setDerived(a, s.cells.get(a).leftover())278 return true279 }280 if spilled && was == v && l.auto == auto {281 return false // its input is its value's282 }283 if s.cells.setSpilled(a, v, auto) { // formatting kept, no formula to unlink284 s.version++285 return true286 }287 c := &Cell{Input: derivedInput(v), Value: v, Format: l.f, Style: l.st, auto: auto, spilled: true}288 if old := s.cells.richAt(a); old != nil {289 c.Note = old.Note290 }291 s.setDerived(a, c)292 return true293}294295// clearSpilled turns the spilled cells of area outside keep back into296// what they were before: blank, or formatting only.297func (s *Sheet) clearSpilled(area, keep Rect) []loc {298 var changed []loc299 var gone []Addr300 for at := range s.cells.anyKeysIn(area) {301 if s.cells.derivedAt(at) == slotSpill && !keep.Contains(at) && !s.regionCell(at) {302 gone = append(gone, at)303 }304 }305 for _, at := range gone {306 s.setDerived(at, s.cells.get(at).leftover())307 changed = append(changed, loc{s, at})308 }309 return append(changed, s.wakeBlocked(area, keep)...)310}311312// wakeBlocked returns the anchors of arrays blocked from spilling over313// the cells of area outside keep, which an array leaving them freed, to314// compute again, and marks the regions blocked there to be sent again.315// The cells it left may have been blank, which changing316// wouldn't find.317func (s *Sheet) wakeBlocked(area, keep Rect) []loc {318 var out []loc319 freed := func(r Rect) bool {320 x, ok := intersectRect(r, area)321 return ok && !(keep.Contains(x.From) && keep.Contains(x.To))322 }323 for b, sp := range s.spills {324 if sp.why != "" && freed(sp.area) {325 sp.stale = true326 out = append(out, loc{s, b})327 }328 }329 for _, me := range s.regionMeta {330 if me.why != "" && freed(me.need) {331 me.stale = true // sent again, as a region blocked by a cell cleared is332 }333 }334 return out335}336337// dropSpill forgets the anchor at a's spill and clears its cells,338// returning those that changed.339func (s *Sheet) dropSpill(a Addr) []loc {340 old := s.spills[a]341 if old == nil {342 return nil343 }344 s.setSpill(a, nil)345 if old.why != "" {346 return nil347 }348 return append(s.clearSpilled(old.area, Rect{From: a, To: a}), s.wb.recheckCircular()...)349}350351// setSpill records the anchor at a's spill (nil for none), indexing352// its area so that changing a cell there recalculates the anchor.353func (s *Sheet) setSpill(a Addr, sp *spill) {354 if old := s.spills[a]; old != nil {355 s.spillAt.remove(a, []Rect{old.area})356 delete(s.spills, a)357 if old.circular {358 s.wb.circArrays--359 }360 }361 if sp == nil {362 return363 }364 if sp.circular {365 s.wb.circArrays++366 }367 if s.spills == nil {368 s.spills = map[Addr]*spill{}369 }370 s.spills[a] = sp371 s.spillAt.add(a, []Rect{sp.area})372}373374// spillTouched notes that the cell at a is being changed by hand (or by375// a paste, a sort or undo): the anchors whose spill covers or needs it376// recompute, and an anchor losing its formula drops its spill.377func (s *Sheet) spillTouched(a Addr, c *Cell) {378 if s.spills == nil {379 return380 }381 if s.spills[a] != nil && (c == nil || !c.IsFormula()) {382 for _, l := range s.forgetSpill(a) {383 s.wb.markDirty(l)384 }385 }386 s.spillAt.readers(a, func(anchor Addr) {387 if anchor != a {388 s.spills[anchor].stale = true389 s.wb.markDirty(loc{s, anchor})390 }391 })392}393394// sameArray reports whether two arrays hold the same values.395func sameArray(x, y *functions.Array) bool {396 if x == y {397 return true398 }399 if x == nil || y == nil || x.Rows != y.Rows || x.Cols != y.Cols || x.DRows != y.DRows || x.DCols != y.DCols || x.Fill != y.Fill {400 return false401 }402 for i, v := range x.V {403 if y.V[i] != v {404 return false405 }406 }407 return true408}409410// recalcSwapped recalculates what an undo or redo changed, and the411// anchors of the spills it touched (markDirty).412func (w *Workbook) recalcSwapped(changed []loc) {413 changed = append(changed, w.hist.dirty...)414 w.hist.dirty = nil415 if w.structural {416 w.structural = false417 w.recalcAll()418 return419 }420 w.recalc(changed)421}422423// markDirty has the step being made or undone recalculate the cell at424// l, without recording it for undo.425func (w *Workbook) markDirty(l loc) {426 w.hist.dirty = append(w.hist.dirty, l)427}428429// SpillAnchor returns the cell whose array result the cell at a shows,430// when a is a spilled cell (not the anchor itself).431func (s *Sheet) SpillAnchor(a Addr) (Addr, bool) {432 var found Addr433 ok := false434 s.spillAt.readers(a, func(anchor Addr) {435 if sp := s.spills[anchor]; anchor != a && sp.why == "" {436 found, ok = anchor, true437 }438 })439 return found, ok440}441442// HasSpills reports whether a formula on the sheet spills or would, or a443// region shows a table (whose cells are spilled cells too), so what444// draws the sheet can skip looking for spilled cells.445func (s *Sheet) HasSpills() bool { return len(s.spills) > 0 || len(s.regions.list) > 0 }446447// SpillArea returns the cells the formula at a spills into, the anchor448// first, when it spills.449func (s *Sheet) SpillArea(a Addr) (Rect, bool) {450 sp := s.spills[a]451 if sp == nil || sp.why != "" {452 return Rect{}, false453 }454 return sp.area, true455}456457// InSpill returns a spilled cell in r whose anchor isn't in r, which an458// edit of r can't change: editing spilled cells is refused, while459// clearing or replacing the anchor with its spill is fine.460func (s *Sheet) InSpill(r Rect) (Addr, bool) {461 for anchor, sp := range s.spills {462 if sp.why != "" || r.Contains(anchor) || sp.area == (Rect{From: anchor, To: anchor}) {463 continue464 }465 if overlap, ok := intersectRect(sp.area, r); ok {466 return overlap.From, true // r doesn't hold the anchor: spilled cells467 }468 }469 return Addr{}, false470}471472// intersectRect is the overlap of two ranges, if any.473func intersectRect(a, b Rect) (Rect, bool) {474 r := Rect{475 From: Addr{Col: max(a.From.Col, b.From.Col), Row: max(a.From.Row, b.From.Row)},476 To: Addr{Col: min(a.To.Col, b.To.Col), Row: min(a.To.Row, b.To.Row)},477 }478 return r, r.From.Col <= r.To.Col && r.From.Row <= r.To.Row479}480481// saved is what the file keeps of the cell, or nil: a pivot's results482// are computed, not saved, and a spilled cell keeps its formatting and483// note, not the array's value.484func (c *Cell) saved() *Cell {485 switch {486 case c.derived:487 return nil488 case c.spilled:489 return c.leftover()490 }491 return c492}493494// spillError says why the anchor at a shows #REF!, or "".495func (s *Sheet) spillError(a Addr) string {496 if sp := s.spills[a]; sp != nil {497 return sp.why498 }499 return ""500}