How to make a undo/redo function

Question

I want to add an undo/redo function in my script. I have looked around and see some suggestions, most of them recommended to use the command pattern.

The function must work over one page - after a reload of the page the function must able to redo/undo the last things.

I don't know how the command pattern works, I think about to create a object, to store the a name of the function, the old and the new value - but I'm not sure if this is a efficient way to do this or not.

Maybe somebody could give me a small example how the code for an undo/redo function should look.

Answer 1

While there's many different ways to conceptuatlize undo/redo,by far the most established are the Memento Pattern and the Command Pattern.

Both are part of the original GoF:Behavioral Design Patterns. and they are so strongly related to undo/redo that some just call them the "undo patterns".

note: these are OOP-y patterns; if you're doing functional programming, which also lends itself to nice & straightforward undo, you're better off asking another question or have a look into how Redux supports a feature they call time-travel.

Theory 101:

Almost any software can be modelled as a state machine, which is a conceptual machine that changes its state in reaction to a transition.

Simply put: you ask it to do something, which it executes (transition), and now there's a different/new thing (state) on your screen/disk etc..

For the sake of brevity, let's imagine your system is a simple desk lamp.

• 2 states: light on & light off.
• 2 transitions: flip switch up & flip switch down

note: transitions/commands and later on actions refer to the same thing.

In the context of undo, it's almost always a user action. For example: flipped switch up, pressed start button, clicked "delete" file etc...

example:

// state
{ 
  id: 'shape-1',
  x: 0, y: 100,
  width: 100, height: 100
  fill: '#000000',
}
       
// a transition
shape.moveTo({ x: 800, y: 500} ) 

// new state 
{ 
  id: 'shape-1',
  x: 800, y: 500,
  width: 100, height: 100
  fill: '#000000',
}

So in essence, the interaction with the system takes place via transitions. The end effect is a change (or not) of the program state in one way or another.

Now it's easy to conceptualise:

• Undo is being able to return from the current state to the previous state.

• Redo is the ability to return back to the current state.

Their difference stems from what they process/store in order to return to a previous state.

• The Memento pattern saves the entire state which it can then reload as the current state.

• The Command pattern saves the transition and the inverse transition so it can replay the invesrse transition and cancel out the transition that lead to the new state, thus bringing it back to the previous state.

example:

// initial state
// at: `0,0`
{ 
  id: 'shape-1',
  x: 0, y: 0,
  width: 100, height: 100
  fill: '#000000',
}
       
const command = {
  // a transition
  do: { fn: shape.moveBy, params: [100,100] },
  // inverse transition
  undo: { fn: shape.moveBy, params: [-100,-100] },
}

// execute the transition
command.do.fn.call(this, ...command.do.params)

// save the command with both 
undostack.push(command)


// new state 
// at: `100, 100`
{ 
  id: 'shape-1',
  x: 100, y: 100,
  width: 100, height: 100
  fill: '#000000',
}

// pop the last pushed command 
// and execute the inverse
const command = undostack.pop()
command.undo.fn.call(this, cmd.undo.params...)

// new state
// back to: `0,0`
{ 
  id: 'shape-1',
  x: 0, y: 0,
  width: 100, height: 100
  fill: '#000000',
}

In both patterns you have an Undo Stack, in which you save either mementos or commands. When you want to undo you pop off the undo stack and proceed accordingly, depending on which pattern you chose for your undo system.

So a user is trying to issue a command/transition. Right before we start running code to execute it so it can alter state:

• In the Memento pattern, capture and store a copy of the current state, called the memento, which is then used to reinstate the current state, later on when and if the user wants t undo..

• In the Command Pattern you save the transitions/commands that affected the state in pairs. The 1st pair is the actual transition and the 2nd pair is the same as the actual but the values are negated.

If the user wants to undo you pop the last executed transition pair and execute the negated transition. Each command implements an action and it's inverse action which negates the action. You replay them but this time use the inverse action which undoes the previous actions.

Pros and cons of each pattern

Mementos:

pro: super easy to implement because all you need to do is capture your current state

con: memory inefficient saving nearly indentical copies of the state is wasteful

Command pattern

con: A pain-in-the-ass to implement You have to explicitly code the inverse actions

pro: much more efficient memory-wise; the transitions are simple code commands.

Long story short; try mementos first - they are very easy to implement and reason about again provided that your state is consolidated in one-place. If the performance aspect is also OK, use this one.

An undo system for a simple multiple-step form will probably use the Memento pattern since it's current state, the chosen answers for each step, is miniscule. You can get away with continuously saving nearly-identical copies of the state.

A vector-drawing application like Adobe Illustrator, will probably be using the Command Pattern since it's current state, the Scene Graph, is enormous.

