1package sheet23import (4 "src.rest/cat/012/internal/formula"5 "src.rest/cat/012/internal/functions"6)78// Recalculation: a change marks the changed cells and everything that9// transitively reads them dirty, on any sheet, then evaluates the dirty10// cells lazily in dependency order.1112// RecalcAll recomputes every formula in the workbook. Loaders call it13// once the sheets are built, so it also starts a fresh undo history:14// loading isn't undoable.15func (s *Sheet) RecalcAll() { s.wb.RecalcAll() }1617// RecalcAll recomputes every formula and clears the undo history.18func (w *Workbook) RecalcAll() {19 w.recalcAll()20 w.ClearHistory()21}2223// recalcAll recomputes every formula on every sheet, as after loading or24// after a sheet is added, renamed or deleted, when references by name may25// resolve differently. Every cell is dirty, so there is nothing to26// propagate: tracing dependents from each cell cost O(cells x range27// users). Plain cells hold their values already (store.go), so only rich28// ones are marked.29func (w *Workbook) recalcAll() {30 w.gen++31 start := w.recalcStart()32 n := 033 for _, s := range w.sheets {34 s.calc = make(map[Addr]int, len(s.cells.rich)-len(s.cells.richFree))35 for a := range s.cells.richCells() {36 s.calc[a] = dirty37 }38 n += s.cells.len()39 }40 w.evaluate()41 w.settleSpills(nil)42 w.refreshPivots(w.allPivots())43 w.settleRegions()44 w.observe(true, start, n)45}4647// Recalculation states of a cell.48const (49 dirty = iota + 150 visiting51 done52 deferred // put off: evaluation went too deep, see evaluate.go53)5455// recalc recomputes the changed cells, volatile formulas, and everything56// that transitively depends on them, on any sheet.57func (w *Workbook) recalc(changed []loc) { w.recalcFrom(changed, true) }5859// recalcFrom recomputes the changed cells and everything that60// transitively depends on them, and the volatile formulas with theirs61// when volatiles is set.62func (w *Workbook) recalcFrom(changed []loc, volatiles bool) {63 w.gen++64 start := w.recalcStart()65 n := w.affected(changed, volatiles)66 stale := w.stalePivots()67 w.evaluate()68 w.refreshPivots(w.settleSpills(stale))69 w.settleRegions()70 w.observe(false, start, n)71}7273// affected marks dirty, in each sheet's calc, the changed cells, volatile74// formulas if volatiles is set, and every formula that transitively reads75// them, on any sheet, and returns how many it marked.76func (w *Workbook) affected(changed []loc, volatiles bool) int {77 return w.affectedBy(changed, nil, volatiles)78}7980// affectedBy is affected, with the formulas reading the cells of81// readers marked too, but not those cells: spilling changed what an82// anchor shows (spill.go), not its formula.83func (w *Workbook) affectedBy(changed, readers []loc, volatiles bool) int {84 m := marking{readerLookup: w.readerLookup(), queue: append([]loc(nil), changed...)}85 for _, s := range w.sheets {86 s.calc = make(map[Addr]int)87 if !volatiles {88 continue89 }90 for a := range s.volatile {91 m.queue = append(m.queue, loc{s, a})92 }93 }94 for _, l := range readers {95 m.readersOf(l)96 }97 n := 098 for len(m.queue) > 0 {99 l := m.queue[0]100 m.queue = m.queue[1:]101 if !l.s.live || l.s.calc[l.a] == dirty {102 continue103 }104 l.s.calc[l.a] = dirty105 n++106 m.readersOf(l)107 }108 return n109}110111// marking is the state of affected: the cells still to mark.112type marking struct {113 readerLookup114 queue []loc115}116117// readerLookup finds the formulas that read a cell, with what it looks118// up once rather than for every cell.119type readerLookup struct {120 w *Workbook121 named []namedUsers122 byName map[*Sheet]bool // whether some formula names the sheet123}124125func (w *Workbook) readerLookup() readerLookup {126 r := readerLookup{w: w, named: w.namedInUse(), byName: make(map[*Sheet]bool, len(w.sheets))}127 for _, s := range w.sheets {128 r.byName[s] = w.crossKeys[formula.SheetKey(s.name)] > 0129 }130 return r131}132133// namedUsers are the formulas that use a named range, with its cells,134// and whether it is a region's table.135type namedUsers struct {136 s *Sheet137 r Rect138 users map[loc]struct{}139 region bool140}141142// namedInUse returns the defined named ranges, tables and regions that143// formulas use.144func (w *Workbook) namedInUse() []namedUsers {145 var named []namedUsers146 for k, users := range w.nameUsers {147 if nm, ok := w.names[k]; ok && !nm.Gone() {148 named = append(named, namedUsers{s: nm.Sheet, r: nm.Range, users: users})149 }150 }151 named = append(named, w.tablesInUse()...)152 return append(named, w.regionsInUse()...)153}154155// push queues the formula at u unless it's already marked, so each is156// queued once rather than once per changed cell it reads.157func (m *marking) push(u loc) {158 if u.s.calc[u.a] != dirty {159 m.queue = append(m.queue, u)160 }161}162163// readersOf queues the formulas that read the cell l.164func (m *marking) readersOf(l loc) { m.each(l, m.push) }165166// each calls fn with the formulas that read the cell l: by reference, by167// a range over it, through a named range, or by naming its sheet.168func (r readerLookup) each(l loc, fn func(loc)) {169 s, a := l.s, l.a170 for d := range s.dependents[a] {171 fn(loc{s, d})172 }173 s.rangeUsers.readers(a, func(u Addr) { fn(loc{s, u}) })174 for _, nu := range r.named {175 if nu.s == s && nu.r.Contains(a) {176 for u := range nu.users {177 fn(u)178 }179 }180 }181 if !r.byName[s] {182 return // no formula names this sheet183 }184 for u := range r.w.crossUsers {185 if r.w.crossReads(u, l) {186 fn(u)187 }188 }189}190191// crossReads reports whether the formula at u reads the cell l through a192// reference that names l's sheet.193func (w *Workbook) crossReads(u, l loc) bool {194 c := u.s.cells.get(u.a)195 if c == nil {196 return false197 }198 for _, x := range c.xrefs {199 if x.r.Contains(l.a) && w.byKey[x.key] == l.s {200 return true201 }202 }203 return false204}205206// reader is the engine's side of how formulas on s read cells: the Book207// the function library reads through (functions.Book). It resolves208// references with read: references without a sheet ("") read s, others209// the sheet they name, with cells on a sheet no sheet has the name of210// reading as #REF!. The last sheet name is remembered, so a range on211// another sheet resolves its name once.212type reader struct {213 w *Workbook214 s *Sheet215 read func(*Sheet, Addr) Value216 memo *aggMemo // running aggregates shared by a recalculation; nil otherwise217 lastName string218 last *Sheet219 lib *functions.Reader // what the function library is given, reading through rd220 dense bool // denseReads when lib was made221}222223func (w *Workbook) lookupOn(s *Sheet, read func(*Sheet, Addr) Value) *reader {224 rd := &reader{w: w, s: s, read: read, dense: denseReads}225 rd.lib = functions.NewReader(rd, &w.depth, denseReads)226 return rd227}228229// recalcReader is the reader for formulas on s in a recalculation, which230// reads through e and shares running aggregates in memo: the one kept231// from the last recalculation, when there is one.232func (w *Workbook) recalcReader(s *Sheet, e *evaluator, memo *aggMemo) *reader {233 rd := s.recalcs234 if rd == nil || rd.w != w || rd.dense != denseReads {235 rd = w.lookupOn(s, nil)236 s.recalcs = rd237 }238 rd.read, rd.memo, rd.lastName, rd.last = e.compute, memo, "", nil239 rd.lib.Forget()240 return rd241}242243// sheet is the sheet a reference written with the name sheet points at.244func (rd *reader) sheet(sheet string) *Sheet {245 if sheet == "" {246 return rd.s247 }248 if sheet != rd.lastName || rd.last == nil {249 rd.lastName, rd.last = sheet, rd.w.byKey[formula.SheetKey(sheet)]250 }251 return rd.last252}253254// Cell returns the current value of a cell.255func (rd *reader) Cell(sheet string, a Addr) Value {256 t := rd.sheet(sheet)257 if t == nil {258 return ErrRef259 }260 if reg, ok := t.pagedRegion(); ok {261 return rd.pagedCell(t, reg, a)262 }263 return rd.read(t, a)264}265266// Scan reads the stored cells of r from the cell from on, row by row, as267// functions.Book describes: blank cells are skipped without being268// visited, so a whole column costs what it holds. It finds the cells269// first, then reads their values, so the chunk is filled without a call270// per cell.271func (rd *reader) Scan(sheet string, r Rect, from Addr, addrs []Addr, vals []Value) int {272 t := rd.sheet(sheet)273 if t == nil {274 return -1275 }276 if reg, ok := t.pagedRegion(); ok {277 return rd.pagedScan(t, reg, r, from, addrs, vals)278 }279 n := fill(t, r, from, addrs)280 if vals == nil {281 return n282 }283 for i, a := range addrs[:n] {284 v := rd.read(t, a)285 vals[i] = v286 if v.Kind == Error {287 return i + 1288 }289 }290 return n291}292293// fill writes the stored cells of r on t from the cell from on into dst,294// row by row, until it is full, and returns how many.295func fill(t *Sheet, r Rect, from Addr, dst []Addr) int {296 switch {297 case denseReads:298 return fillDense(r, from, dst)299 case r.From.Col == r.To.Col:300 return t.cells.colFill(r.From.Col, from.Row, r.To.Row, dst)301 }302 return t.cells.rangeFill(r, from, dst)303}304305// fillDense writes every address of r from the cell from on into dst,306// row by row, until it is full, as tests ask with denseReads.307func fillDense(r Rect, from Addr, dst []Addr) int {308 n := 0309 for a := from; a.Row <= r.To.Row && n < len(dst); n++ {310 dst[n] = a311 if a.Col++; a.Col > r.To.Col {312 a = Addr{Col: r.From.Col, Row: a.Row + 1}313 }314 }315 return n316}317318// Bounds is the smallest range holding every stored cell of r.319func (rd *reader) Bounds(sheet string, r Rect) (b Rect, any, exists bool) {320 t := rd.sheet(sheet)321 if t == nil {322 return Rect{}, false, false323 }324 if reg, ok := t.pagedRegion(); ok {325 b, any = t.pagedBounds(reg, r)326 return b, any, true327 }328 b, any = t.cells.bounds(r)329 return b, any, true330}331332// Ask looks up the answer to a JEV function's question in the workbook's333// RemoteSource, noting that the formula being evaluated waits for it334// when it isn't known yet.335func (rd *reader) Ask(call RemoteCall) (RemoteAnswer, Value) {336 w := rd.w337 if w.remote == nil {338 return RemoteAnswer{}, ErrNoRemote339 }340 ans, ok := w.remote.Lookup(call)341 if !ok {342 w.wait(call)343 return RemoteAnswer{}, Pending344 }345 return ans, Value{}346}347348// denseReads makes formulas read every address of their ranges, as they349// did before ranges were clipped to what they hold, so tests can check350// that the two agree.351var denseReads bool352353// values reads current values for formulas on s, across sheets.354func (w *Workbook) values(s *Sheet) *reader {355 return w.lookupOn(s, func(t *Sheet, a Addr) Value { return t.Value(a) })356}357358// formatFrom reads display formats for formulas on s, across sheets: on359// a linked source's tab, the format its column's type shows in.360func (w *Workbook) formatFrom(s *Sheet) func(string, Addr) Format {361 return func(sheet string, a Addr) Format {362 t := w.resolve(s, sheet)363 if t == nil {364 return Format{}365 }366 if r, ok := t.pagedRegion(); ok {367 return t.sourceFormat(r, a)368 }369 return t.DisplayFormat(a)370 }371}