跳至主要内容

[Google Docs] Optimization - Undo/Redo

source code

https://github.com/MechaChen/undo-manager-lite


Undo/Redo demo​




There are 2 ways to implement undo/redo mechanism:

  1. single undo stack and move by index (./src/hooks/useUndoRedoByIndex.ts)
  2. 2 stacks - undo stack & redo stack (./src/hooks/useUndoRedoByTwoStack.ts)

Single undo stack and move by index​

Use a single stack to store the user's operation history, and

  • when user undo, move index backward (-1)
  • when user redo, move index forward (+1)
const undo = () => {
    const prevStep = Math.max(LOWER_BOUND, currentIndex - 1);
    setCurrentIndex(prevStep);
}

const redo = () => {
    const nextStep = Math.min(UPPER_BOUND, currentIndex + 1);
    setCurrentIndex(nextStep);
}

2 Stacks - undo stack & redo stack​

Use 2 stacks to store the undo and redo histories

  • when user undo
    1. pop current state from undo stack
    2. push current state to redo stack
    3. get the latest previous state from the last item in the undo stack
    4. set state with the latest previous version
const undo = () => {
    if (undoStack.current.length <= 1) {
        return;
    }

    const currentValue = undoStack.current.pop();
    const prevValue = undoStack.current[undoStack.current.length - 1];
    redoStack.current.push(currentValue!);
    setValue(prevValue);
}

  • when user redo
    1. pop next state from redo stack
    2. push redo state to undo stack
    3. set state with next version
const redo = () => {
    if (redoStack.current.length === 0) {
        return;
    }

    const nextStep = redoStack.current.pop();
    undoStack.current.push(value);
    setValue(nextStep!);
}

Comparison​

Featureby index🏆 by 2 stacks
ImplementationSingle array + indexTwo stacks (undo/redo)
Memory Usage✅ Less (single array)⚠️ More (two arrays)
Code Complexity⚠️ Complex (index management)✅ Simple (intuitive push/pop)
Error Risk⚠️ High (index out of bounds)✅ Low (no index management)
Extensibility⚠️ Difficult (complex index logic)✅ Easy (simple to add features)
Performance✅ Better (fewer slice operations)⚠️ Worse (maintain two arrays)
Readability⚠️ Poor (need to understand index logic)✅ Good (clear semantics)
Maintainability⚠️ Poor (prone to bugs)✅ Good (clear logic)
Used by
  • Google Docs (early version)
  • Microsoft Word (early version)
  • Adobe Photoshop (early version)
  • Lexical
  • NSUndo manager (iOS, macOS standard)
  • VS Code
  • Sublime Text
  • Atom
  • Google Docs (current version)
  • Microsoft Word (current version)
  • Adobe Photoshop (current version)
  • Figma

Optimization​

To prevent memory leak, we can setup undo stack size limit, and when new operation come in, which makes the stack exceed the limit, slice the stack by size of (current stack size - limit)

const push = (value: T) => {
    let newUndoStack = undoStack.current.slice(0, currentIndex + 1);
    newUndoStack.push(value);

    if (undoStack.current.length > limit) {
        newUndoStack = newUndoStack.slice(undoStack.current.length - limit);
    }
    undoStack.current = newUndoStack;
    setCurrentIndex(newUndoStack.length - 1);
}


References​