There are hybrid solutions; or optimisations of the patterns themselves, for example δ-encoding, but they tend to fall into either of these 2 concepts so I won't expand on those.

I'll expand in very painful detail below but in effect I'm just expanding on these 2 patterns. If you need a more consise explanation, google them. I'm sure there's an implementation for most languages, provided they have some OOP-y capabilities.

Before you continue. This answer is assuming a single, local user. Collaborative, multiparty undo is significantly different in its method of operation and far more complex to get correct, especially so if it involves a network. Such undo systems necessitate taking into account the limitations of the CAP theorem + handling of the fallacies of distributed computing. They tend to be very coupled ith the underlying data structures/architecture (CRDT, OT) but regardless , they are out of scope of this answer.

Quick recap on state

Descriptions of program state are sometimes dizzying. It's simple:

Program state is the current situation you're in, from a given perspective, in a particular point-in-time.

For example I'm in my flat right now, and the TV is turned on. It's temperature is also 31 Celcius but I only care about undoing changes to my electrical appliances so the 2nd part is ignored.

So I need to be capturing some interesting attributes, in a point-in-time; in a format that allows me to reinstate the state to that previous point.

A key point here is whether you have the state that interests you in one place so you can easily reach it without jumping haphazardly through a lot of loops;

This is an example of a deliberate structure to store state.

Example: Our "Totally not© Adobe Illustrator" drawing software stores it's state in a tree data structure which describes the content, attributes and hierarchy of all the parts that make the drawing = the current state.

ignore the actual numbers in code they are just fillers.
You mostly care about the tree data structure (expressed both in pseudocode and visually).

If this is similar to what you're doing (it's a nested object at the end of the day), you're almost clear to use the Memento Pattern. Simply serialize the data from the root before any change andpush it into your undo stack. This serialised representation of a past state is the memento. It should include all data necessary to reconstruct a working state.

If you need to undo (the last change), pop the undo stack and use that memento to reinstate the current state.

sidenote: you're using a very similar structure right now, as you're viewing this, the DOM of the current page; another case of state being represented by a tree structure.

clarification:

serialise = turn an instance/object into text, like let json = JSON.stringify(john).

deserialise/parse = recreate Person: john from that text, as in: JSON.parse(json)

The reason you serialise and deserialise is to make sure you have a clone of the state that has absolutely no references attached to the original state itself, otherwise you risk polluting the memento in the undoStack with changes currently being applied to the state. It doesn't have to be a text representation. If you can get an exact clone by some other method, with zero referenes to the > original, that could work as well.

A secondary reason is easy storage, although usually undo lives only in-memory so this might be a moot point.

in all cases try to encapsulate as much data in the memento itself.

The Memento pattern

In the Memento Pattern you simply capture the whole current state.

The user wants to edit something:

• you serialise the current state of the program
• you push that serialised state into an undo stack
• you actually perform the edit

In it's extreme, you can even capture a JSON of the entirety of your application in that point-in-time. That whole state you just captured/snapshotted or turned into JSON is called the memento.

When you want to undo afterwards:

• pop that previously saved memento off the undo stack
• feed it to your program, asking it to use it to replace it's current state with the state captured in the memento.

The program is now back to how it was before the edit.

Pros:

• Straightforward implementation
• Flexible. Since you capture and recreate entire states, you can go ahead and make any change you want to your program state in the meantime. When you undo, you recreate the entire state anyway so it's no problem. In other words, it's saves an absolute state change.

Cons:

• In some cases, a prohibitively heavy memory hog.
• Capturing a save point is explicit. In most implementations you'll need to explicitly do something like app.captureUndoSavepoint() before you do some change.

Each time you want to capture an undo save point, you save an entire copy of the current state. That's obviously very inefficient memory-wise.

In a lot of cases, it's also expensive to reinstate entire copies of state. When you open a file of a Word Document, the program needs a bit of time to initialise the document and this and that. Undo needs to be snappy.

The Command Pattern

In this pattern whatever action your application can take is coded as a Command.

A command is packaged as a unit-of-work with 2 specific methods:

• execute which performs the action.
• undo which performs the opposite of execute, thus negating or undoing the effects that execute created.

This is an example of a Command that turns on a light bulb:

class TurnOnLightbulbCommand {
  constructor (lightbulb) {
    this.lightbulb = lightbulb
  }

  execute() {
    this.lightbulb.turnOn()
  }

  undo() {
    this.lightbulb.turnOff()
  }
}

// Usage 

const command = new TurnOnLightbulbCommand(lightbulb)

command.execute() // lightbulb turned on 

// Undo 

command.undo() // lightbulb turned off

If you're writing a text editor for example, you would need to write a CharacterAddedCommand, CharacterRemovedCommand, CharacterPastedCommand and so on.

