[SOLVED] How to make a undo/redo function

There's 2 common ways of implementing undo/redo, both of them very well established and defined Behavioral Design Patterns.

The Memento Pattern and the Command Pattern.

In the context of undo, both of them are conceptual OOP-y mechanisms to return back to a previous program state.

In the Memento pattern, you save a copy of the current state, called the memento, so you can reinstate it as the current state, later on when you undo.. You get up and running with this pattern - super easily - provided your state isn't scattered around and you have the ability to serialize it and reinstate it easily.
In the Command pattern, you save the commands that affected the state and replay them backwards 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.
Mementos are super easy to implement but memory inefficient. Commands are a pain-in-the-ass to implement but very efficient memory-wise.

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.

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.

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.

Which undo pattern should I use?

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.

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.

Let's look at another example...

Running Examples (memory profile comparison)

Task: We are now implementing a different program, a text editor.

We want to code the feature that allows adding characters in > text. That action must be undoable.

Memento pattern

Here we capture the state as the memento. The current state here is the value of the textarea.

You can see that with 5 lines of codes I've implemented undo that covers all the cases of manipulating the textarea. Adding text, removing text, pasting text etc. It just works.

...but the memory consumption of the Undo Stack grows very large, very quickly.

// The important bits:

const undoStack = []

const captureMemento = () => {
  // the memento is just the value of the textarea!
  const memento = document.querySelector('#textarea').value
  undoStack.push(memento)

  updateUI()
}

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

  // reinstate the program state from memento
  if (lastMemento)
    document.querySelector('textarea').value = lastMemento


  updateUI()
}

// Just utilities, event binding etc...

const updateUI = () => {
  const bytes = new Blob([JSON.stringify(undoStack)]).size
  document.querySelector('#bytes').innerText = bytes

  if (undoStack.length)
    document.querySelector('#undo-btn').removeAttribute('disabled')
  else
    document.querySelector('#undo-btn').setAttribute('disabled', true)
}

document.querySelector('#undo-btn')
  .addEventListener('click', () => undo())

document.querySelector('#textarea')
  .addEventListener('keydown', () => captureMemento())
  
// Prevent undo by CTRL + Z 
document.addEventListener('keydown', e => {
  if ((e.metaKey || e.ctrlKe) && e.key === 'z') 
    e.preventDefault()
})

// Just filling with a lot of text ...
document.querySelector('textarea').value = `
Lorem Ipsum is simply dummy text of the printing and typesetting industry.
Lorem Ipsum has been the industry's standard dummy text ever since the
1500s, when an unknown printer took a galley of type and scrambled it to
make a type specimen book. It has survived not only five centuries,
but also the leap into electronic typesetting, remaining essentially
unchanged. It was popularised in the 1960s with the release of Letraset
sheets containing Lorem Ipsum passages, and more recently with desktop
publishing software like Aldus PageMaker including versions of Lorem
Ipsum.
`

textarea {
  width: 100%;
}

<h3> Memento Pattern </h3>
<h4> Click in text. Type characters. Click "Undo" to undo</h4>
<button id="undo-btn" disabled="true">Undo</button>
<label> Undo stack consumes: <strong id="bytes">0</strong>  bytes.</label>
<hr>
<textarea id="textarea" rows="8" cols="6"></textarea>

Since we save a memento on each character addition, our undo stack looks like this when we type "hello":

entire-initial-text + 'h'
entire-initial-text + 'h' + 'e'
entire-initial-text + 'h' + 'e' + 'l'
entire-initial-text + 'h' + 'e' + 'l' + 'l'
entire-initial-text + 'h' + 'e' + 'l' + 'l' + 'o'

Just typing "Hello" requires 4134 bytes of undo stack size. And the growth curve isn't linear so the more you type the worse it becomes.

On some programs you can get smart here, see comments below on diffing, others not so much; think about a Photoshop-like application where the state is entire high-res images.

Command Pattern

A far more tricky implementantion.

Here have only implemented 1 command, the KeyAddedCommand so the app only takes cares of the case where we want to add characters (and undo that addition).

However, this is much more memory efficient.

That's because we're only saving the commands we executed in the undo stack.

// The important bits:

const undoStack = []

const executeCommand = command => {
  command.execute()
  undoStack.push(command)

  updateUI()
}

const undo = () => {
  const lastCommand = undoStack.pop()
  
  if (lastCommand)
    lastCommand.undo()

  updateUI()
}

