1package sheet23import "slices"45// Authors: a workbook several people edit at once (012 serve's shared6// rooms) is still changed through the one mutation path, Batch and the7// history's steps, in the one order the server runs them in. Each step8// records its author (SetAuthor names who is acting) and a sequence9// number, and the steps made, undone and redone are a stream of10// operations (Op) the room sends every participant.11//12// With the history shared (ShareHistory), Undo and Redo take back only13// the author's own steps: Undo reverts the author's latest step even14// when others' steps came after it, as long as none of those changed15// what it changed (the same cells, widths, heights, line formats or16// names; the same sheet's charts, pivot, rules, regions or view; the17// sheet list, the settings or the macros), and none of them, nor it,18// inserted or deleted rows or columns on a sheet the other changed. The19// step then leaves the middle of the history, and the later steps stay20// as they are, their before-images still true: they touched none of21// what it restores. Otherwise Undo refuses, and UndoBlocked says whose22// step is in the way. Redo takes back the author's latest undo on the23// same terms, against the steps made since. Formulas that read what an24// undone step changed recalculate; entries typed after it that don't25// overlap it stay as typed.2627// OpKind is what an operation did to the history.28type OpKind int2930const (31 OpDo OpKind = iota // a step made32 OpUndo // a step undone33 OpRedo // a step redone34)3536// Op is one operation in the order the workbook ran it: a step made,37// undone or redone, by its author, with what the step says of itself.38type Op struct {39 Seq uint64 // its place in the order, from 140 Author int41 Kind OpKind42 Change43}4445// opLogSize is how many of the latest operations the workbook keeps for46// OpsSince.47const opLogSize = 2564849// Blocked is a later step that keeps an author's step from being50// undone or redone: whose it is, and what it did.51type Blocked struct {52 Author int53 Label string54}5556// SetAuthor names who makes the steps that follow; 0 is nobody in57// particular, as in a workbook only one person edits.58func (w *Workbook) SetAuthor(a int) { w.author = a }5960// Author is who makes the steps that follow (SetAuthor).61func (w *Workbook) Author() int { return w.author }6263// ShareHistory has undo and redo take back only each author's own64// steps, from now on.65func (w *Workbook) ShareHistory() { w.hist.shared = true }6667// Adopt makes the steps of nobody in particular (author 0), made while68// one person edited alone, the author's: a session sharing its workbook69// from then on keeps its person's earlier steps theirs to undo.70func (w *Workbook) Adopt(author int) {71 for _, st := range w.hist.undo {72 if st.author == 0 {73 st.author = author74 }75 }76 for _, st := range w.hist.redo {77 if st.author == 0 {78 st.author = author79 }80 }81}8283// Version changes whenever the workbook changes: a step made, undone or84// redone, a recalculation, rows arriving at a region.85func (w *Workbook) Version() uint64 { return w.gen + w.hist.seq }8687// OpsSince is the operations after seq, the last opLogSize at most, and88// the sequence number of the latest.89func (w *Workbook) OpsSince(seq uint64) ([]Op, uint64) {90 h := &w.hist91 i, _ := slices.BinarySearchFunc(h.log, seq+1, func(o Op, s uint64) int { return int(o.Seq) - int(s) })92 return slices.Clone(h.log[i:]), h.seq93}9495// Checkpoint marks where the history stands, for UndoTo.96func (w *Workbook) Checkpoint() int { return int(w.hist.seq) }9798// UndoTo undoes the current author's steps made after checkpoint c, as99// cancelling a dialog does, whatever others changed meanwhile; it stops100// at a step it can't undo.101func (w *Workbook) UndoTo(c int) {102 h := &w.hist103 for i := h.mine(w.author); i >= 0 && h.undo[i].seq > uint64(c); i = h.mine(w.author) {104 if _, ok := w.Undo(); !ok {105 return106 }107 }108}109110// LastOp is the latest operation's sequence number, 0 before any.111func (w *Workbook) LastOp() uint64 { return w.hist.seq }112113// EndStep closes the step left open (Begin) by a participant who is114// gone, as if they had ended it: what it did stays, one step.115func (w *Workbook) EndStep() {116 for w.hist.depth > 0 {117 w.finish()118 }119}120121// InStep reports whether a step is open (Begin, a macro running), and122// whose it is.123func (w *Workbook) InStep() (bool, int) {124 if w.hist.open == nil {125 return false, 0126 }127 return true, w.hist.open.author128}129130// logOp notes an operation in the order.131func (w *Workbook) logOp(kind OpKind, author int, c Change) uint64 {132 h := &w.hist133 h.seq++134 h.log = append(h.log, Op{Seq: h.seq, Author: author, Kind: kind, Change: c})135 if len(h.log) > opLogSize {136 h.log = slices.Delete(h.log, 0, len(h.log)-opLogSize)137 }138 return h.seq139}140141// mine is the index in the undo stack of the author's latest step, or142// -1; with the history unshared, the top's.143func (h *history) mine(author int) int {144 if !h.shared {145 return len(h.undo) - 1146 }147 for i := len(h.undo) - 1; i >= 0; i-- {148 if h.undo[i].author == author {149 return i150 }151 }152 return -1153}154155// mineRedo is the index in the redo stack of the author's latest undo.156func (h *history) mineRedo(author int) int {157 if !h.shared {158 return len(h.redo) - 1159 }160 for i := len(h.redo) - 1; i >= 0; i-- {161 if h.redo[i].author == author {162 return i163 }164 }165 return -1166}167168// UndoBlocked reports whether the current author's latest step can't be169// undone, and the first later step in the way.170func (w *Workbook) UndoBlocked() (Blocked, bool) {171 h := &w.hist172 i := h.mine(w.author)173 if i < 0 {174 return Blocked{}, false175 }176 return h.blocking(h.undo[i], h.undo[i+1:], 0)177}178179// RedoBlocked reports whether the current author's latest undo can't be180// redone, and the first step made since that's in the way.181func (w *Workbook) RedoBlocked() (Blocked, bool) {182 h := &w.hist183 i := h.mineRedo(w.author)184 if i < 0 {185 return Blocked{}, false186 }187 return h.blocking(h.redo[i], h.undo, h.redo[i].seq)188}189190// blocking is the first of later, made after seq by another author,191// that overlaps st. The author's own steps after one of theirs are192// redos of their own undos, which came back in order; with the history193// unshared nothing blocks.194func (h *history) blocking(st *step, later []*step, seq uint64) (Blocked, bool) {195 if !h.shared {196 return Blocked{}, false197 }198 for _, o := range later {199 if o.seq > seq && o.author != st.author && st.overlaps(o) {200 return Blocked{Author: o.author, Label: o.label}, true201 }202 }203 return Blocked{}, false204}205206// takeUndo removes the author's latest step from the undo stack, when207// nothing later is in the way, giving the steps after it new IDs: the208// states they lead to are new.209func (h *history) takeUndo(author int) *step {210 i := h.mine(author)211 if i < 0 {212 return nil213 }214 if _, blocked := h.blocking(h.undo[i], h.undo[i+1:], 0); blocked {215 return nil216 }217 st := h.undo[i]218 h.undo = slices.Delete(h.undo, i, i+1)219 h.bytes -= st.bytes220 for _, later := range h.undo[i:] {221 h.lastID++222 later.id = h.lastID223 }224 return st225}226227// takeRedo removes the author's latest undo from the redo stack, when228// no step made since is in the way.229func (h *history) takeRedo(author int) *step {230 i := h.mineRedo(author)231 if i < 0 {232 return nil233 }234 if _, blocked := h.blocking(h.redo[i], h.undo, h.redo[i].seq); blocked {235 return nil236 }237 st := h.redo[i]238 h.redo = slices.Delete(h.redo, i, i+1)239 return st240}241242// dropRedo forgets the author's undos, which a new step of theirs ends,243// or everyone's when the history isn't shared.244func (h *history) dropRedo(author int) {245 if !h.shared {246 h.redo = nil247 return248 }249 h.redo = slices.DeleteFunc(h.redo, func(st *step) bool { return st.author == author })250}251252// recordShift notes that the open step moves the sheet's cells by253// inserting or deleting lines, which conflicts with any other step on254// the sheet.255func (s *Sheet) recordShift() {256 if st := s.wb.hist.open; st != nil {257 if st.shifts == nil {258 st.shifts = map[*Sheet]bool{}259 }260 st.shifts[s] = true261 }262}263264// overlaps reports whether st and o change any of the same things, so265// one can't be undone past the other (see Authors above).266func (st *step) overlaps(o *step) bool {267 if st.sheets != nil || o.sheets != nil || st.settings != nil && o.settings != nil || st.macros != nil && o.macros != nil {268 return true269 }270 for s := range st.shifts {271 if o.touches(s) {272 return true273 }274 }275 for s := range o.shifts {276 if st.touches(s) {277 return true278 }279 }280 return st.sameCells(o) || sharesKey(st.widths, o.widths) || sharesKey(st.heights, o.heights) ||281 sharesKey(st.lines, o.lines) || sharesKey(st.names, o.names) || sharesKey(st.views, o.views) ||282 sharesKey(st.charts, o.charts) || sharesKey(st.pivots, o.pivots) || sharesKey(st.rules, o.rules) ||283 sharesKey(st.regions, o.regions)284}285286// sameCells reports whether the steps changed any of the same cells.287func (st *step) sameCells(o *step) bool {288 for s, img := range st.cells {289 other := o.cells[s]290 if other == nil {291 continue292 }293 if img.len() > other.len() {294 img, other = other, img295 }296 if img.anyIn(other) {297 return true298 }299 }300 return false301}302303// touches reports whether the step changed anything of sheet s.304func (st *step) touches(s *Sheet) bool {305 if st.cells[s] != nil || st.views[s] != nil || st.shifts[s] {306 return true307 }308 for _, m := range []map[*Sheet]bool{keysOf(st.charts), keysOf(st.pivots), keysOf(st.rules), keysOf(st.regions)} {309 if m[s] {310 return true311 }312 }313 for k := range st.widths {314 if k.s == s {315 return true316 }317 }318 for k := range st.heights {319 if k.s == s {320 return true321 }322 }323 for k := range st.lines {324 if k.s == s {325 return true326 }327 }328 return false329}330331// keysOf is a map's sheets as a set.332func keysOf[V any](m map[*Sheet]V) map[*Sheet]bool {333 out := make(map[*Sheet]bool, len(m))334 for s := range m {335 out[s] = true336 }337 return out338}339340// sharesKey reports whether two maps have a key in common.341func sharesKey[K comparable, V1, V2 any](a map[K]V1, b map[K]V2) bool {342 if len(a) > len(b) {343 for k := range b {344 if _, ok := a[k]; ok {345 return true346 }347 }348 return false349 }350 for k := range a {351 if _, ok := b[k]; ok {352 return true353 }354 }355 return false356}357358// anyIn reports whether img holds a before-image of any cell other359// holds one of.360func (img *image) anyIn(other *image) bool {361 found := false362 img.addrs(func(a Addr) bool {363 found = other.seen(a)364 return !found365 })366 return found367}368369// addrs calls fn with the address of every cell the image holds, until370// fn returns false.371func (img *image) addrs(fn func(Addr) bool) {372 for _, ic := range img.small {373 if !fn(ic.a) {374 return375 }376 }377 st := img.tables()378 more := true379 for _, occ := range []*occupancy{&st.stored, &img.blank} {380 for _, col := range occ.colIDs {381 occ.colScan(col, 0, MaxRows-1, func(row int) bool {382 more = fn(Addr{Col: col, Row: row})383 return more384 })385 if !more {386 return387 }388 }389 }390}