7 ms·

Writing a tiny undo/redo stack in JavaScript

170 points by julik 2y ago

hyperhello 2y ago
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.
- nukem222 2y ago
  > 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.
  - rekabis 2y ago
    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.
  - frou_dh 2y ago
    2019: https://www.macworld.com/article/233056/ios-13-and-ipados-13-how-to-use-the-new-gestures-for-cut-copy-paste-undo-and-redo.html https://www.macworld.com/article/233056/ios-13-and-ipados-13...
    - nukem222 2y ago
      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.
      - julik 2y ago
        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.
        nukem222 2y ago
        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.
- julik 2y ago
  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 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 2y ago
    If you're interested, [plug] here is my technique, just a page of script. https://hypervariety.com/NativeBrowserUndo/NativeBrowserUndo.html https://hypervariety.com/NativeBrowserUndo/NativeBrowserUndo...
- sgarland 2y ago
  TIL this is why that modal has popped up at seemingly random times. Very useful, if you know how to summon it!
  - aitchnyu 2y ago
    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 2y ago
      Element's crash reporting system is still called 'rageshake' today, and you can enable the shake-to-report function in dev settings.
balamatom 2y ago
You can clear an array in JS by setting foo.length = 0? TIL.
- kupopuffs 2y ago
  omg this language just keeps getting deeper and deeper
  - deleted 2y ago
    [deleted]
  - animanoir 2y ago
    [dead]
  - z3t4 2y ago
    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.
- dudus 2y ago
  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 2y ago
    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/Reference/Global_Objects/Array/splice#deletecount https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe...
- sieabahlpark 2y ago
molszanski 2y ago
Thank you for sharing Other notable inspirations https://immerjs.github.io/immer/patches/ https://immerjs.github.io/immer/patches/ https://github.com/webstudio-is/immerhin https://github.com/webstudio-is/immerhin
- bhl 2y ago
  https://github.com/coolsoftwaretyler/mst-middlewares/blob/main/src/undo-manager.ts https://github.com/coolsoftwaretyler/mst-middlewares/blob/ma...
benatkin 2y ago
Using two stacks doesn't actually make it more robust. I think using a private property for the stack would, though.
- julik 2y ago
  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.
  - benatkin 2y ago
    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.
    - julik 2y ago
      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.
      - 2y ago
atum47 2y ago
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.
evanrelf 2y ago
A zipper!
catapart 2y ago
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 https://github.com/catapart/magnitce-action-history
- julik 2y ago
  This is very neat. Doesn't this kinda cross functuionalities with the MutationObserver?
  - catapart 2y ago
    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?
londons_explore 2y ago
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.
- superb_dev 2y ago
  Is your moral just to give up?
  - londons_explore 2y ago
    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".
    - esperent 2y ago
      The main reason you can't do that on Facebook is that it would confuse the hell out of people.
    - muspimerol 2y ago
      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.
    - deleted 2y ago
      [deleted]
    - benatkin 2y ago
      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.
noduerme 2y ago
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 2y ago
  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 2y ago
    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.
infogulch 2y ago
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/0576f199cb7a765efb3cd7a7828fd19ff3af094b#diff-4f43ed31c28406a288f2c26932c9827db19761ce9449e7d6c24b2339b19a3080R100-R140 https://github.com/VSCodeVim/Vim/commit/0576f199cb7a765efb3c... [2]: https://github.com/VSCodeVim/Vim/blame/v1.29.0/src/history/historyTracker.ts#L156-L201 https://github.com/VSCodeVim/Vim/blame/v1.29.0/src/history/h...
- opello 2y ago
  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-235476908 https://github.com/VSCodeVim/Vim/pull/496#issuecomment-23547...
  - infogulch 2y ago
    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.
ulrischa 2y ago
I wonder why undo redo is not a built in feature. It is such a core functionality
- mrkeen 2y ago
  Built into what, exactly? Undo-redo is in tension with how a lot of people like to program, namely using (non-undoable) effects.
hyperbolablabla 2y ago
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
- dividuum 2y ago
  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 2y ago
    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.
    - 2y ago
nyanpasu64 2y ago
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).
fergie 2y ago
Very elegant code. Somebody will surely find a way to make it much less robust and readable by converting it to Typescript
- julik 2y ago
  Good one! I thin it will be fine.... ..exceptForThisArgumentAtTheEnd.