// The commands (super important)
// ...actually it's just one command for now

class KeyAddedCommand {
  constructor({
    id,
    key,
    position
  }) {
    this.id = id
    this.key = key
    this.position = position
  }

  execute() {
    const target = document.querySelector('#' + this.id)
    const split = target.value.split('')
    split.splice(this.position, 0, this.key)
    target.value = split.join('')

    target.setSelectionRange(this.position + 1, this.position + 1)
    target.focus()
  }

  undo() {
    const target = document.querySelector('#' + this.id)
    const split = target.value.split('')
    split.splice(this.position, 1)
    target.value = split.join('')

    target.setSelectionRange(this.position, this.position)
    target.focus()
  }
}

// Must implement:
// - KeyRemoved command
// - TextPastedCommand
//
// ...and many others...
document.querySelector('#textarea').addEventListener('keydown', e => {
  e.preventDefault()

  if (e.key.length === 1) {

    const command = new KeyAddedCommand({
      id: e.target.getAttribute('id'),
      key: e.key,
      position: e.target.selectionEnd
    })

    executeCommand(command)

  } else if (e.key === 'Backspace') {

    // Not implemented yet!
    /*
    const command = new KeyRemovedCommand({
      id: e.target.getAttribute('id'),
      position: e.target.selectionEnd
    })

    executeCommand(command)
    */
  }
})

// Just utilities, event bindings etc...

document.querySelector('#undo-btn').addEventListener('click', () => undo())

// Prevent undo by CTRL + Z 
document.addEventListener('keydown', e => {
  if ((e.metaKey || e.ctrlKe) && e.key === 'z') 
    e.preventDefault()
})

const updateUI = () => {
  const bytes = new Blob([JSON.stringify(undoStack)]).size
  document.querySelector('#bytes').innerText = bytes

  if (undoStack.length)
    document.querySelector('#undo-btn').removeAttribute('disabled')
  else
    document.querySelector('#undo-btn').setAttribute('disabled', true)
}

document.querySelector('textarea').value = `
Lorem Ipsum is simply dummy text of the printing and typesetting industry.
Lorem Ipsum has been the industry's standard dummy text ever since the
1500s, when an unknown printer took a galley of type and scrambled it to
make a type specimen book. It has survived not only five centuries,
but also the leap into electronic typesetting, remaining essentially
unchanged. It was popularised in the 1960s with the release of Letraset
sheets containing Lorem Ipsum passages, and more recently with desktop
publishing software like Aldus PageMaker including versions of Lorem
Ipsum.
    `

textarea {
  width: 100%;
}

<h3> Command Pattern </h3>
<h4> Click in text. Type characters. Click "Undo" to undo</h4>
<button id="undo-btn" disabled>Undo</button>
<label> Undo stack consumes: <strong id="bytes">0</strong>  bytes.</label>
<hr>
<textarea id="textarea" rows="8" cols="6"></textarea>
</body>

Now the undo stack looks like this when we type "hello":

{ command: 'KeyAdded', key: 'h', position: '10' }
{ command: 'KeyAdded', key: 'e', position: '11' }
{ command: 'KeyAdded', key: 'l', position: '12' }
{ command: 'KeyAdded', key: 'l', position: '13' }
{ command: 'KeyAdded', key: 'o', position: '14' }

Typing "hello" requires just 206 bytes (compared with 4134 bytes of the Memento pattern) and the growth factor here is constant.

So it's much more memory efficient.

But again, a PITA to implement; each action needs to be coded as a command.

Here's the command that adds characters (and undoes the same):

class KeyAddedCommand {
  constructor({ id, key, position }) {
    this.id = id
    this.key = key
    this.position = position
  }

  execute() {
    // code that adds the `this.key` at `this.position`
  }

  undo() {
    // code that remove item at `this.position`
    //
    // in this case, the `key` added in `execute` above.
    // thus, this method negates, reverses or undoes what
    // the `execute` method did.

  }
}

You have to also code the following commands (not an exhaustive list):

keyRemovedCommand
textPastedCommand

...etc

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.

How to make a undo/redo function

Quick recap on state

Which undo pattern should I use?

The Memento pattern

The Command Pattern

Running Examples

Memento pattern

Command Pattern

Running Examples (memory profile comparison)

Memento pattern

Command Pattern

Gotchas of the Command Pattern

What about redo?

What about `redo`?