1package functions23import "src.rest/cat/012/internal/value"45// Book is how formulas reach the workbook: the engine implements it, once6// for each sheet whose formulas it evaluates. Sheets are named as7// references write them; "" is the formula's own sheet.8//9// Every method takes and returns plain values, never a callback: a10// function value or pointer passed through an interface escapes to the11// heap, so a callback per range read would cost an allocation that an12// engine reading its own cells doesn't pay. Ranges are read instead in chunks, into13// buffers the Reader keeps and reuses (Scan), and each function walks14// them with callbacks of its own that stay on the stack.15type Book interface {16 // Cell is the current value of a cell, evaluated first if it's17 // dirty; #REF! on a sheet that doesn't exist.18 Cell(sheet string, a Addr) Value19 // Scan reads the cells of r that hold something, row by row, from20 // the cell from on (those before it in that order are skipped): their21 // addresses into addrs and, unless vals is nil, their values into22 // vals, evaluating them as Cell does. It stops when addrs is full or23 // just after a value that is an error, so no cell past the first24 // error is evaluated, and returns how many it read: -1 when the sheet25 // doesn't exist.26 Scan(sheet string, r Rect, from Addr, addrs []Addr, vals []Value) int27 // Bounds is the smallest range holding every stored cell of r, with28 // false if r holds none; exists is false when the sheet doesn't.29 Bounds(sheet string, r Rect) (b Rect, any, exists bool)30 // RangeAgg is the aggregate of r that SUM-like functions share within31 // a recalculation (see Agg), with the first error in it, or false32 // when r should be read directly.33 RangeAgg(sheet string, r Rect) (Agg, *Value, bool)34 // Fold adds the cells of r that hold something to s, row by row, as35 // SUM-like functions read a range (Agg.Add), evaluating them as Cell36 // does and stopping at the first error, which it returns. On a sheet37 // that doesn't exist the range is one #REF!.38 Fold(sheet string, r Rect, s Agg) (Agg, *Value)39 // Ask looks up the answer to a remote question (JEV functions). The40 // value is an error when there is none to give: Pending while it is41 // on its way, ErrNoRemote when nothing answers them.42 Ask(call RemoteCall) (RemoteAnswer, Value)43 // Paged reports whether the sheet is a paged source (stream.go),44 // whose ranges a function is given through Stream.45 Paged(sheet string) bool46 // Stream answers a call over paged sources, with an array when it47 // computes several values: Pending while the answer is on its way.48 Stream(call StreamCall) (Value, *Array)49}5051// Reader is what a function is given to read the cells its arguments52// refer to: a Book, and the buffers ranges are read through. It is a53// concrete type so the callbacks functions pass to it stay on the stack.54type Reader struct {55 book Book56 depth *int // how deeply evaluation is nested; see the engine's evaluate.go57 dense bool // read every address of a range; see NewReader58 // stream is set on a Reader computing a StreamCall, over a Book that59 // streams paged sources: functions over aligned ranges read them a60 // window of rows at a time (streamed.go) rather than gathering the61 // positions of their cells.62 stream bool63 bufs []*scanBuf64 level int // how many of bufs are in use by range reads in progress6566 evalState67 // arena holds the arrays and LAMBDAs of the formulas being evaluated68 // (array.go), emptied when the outermost is done; nest counts them.69 arena []any70 nest int71 outer []evalState // the states of the formulas nest counts, but the innermost72 spilled *Array // the array the last formula computed; see Spilled73 // ranges are the ranges read whole as arrays since Forget, shared by74 // the formulas reading them: a thousand FILTERs of one column read it75 // once. See Forget.76 ranges map[rangeKey]*Array77}7879// rangeKey is a range as a formula names it.80type rangeKey struct {81 sheet string82 r Rect83}8485// Forget drops the ranges read as arrays. The engine calls it as each86// recalculation starts and ends: within one, a range's values don't87// change once read, since reading it evaluates its dirty cells first (a88// range holding a cell being evaluated is a cycle, an error either way),89// and spilled cells are written between passes.90func (rd *Reader) Forget() { clear(rd.ranges) }9192// evalState is where a formula's evaluation is: saved while a cell it93// reads is evaluated through the same Reader, and given back after.94type evalState struct {95 here Addr // the cell whose formula is being evaluated; see EvalAt96 // wantArr is set when the expression being evaluated may compute an97 // array: at the top of a cell's formula, in operands and in what98 // IF-like functions return. Elsewhere an array reads as its first99 // entry (Reader.reduce).100 wantArr bool101 // lift counts the array contexts enclosing the expression: ranges102 // read whole and functions of one value are mapped over arrays.103 lift int104 // scope holds the names LET and LAMBDA bound, innermost last.105 scope []binding106}107108// lookup is the parameter every evaluator takes.109type lookup = *Reader110111// NewReader reads cells through book. depth counts how deeply evaluation112// nests (cells, operators and calls), for the engine to put off cells113// past its limit. With dense, functions read every address of their114// ranges, as they did before ranges were clipped to what they hold, so115// tests can check that the two agree.116func NewReader(book Book, depth *int, dense bool) *Reader {117 return &Reader{book: book, depth: depth, dense: dense}118}119120// A range is read in chunks that start small, for the many short ranges,121// and double up to maxChunk as a range proves long. Nested range reads (a122// SUM whose cells hold SUMs) each use a buffer of their own.123const (124 firstChunk = 8125 maxChunk = 1024126)127128type scanBuf struct {129 addrs []Addr130 vals []Value131}132133// take returns the buffer for a range read starting now; give returns it.134func (rd *Reader) take() *scanBuf {135 if rd.level == len(rd.bufs) {136 rd.bufs = append(rd.bufs, &scanBuf{addrs: make([]Addr, firstChunk), vals: make([]Value, firstChunk)})137 }138 b := rd.bufs[rd.level]139 rd.level++140 return b141}142143func (rd *Reader) give() { rd.level-- }144145// fit makes the buffer hold at least n cells.146func (b *scanBuf) fit(n int) {147 if len(b.addrs) < n {148 b.addrs, b.vals = make([]Addr, n), make([]Value, n)149 }150}151152// next is the cell after a in r, row by row.153func next(r Rect, a Addr) Addr {154 if a.Col < r.To.Col {155 return Addr{Col: a.Col + 1, Row: a.Row}156 }157 return Addr{Col: r.From.Col, Row: a.Row + 1}158}159160// cell returns the current value of a cell.161func (rd *Reader) cell(sheet string, a Addr) Value { return rd.book.Cell(sheet, a) }162163// cells calls fn with the address and value of every cell of r that164// holds something, row by row, until fn returns false: blank cells are165// skipped without being visited, so a whole column costs what it holds.166// A range on a sheet that doesn't exist reads as one #REF!. Cells are167// evaluated a chunk ahead of fn, but never past an error: every caller168// stops at the first error, so none evaluates a cell it wouldn't have169// read one at a time.170func (rd *Reader) cells(sheet string, r Rect, fn func(Addr, Value) bool) {171 b := rd.take()172 defer rd.give()173 for from := r.From; from.Row <= r.To.Row; {174 n := rd.book.Scan(sheet, r, from, b.addrs, b.vals)175 if n < 0 {176 fn(r.From, value.ErrRef)177 return178 }179 for i := range n {180 if !fn(b.addrs[i], b.vals[i]) {181 return182 }183 }184 switch {185 case n == len(b.addrs):186 from = next(r, b.addrs[n-1])187 b.fit(min(2*n, maxChunk))188 case n > 0 && b.vals[n-1].Kind == value.Error:189 from = next(r, b.addrs[n-1])190 default:191 return192 }193 }194}195196// stored calls fn with every cell of r that holds something, row by row,197// until fn returns false, without evaluating any. A sheet that doesn't198// exist holds none.199func (rd *Reader) stored(sheet string, r Rect, fn func(Addr) bool) {200 c := rd.walk(sheet, r)201 defer c.close()202 for a, ok := c.next(); ok && fn(a); a, ok = c.next() {203 }204}205206// cursor walks the cells of a range that hold something, row by row,207// without evaluating any: stored as a loop, for searches that stop part208// way and read values as they go. Searches stop at their match, so a209// walk starts with a small chunk, however long earlier ranges were, and210// doubles it as the range goes on: finding a key near the top of a211// whole column costs the cells before it. A cursor holds a buffer until212// it is closed.213type cursor struct {214 rd *Reader215 b *scanBuf216 sheet string217 r Rect218 from Addr // where the next chunk starts219 size int // how many cells it asks for220 n, i int // the cells in the buffer, and the next of them221}222223// walk starts a cursor over the stored cells of r.224func (rd *Reader) walk(sheet string, r Rect) cursor {225 return cursor{rd: rd, b: rd.take(), sheet: sheet, r: r, from: r.From, size: firstChunk}226}227228// next returns the next cell, or false when there are no more.229func (c *cursor) next() (Addr, bool) {230 if c.i < c.n {231 c.i++232 return c.b.addrs[c.i-1], true233 }234 return c.fill()235}236237// fill reads the next chunk and returns its first cell.238func (c *cursor) fill() (Addr, bool) {239 if c.from.Row > c.r.To.Row {240 return Addr{}, false241 }242 // Grown here, before the chunk is read: growing makes a new buffer,243 // which mustn't happen while the last chunk is still being walked.244 c.b.fit(c.size)245 c.n, c.i = c.rd.book.Scan(c.sheet, c.r, c.from, c.b.addrs[:c.size], nil), 1246 if c.n <= 0 {247 c.from.Row = c.r.To.Row + 1248 return Addr{}, false249 }250 if c.n < c.size {251 c.from.Row = c.r.To.Row + 1 // that was the last252 } else {253 c.from = next(c.r, c.b.addrs[c.n-1])254 if c.size < maxChunk {255 c.size *= 2256 }257 }258 return c.b.addrs[0], true259}260261// close gives the cursor's buffer back.262func (c *cursor) close() { c.rd.give() }