The user wants to add a character to the document:

• Construct the appropriate command for the action, i.e CharacterAddedCommand
• Invoke the commands execute method
• Push the executed command into your undo stack.

To undo:

• pop the last executed Command from the undo stack.
• invoke it's command.undo() method to undo the effects of that same commands execute method - which was executed earlier.

Real-life examples:

Most sophisticated editing program nowadays will mostly be using this pattern.

The "simple" database transaction. In a database transaction you explicitly code what the transaction should do but also how to rollback those actions in case s hits the fan.

If something goes south, you "rollback" or "undo" the transaction. Command Pattern Undo is almost identical, except we save each executed transaction so we can call it's rollback/undo when we want to undo.

Pros:

• Memory efficient.
• Capturing a save point is automatic/implicit. No need to explicitly state it before doing some change.

Cons:

• Clunky to implement. There's a fundamental change into how you interact with the program to execute actions.
• Inflexible. Every change must now happen via prescribed commands. If you go ahead and mess with the state without going through this command mechanism, there's a chance the commands undos won't work, i.e: removing app.house.tv then trying to undo will throw a ReferenceError: this.house.tv is not defined.

Each action in your software must code inverse actions. Every undoable action in your application must be executed via Commands. For each command you must reason and explicitly code it's executeand undo methods.

Running Examples

The Mechanics of each pattern

Task: Our application, App, manages a House. We make changes on the house. We now want to implement undo functionality so we can revert any changes we make.

The app without undo functionality:

class App {
  constructor() {
    this.house = new House({ tvIsOn: true, wallColor: 'beige' })
  }
}

class House {
  constructor({ tvIsOn, wallColor }) {
    this.tv = new Television({ isOn: tvIsOn })
    this.wallColor = wallColor
  }
}

class Television {
  constructor({ isOn }) {
    this.isOn = isOn
  }
}

const app = new App()

console.log('initial state:', app.house.wallColor, app.house.tv.isOn)
// 'beige', true

/* Mess up the house */

app.house.wallColor = 'red'
app.house.tv.isOn = false
console.log('new state:', app.house.wallColor, app.house.tv.isOn)
// 'red', false

...now it sucks we messed up the house and wish there was a way to undo back to when the walls were beige and the TV was on.

Memento pattern

Implementing undo using the Memento Pattern.

That's easy:

• Add an App.undoStack, the undo stack to save our mementos.
• Add a App.captureUndoPoint method that saves the state of the house, as the memento
• Add an App.undo method that reconstructs a House from the saved mementos.

class App {
  constructor() {
    this.undoStack = []
    this.house = new House({ tvIsOn: true, wallColor: 'beige' })
  }

  captureUndoPoint() {
    // serialize the whole house
    const memento = JSON.stringify(this.house)
    this.undoStack.push(memento)
  }

  undo() {
    const lastMemento = this.undoStack.pop()

    if (lastMemento) {
      const lastState = JSON.parse(lastMemento)
      // reconstruct the whole house back
      this.house = new House({
        tvIsOn: lastState.tv.isOn,
        wallColor: lastState.wallColor
      })
    }
  }
}

class House {
  constructor({ tvIsOn, wallColor }) {
    this.tv = new Television({
      isOn: tvIsOn
    })
    this.wallColor = wallColor
  }
}

class Television {
  constructor({ isOn }) {
    this.isOn = isOn // `true`/`false`, if 'on' or 'off'
  }
}

/* *** Initial State *** */

const app = new App()
app.captureUndoPoint()
console.log('initial state:', app.house.wallColor, app.house.tv.isOn)
// initial state: `beige`, `true`


/* *** Mess up the house *** */

// Mess up the wall color...
app.house.wallColor = 'red'
// and turn off the TV
app.house.tv.isOn = false

console.log('new state:', app.house.wallColor, app.house.tv.isOn)
// new state: `red`, `false`


/* *** Undo back to previous state *** */

app.undo()
console.log('undone state:', app.house.wallColor, app.house.tv.isOn)
// undone state: `beige`, `true`

That was easy, we just JSON.stringify the house, saved it as the memento and used it to reconstruct a new house on undo.

In fact you could go ahead and crash the whole house:

app.house = null

and it wouldn't be a problem since when we undo we recreate it.

Command Pattern

Implementing undo using the Command Pattern

Here it gets tricky. To effect changes on the house, we have to explicitly code the Commands. Each command must code an execute method to perform the action and an undo method to reverse the action.

So we need:

• The Commands themselves.
• an undoStack again
• an App.executeCommand method that executes our commands and saves them in the undoStack
• an App.undo method that pulls previously executed commands out of the undoStack and calls command.undo.

Here are the 2 new commands:

