1// Package sheet is the spreadsheet engine: cell storage, formula parsing and2// dependency-ordered recalculation. It has no knowledge of the terminal UI.3package sheet45import (6 "maps"7 "sort"8 "strings"9 "unicode"1011 "src.rest/cat/012/internal/formula"12 "src.rest/cat/012/internal/functions"13)1415// DefaultWidth is the initial column width: nine characters plus padding.16const DefaultWidth = 101718// Cell holds what the user typed, what it evaluates to, and how it is19// formatted. A cell may have formatting but no contents (Sheets lets you20// format blank cells before typing); such a cell counts as blank21// everywhere contents matter.22type Cell struct {23 // Input is the entry exactly as typed: text, a number such as "$1,200"24 // or "12%", or a formula starting with "=". Empty for a blank cell25 // that only has formatting.26 Input string27 Value Value2829 // Format and Style are plain values, so copying a Cell copies its30 // formatting. They survive clearing the contents, as in Sheets.31 // Style is kept at the end, with the flags, where it fits in what32 // alignment would otherwise pad, so a Cell stays 256 bytes.33 Format Format3435 // Note is the cell's note, as Sheets' Insert > Note: text shown when36 // the cell is active or hovered. Like formatting, it survives clearing37 // the contents, and it moves and copies with the cell.38 Note string3940 auto Format // format inferred from a formula, shown when Format is Automatic41 expr Node // nil for text42 refs []Addr // single-cell references in expr to its own sheet43 ranges []Rect // range references in expr to its own sheet44 xrefs []xref // references that name a sheet, e.g. Sheet2!A145 names []string // names and tables in expr, as keys of Workbook.names and tables46 Style Style47 volatile bool // expr calls TODAY, NOW, RAND...48 derived bool // a pivot table's result, owned by the engine: see pivot.go49 spilled bool // part of an array a formula spills, owned by it: see spill.go50 // typedText marks text typed into a Plain text cell that would read51 // as a number or formula, or not at all, typed into a cell of another52 // format: it stays text when the cell's format changes, as in Sheets,53 // until it's typed again.54 typedText bool55}5657// Spilled reports whether the cell shows part of an array another58// cell's formula computed (see SpillAnchor).59func (c *Cell) Spilled() bool { return c != nil && c.spilled }6061// IsFormula reports whether the cell holds a formula.62func (c *Cell) IsFormula() bool {63 return c.expr != nil && IsFormulaEntry(c.Input)64}6566// Blank reports whether the cell has no contents (it may still have67// formatting).68func (c *Cell) Blank() bool { return c == nil || c.Input == "" }6970// Sheet is a sparse worksheet, one of a Workbook's sheets.71type Sheet struct {72 wb *Workbook73 name string74 live bool // in the workbook's list; false once deleted75 tabHidden bool // left out of the tabs; see hidden.go7677 cells cellStore // see store.go78 widths map[int]int79 heights map[int]int // rows' heights set by hand, in lines; see rowlayout.go80 lines lineFormats // column and row formats, see lines.go81 shapers shaperIndex // the cells that wrap or draw borders, see rowlayout.go8283 // dependents maps a cell to the formula cells that reference it84 // directly. Range references are kept on the formula cell itself and85 // found through rangeUsers, by column, so a huge range doesn't create86 // millions of edges.87 dependents map[Addr]map[Addr]struct{}88 rangeUsers rangeIndex89 volatile map[Addr]struct{} // formulas recalculated on every change9091 // version counts changes to cells and their values, so what is derived92 // from them can be cached; see RangeStats.93 version uint6494 stats statsCache9596 // calc is the recalculation state of cells while the workbook97 // recalculates, with calcGet and calcFmt, the lookups its formulas98 // read other cells and formats with; all nil otherwise.99 calc map[Addr]int100 calcGet *reader101 calcFmt func(string, Addr) Format102 // calcPaged reports whether a sheet is a linked source's tab, whose103 // counts show as whole numbers.104 calcPaged func(string) bool105 // recalcs is calcGet kept between recalculations, so the buffers the106 // function library reads ranges through are made once.107 recalcs *reader108109 charts []Chart // floating charts, bottom first; see chart.go110 pivot pivotState // the sheet's pivot table, if any; see pivot.go111112 // spills are the arrays formulas spill, by the anchor's address, and113 // spillAt the anchors by the cells they cover; see spill.go.114 spills map[Addr]*spill115 spillAt rangeIndex116117 view viewState // frozen panes, the filter and merges, see view.go118 mergeIdx mergeIndex // the merges by the cells they cover, see merge.go119 hidden hiddenCache // rows the filter hides, see filter.go120121 rules rulesState // conditional formats and data validation, see rules.go122 looks looksCache // how the rules draw cells, see looks.go123124 // regions are the sheet's regions and, on a notebook tab, its cells;125 // regionMeta what isn't undone of the regions; regionsStale has their126 // cells written again once the change ends. See region.go and127 // notebook.go.128 regions regionState129 regionMeta map[string]*regionMeta130 regionsStale bool131}132133// New returns an empty worksheet, the only sheet of a new workbook.134func New() *Sheet {135 return NewBook().Sheet(0)136}137138// Cell returns the cell at a, or nil if it has neither contents nor139// formatting. Use Blank to test for contents.140func (s *Sheet) Cell(a Addr) *Cell { return s.cells.get(a) }141142// Filled reports whether the cell at a has contents: !Cell(a).Blank(),143// without making the cell.144func (s *Sheet) Filled(a Addr) bool { return s.cells.filledAt(a) }145146// Value returns the computed value at a.147func (s *Sheet) Value(a Addr) Value { return s.cells.value(a) }148149// Len returns the number of non-blank cells.150func (s *Sheet) Len() int { return s.cells.filledLen() }151152// Addrs returns every non-blank cell in row-major order.153func (s *Sheet) Addrs() []Addr {154 out := make([]Addr, 0, s.cells.filledLen())155 for a := range s.cells.keys() {156 if s.cells.filledAt(a) {157 out = append(out, a)158 }159 }160 sortAddrs(out)161 return out162}163164func sortAddrs(out []Addr) {165 sort.Slice(out, func(i, j int) bool {166 if out[i].Row != out[j].Row {167 return out[i].Row < out[j].Row168 }169 return out[i].Col < out[j].Col170 })171}172173// ColWidth returns the display width of column c.174func (s *Sheet) ColWidth(c int) int {175 if w, ok := s.widths[c]; ok {176 return w177 }178 return DefaultWidth179}180181// SetColWidth sets column c's width; w <= 0 resets it to the default.182func (s *Sheet) SetColWidth(c, w int) {183 s.pivot.fit = false // the user's widths win over the pivot's184 s.change("column width", colRect(c, c), func() { s.setWidth(c, w) })185}186187func (s *Sheet) setWidth(c, w int) {188 s.recordWidth(c)189 s.version++ // wrapped text may take other lines190 if w <= 0 || w == DefaultWidth { // keep the map to non-default widths191 delete(s.widths, c)192 return193 }194 s.widths[c] = min(w, 240)195}196197// Widths returns the columns that have a non-default width.198func (s *Sheet) Widths() map[int]int {199 return maps.Clone(s.widths)200}201202// IsFormulaEntry reports whether input is written as a formula: it starts203// with "=", or with "+" or "-" followed by something that isn't a plain204// number (as Sheets accepts "+A1").205func IsFormulaEntry(input string) bool {206 if strings.HasPrefix(input, "=") {207 return true208 }209 if !strings.HasPrefix(input, "+") && !strings.HasPrefix(input, "-") {210 return false211 }212 if _, _, isNum := ParseValue(input); isNum {213 return false214 }215 _, err := Parse(input)216 return err == nil217}218219// classify turns an entry into an expression, or nil for text, and220// returns the format the entry implies (Currency for "$5", Date for221// "9/26/2026"). Entries starting with ' are always text.222func classify(input string) (Node, Format, error) {223 if strings.HasPrefix(input, "'") {224 return nil, Format{}, nil225 }226 if v, f, ok := ParseValue(input); ok {227 return formula.Num{V: v}, f, nil228 }229 switch strings.ToUpper(input) {230 case "TRUE":231 return formula.Bool{V: true}, Format{}, nil232 case "FALSE":233 return formula.Bool{V: false}, Format{}, nil234 }235 if IsFormulaEntry(input) {236 n, err := Parse(input)237 return n, Format{}, err238 }239 return nil, Format{}, nil240}241242// Set stores an entry at a and recalculates affected cells. An empty input243// erases the contents but keeps the cell's formatting. A formula that244// fails to parse is rejected with a *ParseError and the sheet is left245// unchanged. A pivot table's results can't be set: that's ErrPivotEdit.246func (s *Sheet) Set(a Addr, input string) error {247 if s.InPivot(Rect{From: a, To: a}) {248 return ErrPivotEdit249 }250 if _, ok := s.SpillAnchor(a); ok {251 return ErrSpillEdit252 }253 if s.IsSource() {254 return ErrSourceEdit255 }256 if r, ok := s.RegionAt(a); ok {257 if r.Linked() {258 return ErrLinkedEdit259 }260 return ErrOutputEdit261 }262 var err error263 s.change("edit "+a.String(), Rect{From: a, To: a}, func() { err = s.put(a, input) })264 return err265}266267// put stores an entry without recalculating, keeping the cell's268// formatting.269func (s *Sheet) put(a Addr, input string) error {270 f, st, _ := s.cells.look(a)271 note := s.Note(a)272 if f.IsZero() && !st.own && s.inherited(a).Format.Kind == FmtText {273 f = Format{Kind: FmtText} // typed into a plain text column: text274 }275 c, err := newCell(input, f, st, true)276 if err != nil {277 return err278 }279 s.place(a, c.withNote(note))280 return nil281}282283// newCell builds a cell for an entry with formatting, or returns nil when284// there is neither. With implied, an entry that implies a format, such as285// "$5" or a date, sets it, as in Sheets. In a Plain text cell every entry286// is text. Control characters are dropped so a worksheet file can't287// smuggle escape sequences to the terminal.288func newCell(input string, f Format, st Style, implied bool) (*Cell, error) {289 return readEntry(input, f, st, implied, f.Kind == FmtText)290}291292// readEntry is newCell reading the entry as text when asText, and as293// typed into a cell of another format than Plain text otherwise, as a294// file says to of an entry typed before its cell's format changed.295func readEntry(input string, f Format, st Style, implied, asText bool) (*Cell, error) {296 input = strings.Map(func(r rune) rune {297 if unicode.IsControl(r) {298 return -1299 }300 return r301 }, input)302 if input == "" {303 return formattingOnly(f, st), nil304 }305 var n Node306 if !asText {307 var fi Format308 var err error309 if n, fi, err = classify(input); err != nil {310 return nil, err311 }312 if implied && !fi.IsZero() && f.Kind != FmtText {313 f = fi314 }315 }316 c := &Cell{Input: input, Format: f, Style: st, typedText: asText && readsOtherwise(input)}317 c.setExpr(n)318 return c, nil319}320321// readsOtherwise reports whether an entry typed as text reads as322// something else, or not at all, typed into a cell of another format.323func readsOtherwise(input string) bool {324 n, _, err := classify(input)325 return n != nil || err != nil326}327328// formattingOnly is a blank cell holding formatting, or nil when there is329// none.330func formattingOnly(f Format, st Style) *Cell {331 if f.IsZero() && st.IsZero() {332 return nil333 }334 return &Cell{Format: f, Style: st}335}336337// leftover is what clearing c's contents leaves: its formatting and its338// note, or nil when there are neither.339func (c *Cell) leftover() *Cell {340 return formattingOnly(c.Format, c.Style).withNote(c.Note)341}342343// withNote returns c with note, making a blank cell to hold it if c is344// nil. c must be a cell not yet placed.345func (c *Cell) withNote(note string) *Cell {346 if note == "" {347 return c348 }349 if c == nil {350 c = &Cell{}351 }352 c.Note = note353 return c354}355356// setExpr sets c's expression and the references indexed from it.357func (c *Cell) setExpr(n Node) {358 c.expr, c.refs, c.ranges, c.xrefs, c.names, c.volatile = n, nil, nil, nil, nil, false359 if n != nil {360 formula.WalkRefs(n,361 func(sheet string, r Addr) {362 if sheet != "" {363 c.xrefs = append(c.xrefs, xref{formula.SheetKey(sheet), Rect{From: r, To: r}})364 return365 }366 c.refs = append(c.refs, r)367 },368 func(sheet string, r Rect) {369 if sheet != "" {370 c.xrefs = append(c.xrefs, xref{formula.SheetKey(sheet), r})371 return372 }373 c.ranges = append(c.ranges, r)374 })375 formula.WalkNames(n, func(nn formula.Name) { c.names = append(c.names, nameKey(nn.Name)) })376 formula.WalkTables(n, func(t formula.TableRef) { c.names = append(c.names, nameKey(t.Table)) })377 c.volatile = functions.IsVolatile(n)378 }379}380381// place stores c at a (nil blanks it), recording the old cell for undo and382// keeping the dependency indexes current. Every cell mutation goes through383// here, except a pivot table or a spill writing its results (setDerived).384// Anything placed over those has the pivot or the spill's formula385// recomputed, which reports it in the way. A spilled cell placed (by undo,386// a move or a format) places only its formatting and note: its value is387// its anchor's to write.388func (s *Sheet) place(a Addr, c *Cell) {389 s.version++390 s.record(a)391 if s.pivot.def != nil && (s.pivot.out.Contains(a) || s.pivot.err != "" && s.pivot.blocked.Contains(a)) {392 s.pivot.stale = true393 }394 if c.Spilled() {395 c = c.leftover()396 }397 if len(s.regions.list) > 0 {398 if _, _, ok := s.ownerOf(a); ok {399 // A region's cell keeps its value: only its formatting and400 // note are placed.401 v, lk, _ := s.cells.derivedOf(a)402 defer s.writeSpilled(a, v, lk.auto)403 if c != nil {404 c = c.leftover()405 }406 }407 s.regionTouched(a, c)408 }409 s.trackShape(a, c)410 s.spillTouched(a, c)411 if c == nil {412 s.unlink(a)413 return414 }415 s.unindex(a) // the old cell's edges; set replaces it in the store416 s.cells.set(a, c)417 for _, r := range c.refs {418 if s.dependents[r] == nil {419 s.dependents[r] = make(map[Addr]struct{})420 }421 s.dependents[r][a] = struct{}{}422 }423 s.rangeUsers.add(a, c.ranges)424 if c.volatile {425 s.volatile[a] = struct{}{}426 }427 if s.live {428 s.wb.index(loc{s, a}, c)429 }430}431432// EraseRange clears the contents of every cell in r, keeping their433// formatting and notes as Sheets' Delete does.434func (s *Sheet) EraseRange(r Rect) {435 s.change("clear "+r.String(), r, func() {436 for _, a := range s.cellsIn(r) {437 if s.cells.filledAt(a) {438 f, st, _ := s.cells.look(a)439 s.place(a, formattingOnly(f, st).withNote(s.Note(a)))440 }441 }442 })443}444445// cellsIn returns the cells in r that have contents or formatting.446func (s *Sheet) cellsIn(r Rect) []Addr {447 var out []Addr448 for a := range s.cells.anyKeysIn(r) {449 out = append(out, a)450 }451 return out452}453454// unlink removes the cell at a and its dependency edges.455func (s *Sheet) unlink(a Addr) {456 if s.unindex(a) {457 s.cells.delete(a)458 }459}460461// unindex removes the dependency edges of the cell at a, reporting462// whether there is one.463func (s *Sheet) unindex(a Addr) bool {464 old := s.cells.richAt(a) // plain cells have no edges465 if old == nil {466 return s.cells.has(a)467 }468 for _, r := range old.refs {469 delete(s.dependents[r], a)470 if len(s.dependents[r]) == 0 {471 delete(s.dependents, r)472 }473 }474 if s.live {475 s.wb.unindex(loc{s, a}, old)476 }477 s.rangeUsers.remove(a, old.ranges)478 delete(s.volatile, a)479 return true480}