z3t4 2y ago
If you have Collaborative Text Editing ( Operational Transform or CRDT) you get undo/redo for free!
samchon 2y ago
The background is yellow and it hurts my eyes ToT
2bit 2y ago
You can find a similar method in zundo, a zustand middleware for undo/redo. It has the concept of pastStates and futureStates.
im3w1l 2y ago
In this code past uses push/pop and future uses shift/unshift. But they can both use push/pop.
- julik 2y ago
  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)
  - im3w1l 2y ago
    push pop is faster though
neilparikh 2y ago
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-fp/docs/huet-zipper.pdf https://www.st.cs.uni-saarland.de/edu/seminare/2005/advanced...

170 points by julik 2y ago

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.

nukem222 2y ago
> 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.
- rekabis 2y ago
  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.
- frou_dh 2y ago
  2019: https://www.macworld.com/article/233056/ios-13-and-ipados-13-how-to-use-the-new-gestures-for-cut-copy-paste-undo-and-redo.html https://www.macworld.com/article/233056/ios-13-and-ipados-13...
  - nukem222 2y ago
    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.
    - julik 2y ago
      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.
      - nukem222 2y ago
        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.
julik 2y ago
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 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 2y ago
  If you're interested, [plug] here is my technique, just a page of script. https://hypervariety.com/NativeBrowserUndo/NativeBrowserUndo.html https://hypervariety.com/NativeBrowserUndo/NativeBrowserUndo...
sgarland 2y ago
TIL this is why that modal has popped up at seemingly random times. Very useful, if you know how to summon it!
- aitchnyu 2y ago
  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 2y ago
    Element's crash reporting system is still called 'rageshake' today, and you can enable the shake-to-report function in dev settings.

balamatom 2y ago

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

kupopuffs 2y ago
omg this language just keeps getting deeper and deeper
- deleted 2y ago
  [deleted]
- animanoir 2y ago
  [dead]
- z3t4 2y ago
  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.
dudus 2y ago
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 2y ago
  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/Reference/Global_Objects/Array/splice#deletecount https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe...
sieabahlpark 2y ago

molszanski 2y ago

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

bhl 2y ago
https://github.com/coolsoftwaretyler/mst-middlewares/blob/main/src/undo-manager.ts https://github.com/coolsoftwaretyler/mst-middlewares/blob/ma...

benatkin 2y ago

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

julik 2y ago
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.
- benatkin 2y ago
  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.
  - julik 2y ago
    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.
    - 2y ago

atum47 2y ago

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.

evanrelf 2y ago

A zipper!

catapart 2y ago

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 https://github.com/catapart/magnitce-action-history

julik 2y ago
This is very neat. Doesn't this kinda cross functuionalities with the MutationObserver?
- catapart 2y ago
  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?

londons_explore 2y ago

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.

superb_dev 2y ago
Is your moral just to give up?
- londons_explore 2y ago
  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".
  - esperent 2y ago
    The main reason you can't do that on Facebook is that it would confuse the hell out of people.
  - muspimerol 2y ago
    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.
  - deleted 2y ago
    [deleted]
  - benatkin 2y ago
    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.

noduerme 2y ago

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 2y ago
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 2y ago
  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.

infogulch 2y ago

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/0576f199cb7a765efb3cd7a7828fd19ff3af094b#diff-4f43ed31c28406a288f2c26932c9827db19761ce9449e7d6c24b2339b19a3080R100-R140 https://github.com/VSCodeVim/Vim/commit/0576f199cb7a765efb3c... [2]: https://github.com/VSCodeVim/Vim/blame/v1.29.0/src/history/historyTracker.ts#L156-L201 https://github.com/VSCodeVim/Vim/blame/v1.29.0/src/history/h...

opello 2y ago
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-235476908 https://github.com/VSCodeVim/Vim/pull/496#issuecomment-23547...
- infogulch 2y ago
  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.

ulrischa 2y ago

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

mrkeen 2y ago
Built into what, exactly? Undo-redo is in tension with how a lot of people like to program, namely using (non-undoable) effects.

hyperbolablabla 2y ago

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

dividuum 2y ago
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 2y ago
  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.
  - 2y ago

nyanpasu64 2y ago

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

fergie 2y ago

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

julik 2y ago
Good one! I thin it will be fine.... ..exceptForThisArgumentAtTheEnd.

z3t4 2y ago

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

samchon 2y ago

The background is yellow and it hurts my eyes ToT

2bit 2y ago

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

im3w1l 2y ago

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

julik 2y ago
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)
- im3w1l 2y ago
  push pop is faster though

neilparikh 2y ago

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-fp/docs/huet-zipper.pdf https://www.st.cs.uni-saarland.de/edu/seminare/2005/advanced...