1package functions23import (4 "src.rest/cat/012/internal/formula"5 "src.rest/cat/012/internal/value"6)78// Arrays, as Sheets computes them. A range read whole, an array literal9// ({1,2;3,4}) and what FILTER, SORT, SEQUENCE and the like return are10// arrays; operators over arrays work element by element, and in an array11// context (ARRAYFORMULA, or an argument that takes ranges, as in12// SUM(B2:B4*2)) functions that take one value are applied to each13// element (lift.go). A formula whose result is an array spills it into14// the cells to its right and below (the engine's spill.go).15//16// While a formula is evaluated, an array travels as a Value of kind17// value.Array whose Num indexes the Reader's arena, so the Value every18// cell holds stays as small as it is. Only callers that asked for an19// array get one (Reader.wantArr); anywhere else it reads as its first20// element, as Sheets reads an array where one value is wanted.2122// Array is the value of a formula that computes several: Rows by Cols23// entries. Only the top-left DRows by DCols hold values of their own, in24// V row by row; every other entry is Fill. A whole column read as an25// array costs what it holds: A:A is 1,048,576 rows, of which the rows26// holding data are stored, the rest blank.27type Array struct {28 Rows, Cols int29 DRows, DCols int30 V []Value31 Fill Value32}3334// maxArray caps how many values an array stores (DRows x DCols), so a35// formula can't exhaust memory: past it the formula is #VALUE!.36const maxArray = 1 << 213738// NewArray is a dense array of rows x cols values, all blank.39func NewArray(rows, cols int) *Array {40 return &Array{Rows: rows, Cols: cols, DRows: rows, DCols: cols, V: make([]Value, rows*cols)}41}4243// At is the entry at row r and column c, counting from 0.44func (a *Array) At(r, c int) Value {45 if r < a.DRows && c < a.DCols {46 return a.V[r*a.DCols+c]47 }48 return a.Fill49}5051// Set stores v at row r and column c of a dense array.52func (a *Array) Set(r, c int, v Value) { a.V[r*a.DCols+c] = v }5354// size is how many entries the array has.55func (a *Array) size() int { return a.Rows * a.Cols }5657// bcast is the entry at r, c of a broadcast to more rows or columns: a58// single row repeats down, a single column across. Past a's size in a59// dimension it doesn't broadcast in, the entry is #N/A, as Sheets shows60// arrays of different sizes lined up.61func (a *Array) bcast(r, c int) Value {62 if a.Rows == 1 {63 r = 064 }65 if a.Cols == 1 {66 c = 067 }68 if r >= a.Rows || c >= a.Cols {69 return value.ErrNA70 }71 return a.At(r, c)72}7374// tooBig reports whether an array of rows x cols stored values is past75// maxArray.76func tooBig(rows, cols int) bool {77 return rows < 0 || cols < 0 || rows > 0 && cols > maxArray/rows78}7980// lambda is a LAMBDA's value: its parameters, its expression and the81// names bound where it was written (lambda.go).82type lambda struct {83 params []string84 body Node85 scope []binding86}8788// arrayValue is a as a value: its only entry when it has one, else a89// handle to it in the arena.90func (rd *Reader) arrayValue(a *Array) Value {91 if a.Rows == 1 && a.Cols == 1 {92 return a.At(0, 0)93 }94 if a.size() == 0 {95 return value.ErrNA96 }97 return rd.handle(a)98}99100// handle stores x (an *Array or a *lambda) in the arena and returns the101// value that stands for it.102func (rd *Reader) handle(x any) Value {103 rd.arena = append(rd.arena, x)104 return Value{Kind: value.Array, Num: float64(len(rd.arena) - 1)}105}106107// arrayOf is the array v stands for, or nil when v is one value (or a108// LAMBDA).109func (rd *Reader) arrayOf(v Value) *Array {110 if v.Kind != value.Array {111 return nil112 }113 a, _ := rd.arena[int(v.Num)].(*Array)114 return a115}116117// lambdaOf is the LAMBDA v stands for, or nil.118func (rd *Reader) lambdaOf(v Value) *lambda {119 if v.Kind != value.Array {120 return nil121 }122 l, _ := rd.arena[int(v.Num)].(*lambda)123 return l124}125126// first is v as one value: an array's first entry. A LAMBDA isn't a127// value a cell can show: #VALUE!, as a LAMBDA not called with arguments128// is in Sheets.129func (rd *Reader) first(v Value) Value {130 if v.Kind != value.Array {131 return v132 }133 if a := rd.arrayOf(v); a != nil {134 return a.At(0, 0)135 }136 return value.ErrValue137}138139// reduce is v as the caller wants it: an array only if it asked for one.140func (rd *Reader) reduce(v Value) Value {141 if v.Kind == value.Array && !rd.wantArr {142 return rd.first(v)143 }144 return v145}146147// eval1 evaluates n where one value is wanted, whatever the context: a148// range reads as one of its cells and an array as its first entry.149func eval1(n Node, get lookup) Value {150 if get.lift == 0 && !get.wantArr {151 return eval(n, get)152 }153 lift, want := get.lift, get.wantArr154 get.lift, get.wantArr = 0, false155 v := eval(n, get)156 get.lift, get.wantArr = lift, want157 return v158}159160// evalArr evaluates n in an array context: ranges read whole, operators161// work element by element and functions of one value are applied to each162// element. Arguments that take ranges (SUM(B2:B4*2)) and array functions163// (FILTER, SORT) read theirs this way.164func evalArr(n Node, get lookup) Value {165 lift, want := get.lift, get.wantArr166 get.lift, get.wantArr = lift+1, true167 v := eval(n, get)168 get.lift, get.wantArr = lift, want169 return v170}171172// arrayArg is argument n read as an array: a range, an array, or one173// value as a 1x1 array.174func arrayArg(n Node, get lookup) (*Array, *Value) {175 v := evalArr(n, get)176 if a := get.arrayOf(v); a != nil {177 return a, nil178 }179 if v.Kind == value.Error {180 return nil, errOf(v)181 }182 if v.Kind == value.Array { // a LAMBDA183 return nil, &value.ErrValue184 }185 a := NewArray(1, 1)186 a.V[0] = v187 return a, nil188}189190// rangeArray reads the range r on sheet as an array: its cells up to191// the last one holding something, blank past them. Arrays are never192// changed once made, so a range read before (see Forget) is shared.193func (rd *Reader) rangeArray(sheet string, r Rect) Value {194 if r.From == r.To {195 return rd.cell(sheet, r.From)196 }197 k := rangeKey{sheet, r}198 if a, ok := rd.ranges[k]; ok {199 return rd.arrayValue(a)200 }201 v := rd.readRange(sheet, r)202 if a := rd.arrayOf(v); a != nil {203 if rd.ranges == nil {204 rd.ranges = map[rangeKey]*Array{}205 }206 rd.ranges[k] = a207 }208 return v209}210211// readRange reads a range as an array.212func (rd *Reader) readRange(sheet string, r Rect) Value {213 a := &Array{Rows: r.To.Row - r.From.Row + 1, Cols: r.To.Col - r.From.Col + 1}214 b, any, exists := rd.book.Bounds(sheet, r)215 switch {216 case !exists:217 return value.ErrRef218 case rd.dense:219 a.DRows, a.DCols = a.Rows, a.Cols220 case any:221 a.DRows, a.DCols = b.To.Row-r.From.Row+1, b.To.Col-r.From.Col+1222 }223 if tooBig(a.DRows, a.DCols) {224 return value.ErrValue225 }226 a.V = make([]Value, a.DRows*a.DCols)227 data := Rect{From: r.From, To: Addr{Col: r.From.Col + a.DCols - 1, Row: r.From.Row + a.DRows - 1}}228 if a.DRows > 0 && a.DCols > 0 {229 rd.cells(sheet, data, func(at Addr, v Value) bool {230 a.Set(at.Row-r.From.Row, at.Col-r.From.Col, v)231 return true232 })233 }234 return rd.arrayValue(a)235}236237// literal evaluates an array literal: each element in an array context,238// elements side by side in a row and rows stacked, so {A1:A3,B1:B3} is239// three rows of two. Rows of different widths are #VALUE!, as Sheets240// says an array literal is missing values.241func (rd *Reader) literal(n formula.Array) Value {242 var rows []*Array243 for _, row := range n.Rows {244 var parts []*Array245 for _, e := range row {246 a, err := arrayArg(e, rd)247 if err != nil {248 return *err249 }250 parts = append(parts, a)251 }252 joined, ok := hstack(parts)253 if !ok {254 return value.ErrValue255 }256 rows = append(rows, joined)257 }258 a, ok := vstack(rows)259 if !ok {260 return value.ErrValue261 }262 return rd.arrayValue(a)263}264265// hstack puts arrays of the same height side by side.266func hstack(parts []*Array) (*Array, bool) {267 if len(parts) == 1 {268 return parts[0], true269 }270 rows, cols := parts[0].Rows, 0271 for _, p := range parts {272 if p.Rows != rows {273 return nil, false274 }275 cols += p.Cols276 }277 if tooBig(rows, cols) {278 return nil, false279 }280 out := NewArray(rows, cols)281 at := 0282 for _, p := range parts {283 for r := range rows {284 for c := range p.Cols {285 out.Set(r, at+c, p.At(r, c))286 }287 }288 at += p.Cols289 }290 return out, true291}292293// vstack stacks arrays of the same width.294func vstack(parts []*Array) (*Array, bool) {295 if len(parts) == 1 {296 return parts[0], true297 }298 rows, cols := 0, parts[0].Cols299 for _, p := range parts {300 if p.Cols != cols {301 return nil, false302 }303 rows += p.Rows304 }305 if tooBig(rows, cols) {306 return nil, false307 }308 out := NewArray(rows, cols)309 at := 0310 for _, p := range parts {311 for r := range p.Rows {312 for c := range cols {313 out.Set(at+r, c, p.At(r, c))314 }315 }316 at += p.Rows317 }318 return out, true319}320321// shape is the size of arrays lined up for an element-wise operation,322// and how much of it holds values of its own.323type shape struct{ rows, cols, drows, dcols int }324325// fit widens s to take in a: sizes must match, or be 1 to broadcast.326func (s *shape) fit(a *Array) bool {327 if a == nil {328 return true329 }330 if s.rows == 0 {331 *s = shape{rows: a.Rows, cols: a.Cols}332 }333 var ok bool334 if s.rows, ok = fitDim(s.rows, a.Rows); !ok {335 return false336 }337 if s.cols, ok = fitDim(s.cols, a.Cols); !ok {338 return false339 }340 return true341}342343// fitDim is the length two broadcast dimensions line up to: the longer,344// when one is 1 or both are equal. Arrays of different sizes otherwise345// line up to the longer, the missing entries #N/A (Array.bcast).346func fitDim(a, b int) (int, bool) {347 return max(a, b), true348}349350// data sets how much of s holds values of their own, given the arrays351// lined up in it.352func (s *shape) data(arrs ...*Array) {353 s.drows, s.dcols = 0, 0354 for _, a := range arrs {355 if a == nil {356 continue357 }358 r, c := a.DRows, a.DCols359 if a.Rows == 1 && r > 0 {360 r = s.rows361 }362 if a.Cols == 1 && c > 0 {363 c = s.cols364 }365 if a.Rows != s.rows && a.Rows != 1 || a.Cols != s.cols && a.Cols != 1 {366 r, c = s.rows, s.cols // #N/A past its end367 }368 s.drows, s.dcols = max(s.drows, r), max(s.dcols, c)369 }370 s.drows, s.dcols = min(s.drows, s.rows), min(s.dcols, s.cols)371}372373// newArray is an array of shape s, its values to fill in.374func (s shape) newArray() (*Array, bool) {375 if tooBig(s.drows, s.dcols) {376 return nil, false377 }378 return &Array{Rows: s.rows, Cols: s.cols, DRows: s.drows, DCols: s.dcols, V: make([]Value, s.drows*s.dcols)}, true379}380381// entry is v at r, c: its entry when it is an array, else v itself.382func entry(a *Array, v Value, r, c int) Value {383 if a == nil {384 return v385 }386 return a.bcast(r, c)387}388389// fillOf is the value past v's data: its fill when it is an array.390func fillOf(a *Array, v Value) Value {391 if a == nil {392 return v393 }394 return a.Fill395}396397// elementwise applies op to the entries of l and r lined up, one of398// them at least an array.399func (rd *Reader) elementwise(l, r Value, op func(l, r Value) Value) Value {400 la, ra := rd.arrayOf(l), rd.arrayOf(r)401 if la == nil && l.Kind == value.Array || ra == nil && r.Kind == value.Array {402 return value.ErrValue // a LAMBDA403 }404 var s shape405 if !s.fit(la) || !s.fit(ra) {406 return value.ErrValue407 }408 s.data(la, ra)409 out, ok := s.newArray()410 if !ok {411 return value.ErrValue412 }413 for i := range s.drows {414 for j := range s.dcols {415 out.Set(i, j, op(entry(la, l, i, j), entry(ra, r, i, j)))416 }417 }418 out.Fill = op(fillOf(la, l), fillOf(ra, r))419 return rd.arrayValue(out)420}