Writing a tiny undo/redo stack in JavaScript
70 comments
·March 24, 2025infogulch
opello
And it looks like "the most beautiful possible" `let [current, ...rest] = changes` [1] never happened either!
[1] https://github.com/VSCodeVim/Vim/pull/496#issuecomment-23547...
infogulch
True! I didn't even remember that detail. To respond to that comment nearly a decade later, I might object that swapping a zero copy zero allocations iterator for something that does O(N^2) element copies and allocates N new lists for zero practical benefit cannot be beautiful on principle, regardless of how pretty it looks on the surface.
Beauty is when practicality and perception pull in parallel towards purpose. Sacrificing one for the other can have a certain aesthetic quality, but I would not call it beautiful.
londons_explore
In reality, you're gonna quickly run into battles with state's that are complex and unclonable - in flight fetch requests, circular references, webasm modules that have internal state, etc.
Then there are things where the browser already implements undo functionality like navigation (back button) and editing text boxes. Your undo is going to have to work nicely with those.
You'll either end up with a buggy undo implementation, or end up spending a lot of engineering time hunting corner cases.
julik
I am well aware of those challenges, but I believe for the purposes I need it for it will work just fine.
superb_dev
Is your moral just to give up?
londons_explore
Thats what the vast majority of webapps do...
Can't exactly log into facebook, post something to your wall, and then press Command+Z to undo the post, and the Command+Z again to undo the login...
No - both of the undo's have a special way to do it - click "delete post" followed by "log out".
benatkin
Having Command-Z and Command-Y work with actions such as deleting a post or logging in doesn't help with having a proper undo system undo anyway.
Command-Z and Command-Y should be for document-based undo. Give the user some way of knowing what document they're working on. Even if the user is going to use the keyboard it helps to have Undo/Redo icons so they know what Undo/Redo applies to. Now, documents in code are more complex, but there's a wealth of research on it, and stuff like CRDTs and the history systems of libraries like ProseMirror and CodeMirror.
And often the undo of deleting a post is needed, but that's a separate thing, nowadays handled by the snackbar components. And if you really needed a redo, that would be something to put in a history feature.
Navigation does have a stack which works the same way as undo/redo but it doesn't normally use Command-Z and Command-Y.
muspimerol
But logging in and posting don't seem like "undoable" actions to me. That would be similar to undoing a save or undoing a login to Adobe CC in Photoshop. Things definitely get trickier with network requests, but that can be solved with something like CRDT.
esperent
The main reason you can't do that on Facebook is that it would confuse the hell out of people.
null
probabletrain
Navigation isn't usually "undo", conceptually.
hyperbolablabla
In my C code, I implement undo/redo using write protection (mprotect).
First you mark all of your app memory as read only, so that you can define a SIGBUS handler when attempts are made to write to it.
Then when you detect a write to a page in the app memory, you append a copy of that page's memory to a stack, and then mark the page as writeable so that the page can be updated.
Then undo is simply a matter of popping the stack and overwriting the app memory with the copy stored on the stack entry.
This means you don't have to explicitly write "actions" for everything you want to undo/redo. All in-memory actions are handled automatically.
Obviously this means that things like FS changes or network IO changes aren't captured, but sometimes that's fine, and I'm sure there's a way to extend this scheme to handle those things somehow
zombot
I'd call that the Russian Roulette of C coding. I bet it's entertaining, but survival is sheer luck.
actionfromafar
Emacs did something similar to optimize cold starts or something back in the day. It works if you are holding it right™
amelius
That's great until your manager says something like: please group undo actions such that typing a word+undo will remove the entire word, not just one character at a time. Or show "Redo" in the menu after the undo.
Anyway perhaps there's a place for your solution at the compiler/language level, at various granularities. I've played with the thought, but considered it impractical so far considering those always changing requirements. Also, memory use might go through the roof for some applications.
dividuum
I honestly can’t tell if that’s an elaborate joke response or if that’s really something that works. If it does:
* How do you make sure you capture all mapped memory within a process? Walking something like /proc/self/maps?
* Does this include the stack and if so, doesn’t this cause havok when you write back. And if it doesn’t include the stack, can’t run things out of sync easily?
* This is then a page sized undo/redo, so it isn’t atomic with regards to actions triggered. Wouldn’t partially undoing such changes easily cause an invalid state?
hyperbolablabla
I can't speak to every use case but it's been working great for my game:
1. I don't heap allocate anything after init. All allocations are custom allocated from this memory. I use a linear allocator, but could use some other scheme.
2. I don't account for the stack at all, but it doesn't mess anything up. The only important memory is the app memory, and that persists across frames.
3. It is, but you're computing deltas across frames, so they are atomic wrt user input. It's true that if multiple changes are made to the same page in the same frame then undoing that page undoes all of the changes, but that is often desirable from the user's perspective.
dividuum
Thanks for your response. Interesting. I can see that working with these restrictions. This basically also assumes the data within that memory area only has pointers to either somewhere else in that area or to static structures outside, correct? Also the write rate is probably quite low as I imagine constantly handling SIGBUS would quickly slow things down? Did you look into userfaultfd?
julik
That's clever and can work great if you don't hold any resource handles
molszanski
Thank you for sharing
Other notable inspirations https://immerjs.github.io/immer/patches/ https://github.com/webstudio-is/immerhin
nyanpasu64
If you get clever with things you can define actions with a single "apply_swap()" method which applies an edit and saves the old state (on the first call and subsequent odd calls), and reverts the edit and saves the new state (on the second call and subsequent even calls). This avoids having to write separate implementations for adding/removing items and redo/undo, and allows applying edits on a real-time thread with zero memory allocations (after constructing an edit action).
balamatom
You can clear an array in JS by setting foo.length = 0? TIL.
koito17
That works because the length field acts as a fill pointer. In Common Lisp, it's also a common technique to empty an array in-place by setting the fill pointer to 0. The concept is quite old!
In most cases, there isn't a beneficial performance boost from emptying an array this way. One needs to allocate in a loop or do something equally inefficient to measure the difference between `coll = []` and `coll.length = 0`. (This assumes the language runtime does not statically allocate an immutable, empty array and use that to represent all empty arrays. Clojure does this, for instance, so no allocations occur when binding a variable to [] or other empty collections).
normie3000
> `coll = []` and `coll.length = 0`
In JavaScript these two statements have very different effects.
dudus
I think this is actually the best way to zero an array in place. The other option is using foo.splice(0,foo.length)
foo = []; Will reassign the reference but other pointers can still have the array.
foo.length=1 will remove all elements but the first.
jansan
foo.splice(0) is actually sufficient. From the docs:
"If deleteCount is omitted, or if its value is greater than or equal to the number of elements after the position specified by start, then all the elements from start to the end of the array will be deleted."
https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe...
kupopuffs
omg this language just keeps getting deeper and deeper
z3t4
and just when you think you know it all it will get a major overhaul. Then there will come another language that compiles to JS, and then that language will die out and you have to rewrite your code into the next language that compiles to JS.
null
animanoir
[dead]
kazinator
Adjusting the length of an array is a basic operation that should be in any language that has arrays/vectors.
sieabahlpark
[dead]
noduerme
I think it's a clever and elegant solution. Obviously, ymmv depending on the environment, or what exactly you're trying to undo/redo. But I like that it thinks of two stacks. StructuredClone is not something I've ever used or am familiar with... I'm used to storing and later de-referencing pointers to anonymous functions. But in your use case, a clone makes a lot more sense, and I'm kinda looking forward to playing with that next time I have a mess of event handlers.
neRok
I wonder if using structuredClone() has a performance penalty compared to a simple block-scoped closure though?
let doFn, undoFn; {const newStroke = currentStroke; doFn = ()=>strokes.push(newStroke); undoFn = ()=>strokes.pop();}noduerme
I'm sure it has a massive performance penalty, but probably not as much as other runtime ways of deep-copying. It's doing something different than your code above.
In the code above, `newStroke` just makes a reference to `currentStroke`. Nothing is changed by creating a `const newStroke` and pushing it to the array. You're just pushing a reference to the original. In the OP's example, `currentStroke` is something that gets modified. If you used the code above, as soon as you modify `currentStroke`, every reference in the `strokes` array will change. The fact that you used `let` instead of `var` in the loop means you are creating a new constant, but that constant isn't preserving a snapshot of `currentStroke` unless you explicitly make it a new object. Otherwise it's just a reference. You need to deep-clone it in the undo function in order to preserve its previous state. Something like:
`let previousStroke = {a:currentStroke.a,b:currentStroke.b}` where `a` and `b` are primitives that are copied, not objects that are referenced, before you change `currentStroke`. If you did it manually, you'd have to keep keep recursively checking `a` and `b` all the way down to their primitives, and rebuild the object.
An easy way of doing this for objects without functions or classes in them is just `const previousStroke = JSON.parse(JSON.stringify(currentStroke));` but usually I've had to write custom re-initializers if for example `previousStroke.a` was a class instance.
neRok
> Nothing is changed by creating a `const newStroke` and pushing it to the array.
Not true. If you look carefully you will see the `const` and everything after it is wrapped in curly braces, and those braces create a block...
> Traditionally (before ES6)... blocks with curly braces do not create scopes... [but] blocks are finally treated as scopes in ES6, but only if you declare variables with let or const. — https://developer.mozilla.org/en-US/docs/Web/JavaScript/Guid...
So the curly braces with the use of const/let creates a new lexical scope, hence solving the issue. You can test it in the browser console to confirm;
var stack=[], cmd="";
cmd="success"; stack.push(()=>cmd);
cmd="fail"; stack.push(()=>cmd);
stack[0](); /* returns "fail" */
var stack=[], cmd="";
cmd="success"; {const c=cmd; stack.push(()=>c);}
cmd="fail"; {const c=cmd; stack.push(()=>c);}
stack[0](); /* returns "success" */
catapart
Ha! I wrote my own version of this as a web component[0]. Very handy thing to have, for web apps!
Nice to see it distilled into something so straightforward! Thanks for sharing!
julik
This is very neat. Doesn't this kinda cross functuionalities with the MutationObserver?
catapart
It doesn't actually use the MutationObserver, no, but it does use the `slotchange` event which might be syntax sugar for a mutation observer on a slot element? Not really sure how it works under the hood.
Of course, the end result can be thought of as a kind of specialized mutation observer. It's "reactive" to adding certain kinds of children and alerting you when those children change. The specialization, though, is in how it also implements the structural notion of a timeline and can therefore provide "back" and "forward" and "point in time" information about the children during events. This makes it a lot more useful for history than a simple mutation observer.
Of course, at the end of the day, it's only exposing the objects that you put in to the history back to you, so it's entirely on the implementing dev to decide how to display and what gets done with "action" data. In that way, it's not actually doing the functional work that one might expect of a history framework. But the intention is to keep it agnostic. This same history component could work with CRDTs as easily as a simple local data store or a REST api.
The main thing I think of it as is an "input" that can give the implementing dev a good idea of what the user is trying to do. An "undo", a "redo", or a "jump to point". That way I can drop it in to any web project and all I need to implement is "what happens on undo", "what happens on redo", etc...
And then, of course, that last part about using it wherever is why it was built as a "web component" (custom element, but whatever). Include a single js script, and I can start using the component like a text input - a way to collect user input so that I can implement what happens during the interactions I want to influence.
ETA: Off topic, but since I've got you here...
I actually created the action-history element for use in a drawing web app I had been messing with. It's meant to mimic the design and functionality of the history panel in photoshop. To that end, given your examples, I wonder if it might have some use for what you were trying to do?
neilparikh
This data structure is called the zipper, and the neat thing is that you can generalize this to more complicated types like trees: https://www.st.cs.uni-saarland.de/edu/seminare/2005/advanced...
2bit
You can find a similar method in zundo, a zustand middleware for undo/redo. It has the concept of pastStates and futureStates.
hyperhello
It's very nice, but it doesn't do system undo. You can shake iPhones to get an Undo/Redo dialog, for example.
So you can probably trap Meta-Z but some people use menus or the other affordances.
julik
Well, hooking into system undo is tricky as there still seems to be no native web platform thing for that. I see all kinds of things like https://github.com/samthor/undoer but the article was about the foundation, rather than the integration. For what I am doing, shortcuts + clickable buttons on screen will do the job.
hyperhello
If you're interested, [plug] here is my technique, just a page of script.
https://hypervariety.com/NativeBrowserUndo/NativeBrowserUndo...
nukem222
> You can shake iPhones to get an Undo/Redo dialog, for example.
When are they gonna add a proper UI for this? I look like a moron using the phone this way, and shaking only works to trigger the undo about half the time.
frou_dh
nukem222
Edit: thank you!
Man I get gestures have been embraced by the community, but this is emphatically not what I meant. The only gesture that makes sense to me is pinch-to-zoom and maybe swiping on cards that appear to be floating.
There's no way to discover this functionality outside of googling documentation and it often doesn't work with one hand.
rekabis
Half the time? More like 10% of the time.
Sometimes I think I have to use a paint can shaker on a 5-minute cycle just to trigger it.
sgarland
TIL this is why that modal has popped up at seemingly random times.
Very useful, if you know how to summon it!
aitchnyu
Around 2018, the ultra buggy Matrix messenger had a onShakeListener that triggered a dialog "It seems you are frustrated. Do you want to raise a bug report?"
JadedBlueEyes
Element's crash reporting system is still called 'rageshake' today, and you can enable the shake-to-report function in dev settings.
im3w1l
In this code past uses push/pop and future uses shift/unshift. But they can both use push/pop.
In 2016 I was frustrated by vscode vim mode undo/redo stack: when you activated undo it would process each individual character insertion/deletion event in sequence exactly as you typed it, e.g. if you type and delete the same character 100 times it would replay that exact sequence even if it was all one logical INSERT. Replay speed was slow enough (maybe 15-20 changes per second?) that it was excruciating to use.
So I rewrote it and added logic to merge adjacent changes [1] which helped immensely, enough that undo/redo felt instant again. It looks like the core merging logic was rewritten a few years ago [2] (which caused a regression, is imo less readable, and removed useful comments -_-) but the basic idea is still there today.
[1]: https://github.com/VSCodeVim/Vim/commit/0576f199cb7a765efb3c...
[2]: https://github.com/VSCodeVim/Vim/blame/v1.29.0/src/history/h...