class ChangeWallColorCommand {
  constructor({ house, currentColor, newColor }) {
    this.house = house
    this.currentColor = currentColor
    this.newColor = newColor
  }

  execute() {
    this.house.wallColor = this.newColor
  }

  undo() {
    this.house.wallColor = this.currentColor
  }
}

class switchTelevisionCommand {
  constructor({ tv, isOn }) {
    this.tv = tv
    this.isOn = isOn
  }

  execute() {
    this.tv.isOn = this.isOn
  }

  undo() {
    this.tv.isOn = !this.isOn
  }
}

Note that Commands must always implement two methods; undo and execute.

These 2 methods must never take arguments. They must use data saved in the instance to perform their work.

...now the complete example:

class App {
  constructor() {
    this.undoStack = []
    this.house = new House({ tvIsOn: true, wallColor: 'beige' })
  }

  executeCommand(command) {
    command.execute()
    this.undoStack.push(command)
  }

  undo() {
    const lastCommand = this.undoStack.pop()

    if (lastCommand)
      lastCommand.undo()
  }
}

class House {
  constructor({ tvIsOn, wallColor }) {
    this.tv = new Television({ isOn: tvIsOn })
    this.wallColor = wallColor
  }
}

class Television {
  constructor({ isOn }) {
    this.isOn = isOn // `true`/`false`, if 'on' or 'off'
  }
}

// Commands

class ChangeWallColorCommand {
  constructor({ house, currentColor, newColor }) {
    this.house = house
    this.currentColor = currentColor
    this.newColor = newColor
  }

  execute() {
    this.house.wallColor = this.newColor
  }

  undo() {
    this.house.wallColor = this.currentColor
  }
}

class switchTelevisionCommand {
  constructor({ tv, isOn }) {
    this.tv = tv
    this.isOn = isOn
  }

  execute() {
    this.tv.isOn = this.isOn
  }

  undo() {
    this.tv.isOn = !this.isOn
  }
}

/* *** Initial State *** */

const app = new App()
console.log('initial state:', app.house.wallColor, app.house.tv.isOn)
// initial state: `beige`, `true`


/* *** Mess up the house *** */

// Mess up the wall color...
const command1 = new ChangeWallColorCommand({
  house: app.house,
  currentColor: app.house.wallColor,
  newColor: 'red'
})

// and turn off the TV
const command2 = new switchTelevisionCommand({
  tv: app.house.tv,
  isOn: false
})

app.executeCommand(command1)
app.executeCommand(command2)
console.log('new state:', app.house.wallColor, app.house.tv.isOn)
// new state: `red`, `false`


/* *** Undo back to previous state *** */

app.undo() // undo command 1
app.undo() // undo command 2
console.log('undone state:', app.house.wallColor, app.house.tv.isOn)
// undone state: `beige`, `true`

At first glance, this looks terrible and convoluted. Why go into the hassle of coding those commands? The Memento pattern looks far more simple.

Well, memory issues. The Memento Pattern takes up a lot of space and doesn't scale well.

Gotchas of the Command Pattern

A Command must:

keyword must means it is an absolute requirement, otherwise the mechanism will not work

• save all the data it needs to perform it's execute/undo as internal state at construction/instantiation.
• provide an: execute.
• provide an: undo method.

It's crucial that your execute or undo methods take no parameters. They must use the data they possess as part of their construction to perform their action and/or undo that action.

All the parameters to complete the action must be passed and saved in the instance, when you construct/initialise it.

The method names could instead be apply and rollback but whatever they are, all your commands must expose 2 methods and name them uniformly. You can't have one command with execute/undo methods and another with apply/rollback, obviously.

Good example of a Command:

• Implements execute and undo methods
• Data to perform either is saved in the instance, during construction

class switchTelevisionCommand {
  constructor({ tv, isOn }) {
    // GOOD:
    // All data is passed on construction time and saved
    // in the command
    this.tv = tv
    this.isOn = isOn
  }

  // GOOD. 
  // Takes no parameters, uses internal state to
  // execute
  execute() {
    tv.isOn = this.isOn
  }

  // GOOD. 
  // Takes no parameters, uses internal state to
  // execute
  undo() {
    this.tv.isOn = !this.isOn
  }
}

Bad example of a Command:

Data to perform either does not exist in instance and passed as parameter to execute or undo.

class switchTelevisionCommand {
  constructor({ tv }) {
    this.tv = tv
  }

  // BAD: Passing parameters to `execute` or `undo`
  execute(isOn) {
    this.tv.isOn = isOn
  }

  undo() {
    // won't be able to `undo()` later
    // `this.isOn === undefined ``
    this.tv.isOn = !this.isOn
  }
}

What about redo?

Redo is nothing more than saving an undone command into a redoStack. On redo, you pop the redoStack and call the execute method again.

Hope this helps.