Approaches to Undo and Redo

One of PSPDFKit for Web’s newest features is the annotations History API, which provides undo and redo capabilities for our SDK, both via the API and the UI.

While working on the implementation, we had to make several design decisions around how the feature should work internally to optimize its resource usage and its robustness — all while keeping state consistency.

In this article, we want to share with you some of the challenges we faced, as well as the path we ended up taking. We think it may be useful for other developers when trying to implement undo and redo capabilities in different scenarios.

What Is History?

In the context of this post, history is a list of actions performed that modify an application’s state, ordered by their occurrence in time. When an “undo” command is executed, the application state is rolled back to the previous step, as if the last action performed had not taken place. When one or more undo commands have been executed, “redo” actions will be available. These can roll the application’s state forward again, bringing it to the moment where the next action in the history list had been performed. Independent of the step we moved to by issuing undo and redo commands, any new action performed will set a new history path in the future and clear the redo actions history, while the history path to the past (the available undo actions) is kept.

There are several ways to implement this feature, and we may choose one or another depending on the nature of the application’s state and the way that state may be affected by internal and external factors. Two of the main approaches usually considered are the memento and command patterns.

The memento pattern may appear to be the simplest and most straightforward way of implementing state history: It involves keeping a copy of the state before any action is performed. Thus, the only operation needed to execute an undo or redo command consists of replacing the current application state with the one that precedes or follows it in the history array.

Meanwhile, the command pattern involves executing the necessary commands on the state so as to make it look like it was before the undone action was performed.

We’ll consider the pros and cons of both approaches in the next steps and make the corresponding decisions through our example implementation.

Initial Implementation

In its simplest form, a history stack data model may look like this in JavaScript when using the memento pattern:

// Initial state.
// State is just a number in this initial implementation.
const state = 1;

const history = {
	undo: [],
	current: 1,
	redo: [],
};

Let’s say we perform some actions that modify the state. Now the history looks like this:

// After some actions.
const history = {
	undo: [1, 2, 3, 4],
	current: 5,
	redo: [],
};

We kept previous copies of the state in the history.undo array, but the history.redo array is still empty, as we haven’t executed any undo operations. Let’s do this now, just once:

// After some actions.
const history = {
	undo: [1, 2, 3],
	current: 4,
	redo: [5],
};

As you see, now the history.redo array holds a copy of the previous state, while the last element of the history.undo array has been popped out and set as the current state.

History in the Real World

The example above is only useful to demonstrate the basic functionality required by a history implementation. However, it’s not very useful in actual applications, where the state always contains multiple elements of a very different kind.

Let’s use a more realistic example — one of a simple calendar application that allows us to create events:

// Initial state.
const initialState = [
	{
		title: "Doctor's appointment",
		date: new Date('April 23, 2021 11:30:00'),
	},
];

// Initial history stack.
const history = {
	undo: [],
	current: initialState,
	redo: [],
};

After adding some more events, it appears we can still make use of the memento pattern:

// After some actions.
const secondState = [
	...initialState,
	{
		title: 'Buy groceries',
		date: new Date('April 20, 2021 10:00:00'),
	},
];
const thirdState = [
	...secondState,
	{
		title: 'Watch movie',
		date: new Date('April 24, 2021 20:00:00'),
	},
];
const fourthState = [
	...thirdState,
	{
		title: 'Dinner with friends',
		date: new Date('April 26, 2021 19:30:00'),
	},
];

const history = {
	undo: [initialState, secondState],
	current: thirdState,
	redo: [fourthState],
};

These are just object references to previous states, so as long as we handle state properties as immutable by creating a new object reference if a property is modified, keeping all those copies shouldn’t end up being very expensive.

However, we notice that our state data model looks naively simple, even for a basic calendar implementation. What if we need to include more information there, as would usually be the case?

const state = {
	events: [
		{
			title: "Doctor's appointment",
			date: new Date('April 23, 2021 11:30:00'),
			recurring: {
				every: 'month',
				until: new Date('September 23, 2021 11:30:00'),
			},
			allDay: false,
			sharedWith: ['mybestfriend@email.com', 'otherfriend@email.com'],
		},
	],
	locale: 'en',
	timezone: 'GMT',
	view: 'week',
	avatar: 'myavatar.png',
	theme: 'dark',
};

Things can get complicated very easily, as you can see: Now the object representing the application state contains much more data than before. And keeping copies of the same primitives and object references over and over may start to feel like an unnecessary waste of resources. We may want to handle history a bit differently.

