« back published by @mmartin_joo on July 30, 2024
Undo/Redo Stacks
The following article is a post from my brand new Substack newsletter - Computer Science Simplified. Join the publication and become a real software engineer who understands the principles of computer science, system design, architecture, and software engineering in general.
When I first learned about how to implement undo/redo with the command design pattern it felt like magic. Because I didn’t understand a single word. Online tutorials didn’t help too much either. They always showed “hello world” level stuff such as entering a text into an input and then undoing/redoing it with an in-memory array. Unfortunately, my applications have databases, users, and multiple servers. I cannot use an array with strings. And usually, the most important feature is not copying strings but running database queries.
In this post, I’d like to show you a real-world undo/redo setup with stacks, database queries, APIs, and users. We will imitate some of Trello’s features.
At the end of the post, you can find the repository that contains everything.
Stacks
Stack is crucial for implementing undo/redo. It’s a simple LIFO data structure which means that the last element added to the stack is the first one to be removed:
When implementing undo/redo we need to have the changes in LIFO order. For example, if a user does the following things:
- Creates a card with the title “Buy milk“
- Writes a description: “I really need to buy milk“
- Assign a due date 2024-10-01
The history stack should be the following:
So it’s possible to undo these actions in the appropriate order (due date, description, creation).
A stack can be implemented with a simple array:
class Stack {
items = [];
push(item) {
this.items.push(item);
}
pop() {
return this.items.pop();
}
}
const stack = new Stack();
stack.push(1);
stack.push(2);
stack.push(3);
console.log(stack.pop());
console.log(stack.pop());
console.log(stack.pop());
In fact, you don’t even need the Stack class in this case. push() as pop() does the job:
const stack = [];
stack.push(1);
stack.push(2);
stack.push(3);
console.log(stack.pop());
console.log(stack.pop());
console.log(stack.pop());
Stacks with Redis
Since Redis can be used to implement anything I’m going to use it as the stack.
This is the interface:
namespace App\Stacks;
interface Stack
{
public function push(array $event, User $user): void;
public function pop(int $todoId, User $user): array;
}
Just a quick disclaimer: the interface won’t use arrays. I’m going to refactor this later. But for now, it’s much easier to understand.
The stack holds events with data. An event can be something like “description updated” and it holds data such as the todo attributes before and after the change.
To push or pop an item in or out of the stack we need a user. Each history stack belongs to a todo and a user. We don’t want to treat history as global since if I open Trello and change a card this is my personal history. If I click on “Undo” I want to reverse my own stupidity.
To implement this interface with Redis a list can be used. It offers two functions:
- lpush pushes an item to the left side of the list. It’s an append.
- lpop pops an item from the left side of the list. It removes the 0th element.
namespace App\Stacks;
class HistoryStack implements Stack
{
public function __construct(private Redis $redis)
{
}
public function push(array $event, User $user): void
{
$this->redis->lPush(
'history:todos:' . $event['data']['todo_id'] . ':' . $user->id,
json_encode($event),
);
}
public function pop(int $todoId, User $user): array
{
$eventJson = $this->redis->lPop(
'history:todos:' . $todoId . ':' . $user->id
);
if (!$eventJson) {
throw new InvalidArgumentException('Not found');
}
return json_decode($eventJson, true);
}
}
It stores the given array as a JSON string. In pop() it decodes the string to an array.
As I said, a history stack belongs to a user and a todo so it has the following index format: history:todos:<todo_id>:<user_id>
Why does the pop() method accept an integer instead of a Todo? Because it’s not guaranteed that the given todo exists in the database when pop() is called. Think about an action such as deleting a todo. When a user wants to undo that, there’s no Todo object to work with.
Simplified Command design pattern
The purpose of the command design pattern is to encapsulate commands into separate objects. Each command such as creating a todo, updating the description, or adding a due date should be its own object. The original design is a little bit more complex than this because it involves four components: command, concrete command, invoker, and receiver. I’m going to leave out the invoker and the receiver in this example because they are not needed for undo/redo.
I’m going to call my commands “actions” since it’s a pretty popular name in the Laravel community.
All actions that need undo/redo have to implement the Undoable interface:
namespace App\Actions;
interface Undoable
{
public function execute(array $data): ?Todo;
public function undo(array $event, User $user): ?Todo;
public function redo(array $event, User $user): ?Todo;
}
Just a quick disclaimer: undo and redo won’t use arrays. I’m going to refactor this later. But for now, it’s much easier to understand.
This is what the StoreTodoAction looks like:
class StoreTodoAction implements Undoable
{
public function __construct(
private HistoryStack $historyStack,
) {}
public function execute(array $data): Todo
{
$dto = StoreTodoData::from($data);
$todo = Todo::create([
'title' => $dto->title,
'user_id' => $dto->user->id,
]);
$event = [
'action' => self::class,
'data' => [
'todo_id' => $todo->id,
'todo' => [
'before' => null,
'after' => $todo->toArray(),
],
],
];
$this->historyStack->push($event, $dto->user);
return $todo;
}
}
It accepts an array and creates a DTO (DataTransferObject) from it. The DTO is very simple:
readonly class StoreTodoData
{
public function __construct(
public string $title,
public User $user,
) {}
public static function from(array $data): self
{
return new self(
title: $data['title'],
user: $data['user'],
);
}
}
There are going to be more DTOs in this example. All of them follow the same logic so I won’t show you the other ones. You can check them out in the GitHub repository at the end of the post, of course.
Using this DTO the action then creates the Todo. After that, it creates an array and then pushes it onto the history stack. The stack will store it as a JSON string. This is the structure of every event:
{
"action": "App\Actions\StoreTodoAction",
"data": {
"todo_id": 1,
"todo": {
"before": null,
"after": {
"id": 1,
"title": "Buy a new car",
"description": "Or at least spend an hour on the internet browsing for X7 and GLS"
}
}
}
}
The “action” key contains the class name of the action. The “todo” key always has a “before” and “after” key but both can be null. For example, there’s no “before” when creating a new todo and there’s no “after” when deleting one.
Usually, I’d like to avoid working with nested associative arrays because they can’t be type-hinted and are a source of lots of annoying bugs. So I added 3 DTOs to map the array to objects:
- One for the top-level indices (action, data). It’s called Event
- One for the data index. It’s called EventData
- And one for the todo index. It’s called EventDataTodo
This is the top-level object:
namespace App\DataTransferObjects\Event;
readonly class Event
{
public function __construct(
public string $action,
public EventData $data,
) {}
public static function fromJson(string $json): self
{
$data = json_decode($json, true);
return self::fromArray($data);
}
public static function fromArray(array $data): self
{
return new self(
action: $data['action'],
data: EventData::fromArray($data['data']),
);
}
}
DTOs always have these small but useful factory functions. You can check out the other classes in the repository under the App\DataTransferObjects\Event namespace.
So the action uses the DTO instead of an array:
$event = Event::fromArray([
'action' => self::class,
'data' => [
'todo_id' => $todo->id,
'todo' => [
'before' => null,
'after' => $todo->toArray(),
],
],
]);
$this->historyStack->push($event, $dto->user);
The HistoryStack and the Stack interfaces also use the event DTO:
interface Stack
{
public function push(Event $event, User $user): void;
public function pop(int $todoId, User $user): Event;
}
class HistoryStack implements Stack
{
public function push(Event $event, User $user): void
{
$this->redis->lPush(
'history:todos:' . $event->data->todo_id . ':' . $user->id,
json_encode($event),
);
}
}
So whenever a new Todo is created a new item is pushed onto the Redis stack:
As you can see, the key is history:todos:14:1 where 14 is the Todo ID and 1 is the user ID.
Undo
Now that the history stack is ready let’s do the first undo. We can undo the StoreTodoAction.
Technically, undoing the creation of a todo is dead simple: delete it. The preparation is a bit more “complicated:”
- Get the latest change from the stack
- Instantiate the appropriate action object
- Execute the undo() method
This is what the Controller looks like:
To find out how undo() looks like check out my new newsletter Computer Science Simplified
