1package sheet23import (4 "iter"5 "math"6 "math/bits"7 "slices"8 "strconv"910 "src.rest/cat/012/internal/formula"11)1213// cellStore holds a sheet's cells: those with contents or formatting, by14// address. The rest of the engine reads and writes cells only through15// these methods, never the representation beneath.16//17// Cells live in columns of blocks of blockRows rows: the stored18// occupancy index (occupancy.go) has a bitmap per block of the rows19// holding a cell, and each block keeps their slots (slot.go) in row20// order, so a cell is found by indexing a column, a block and a popcount,21// without hashing. A plain number costs its 16-byte slot, and so does a22// pivot's or a spill's result (a derived cell, marked in its slot). Rich23// cells (formulas, notes) are whole Cells in a side table the slot24// points at.25//26// get returns a rich cell's own Cell, which recalculation updates in27// place, as ever, and a plain cell as a Cell made for the caller (a28// view): the caller may keep it, but changing it changes nothing29// stored; set is the one way to change a cell. Views cost an allocation30// or three, so what reads many cells asks for what it needs: peek and31// value for values, has and filledAt for presence, richAt for formulas,32// look for formatting, and the key iterators for addresses.33//34// A second occupancy index records which cells have contents, so the35// used range and data edges are found without scanning.36//37// Iteration yields column by column, except inRange and keysIn, which38// yield in row-major order. Cells may be set or deleted while iterating,39// with a map's rules: a deleted cell not yet reached isn't yielded, a new40// one may or may not be.41type cellStore struct {42 stored occupancy // every cell, with the blocks holding their slots43 filled occupancy // the cells with contents (not Blank), with their statistics; see stats.go44 statsUsed bool // a selection has been summed from the statistics index4546 strs strTable // plain cells' text47 looks []look // formats and styles, by slot.look48 lookIdx map[look]uint16 // looks' entries49 rich []richCell // rich cells, by slot.ref50 richFree []uint32 // entries of rich not in use5152 // pivots counts the pivot's results stored (Cell.derived), and53 // pivotArea holds them all while there are any, so they are found54 // without visiting every cell.55 pivots int56 pivotArea Rect57}5859func newCellStore() cellStore { return cellStore{} }6061// find returns the block holding a's slot and its position there, or nil.62func (st *cellStore) find(a Addr) (*rowBlock, int) {63 b := st.stored.col(a.Col).block(a.Row >> blockShift)64 if b == nil {65 return nil, 066 }67 i, ok := b.index(a.Row & (blockRows - 1))68 if !ok {69 return nil, 070 }71 return b, i72}7374// get returns the cell at a, or nil: a rich cell itself, a plain one as75// a view.76func (st *cellStore) get(a Addr) *Cell {77 b, i := st.find(a)78 if b == nil {79 return nil80 }81 return st.cellOf(b.vals[i])82}8384func (st *cellStore) cellOf(sl slot) *Cell {85 if sl.kind == slotRich {86 return st.rich[sl.ref].c87 }88 return st.view(sl)89}9091// peek returns the rich cell at a, or else the plain cell's value, and92// whether a holds a cell at all. It allocates nothing: recalculation93// reads every cell through it.94func (st *cellStore) peek(a Addr) (*Cell, Value, bool) {95 b, i := st.find(a)96 if b == nil {97 return nil, Value{}, false98 }99 sl := b.vals[i]100 if sl.kind == slotRich {101 return st.rich[sl.ref].c, Value{}, true102 }103 return nil, st.slotValue(sl), true104}105106// value returns the value of the cell at a.107func (st *cellStore) value(a Addr) Value {108 c, v, _ := st.peek(a)109 if c != nil {110 return c.Value111 }112 return v113}114115// has reports whether a holds a cell, if only formatting.116func (st *cellStore) has(a Addr) bool { return st.stored.has(a) }117118// filledAt reports whether the cell at a has contents: !get(a).Blank().119func (st *cellStore) filledAt(a Addr) bool { return st.filled.has(a) }120121// richAt returns the cell at a if it is rich (a formula or a note, or a122// cell a slot can't hold), or nil.123func (st *cellStore) richAt(a Addr) *Cell {124 b, i := st.find(a)125 if b == nil || b.vals[i].kind != slotRich {126 return nil127 }128 return st.rich[b.vals[i].ref].c129}130131// look returns the format and style of the cell at a, and whether there132// is one.133func (st *cellStore) look(a Addr) (Format, Style, bool) {134 b, i := st.find(a)135 if b == nil {136 return Format{}, Style{}, false137 }138 if sl := b.vals[i]; sl.kind == slotRich {139 c := st.rich[sl.ref].c140 return c.Format, c.Style, true141 } else {142 l := st.lookOf(sl)143 return l.f, l.st, true144 }145}146147// holds reports whether the cell at a is c: the same Cell if rich, the148// same contents and formatting if plain; nil for none.149func (st *cellStore) holds(a Addr, c *Cell) bool {150 b, i := st.find(a)151 if b == nil || c == nil {152 return b == nil && c == nil153 }154 sl := b.vals[i]155 if sl.kind == slotRich {156 return st.rich[sl.ref].c == c157 }158 if l := st.lookOf(sl); c.Note != "" || c.auto != l.auto || c.Format != l.f || c.Style != l.st {159 return false160 }161 if c.derived != (sl.kind&slotPivot != 0) || c.spilled != (sl.kind&slotSpill != 0) {162 return false163 }164 if sl.kind&slotDerived != 0 {165 return c.expr == nil && c.Value == st.slotValue(sl)166 }167 switch sl.kind {168 case slotText:169 return c.expr == nil && c.Input == st.strs.strs[sl.ref]170 case slotNum:171 e, ok := c.expr.(formula.Num)172 return ok && math.Float64bits(e.V) == math.Float64bits(sl.num) && st.inputIs(sl, c.Input)173 case slotBool:174 e, ok := c.expr.(formula.Bool)175 return ok && e.V == (sl.num != 0) && st.inputIs(sl, c.Input)176 }177 return c.expr == nil && c.Input == ""178}179180// inputIs reports whether input is the entry of the plain number or181// boolean sl, without making it.182func (st *cellStore) inputIs(sl slot, input string) bool {183 switch {184 case sl.ref != 0:185 return input == st.strs.strs[sl.ref]186 case sl.kind == slotBool:187 return input == boolText(sl.num != 0)188 }189 var buf [64]byte190 return string(strconv.AppendFloat(buf[:0], sl.num, 'f', int(sl.dec)-1, 64)) == input191}192193// copyOf is the cell at a as a Cell the caller owns, or nil.194func (st *cellStore) copyOf(a Addr) *Cell {195 b, i := st.find(a)196 if b == nil {197 return nil198 }199 if sl := b.vals[i]; sl.kind == slotRich {200 return st.rich[sl.ref].c.clone()201 } else {202 return st.view(sl)203 }204}205206// set stores c, which isn't nil, at a. A rich c is kept as it is, so207// recalculation can update it in place; a plain one is copied into a208// slot, and its value is its entry's from then on.209func (st *cellStore) set(a Addr, c *Cell) {210 b, i := st.find(a)211 if b == nil {212 b = st.stored.mark(a)213 i, _ = b.index(a.Row & (blockRows - 1))214 b.vals = slices.Insert(b.vals, i, slot{kind: slotBlank})215 }216 old := b.vals[i]217 st.countPivot(a, st.isPivot(old), c.derived)218 sl, ok := st.plainSlot(c) // before releasing old, which may share its strings219 switch {220 case ok:221 st.releaseSlot(old)222 case old.kind == slotRich:223 st.rich[old.ref] = richCell{c, a}224 sl = old225 default:226 st.releaseSlot(old)227 sl = slot{kind: slotRich, ref: st.addRich(a, c)}228 }229 b.vals[i] = sl230 st.filledAs(a, st.filled.has(a), !c.Blank())231 st.touch(a)232}233234// setSlot stores sl, a plain slot whose strings and look st already235// counts, at a: set for a slot made directly, as a file's numbers are.236func (st *cellStore) setSlot(a Addr, sl slot) {237 b, i := st.find(a)238 if b == nil {239 b = st.stored.mark(a)240 i, _ = b.index(a.Row & (blockRows - 1))241 b.vals = slices.Insert(b.vals, i, slot{kind: slotBlank})242 }243 st.countPivot(a, st.isPivot(b.vals[i]), false)244 st.releaseSlot(b.vals[i])245 b.vals[i] = sl246 st.filledAs(a, st.filled.has(a), sl.kind != slotBlank)247 st.touch(a)248}249250// filledAs updates the index of filled cells for a cell at a that was251// and is filled or not.252func (st *cellStore) filledAs(a Addr, was, is bool) {253 switch {254 case is && !was:255 st.filled.mark(a)256 case was && !is:257 st.filled.unmark(a)258 }259}260261// delete removes the cell at a, if any.262func (st *cellStore) delete(a Addr) {263 b, i := st.find(a)264 if b == nil {265 return266 }267 st.touch(a)268 old := b.vals[i]269 st.countPivot(a, st.isPivot(old), false)270 if st.filled.has(a) {271 st.filled.unmark(a)272 }273 b.vals = slices.Delete(b.vals, i, i+1)274 st.stored.unmark(a)275 st.releaseSlot(old)276}277278// len is the number of cells stored, formatting-only ones included.279func (st *cellStore) len() int { return st.stored.n }280281// filledLen is the number of cells with contents.282func (st *cellStore) filledLen() int { return st.filled.n }283284// all yields every stored cell, plain ones as views.285func (st *cellStore) all() iter.Seq2[Addr, *Cell] { return st.cellsOf(st.keys()) }286287// keys yields the address of every stored cell, column by column.288func (st *cellStore) keys() iter.Seq[Addr] {289 return st.anyKeysIn(Rect{To: Addr{Col: MaxCols - 1, Row: MaxRows - 1}})290}291292// richCells yields every rich cell: the formulas, notes and results of293// pivots and spills.294func (st *cellStore) richCells() iter.Seq2[Addr, *Cell] {295 return func(yield func(Addr, *Cell) bool) {296 for i := 0; i < len(st.rich); i++ {297 if rc := st.rich[i]; rc.c != nil && !yield(rc.a, rc.c) {298 return299 }300 }301 }302}303304// cellsOf yields the cells at the addresses of keys, skipping any no305// longer stored.306func (st *cellStore) cellsOf(keys iter.Seq[Addr]) iter.Seq2[Addr, *Cell] {307 return func(yield func(Addr, *Cell) bool) {308 for a := range keys {309 if c := st.get(a); c != nil && !yield(a, c) {310 return311 }312 }313 }314}315316// bounds returns the smallest range holding every stored cell of r, and317// false if r holds none.318func (st *cellStore) bounds(r Rect) (Rect, bool) { return st.stored.bounds(r) }319320// colScan calls fn with each row from r0 to r1 of column c that holds a321// cell; see occupancy.colScan.322func (st *cellStore) colScan(c, r0, r1 int, fn func(row int) bool) bool {323 return st.stored.colScan(c, r0, r1, fn)324}325326// colFill writes the rows from r0 to r1 of column c that hold a cell327// into dst, until it is full; see occupancy.colFill.328func (st *cellStore) colFill(c, r0, r1 int, dst []Addr) int {329 return st.stored.colFill(c, r0, r1, dst)330}331332// inRange yields the stored cells in r in row-major order, visiting only333// the rows of each column that hold cells.334func (st *cellStore) inRange(r Rect) iter.Seq2[Addr, *Cell] { return st.cellsOf(st.keysIn(r)) }335336// valuesIn yields the values of the stored cells in r in row-major337// order, without making views of them.338func (st *cellStore) valuesIn(r Rect) iter.Seq2[Addr, Value] {339 return func(yield func(Addr, Value) bool) {340 for a := range st.keysIn(r) {341 if !yield(a, st.value(a)) {342 return343 }344 }345 }346}347348// keysIn yields the addresses of the stored cells in r in row-major349// order.350func (st *cellStore) keysIn(r Rect) iter.Seq[Addr] {351 return func(yield func(Addr) bool) {352 cols := slices.Clone(st.stored.colsIn(r.From.Col, r.To.Col))353 if len(cols) == 0 || r.From.Row > r.To.Row {354 return355 }356 b0, b1 := r.From.Row>>blockShift, r.To.Row>>blockShift357 for _, id := range st.stored.blockIDs(cols, b0, b1) {358 var in []colBlock359 for _, c := range cols {360 if st.stored.col(c).block(id) != nil {361 in = append(in, colBlock{col: c})362 }363 }364 if !st.yieldBlock(in, id, r, yield) {365 return366 }367 }368 }369}370371// rangeFill writes the stored cells of r from the cell from on, in372// row-major order, into dst until it is full, and returns how many.373func (st *cellStore) rangeFill(r Rect, from Addr, dst []Addr) int {374 n := 0375 if from.Col > r.From.Col { // the rest of a row first376 for a := range st.keysIn(Rect{From: from, To: Addr{Col: r.To.Col, Row: from.Row}}) {377 dst[n] = a378 if n++; n == len(dst) {379 return n380 }381 }382 from = Addr{Col: r.From.Col, Row: from.Row + 1}383 }384 for a := range st.keysIn(Rect{From: from, To: r.To}) {385 dst[n] = a386 if n++; n == len(dst) {387 break388 }389 }390 return n391}392393// anyInRange yields the stored cells in r in no particular order.394func (st *cellStore) anyInRange(r Rect) iter.Seq2[Addr, *Cell] {395 return st.cellsOf(st.anyKeysIn(r))396}397398// anyKeysIn yields the addresses of the stored cells in r column by399// column, which walks each block's bitmap once.400func (st *cellStore) anyKeysIn(r Rect) iter.Seq[Addr] {401 return func(yield func(Addr) bool) {402 if r.From.Row > r.To.Row {403 return404 }405 b0, b1 := r.From.Row>>blockShift, r.To.Row>>blockShift406 for _, c := range slices.Clone(st.stored.colsIn(r.From.Col, r.To.Col)) {407 if st.stored.col(c) == nil {408 continue409 }410 for _, id := range st.stored.blockIDs([]int{c}, b0, b1) {411 if !st.yieldBlock([]colBlock{{col: c}}, id, r, yield) {412 return413 }414 }415 }416 }417}418419type colBlock struct {420 col int421 b *rowBlock422}423424// yieldBlock yields the addresses of the cells of block id in the425// columns in, row by row, limited to the rows of r. Each word is read426// from the blocks as they are then, and each address checked before it427// is yielded, so cells may be set and deleted meanwhile.428func (st *cellStore) yieldBlock(in []colBlock, id int, r Rect, yield func(Addr) bool) bool {429 base := id << blockShift430 lo, hi := max(r.From.Row-base, 0), min(r.To.Row-base, blockRows-1)431 for w := lo >> 6; w <= hi>>6; w++ {432 var occ uint64433 for i := range in {434 in[i].b = st.stored.col(in[i].col).block(id)435 if in[i].b != nil {436 occ |= in[i].b.bits[w]437 }438 }439 occ &= wordMask(w, lo, hi)440 for occ != 0 {441 bit := bits.TrailingZeros64(occ)442 occ &^= 1 << bit443 row := base + w<<6 + bit444 for _, cb := range in {445 if cb.b == nil || cb.b.bits[w]&(1<<bit) == 0 {446 continue447 }448 if a := (Addr{Col: cb.col, Row: row}); st.stored.has(a) && !yield(a) {449 return false450 }451 }452 }453 }454 return true455}