Undo is a funny feature to implement, because it can be incredibly difficult to design and code, and once you're done users nod and say, 'oh, okay, it has undo.' The web doesn't have undo built-in, and a lot of websites don't support undo at all.
But on the other hand, undo is a powerful feature that lets you design the rest of your application differently. When you don't have undo, big destructive actions need confirmation steps. But if you can undo, users can be fearless, knowing that command+z is there.
There are lots and lots of ways to implement undo. Placemark landed on a solution in the same vein as Figma's – but undoubtedly less sophisticated.
I'll try to outline some of the families of thought here:
Whatever your data model is, keeping a copy of it for every change that a user makes. Hitting command-z finds the most recent version of all your data and replaces the current state with that.
Because storing a copy of everything will obviously consume a lot of storage, many immutable history implementations find ways to cut down on storage. You can use immer or another library that does structural sharing, or specialized compression setups.
Immutable history was how I learned to implement undo/redo. I wrote about this back in 2015, using Immutable.js. And the same technique is more or less in place in Mapbox Studio and iD.
The main alternative to immutable history is storing a history of the commands you performed on a dataset. For example, if you can increment a number, the reverse is to decrement that number. So running undo runs the "reverse" and redo runs the "forward" of that action.
Under the heading of command history, there are some additional wrinkles:
I quickly discovered that the idea of immutable history powered undo was totally incompatible with collaboration. Basically, you and some collaborator are working on a document and your changes are merged into the document in real-time. You might be editing one feature, your collaborator is editing another.
When one of you hits command-z, you want to undo the changes you made, not your collaborator's changes. You might not even be aware of what the other person is doing - their work is offscreen, somewhere else. So you need a sort of ownership built into your undo system.
So, commands. And I first implemented commands in the 'bidirectional' sense, generating both the undo & redo commands at the time you do something. This was quickly disproven because, well:
The last step feels wrong. What if the shape was heavily modified by your team before you delete it, and then your delete-undelete step turns it back into its initial form? That would be bad.
So I'm just agreeing with Figma's blog post some more - when it comes to collaborative undo/redo, there isn't some provable definition of what the "good behavior" is, but I think it's clear that some of the solutions end up feeling wrong. A simple immutable history was a lovely, comfortable idea, but it only worked for me in the past because Mapbox Studio is single-player, and iD editor isn't a realtime collaboration tool.
There are some interesting things to note about actually putting this system into practice.
First, batches and transactions are really important. Let's say you merge a bunch of features in Placemark. This removes the original features and adds a new feature. A naive undo history might look like:
This obviously feels wrong: the deletion of old features & addition of new features should be part of the same thing.
The abstraction I chose for this I call a "moment" but it could be a "step" or a "commit" or something else. Moment felt like it didn't conflict with any existing terminology and it felt whimsical. Here's what a moment looks like:
This follows a theme in Placemark - basically everything is plural, whether it's deleting or updating things, selections, and so on - almost everything should be compatible with batching. This really benefits things like server communication, with fewer requests, and some aspects of frontend performance, like transactions with Replicache.
This is the weirdest part, and the part that the aforementioned Figma article refers to. So the history in Placemark is stored as two arrays, for undo & redo states. You could totally store this as one single array and some pointer to where the current state is. And the order of the arrays is from most recent to least, in both directions, but that again is up to you.
But the weird part is here:
The weird part is the call to this.apply, which generates a new reverse moment. So if you created a feature and then hit undo, you execute a "delete" command, and create a new "create" command with the feature you just deleted.
One neat aspect of this change is that when you create a feature, the only thing that needs to be created and stored on the list of commands is a "delete" command with that feature's id.
Of course, there's more. Think about a color picker or what happens when you drag a vertex. Most likely, what you want out of that experience is
This necessitates an idea of ephemeral states, or a sort of pausing or grouping of the undo history. That's precisely what Placemark has right now - in the informal state machine for drawing lines and polygons, all of the geometry modifications that happen during a drag are ignored, and a new moment in history is only added when you click.
I really wanted one system to handle both undo history and versioning, but that just doesn't make sense: undo history should be different for every user, and it naturally fits in local state, though you could sync it to a server as a treat.
Placemark's version system will be something more like the immutable history idea, using snapshots on in object storage or a fancy table layout in Postgres. Its history will be initially linear, and might have to eventually include concepts like forking and merging.
The idea of using git or another pre-existing versioning system for this part of the system keeps coming up, but so far I don't see it working. Placemark will likely sync to GitHub, but not use git internally, unless my architecturally calculus changes drastically.
Placemark's system for undo works for a lot of map-making experiences, and it generally makes command+z work.
There are still some challenges, in the long-term: