Blog
Meld Studio Guides

C++ Undo Redo Frameworks (Part 1)

Meld Studio Team
Meld Studio Team
15 min read
C++ Undo Redo Frameworks (Part 1)

On this page

Undo / Redo is a feature we’ve been beginning to investigate recently at Meld Studio and the following is a summary of some of the best practices we’ve come across for integrating undo / redo support into a native cross platform C++ application.

Given our focus on building a high quality, reliable, live streaming tool we know that this is a feature that is best tackled early on as undo / redo logic often permeates a code base and can involve a significant engineering effort if it needs to be changed down the line.

In this post we’ll delve into the world of undo redo systems, learn the different types and when they should be used, explore the push for single source of truth state management frameworks as well as explain why you can’t always get everything you want.

Requirements

The first thing to work out is what kind of requirements does your undo redo system need to meet. We came up with the following list of features after a little blue sky brainstorming:

  1. [Performance] Both undo and redo operations should be quick to perform.
  2. [Reliable] Undo / redo operations should never fail to be applied.
  3. [Grouping] It should be possible to group operations into a single undo / redo operation.
  5. [Merging] It should be possible to merge operations.
    • Again using the above example, multiple move operations should ideally be merged down to one operation for the sake of efficient memory management.
  6. [Simple] Undo / Redo should not introduce significant boilerplate into the code base and should be easy to test.
    • At Meld Studio we’re using a combination of C++ and QML for the majority of our logic so there is also the added requirement that any undo / redo system should be usable across the two languages.

An example of why this could be important would be a simple move operation for a layer within Meld. Moving a layer may require updating the position hundreds of times but when the mouse is released undo should revert back to the original position skipping all intermediate states.

There were also several open questions we had:

  1. How should pointers, indirection, cycles be handled?
  2. Do we need support for multiple undo / redo “contexts”.
  3. Would the ability to update state without recording undo / redo operations when not required be useful?
  4. Must undo / redo be applied linearly or could we support reorderable undo / redo operations.

Keeping the above requirements and questions in mind lets move onto some common design patterns you will come across if looking into undo / redo yourself to get an idea of how undo / redo are commonly implemented in the real world.

Undo / Redo Implementation Patterns

From a high level, systems for managing undo redo typically make use of one or both of the following design patterns to some degree.

Command Pattern

The first is the Command pattern. It’s a pattern which is not only used for undo / redo systems but also operation queuing more generally. The command pattern at its core is about encapsulating some operation as an object which is then stored in a queue or stack so that it can be executed later.

Memento pattern

The second pattern is the Memento pattern which involves capturing and externalizing an object’s internal state without violating encapsulation. A simple example of this would be serializing an object to JSON. The JSON representation of an object would be the “memento” of the object and could be used to restore the object to that state down the line.

One way I like to think about the above two patterns is with the analogy of raster images (like JPEGs and PNGs) compared to vector images (like SVGs). A vector image. like the command pattern, can be used to define all of the steps to get from one one state to another. But the memento pattern can be thought of as raster image containing the full or partial state of an object at a given time.

Of course the two are not mutually exclusive and you can have a command pattern that stores operations containing mementos for a hybrid system, but you can also have SVG images containing raster images so the analogy holds up.

Lets looks at some real undo / redo APIs to see how these two patterns get used in the wild.

Real World Undo / Redo APIs

Native Undo / Redo Systems

The first undo redo system that a project based on Qt like Meld Studio might look at is Qt’s own undo redo framework. Qt provides a suite of classes for implementing undo inside of a Qt application and bills itself as a framework for implementing a command pattern approach to undo redo.

There are really only three classes that you need to understand to get started with Qt’s undo redo framework.

  1. QUndoCommand: This is the main class for encapsulating operations along with their reverse operation. QUndoCommand has two main methods: undo() and redo(). When a command is executed for the first time, redo() is called. When the user wants to undo the command, undo() is called.
  2. QUndoStack: Is the second main class. It is a simple stack of QUndoCommand objects that provides some ease of life methods to allow you to call undo / redo, set an undo limit or set-up undo macros. When an operation is performed, a corresponding QUndoCommand object is pushed onto the stack. When you want to undo or redo the stack simply calls the respective methods on the command at the top of the stack.
  3. QUndoGroup: This is more of an optional class as it manages a group of QUndoStack objects. A QUndoGroup object is useful when you have several QUndoStack objects, for example one for each opened document. It has an active stack, and undo(), redo(), etc. and any operations are performed on this active stack.

For an example of how all of that comes together for the simple use case of undoing a counter take a look at the following code:

#include <QtGui/QUndoCommand>

class IncrementCommand : public QUndoCommand
{
 public:
  IncrementCommand(int* counter, QUndoCommmand* parent = nullptr)
    : QUndoCommand(parent), m_counter{counter}

  void undo() override {
    Q_ASSERT(m_done);
    
    --(*m_counter);
    m_done = false;
  }

  void redo() override {
    Q_ASSERT(!m_done);

    ++(*m_counter);
    m_done = true;
  }

 private:
  int* m_counter;
  bool m_done{false};
};
int counter = 0;
QUndoStack undoStack;
undoStack.push(new IncrementCommand(&counter));

IncrementCommand inherits from QUndoCommand and is responsible for incrementing the counter on redo and decrementing the counter on undo. The counter is passed to the constructor via a pointer which it stores. And the m_done flag is just used to ensure that we don’t undo or redo in the wrong order.

The second code bock shows an example of how IncrementCommand can be used to increment the counter. By passing a new instance of the command to QUndoStack::push the QUndoStack will take ownership of the command and call it’s redo method, in this case incrementing the counter.

If you think that this example is a lot of code for simply undoing and redoing a counter then you can imagine how this scales to more complicated operations. Having to implement a QUndoCommand subclass for every state mutating operation in an app gets tiring quickly, and this is not even taking into account grouping / merging of operations. The above also raises multiple questions about safety:

  • What happens if the counter can be deleted?
  • What happens if the counter is modified outside of the undo command?

Now these questions are not really specific to Qt’s undo redo framework, in fact they were present in all of the other C++ undo redo framework that use this command pattern approach that we looked at (Apple’s NSUndoManager would be another example). The real takeaway here is that while using a command pattern approach can be powerful it does not stop you from shooting yourself in the foot, nor does it provide an automatic solution to undo / redo, you still have to write much of the logic yourself.

Web Undo / Redo Systems

The web ecosystem is another place that we looked to when investigating undo redo systems. There were a few reasons for this:

  1. Qt provides JavaScript support via QJSEngine and QML out of the box.
  2. Finally several members on the team were curious how the web ecosystem is currently solving this issue, or has had some experience with JS state management libraries in the past.

The web dev ecosystem is infamous for churning out new libraries and with that churn comes many of examples for how an undo state management system could be implemented.

CDN media

Here we’ll touch on two of the most well known state management libraries, Redux and Immer.js as they introduce a concept that can be powerful in undo redo systems, immutability.

Redux

Originally released in 2015 to make state management for single page apps easier, Redux has garnered significant popularity over the years. The original motivation behind Redux was that single page web apps were increasingly storing more and more state and given the asynchronous nature of JavaScript this can quickly become tricky to control.

