Undo/Redo in Vuex using state snapshot

Question

Context

I have built an undo-redo plugin that works on the below steps.

Steps used (Overview)

1. Add the previous state snapshot on every action.
2. Undo using custom replaceState method with previousState as a parameter.
3. Redo using custom replaceState method with previousState as a parameter.

Currently dealing with performance issues as we deal with a huge, nested state.

Performance Issues

• I have used cloneDeep to make deep copy of the state so that reference to the current state is not maintained while replacing the state, as the state becomes bulky the cloneDeep takes more time to clone.

• I have used a custom replaceState method that does exactly the same thing as replaceState, but replaces the module state instead of entire app’s state which also eventually takes much longer time to
  replace.

Due to the above issues, the undo/redo becomes laggy and unusable.

I am rather stuck. Where am I going wrong, or is there a better way to implement undo/redo for complex state applications?

Code

done: used for undo and storing the state snapshots.

undone: used for redo and storing the state snapshots.

GlobalStore.js: Global store where all the modules are clubbed together.

export const store = new Vuex.Store({

     modules: { canvasEditor,dashboardMetrics }
     plugins: [ canvasEditorUndoRedo ]

})

Below are the files within the plugin.

index.js

import { Operations } from ‘./Operations’;

import { actionsToBeUsed } from './constants';

import { cloneDeep } from 'lodash';

export const op = new Operations();

export const canvasEditorUndoRedo = (store) => {

  /*

        Description: Perform undo/redo operation
        Steps:
        1.Initalize the class
        2.Store the previous state based on actions

  */
  op.init(store);

  store.subscribeAction((action, state) => {
    if (action.type != 'undo' &&action.type != 'redo' && actionsToBeUsed.find(actionType => actionType == action.type) != undefined) {
        // Store the state
        let stateClone = cloneDeep(state.canvasEditor);
        op.addSnapshot({ id: op.done.length + 1, action, state: stateClone });
    }
  });
}

Operation.js

import { cloneDeep } from 'lodash';
export class Operations {

  store
  done=[]
  undone = []

  init(store) {
    this.store = store;
  }

  addSnapshot(snapshot) {
    this.done.push(snapshot);
    this.updateOperationsCount();
  }

  clearUndo() {
    this.done = [];
    this.updateOperationsCount();
  }

  clearRedo() {
    this.undone = [];
    this.updateOperationsCount();
  }

  undo() {

    /*
    Description: Performs undo operation based on previousState stored in array(done).
    Steps:

        I.    Get the last stored action from array(done)  pop it out.
        II.  Push the undo element(popped element) to redo’s an array (undone).
        III.   Replace the current state with stored state.

  */

    if (this.done.length != 0) {

      //I
      let undoELement = this.done.pop();

      //II
      this.undone.push({ id: undoELement.id, action: undoELement.action, state: this.store.state.canvasEditor});


      //III
      let state = cloneDeep(undoELement.state);
      this.replaceCanvasEditorState(state); 
      this.updateOperationsCount();

  }

  redo() {

    /*

    Description: Performs redo operation based on State stored in array(undone).
    Steps:
       I.   Get (pop) the last undo element from undone
      II.   Push the undo element(popped element) to undo’s an array (done) .
      III.   Replace the current state with stored state.
  */

    if (this.undone.length != 0) {

      //I
      let redoELement = this.undone.pop();

      //II
      this.done.push({ id: redoELement.id, action: redoELement.action, state: this.store.state.canvasEditor });

      //III
      let state = cloneDeep(redoELement.state);
      this.replaceCanvasEditorState(state);
      this.updateOperationsCount();
    }
  }

  replaceCanvasEditorState(state) {
  /*
     Description: Replaces current state with state provided as parameter.
  */
    this.store._withCommit(() => {
      this.store.state.canvasEditor = state;
    });

  }

  updateOperationsCount() {

    let undoRedo = {
      doneLength: this.done.length,
      undoneLength: this.undone.length
    }
    this.store.commit('updateUndoRedoCount', undoRedo);

  }

}

CodeSandBox

The application deals with a lot of complex operations.

Answer 1

I'm afraid using snapshots (deep cloning) to implement undo/redo on the huge nested state will always be really slow, not to mention memory hog

So your best option is probably to change your strategy completely. As you are using Vuex where every change has to be done using mutations, it should not be too hard to implement this using action/reverse action strategy. Instead of pushing state snapshot on the stack, within each mutation, push the "reverse action" mutation on the stack (with old sub-state as a parameter - deepCloned if it is an object).

Sure it's not as transparent as your original approach and requires mutation author to write a mutation in a specific way but you can always write some helpers to make it more easy and "standardized"...

Or you can take a look at undo-redo-vuex Vuex plugin which implements undo/redo by saving initial state and all mutations executed. When undo is needed, it resets state to initial state and replays all mutations except the last one. Don't know how well this scales but at least its more transparent to mutation authors...