1package sheet23import (4 "math"5 "strconv"6 "strings"78 "src.rest/cat/012/internal/formula"9)1011// A slot is how cellStore keeps one cell: 16 bytes in its column's12// block. Most cells are plain, an entry typed or imported that is a13// number, a boolean or text, with at most a format and a style; their14// slot holds the value itself, the text in the store's string table, the15// format and style in its table of looks, and the input only when it16// isn't the value's own text. What pivots and spills write (derived17// cells) is a slot too, marked by its kind: the value alone, its entry18// being the value's text (derivedInput), and a spill's inferred format19// in its look. Everything else (formulas, notes, text typed with a20// leading ') is rich: the slot points at a whole Cell in the store's21// side table.22type slot struct {23 num float64 // slotNum's value; slotBool's, 1 or 024 // ref is slotText's text in strs; slotNum's or slotBool's input in25 // strs when it isn't the value's text (0 when it is); slotRich's cell26 // in rich.27 ref uint3228 look uint16 // the format, style and inferred format in looks; 0 for none29 // kind is one of the kinds below, with slotPivot or slotSpill added30 // for a derived cell.31 kind uint832 // dec is how a slotNum without ref prints its input: the value with33 // dec-1 decimals, or its shortest text when 0.34 dec uint835}3637// Kinds of slot.38const (39 slotBlank uint8 = iota // formatting only40 slotNum41 slotBool42 slotText43 slotRich44 slotErr // a derived cell's error value, its code in strs45)4647// Marks of a derived cell's slot, added to its kind: a pivot's result48// (Cell.derived) or part of a spilled array (Cell.spilled).49const (50 slotPivot uint8 = 1 << 651 slotSpill uint8 = 1 << 752 slotDerived = slotPivot | slotSpill53)5455// base is sl's kind without the marks of a derived cell.56func (sl slot) base() uint8 { return sl.kind &^ slotDerived }5758// maxDec bounds the decimals a number's input may have to be kept as a59// count rather than as text.60const maxDec = 406162// look is a cell's format and style, and a spilled cell's inferred63// format, kept once per store however many cells share it.64type look struct {65 f Format66 st Style67 auto Format68}6970// strTable holds the text of plain cells, each distinct string once,71// counted by the cells using it; entry 0 is unused.72type strTable struct {73 strs []string74 refs []uint3275 index map[string]uint3276 free []uint3277 bytes int64 // the estimated heap the strings hold, strBytes and their text each78}7980// add counts one more use of s and returns its entry.81func (t *strTable) add(s string) uint32 {82 if i, ok := t.index[s]; ok {83 t.refs[i]++84 return i85 }86 if t.index == nil {87 t.index = map[string]uint32{}88 t.strs, t.refs = []string{""}, []uint32{0}89 }90 var i uint3291 if n := len(t.free); n > 0 {92 i, t.free = t.free[n-1], t.free[:n-1]93 t.strs[i], t.refs[i] = s, 194 } else {95 i = uint32(len(t.strs))96 t.strs, t.refs = append(t.strs, s), append(t.refs, 1)97 }98 t.index[s] = i99 t.bytes += strBytes + int64(len(s))100 return i101}102103// release counts one fewer use of entry i, if it is one.104func (t *strTable) release(i uint32) {105 if i == 0 {106 return107 }108 if t.refs[i]--; t.refs[i] == 0 {109 t.bytes -= strBytes + int64(len(t.strs[i]))110 delete(t.index, t.strs[i])111 t.strs[i] = ""112 t.free = append(t.free, i)113 }114}115116// lookID is the entry of l in the table of looks, added if new, and117// false when the table is full.118func (st *cellStore) lookID(l look) (uint16, bool) {119 if l == (look{}) {120 return 0, true121 }122 if i, ok := st.lookIdx[l]; ok {123 return i, true124 }125 if len(st.looks) > math.MaxUint16 {126 return 0, false127 }128 if st.lookIdx == nil {129 st.lookIdx = map[look]uint16{}130 st.looks = []look{{}}131 }132 i := uint16(len(st.looks))133 st.looks = append(st.looks, l)134 st.lookIdx[l] = i135 return i, true136}137138// lookOf is sl's look, which the caller mustn't change.139func (st *cellStore) lookOf(sl slot) *look {140 if sl.look == 0 {141 return &noLook142 }143 return &st.looks[sl.look]144}145146// noLook is the look of a slot without one, never written.147var noLook look148149// plainSlot is c as a plain slot, or false if c is rich. It adds the150// strings it uses to the table.151func (st *cellStore) plainSlot(c *Cell) (slot, bool) {152 switch {153 case c.Note != "" || c.typedText:154 return slot{}, false155 case c.derived || c.spilled:156 return st.derivedSlot(c)157 case !c.auto.IsZero() || strings.HasPrefix(c.Input, "="):158 return slot{}, false159 }160 lk, ok := st.lookID(look{f: c.Format, st: c.Style})161 if !ok {162 return slot{}, false163 }164 sl := slot{look: lk}165 switch e := c.expr.(type) {166 case nil:167 switch {168 case c.Input == "":169 sl.kind = slotBlank170 case c.Format.Kind != FmtText && strings.HasPrefix(c.Input, "'"):171 return slot{}, false // its value isn't its input172 default:173 sl.kind, sl.ref = slotText, st.strs.add(c.Input)174 }175 case formula.Num:176 if math.IsNaN(e.V) || math.IsInf(e.V, 0) {177 return slot{}, false // its value is #NUM!178 }179 sl.kind, sl.num = slotNum, e.V180 if d, ok := numDec(e.V, c.Input); ok {181 sl.dec = d182 } else {183 sl.ref = st.strs.add(c.Input)184 }185 case formula.Bool:186 sl.kind = slotBool187 if e.V {188 sl.num = 1189 }190 if c.Input != boolText(e.V) {191 sl.ref = st.strs.add(c.Input)192 }193 default:194 return slot{}, false195 }196 return sl, true197}198199// derivedSlot is plainSlot for a derived cell without a note: its value,200// marked with what derived it, its entry being the value's text.201func (st *cellStore) derivedSlot(c *Cell) (slot, bool) {202 if c.expr != nil {203 return slot{}, false204 }205 lk, ok := st.lookID(look{c.Format, c.Style, c.auto})206 if !ok {207 return slot{}, false208 }209 return st.derivedValue(c.Value, lk, c.derived), true210}211212// derivedValue is the slot of a derived cell showing v with look lk: a213// pivot's result if pivot, else a spilled cell. It adds the string v214// uses to the table.215func (st *cellStore) derivedValue(v Value, lk uint16, pivot bool) slot {216 sl := slot{look: lk, kind: slotSpill}217 if pivot {218 sl.kind = slotPivot219 }220 switch v.Kind {221 case Number:222 sl.kind |= slotNum223 sl.num = v.Num224 case Bool:225 sl.kind |= slotBool226 sl.num = v.Num227 case Text:228 sl.kind |= slotText229 sl.ref = st.strs.add(v.Str)230 case Error:231 sl.kind |= slotErr232 sl.ref = st.strs.add(v.Str)233 }234 return sl235}236237// numDec is how input prints v, as slot.dec, or false if it isn't v238// printed plainly.239func numDec(v float64, input string) (uint8, bool) {240 if d, ok := plainDec(v, input); ok {241 return d, true242 }243 var buf [64]byte244 if string(strconv.AppendFloat(buf[:0], v, 'f', -1, 64)) == input {245 return 0, true246 }247 i := strings.IndexByte(input, '.')248 if i < 0 || len(input)-i-1 >= maxDec {249 return 0, false250 }251 d := len(input) - i - 1252 if string(strconv.AppendFloat(buf[:0], v, 'f', d, 64)) == input {253 return uint8(d + 1), true254 }255 return 0, false256}257258// plainDec is numDec for the common input, a plain decimal (see259// plainForm) that is v, found without printing v. It reports false for260// any other input, which numDec then prints v to compare.261func plainDec(v float64, input string) (uint8, bool) {262 d, ok := plainForm(input)263 if !ok {264 return 0, false265 }266 if p, err := strconv.ParseFloat(input, 64); err != nil || math.Float64bits(p) != math.Float64bits(v) {267 return 0, false268 }269 return d, true270}271272// plainForm reports whether input is a plain decimal, of at most 15273// significant digits without a sign but "-", leading zeros or an274// exponent, and returns how it prints its value as slot.dec. Such a275// decimal is its value's shortest text when it doesn't end in a zero276// after the point, and its value printed with as many decimals as it277// has otherwise: 15 digits always come back from a float64.278func plainForm(input string) (uint8, bool) {279 s := input280 if s != "" && s[0] == '-' {281 s = s[1:]282 }283 if s == "" || s[0] == '0' && len(s) > 1 && s[1] != '.' {284 return 0, false285 }286 point, digits, lead := -1, 0, true287 for i := 0; i < len(s); i++ {288 switch c := s[i]; {289 case c == '.' && point < 0 && i > 0 && i < len(s)-1:290 point = i291 case c >= '0' && c <= '9':292 if lead = lead && c == '0'; !lead {293 digits++294 }295 default:296 return 0, false297 }298 }299 d := 0300 if point >= 0 {301 d = len(s) - point - 1302 }303 if digits > 15 || d >= maxDec {304 return 0, false305 }306 if d == 0 || s[len(s)-1] != '0' {307 return 0, true308 }309 return uint8(d + 1), true310}311312func boolText(b bool) string {313 if b {314 return "TRUE"315 }316 return "FALSE"317}318319// input is the entry of a plain slot. A derived slot's is its value's320// text, as derivedInput writes it: a number's shortest text, TRUE or321// FALSE, the text or the error code.322func (st *cellStore) input(sl slot) string {323 switch {324 case sl.base() == slotBlank:325 return ""326 case sl.ref != 0:327 return st.strs.strs[sl.ref]328 case sl.base() == slotBool:329 return boolText(sl.num != 0)330 }331 return strconv.FormatFloat(sl.num, 'f', int(sl.dec)-1, 64)332}333334// slotValue is the value of a plain slot.335func (st *cellStore) slotValue(sl slot) Value {336 switch sl.base() {337 case slotNum:338 return Value{Kind: Number, Num: sl.num}339 case slotBool:340 return Value{Kind: Bool, Num: sl.num}341 case slotText:342 return Value{Kind: Text, Str: st.strs.strs[sl.ref]}343 case slotErr:344 return Value{Kind: Error, Str: st.strs.strs[sl.ref]}345 }346 return Value{}347}348349// view is a plain slot as a Cell of its own: changing it changes nothing350// stored.351func (st *cellStore) view(sl slot) *Cell {352 lk := st.lookOf(sl)353 c := &Cell{Input: st.input(sl), Value: st.slotValue(sl), Format: lk.f, Style: lk.st}354 if sl.kind&slotDerived != 0 { // a derived cell has no expression355 c.auto, c.derived, c.spilled = lk.auto, sl.kind&slotPivot != 0, sl.kind&slotSpill != 0356 return c357 }358 switch sl.kind {359 case slotNum:360 c.expr = formula.Num{V: sl.num}361 case slotBool:362 c.expr = formula.Bool{V: sl.num != 0}363 }364 return c365}366367// releaseSlot counts one fewer use of what sl refers to.368func (st *cellStore) releaseSlot(sl slot) {369 switch sl.base() {370 case slotRich:371 st.rich[sl.ref] = richCell{}372 st.richFree = append(st.richFree, sl.ref)373 case slotNum, slotBool, slotText, slotErr:374 st.strs.release(sl.ref)375 }376}377378// Estimated heap of the store's parts, for the undo history's budget379// (historysize.go): a slot with its share of the blocks and indexes, as380// BenchmarkMemory measures it, and a string's entry in the table.381const (382 slotBytes = 20383 strBytes = 64384)385386// size estimates the heap the cells hold: a slot each, and the rich387// cells and strings on top.388func (st *cellStore) size() int64 {389 n := int64(st.len()) * slotBytes390 for _, rc := range st.rich {391 n += cellSize(rc.c)392 }393 return n + st.strs.bytes394}395396// richCell is a rich cell and where it is.397type richCell struct {398 c *Cell399 a Addr400}401402// addRich stores c, at a, in the side table and returns its entry.403func (st *cellStore) addRich(a Addr, c *Cell) uint32 {404 if n := len(st.richFree); n > 0 {405 i := st.richFree[n-1]406 st.richFree = st.richFree[:n-1]407 st.rich[i] = richCell{c, a}408 return i409 }410 st.rich = append(st.rich, richCell{c, a})411 return uint32(len(st.rich) - 1)412}