The approach Redux takes to make this more manageable can be summarized by the three principles that underpin the library.

  • Single source of truth
  • State is read-only (Immutable
  • Changes are made with pure functions

The first principle is that Redux expects the global state of your application to be stored in a object tree within a single store. This has several advantages as it makes it easier to serialize and transfer the state of the app to clients. It also makes debugging easier as there is only one state tree that you need to inspect. But it also makes undo and redo much easier to implement as I will get into.

The second principle is that the state is immutable, which means that you cannot mutate or change the state as it is read only. This ensures that the only way to mutate the state of the app is by emitting an action which means that you don’t have to worry about views or arbitrary callbacks changing your state from underneath you.

Finally the third principle is that the only way changes are made are through pure functions which Redux calls reducers. Reducers are the core of Redux and are what define how the state should change in response to an action.

For a simple example on how Redux reducers work here are two code snippets taken from the Redux introduction, again showing how to increment a counter:

import { createStore } from 'redux'

/**
 * This is a reducer - a function that takes a current state value and an
 * action object describing "what happened", and returns a new state value.
 * A reducer's function signature is (state, action) => newState
 * 
 * The Redux state should contain only plain JS objects, arrays, and primitives.
 *  The root state value is usually an object. It's important that you should
 * not mutate the state object, but return a new object if the state changes.
 *
 * You can use any conditional logic you want in a reducer. In this example
 * we use a witch statement but it's not required.
 **/
function counterReducer(state = { value: 0}, action) {
  switch (action.type) {
    case 'counter/incremented':
      return { value: state.value + 1 }
    case 'counter/decremented':
      return { value: sate.value - 1 }
    default:
      return state
  }
}

Here a reducer function is created called counterReducer, it defines an initial state for the app with the counter starting at zero and then it defines two actions, “counter/incremented” and “counter/decremented”.

// Create a Redux store holding the state of your app.
// Its API is { subscribe, dispatch, getState }.
let store = createStore(counterReducer)

// You can use subscribe() to update the UI in response to state changes.
// Normally you'd use a view binding library (e.e. React Redux) rather than
// subscribe() directly. There may be additional use cases where it's
// helpful to subscribe as well.
store.subscribe(() => console.log(store.getState()))

// The only way to mutate the internal state is to dispatch an action.
// The action can be serialized, logged or stored and later replayed.
store.dispatch({type: 'count/incremented' })
// { value: 1 }
store.dispatch({type: 'count/incremented' })
// { value: 2 }
store.dispatch({type: 'count/decremented' })
// { value: 1 }

This second snippet shows how you would use this reducer in practice. You create a new store with your reducer and then you dispatch action types to increment and decrement the counter.

Note that the above does not yet contain support for undo, however extending Redux to support it is simple to do by following their reducer paradigm. By adding a history array to the state so that it contains an array of previous states we can effectively create a simple memento pattern undo redo system.

The way Redux suggests you implement this is using something called higher-order reducers. This is just a fancy name for a normal reducer that takes another reducer and extends it in some way.

function undoable(reducer) {
  // Call the reducer with empty action to populate the initial state
  const initialState = {
    past: [],
    present: reducer(undefined, {}),
    future: []
  }

  // Return a reducer that handles undo and redo
  return function (state = initialState, action) {
    const { past, present, future } = state

    switch (action.type) {
      case 'UNDO':
        const previous = past[past.length - 1]
        const newPast = past.slice(0, past.length - 1)
        return {
          past: newPast,
          present: previous,
          future: [present, ...future]
        }
      case 'REDO':
        const next = future[0]
        const newFuture = future.slice(1)
        return {
          past: [...past, present],
          present: next,
          future: newFuture
        }
      default:
        // Delegate handling the action to the passed reducer
        const newPresent = reducer(present, action)
        if (present === newPresent) {
          return state
        }
        return {
          past: [...past, present],
          present: newPresent,
          future: []
        }
    }
  }
}

In this case we have a higher order reducer called undoable which adds two new action types, UNDO and REDO. And if the action is neither an undo or redo action it falls through to the wrapped reducer and then updates the undo redo state.

In practice you wouldn’t create this undoable reducer yourself as Redux has its own redux-undo node package that you can use instead. It is a little more complicated than what we have implemented here but not much more. It just has some extra actions for jumping between states, filtering, grouping updates etc.

One thing I will say at this point is that if you squint things are starting to look very much like Qt’s undo / redo framework at this point. There are some extra guarantees in that all state modifying operations exist on the store as actions instead of potentially anywhere, and it’s guaranteeing that the state can only be modified through these actions, but otherwise an action is similar to a QUndoCommand. Redux does lean more into the Memento pattern as for every undo operation it will keep around a whole copy of the whole state but you still have your undo redo stacks and if memory is not an issue an implementation like this can work quite nicely.

Immer.js

The second Javascript library we’ll look at is Immer.js. It is a separate library to Redux but it can be used alongside Redux as it addresses some different aspects of state management that end up complementing Redux quite nicely when used together.

In fact Immer is actually bundled with the Redux toolkit which is the suggested package for using Redux.

When used on it’s own Immer.js offers the following:

  • It will automatically detect accidental mutations and throw an error
  • If you need to deep copy a large object Immer will handle that for you, this is especially useful with Redux as you often have some state value that you only want to change in some minor way and having to generate a complete copy of the state each time can involve a lot of spread operators.
  • It automatically generates what it calls “Patches” that contain all of the modifications you made. It can then share the memory with the previous state so that you don’t need to keep multiple copies of your whole state around. It can also automatically produce inverse patches that you can apply if you would like to say undo an operation.
  • Finally It handles all state changes via mutable draft objects that you can modify as if it were the original immutable object. This reduces some more boilerplate as it abstracts away the above two points.

This example shows off the most important function in Immer which is the produce function. It also shows how much boilerplate Immer can remove from a Redux reducer.

First we have a simple baseState dictionary that you could imagine standing in for some Redux state that you get from a reducer.

const baseState = {
  {
    title: "Learn TypeScript",
    done: true
  },
  {
    title: "try Immer",
    done: false
  }
}

Next we have an example of what the reducer may look like without Immer:

const nextState = baseState.slice() // shallow clone the array
nextState[1] = {
  // replace element 1...
  ...nextState[1], // with a shallow clone of element 1
  done: true // ...combined with the desired update
}

// since nextState was freshly cloned, using push is safe here,
// but doing the same thing at any arbitrary time in the future would
// violate the immutability principles and introduce a bug!
nextState.push({title: "Tweet about it"})

You can see that it ends up involving a fair bit of shallow copying. However with Immer you instead pass your baseState to the produce function and it creates a draft that you can modify directly.

import {produce} from "immer"

const nextState = produce(baseState, draft => {
  draft[1].done = true
  draft.push({title: "Tweet about it"})
})

This is actually what the Redux tool kit’s createReducer API uses internally so when using the redux tool kit to create reducers you actually get the benefits of Immer out of the box.

If you also think about it, what Immer is doing here is automatically creating a stack of commands that use partial mementos (or patches) to provide undo and redo. it is important to remember that Immer is only able to do this because of the restrictions it makes to its state model. Both Redux and Immer require that the state store is a single unidirectional tree model that is made up of only simple values types or objects containing simple types. That said, trading mutability of state for a safe and maintainable api is potentially a worth while trade off.

Why it’s not possible to have both a mutable model and a safe, reliable undo redo system.

At the beginning of this post we detailed the ability to modify state outside of the undo redo system as a potential nice to have. The reason for this was originally that we thought it might help with grouping. By ignoring some state modifications and only storing the beginning and end states we thought that we might be able to avoid having to deal with undo / redo for at least the majority of state mutating operations.

However this is impossible if you adopt an immutable state model like Redux. The real reason to enforce that all state modifying operations happen through the undo redo system is that any state modification that is not encapsulated in the undo redo system has the potential to invalidate existing undo / redo commands, leading to undo / redo commands that fail to apply at best or crash the application at worst. Note that with pure Redux this is not an issue as it will store the full state at every undo step however this can lead to significant memory usage and there is no guarantee that restoring the full state of an application is fast. 

Note: This is why full memento undo redo systems are normally avoided for anything other than providing snapshots or backups.

Instead it is almost always better to store commands that apply patches to the current state for undo redo, as it is both less memory hungry and more performant. And this is where immutability becomes a must to retain an undo redo system that is guaranteed to be commutative.

One way to prove this is by thinking of an undo / redo system as a distributed system and then applying CAP theorem to it.

Cap Theorem

The CAP Theorem is a fundamental theorem in distributed systems that states any distributed system can have at most two of the following three properties.

Consistency

Any read operation that begins after a write operation completes must return that value, the result of a later write operation, or an error.

Availability

Every request (read or write) received by a non-failing node in the system must eventually result in a response, even if it is out of date.

Partition Tolerance

the network will be allowed to lose arbitrarily many messages sent from one node to another 

A mutable patch based undo / redo system is like a distributed system in that you end up with two partitions that are trying to store your applications state at the same time. The first is your state model which is storing the current state of your application and the second is your undo redo system which can be thought of as storing derivatives of your state model to provide past and future states given the current state.

Partition tolerance can be thought of as the ability to modify the application state without updating the undo / redo system (or vice versa). In such a scenario the undo / redo system is implicitly “loosing” the messages about state modifications in a mutable undo / redo system. If this is required then that means you have to give up on either Consistency or Availability.

If you cannot give up on Consistency then you will have to tolerate that at least some state mutations or read operations may fail with an error. For example applying an undo patch to the current state may result in an error.

If a read or write operation to either the Application state or undo / redo system is not allowed to fail (Availability) then you have to accept that the state you end up with may either be out of date or, in the case of undo / redo, no longer commutative.

In practice there are multiple ways that losing Consistency or Availability may show up in a undo redo system’s API depending on the exact implementation however when we can keep both by forcing synchronized between the two systems it becomes obvious why following Redux’s “single source of truth” principle Is so appealing.

Wrap Up

So far we have touched the main design patterns that you may see in undo / redo systems, some real world examples from both the native and web ecosystems, how Immer.js is able to cut down on boilerplate by restricting its state model and and why keeping an immutable state is so important. However there is still a lot that has not been touched here. How does an immutable state store look in a modern C++ application? How do you best automatically generate patches that are groupable and mergeable to avoid the boilerplate of hand coded undo commands?

These will be explored in a follow up post that delves into why you should avoid JS Proxy objects in QML, how Qt’s QProperty Bindables could be used to automatically detect state changes and produce undo / redo patches and maybe more.

You might also like