Writing a tiny undo/redo stack in JavaScript | Hacker News Reader

Writing a tiny undo/redo stack in JavaScript

blog.julik.nl

170 pointsjulik69 comments

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...

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...

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.

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.

Is your moral just to give up?

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".

The main reason you can't do that on Facebook is that it would confuse the hell out of people.

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.

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.

I am well aware of those challenges, but I believe for the purposes I need it for it will work just fine.

Navigation isn't usually "undo", conceptually.

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

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?

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.

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?

I'd call that the Russian Roulette of C coding. I bet it's entertaining, but survival is sheer luck.

Emacs did something similar to optimize cold starts or something back in the day. It works if you are holding it right™

That's clever and can work great if you don't hold any resource handles

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.

Besides memory use I'm not sure why his approach isn't easy for everything you suggested.

Want to group undo actions? It's pretty easy to define arbitrary grouping algorithms on the sequence of recent state snapshots, which yields...a smaller sequence of state snapshots :-) a nice composeable idea.

To show redo after an undo, store recent undo triggers in the state, and if there is undo in current state, show redo with a list of older mem states to jump to. This repr also makes it easy to wipe out redos when doing a redo-breaking operation like editing the doc.

Memory use can indeed become a problem. But if/when it does, there is probably some obvious trait of the sequence of recent states that makes it easy to compress. Like for example that it's 99% the same contents, after a small edit. Or that one edit type dominates. Or that folks don't often care if they can't Ctrl+Z through 8GB of typing.

I think most programmers would gain by not dismissing simple approaches out of hand as too simple.

If writing it off for memory, write out the math for the size of the state and the allotted memory. This is not the era of computers that our languages were invented in; the page size your CPU fetches from insanely fast SSDs can be 4kb. And it can do a lot of that in a blink. Trying to shift runtime work (that the computer does) back to compile/design time (that the dev does) can cripple a system's performance in the short run (for coding/delivery time) and long run (for performance after pointer chasing)...luckily most of the time it doesn't matter anyway :-)

Thank you for sharing

Other notable inspirations https://immerjs.github.io/immer/patches/ https://github.com/webstudio-is/immerhin

https://github.com/coolsoftwaretyler/mst-middlewares/blob/ma...

You can clear an array in JS by setting foo.length = 0? TIL.

omg this language just keeps getting deeper and deeper

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.

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.

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...

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).

> `coll = []` and `coll.length = 0`

In JavaScript these two statements have very different effects.

Adjusting the length of an array is a basic operation that should be in any language that has arrays/vectors.

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).

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.

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();}

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.

> 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" */

It's probably not a good idea to do it this way, because it's easily "overlooked". I would probably use a class or factory-function if I had the need.

TIL

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!

[0] https://github.com/catapart/magnitce-action-history

This is very neat. Doesn't this kinda cross functuionalities with the MutationObserver?

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?

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...

You can find a similar method in zundo, a zustand middleware for undo/redo. It has the concept of pastStates and futureStates.

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.

> 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.

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.

2019: https://www.macworld.com/article/233056/ios-13-and-ipados-13...

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.

There is another that is fairly intuitive for a Mac person: tap-and-hold to get a contextual menu. Shame they have hidden it under some kind of "haptic feedback" thingamagig.

The ipad also has an icon above its keyboard. Whatever lack of obvious interaction is available on the phone seems intentional.

Cynically, I think you'd just look like even more of a fool shaking an ipad and this is the only reason they approved such a button.

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.

If you're interested, [plug] here is my technique, just a page of script.

https://hypervariety.com/NativeBrowserUndo/NativeBrowserUndo...

TIL this is why that modal has popped up at seemingly random times.

Very useful, if you know how to summon it!

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?"

Element's crash reporting system is still called 'rageshake' today, and you can enable the shake-to-report function in dev settings.

I did something similar the other day but I end up using a circular buffer of fixed size. Everytime you push a new state the oldest state gets discarded.

Using two stacks doesn't actually make it more robust. I think using a private property for the stack would, though.

To me - it does, because using an index is always this fiddly thing. Do you increment/decrement the index before doing something or after? Do you need to check that you have incremented to len or above? Do you need to check that you haven't decremented below 0? You also can't truncate your undo history without also changing your pointer.

It really is better to have two separate arrays - unless your perf requirements dictate that you, for example, preallocate your entire stack and keep it fixed size.

I think it's nice to explore both approaches, but that an equally robust implementation can be made either way. Where yours might shine is if there is a lot of change in code directly accessing the data structures. The code directly accessing it could be constrained to being inside of the class using a private property, as I mentioned above. Logically you can think of it as two stacks while having a single array, and think of the stack pointer as splitting the stacks - and then you can go back and think about it in the more traditional way of an array with a stack pointer. I've written them both ways and it's helped me to understand the problem, but ultimately using a single array actually feels cleaner to me.

Fair point! It also felt clearer to me at first, but I found that I would need some "management" to avoid indexing into nonexistent indices and otherwise manage that pointer - like you are saying, the checks for that index not falling off the end/start of the stack would need to go somewhere. And I just wanted to have... _less stuff._ _Less stuff_ is better, certainly for me when doing solo dev.

I think I'll take another look at it. Maybe I'll prefer two stacks!

When I last implemented it, it was for an ambitious project, where I just got it working and then moved onto something else. The single stack seemed to work pretty well. https://codeberg.org/macchiato/ristretto/src/branch/window-w...

I used .at(), I'm not sure why, with a check to make sure it isn't under 0 at the right place, so the -1 behavior wasn't an issue. To see it working go to https://ristretto.codeberg.page/ on desktop and click client-server-simulator.md

Edit: I think it feels better to use at because it seems an accident of history that using an index doesn't error in JavaScript, while with at() it seems to be on purpose, like how .get() in python dicts doesn't error on a missing key.

In this code past uses push/pop and future uses shift/unshift. But they can both use push/pop.

That is deliberate, because I wanted the `past` + `future` to go in the same direction chronologically. They are separate stacks, but they represent a certain continuity in time - so I wanted to have it ordered the same (chronologically)

push pop is faster though

If you have Collaborative Text Editing ( Operational Transform or CRDT) you get undo/redo for free!

A zipper!

I wonder why undo redo is not a built in feature. It is such a core functionality

Built into what, exactly?

Undo-redo is in tension with how a lot of people like to program, namely using (non-undoable) effects.

The background is yellow and it hurts my eyes ToT

Very elegant code. Somebody will surely find a way to make it much less robust and readable by converting it to Typescript

Good one! I thin it will be fine.... ..exceptForThisArgumentAtTheEnd.

Reply on news.ycombinator.com