1package sheet23import "slices"45// MaxUndoBytes caps the memory the undo history's before-images hold, as6// estimated by step.size. When a new step takes the history past it, the7// oldest steps are dropped first; the newest step is always kept, however8// large, so any single change can be undone (a step past MaxStepBytes9// asks first). 256 MB holds a step clearing a full max-cells sheet of10// numbers, about 195 MB, and MaxUndo steps rewriting a whole column of11// 8192 take 16 MB (see docs/contributing/limits.md).12const MaxUndoBytes = 256 << 201314// undoBudget is MaxUndoBytes; tests lower it.15var undoBudget int64 = MaxUndoBytes1617// Estimated heap held by the parts of a step. A plain cell's18// before-image is a slot (slotBytes) and its text, once per image (see19// historyimage.go); a rich one is also a Cell (216 B) with its input,20// and a formula keeps its parsed tree and reference lists alive, which21// grow with its text. The constants match the heap measured by the22// stress benchmarks (BenchmarkHistoryFull, BenchmarkHistoryWide,23// BenchmarkClearMax) within about 10%.24const (25 stepBytes = 512 // the step and its empty maps26 entryBytes = 64 // a map entry: the key and a pointer27 imageBytes = 256 // a sheet's image, empty28 cellBytes = 256 // a Cell, its input's header and its boxed literal29 formulaBytes = 256 // a parsed formula's tree and references, plus perFormulaByte per byte of text30 perFormulaByte = 1631 chartBytes = 12832 ruleBytes = 256 // a rule with its ranges and values33)3435// keep records the cell at a of s as it stands, unless the step holds36// it already, and counts it.37func (st *step) keep(s *Sheet, a Addr) {38 img := st.cells[s]39 if img == nil {40 img = &image{}41 st.cells[s] = img42 st.cellBytes += imageBytes43 }44 if !img.seen(a) {45 st.cellBytes += img.keep(&s.cells, a)46 }47}4849// size estimates the heap a finished step holds: its cells, counted as50// they were recorded, and the rest, which is small.51func (st *step) size() int64 {52 n := stepBytes + st.cellBytes53 n += int64(len(st.widths)+len(st.heights)+len(st.lines)+len(st.names)+len(st.views)) * entryBytes54 for _, charts := range st.charts {55 n += entryBytes + int64(len(charts))*chartBytes56 }57 for _, r := range st.rules {58 n += entryBytes + int64(len(r.formats)+len(r.validations))*ruleBytes59 }60 for _, r := range st.regions {61 n += entryBytes + int64(len(r.list))*ruleBytes62 }63 if st.sheets != nil {64 n += int64(len(st.sheets.order)) * 2 * entryBytes65 }66 return n67}6869// cellSize estimates the heap one before-image holds; nil stands for a70// blank cell.71func cellSize(c *Cell) int64 {72 if c == nil {73 return 074 }75 n := int64(cellBytes + len(c.Input))76 if c.IsFormula() {77 n += formulaBytes + perFormulaByte*int64(len(c.Input))78 }79 return n80}8182// deletedSize estimates the cells held by sheets a step's sheet list83// has that the workbook no longer does: a deleted sheet keeps its cells84// so undo can bring it back.85func (w *Workbook) deletedSize(st *step) int64 {86 if st.sheets == nil {87 return 088 }89 var n int6490 for _, s := range st.sheets.order {91 if !slices.Contains(w.sheets, s) {92 n += s.cells.size()93 }94 }95 return n96}9798// pushUndo adds st to the undo stack with its size, then drops the99// oldest steps while the history holds more than MaxUndo steps or more100// than the byte budget.101func (w *Workbook) pushUndo(st *step) {102 h := &w.hist103 st.bytes = st.size() + w.deletedSize(st)104 h.undo = append(h.undo, st)105 h.bytes += st.bytes106 drop := 0107 for len(h.undo)-drop > MaxUndo || h.bytes > undoBudget && len(h.undo)-drop > 1 {108 h.bytes -= h.undo[drop].bytes109 drop++110 }111 if drop > 0 {112 clear(h.undo[:drop])113 h.undo = h.undo[drop:]114 }115}116117// popUndo removes and returns the top of the undo stack.118func (h *history) popUndo() *step {119 st := h.undo[len(h.undo)-1]120 h.undo = h.undo[:len(h.undo)-1]121 h.bytes -= st.bytes122 return st123}124125// HistoryBytes estimates the memory the undo steps hold.126func (w *Workbook) HistoryBytes() int64 { return w.hist.bytes }127128// MaxStepBytes is the most undo history one change may hold without129// asking: the UI asks before a change its UndoCost puts over it, and runs130// it WithoutUndo if told to go on. Plain cells cost about 20 B each, so131// only millions of formulas or of distinct long texts come near it.132const MaxStepBytes = 1 << 30133134// UndoCost estimates the undo history a change to every cell of r would135// hold: a slot a cell, the rich cells in r whole, and r's share of the136// sheet's strings. The UI asks it before every command that edits, so137// it costs the fewer of r's cells and the sheet's rich cells.138func (s *Sheet) UndoCost(r Rect) int64 {139 st := &s.cells140 cells := 0141 for _, c := range st.stored.colsIn(r.From.Col, r.To.Col) {142 cells += st.stored.countIn(c, r.From.Row, r.To.Row)143 }144 if cells == 0 {145 return 0146 }147 n := int64(cells)*slotBytes + st.strs.bytes*int64(cells)/int64(st.len())148 add := func(c *Cell) { n += richBytes + cellSize(c) }149 if cells < len(st.rich)-len(st.richFree) { // the cheaper way to find r's rich cells150 for a := range st.anyKeysIn(r) {151 if c := st.richAt(a); c != nil {152 add(c)153 }154 }155 return n156 }157 for _, rc := range st.rich {158 if rc.c != nil && r.Contains(rc.a) {159 add(rc.c)160 }161 }162 return n163}164165// WithoutUndo runs fn, a change too large to undo (see MaxStepBytes),166// recording no before-images, and forgets the undo history, which could167// no longer be undone past it. Inside a Batch it runs fn as part of it.168func (w *Workbook) WithoutUndo(fn func()) {169 h := &w.hist170 if h.depth > 0 {171 fn()172 return173 }174 h.off = true175 defer func() {176 id := h.lastID + 1177 w.hist = history{lastID: id, base: id}178 }()179 fn()180}