Keeping Just the Changes

Instead of copying all the references from one state to the next, we can just keep track of the differences between both, so we can later apply them on top of the state to obtain the next one. Let’s reuse our last state data model example to showcase this approach:

const initialState = {
	events: [
		{
			title: "Doctor's appointment",
			date: new Date('April 23, 2021 11:30:00'),
			recurring: {
				every: 'month',
				until: new Date('September 23, 2021 11:30:00'),
			},
			allDay: false,
			sharedWith: ['mybestfriend@email.com', 'otherfriend@email.com'],
		},
	],
	locale: 'en',
	timezone: 'GMT',
	view: 'week',
	avatar: 'myavatar.png',
	theme: 'dark',
};

const history = {
	undo: [
		// The user has changed `view` to "month", so we enqueue an
		// undo action where we restore `view`'s value to "week".
		(currentState) => ({
			...currentState,
			view: 'week',
		}),
		// The user has changed `theme` to "light", so the
		// undo action restores `theme`'s value to "dark".
		(currentState) => ({
			...currentState,
			theme: 'dark',
		}),
		// The user added an event titled "Read book". The corresponding
		// undo action filters it out (deletes it).
		(currentState) => ({
			...currentState,
			events: currentState.events.filter(
				(event) => event.name !== 'Read book',
			),
		}),
	],
	current: {
		events: [
			{
				title: "Doctor's appointment",
				date: new Date('April 23, 2021 11:30:00'),
				recurring: {
					every: 'month',
					until: new Date('September 23, 2021 11:30:00'),
				},
				allDay: false,
				sharedWith: ['mybestfriend@email.com', 'otherfriend@email.com'],
			},
			{
				title: 'Read book',
				date: new Date('April 20, 2021 16:30:00'),
				recurring: null,
				allDay: false,
				sharedWith: [],
			},
		],
		locale: 'en',
		timezone: 'GMT',
		view: 'month',
		avatar: 'myavatar.png',
		theme: 'light',
	},
	// The user had added an event titled "Change bulb", and afterward,
	// executed undo, pushing a new redo action to the redo stack where
	// the removed event is restored again.
	redo: [
		(currentState) => ({
			...currentState,
			events: [
				...currentState.events,
				{
					title: 'Change bulb',
					date: new Date('April 22, 2021 11:30:00'),
					recurring: null,
					allDay: true,
					sharedWith: [],
				},
			],
		}),
	],
};

Now each state in our history stack is a function of the current state: We’ve switched to the command approach to optimize our implementation, and each next state can be obtained by applying a diff to the current state when executing undo or redo.

One may object here that, in order to apply diffs to states, we needn’t switch from the memento to the command pattern, and that we’re arbitrarily implementing history steps as functions that could be stored as plain diffs instead. However, to implement the diff technique, each undo and redo step must include information external to the state data model; we need to know if the diff to be applied is adding, modifying, or removing data, and this extra logic needs to reside somewhere for each step.

For example: What if we wanted our calendar to be collaborative and shared with other parties? Let’s stop a moment here, because we need to decide in our application design: Will our history stack be global and keep all the undo and redo actions for all actions performed by the stakeholders? Or will our history stack be local and only keep track of the actions performed by the current user?

To make this decision, we have to consider the pros and cons of each approach, outlined below.

Local History:

• Pros

  • Always in sync

  • Avoids interfering with other stakeholders’ actions

• Cons

  • History needs to account for external changes

Global History:

• Pros

  • Simplified implementation of history logic

• Cons

  • The local copy of the state may be out of sync at any moment

  • Executing undo and redo may affect external unrelated stakeholders’ actions

The additional complication of keeping history in sync compels us to lean to the local history approach, especially because interfering with other clients’ actions through undo and redo history — which is more widely implemented as a local helper — could result in annoying other stakeholders.

Having made this decision, let’s consider how clients communicate state changes regardless of how history is implemented. For example, let’s say clients communicate their actions to each other using an extended subset of the state data model:

// Shared delete action.
{
  action: "delete",
  property: "events",
  value: {
    title: "Change bulb",
  }
}

// Shared update action.
{
  action: "update",
  property: "events",
  value: {
    title: "Change bulb",
    date: new Date("April 22, 2021 11:30:00"),
    recurring: null,
    allDay: false,
    sharedWith: []
  }
}

Keep in mind that we need to share the state itself between the different clients for the application to be collaborative, and we’ll need to keep it in sync and resolve conflicts when they occur: If a client creates an event, another client updates it, and the first client deletes it, we may receive the event update notification once the event has been locally deleted. An approach to solving conflicts like this one — and the one we’ll choose for our example — is to mark each action with a timestamp so that earlier actions override later ones:

// Shared delete action.
{
  action: "delete",
  property: "events",
  value: {
    title: "Change bulb",
  },
  timestamp: 1000000000 // Comes first
}

// Shared update action.
{
  action: "update",
  property: "events",
  value: {
    title: "Change bulb",
    date: new Date("April 22, 2021 11:30:00"),
    recurring: null,
    allDay: false,
    sharedWith: []
  },
  timestamp: 1000000001 // Comes second
}

Since deletion came first, the update will be ignored, and the client that issued it will be notified of the deletion so it rolls back its update locally as well and both states are in sync again.

Back to the context of our history implementation: We also need to account for possible conflicts, even if our history stack is local and not shared. One reason is that the logic we use to identify events in our history stack is somewhat flawed. Events are identified by title, but title can be changed by any client.

Consider this local history:

const history = {
	undo: [
		(currentState) => ({
			...currentState,
			events: currentState.filter(
				(event) => event.name !== "Doctor's appointment",
			),
		}),
	],
	current: {
		events: [
			{
				title: "Doctor's appointment",
				date: new Date('April 23, 2021 11:30:00'),
				recurring: {
					every: 'month',
					until: new Date('September 23, 2021 11:30:00'),
				},
				allDay: false,
				sharedWith: ['mybestfriend@email.com', 'otherfriend@email.com'],
			},
		],
		locale: 'en',
		timezone: 'GMT',
		view: 'week',
		avatar: 'myavatar.png',
		theme: 'dark',
	},
	redo: [],
};

Now an external client issues an update:

{
  action: "update",
  property: "events",
  value: {
    title: "Doctor's appointment with friend",
    date: new Date("April 23, 2021 11:30:00"),
    recurring: {
      every: "month",
      until: new Date("September 23, 2021 11:30:00")
    },
    allDay: false,
    sharedWith: [
      "mybestfriend@email.com",
      "otherfriend@email.com"
    ]
  },
  timestamp: 200000000
}

The property we were using to identify each event, title, is precisely the one that the external client has modified, and it has just broken our history logic: Our single stored undo action will no longer work.

One obvious solution to this, which we should have probably thought of from the beginning, is to use a different property to identify each event — one that cannot be modified. Let’s call it an id, as is customary. Let’s go further and set it to the event creation timestamp, which could additionally help us in conflict resolution:

const history = {
	undo: [
		(currentState) => ({
			...currentState,
			events: currentState.filter((event) => event.id !== 300000000),
		}),
	],
	current: {
		events: [
			{
				title: "Doctor's appointment",
				date: new Date('April 23, 2021 11:30:00'),
				recurring: {
					every: 'month',
					until: new Date('September 23, 2021 11:30:00'),
				},
				allDay: false,
				sharedWith: ['mybestfriend@email.com', 'otherfriend@email.com'],
				id: 300000000,
			},
		],
		locale: 'en',
		timezone: 'GMT',
		view: 'week',
		avatar: 'myavatar.png',
		theme: 'dark',
	},
	redo: [],
};

And this is how updates would be broadcasted between calendar clients:

{
  action: "update",
  property: "events",
  value: {
    id: 300000000,
    title: "Doctor's appointment with friend",
    date: new Date("April 23, 2021 11:30:00"),
    recurring: {
      every: "month",
      until: new Date("September 23, 2021 11:30:00")
    },
    allDay: false,
    sharedWith: [
      "mybestfriend@email.com",
      "otherfriend@email.com"
    ]
  },
  timestamp: 400000000
}

Now our undo actions stack will keep pointing to the same event, regardless of the external updates.

We could complicate this example further — for example, by forcing ids to be unique so that we cannot reuse them when restoring a deleted event. However, I think the example above has evolved enough to provide a glimpse of the difficulties that arise when implementing undo and redo in an application.

Conclusion

Our walk through an example implementation of undo and redo shows that stepping back and forth along successive representations of an application’s state is not as easy as it initially might seem, and it can lead to different paths, depending on our project requirements. Moreover, in some cases, it may be difficult to evaluate if we’ve made the correct decision while designing the implementation until we are further along in our development history.

You can learn more about the annotations history API in our Undo and Redo guide or try out the undo and redo UI in our Web Examples Catalog.