Thinking about undo/redo is a great place to start thinking about your text editor's underlying data structure.
I went down this rabbit hole a while back. I had to really dig[1]: it's been 5 years...
---
Data structures aren't the only interesting rabbit-hole, though.
UI/UX doesn't get nearly as much attention as it deserves. There are really only two that I am aware of: Notepad and Vim. Vim's modal editing results in the user explicitly defining undo/redo points. You can even use the "." key to re-redo! Everything else essentially boils down to a greater or lesser version of Notepad: The user can't predict what state undo will take them to.
Something I have wanted to create for a long time (definitely more than 5 years) is a new modal editor. I don't want yet another vi clone: I want something that is defined from the ground up by user configuration. Maybe one of these days I will get far enough past the ADHD wall to make it happen...
I am currently working on an editor. Definitely interesting to try different ideas just to find out why certain things in Vim are that way. Also the "." key is more complicated than I expected, the exact start of an edit operation depends on the behaviour of certain default keybindings. It just works so smoothly I had never thought much about it before.
> Maybe one of these days I will get far enough past the ADHD wall to make it happen...
That's definitely the most difficult part, for me it got easier at some point once it actually seemed realistic that I'd manage to finish it one day.
> Vim's modal editing results in the user explicitly defining undo/redo points.
? How? Does switching to normal mode create an undo/redo point? Someone asked me if the granularity of Vim's undo/redo could be increased (i.e., more frequent undo/redo points). In what they demonstrated, Vim's granularity seemed less than other applications (i.e., undo/redo acted on relatively large chunks of input); in some brief research, I didn't find a solution.
I still use a lot of nvi on openbsd. and it has a strange quirk to it's undo.
so "u" undoes your last action. but if you hit it again it undoes the undo, a redo if you will. I did not really think about it much, just accepted that was how nvi worked, a single level undo. But that is not true at all. the trick is you have to "u" undo then "." repeat previous action and you get the full undo stack. and, like the parent post mentioned, you also get a full redo stack the same way. Get it to redo then repeat previous action.
I am not exactly sure what vim does, But I suspect this is one of it's improvements.
> Something I have wanted to create for a long time (definitely more than 5 years) is a new modal editor. I don't want yet another vi clone: I want something that is defined from the ground up by user configuration.
Some parts of the UI are still defined in the compiled language (so don't fully fit your philosophy yet), but a big part of the UI comes from the configuration loaded at runtime: every time the editor starts, it interpretes and runs this configuration defining the UI: https://github.com/alefore/edge/blob/master/rc/hooks/start.c...
(This file is not compiled into the editor, but loaded and executed directly at runtime; the format of that file is my editor's extension language/configuration (the equivalent to emacs lisp or vimscript), which just happens to be a garbage collected C-like language.)
> Maybe one of these days I will get far enough past the ADHD wall to make it happen...
I have that hope for literally hundreds of things... but I know I will never actually get to do any of those things. I can think of any one of them right now and be unable to even try. I hate this existence.
In my text editor (https://github.com/alefore/edge) I keep the undo/redo history always linear, which I find works pretty well.
So suppose the user does the following operations:
• Insert "Hello"
• Insert " world!"
• Undo once.
• Insert ", Cameron!"
At this point, undo operations would gradually transform the buffer thus: "Hello, Cameron!" => "Hello" => "Hello world!" => "Hello" => "". Obviously, one can redo at any point. The undo/redo days structure don't preserve the state, just the transformations (which are reversible).
The gist of it is that when you apply a modification to the buffer and the redo stack isn't empty, the redo stack gets flipped and inserted into the undo stack. If you undo a long list of transformations and then make a change, that long list is duplicated, but this hasn't been a problem in practice.
This is how traditional Emacs undo is implemented as well. I like it but it seems to be not the norm; it does take a little bit to get used to. (There's plenty of packages to transform Emacs undo into something more like a tree structure, though I don't personally use them because I'm used to the above behavior.)
Interesting, none of the editors I just tested (notepad / visual studio / sublime / github) works like this.
I think of undo/redo as "time traveling", going back to where I was one / two / several steps bevor. The mental model of your implementation is more akin of actually "doing" the undo. Like if you undo insert " world!", you create an action that deletes " world!". The timeline still goes forward, but now has a delete action.
Emacs undo-tree does everything I need. Emacs also supports undo in region which most editors don't seem to support and wasn't covered by the article.
I actually used regular Emacs undo for years which lets you get everywhere in the tree with a kind of tree traversal but you won't know where you are. I resisted undo-tree for ages but it's definitely worth it as it stays out of the way until the occasion you might need to use it.
Emacs's undo is great in that invoking an undo command is itself undoable. And that is different from just your standard redo. It definitely needs some getting used to but it is very powerful.
But I think your second points deserves an even bigger mention: Emacs has the ability to apply undo only to a certain "region" - which in Emacs parlance is basically just a selection of text. For those of you who have never seen it:
imagine two parts of a file you're editing, say one part at the top, one at the bottom. You start by editing the first part (top) and then then move your cursor somewhere down to the second part of the file (bottom) to do some more editing there. But then you realize that your edits in the first part of the file were baloney. In most other editors, if you wanted to undo them, you'd be forced to also undo the edits in the second part of the file. In Emacs, however, you can simply select the first part at the top of your file - if you hit undo then, it will only undo the last edits done inside that selection and leave all edits outside of that region untouched.
I just skimmed it, but it looks like vim really has undo/redo "solved":
- Modal editing makes for nice "undo" points, clarifying whether undo should undo "World!" or "!".
- "g-" and "g+" eliminate the "orphaned redo". They walk the entire undo/redo tree rather than just the linear undo/redo.
- Time travel undo/redo is really handy when you want to go to where you were on the wall-clock. ":earlier 15 minutes" takes you to the code as it was 15 minutes ago.
> but it looks like vim really has undo/redo "solved"
Does it support restricting undo/redo to a selection? In Emacs you can select any region of text and just apply the undo history of the selection. That is extremely useful. Imagine working on to functions in the same file. You have are working on g() and realize you want to undo some change on f(), that you did before. Most editors don't support that. In Emacs you can just select the code of f() and press undo (C-_).
Several popular undo extension libraries break this feature.
Modal editing isn't enough if you type whole sentences/paragraphs of text within a single insert session
Also undo in selection is required to "solve" it, as well as semantic points besides "last 15 minutes" (like "last saved session" or "last time you quit the editor")
Also UI with a diff is sometimes better than having to undo/redo to see changes
I love vim but I actually find undo/redo to be one of the few annoyances of the program, because of the whole linear undo/redo thing. So I guess I need to look into this g+ option…
The idea of an undo “graph” in memory is something I’ve implemented, and in C++ even, so it was fun to read the article. Couldn’t agree more — once you’ve had it, going back to the linear, often truncated thing most application implement is a little sad.
In my case when state A transitioned to B, was undone and further changes made to get state C I would retain the XOR of the changed memory of the A->B transition as run length encoded bytes B’ and similarly C’ so it was lightweight and extremely fast to undo and redo (the latter being exactly the same as the former but applied to A rather than B, since that’s how XOR works). Cool stuff.
Maya's C++ API was what taught me the most about the importance of proper do/undo functionality. As soon as you start to modify the DAG, you really must ensure that the undo operation leaves everything (be it meshes or shaders or curves, whatever) as it was before your custom object got inserted into the DAG. Else your plugin is worthless.
I've been working on an editor (not text) in C++ and pretty early got into undo/redo. I went down the route of doIt/undoIt for commands but that quickly got old. There was both the extra work needed to implement undo separately for every operation, but also the nagging feeling that the undo operation for some operation wasn't implemented correctly.
In the end, I switched to representing the entire document state using persistent data structures (using the immer library). This vastly simplified things and implementing undo/redo becomes absolutely trivial when using persistent data structures. It's probably not something that is suitable for all domains, but worth checking out.
Reading the comments on how vim and Emacs have implemented Undo/Redo with various options was very helpful. I personally don't use these editors, but I'm working on a graph drawing tool where the user usually modifies multiple parts of the graph. Right now we only have linear redo/undo implemented. Reading about all this other options is really helpful. Especially the Time travel and the regional undo are very smart features that are also very helpful for all graphic based editors.
Jetbrains’ IDEs have both of them and more.
The feature is called “Local History”. [1]
You can see the history of an file, a selected region of text, or even your entire project. It can undo file deletions/moves/renames.
It feels like a personal “automated git without the git hassles”.
It has got me out of some really bad situations.
Both Ardour and Cubase (both DAWs) had branching undo/redo systems in the mid-2000s. Ardour and I think also Cubase abandoned it before 2010 because almost all users could not deal with the complexity.
Maybe for programmer-oriented text editors the user reaction/experience might be different.
Some points that often get left out of 'undo' discussions:
* The usual linked-list (or tree) implementation is very cache-unfriendly if you're undoing several steps at a time. Using "linked list inside a buffer" is better; this does not preclude trees, the back "pointer" just has to specify the offset as well as the previous buffer (when you reach the fixed-size allocation you will also have to do this). If you undo across a buffer change you'll also need to update the "most recent redo" backlink from the new buffer.
* SSO strings will usually beat external strings for small edits (this can be variable-size in the linked-list-in-a-buffer case); for large edits see if you can just incref part of the main editing buffer rope.
* It is highly useful to expose a few "shortcut" undo commands: undo to previous save, undo to previous build, etc. Manual tags is probably not very practical most of the time, and "save" is essentially one anyway.
If you are looking for counter examples, take a look at Excel on windows. It undoes in multiple windows.
Say you have two documents open. You make a change in the first then change the second document then go back to the first and make a change. One document has two changes and the other has one.
First undo impacts document one. Second alters document two. Infuriating
Yes. This is arguably the most infuriating implementation of undo/redo that I've used in any application.
It's worse than an undo that just wipes-out the document. In that scenario I'd just not use the feature.
The behavior in Excel tricks you into using the feature by working as you'd expect in a single document scenario. Then you open a second document and end up trashing one or the other when you undo the wrong thing.
I don't know how anybody ever thought this implementation was the right answer. Ever.
I used an editor with a redo tree, DeScribe (I believe) word processor on OS/2 and Windows. The redo tree was pretty cool, but I'm so used to losing my stuff on change after undo that I don't miss it. If I really cared to save a version, I would've committed it to my local git.
thomastjeffery|2 years ago
I went down this rabbit hole a while back. I had to really dig[1]: it's been 5 years...
---
Data structures aren't the only interesting rabbit-hole, though.
UI/UX doesn't get nearly as much attention as it deserves. There are really only two that I am aware of: Notepad and Vim. Vim's modal editing results in the user explicitly defining undo/redo points. You can even use the "." key to re-redo! Everything else essentially boils down to a greater or lesser version of Notepad: The user can't predict what state undo will take them to.
Something I have wanted to create for a long time (definitely more than 5 years) is a new modal editor. I don't want yet another vi clone: I want something that is defined from the ground up by user configuration. Maybe one of these days I will get far enough past the ADHD wall to make it happen...
[1] https://news.ycombinator.com/item?id=15381886
alpaca128|2 years ago
> Maybe one of these days I will get far enough past the ADHD wall to make it happen...
That's definitely the most difficult part, for me it got easier at some point once it actually seemed realistic that I'd manage to finish it one day.
truculent|2 years ago
Once you add deliberate checkpoints and the tree structure from the article, it feels like you’re more than halfway there.
wolverine876|2 years ago
? How? Does switching to normal mode create an undo/redo point? Someone asked me if the granularity of Vim's undo/redo could be increased (i.e., more frequent undo/redo points). In what they demonstrated, Vim's granularity seemed less than other applications (i.e., undo/redo acted on relatively large chunks of input); in some brief research, I didn't find a solution.
somat|2 years ago
so "u" undoes your last action. but if you hit it again it undoes the undo, a redo if you will. I did not really think about it much, just accepted that was how nvi worked, a single level undo. But that is not true at all. the trick is you have to "u" undo then "." repeat previous action and you get the full undo stack. and, like the parent post mentioned, you also get a full redo stack the same way. Get it to redo then repeat previous action.
I am not exactly sure what vim does, But I suspect this is one of it's improvements.
afc|2 years ago
This is more or less the philosophy of the editor I've been working on (and using ~exclusively) since 2014: https://github.com/alefore/edge/tree/master
Some parts of the UI are still defined in the compiled language (so don't fully fit your philosophy yet), but a big part of the UI comes from the configuration loaded at runtime: every time the editor starts, it interpretes and runs this configuration defining the UI: https://github.com/alefore/edge/blob/master/rc/hooks/start.c...
(This file is not compiled into the editor, but loaded and executed directly at runtime; the format of that file is my editor's extension language/configuration (the equivalent to emacs lisp or vimscript), which just happens to be a garbage collected C-like language.)
MrLeap|2 years ago
trws|2 years ago
LoganDark|2 years ago
I have that hope for literally hundreds of things... but I know I will never actually get to do any of those things. I can think of any one of them right now and be unable to even try. I hate this existence.
afc|2 years ago
So suppose the user does the following operations:
• Insert "Hello"
• Insert " world!"
• Undo once.
• Insert ", Cameron!"
At this point, undo operations would gradually transform the buffer thus: "Hello, Cameron!" => "Hello" => "Hello world!" => "Hello" => "". Obviously, one can redo at any point. The undo/redo days structure don't preserve the state, just the transformations (which are reversible).
The gist of it is that when you apply a modification to the buffer and the redo stack isn't empty, the redo stack gets flipped and inserted into the undo stack. If you undo a long list of transformations and then make a change, that long list is duplicated, but this hasn't been a problem in practice.
In case someone finds this interesting, this is mostly implemented here: https://github.com/alefore/edge/blob/28c031230a8babe888ffe1a...
phs2501|2 years ago
danybittel|2 years ago
I think of undo/redo as "time traveling", going back to where I was one / two / several steps bevor. The mental model of your implementation is more akin of actually "doing" the undo. Like if you undo insert " world!", you create an action that deletes " world!". The timeline still goes forward, but now has a delete action.
globular-toast|2 years ago
I actually used regular Emacs undo for years which lets you get everywhere in the tree with a kind of tree traversal but you won't know where you are. I resisted undo-tree for ages but it's definitely worth it as it stays out of the way until the occasion you might need to use it.
kleiba|2 years ago
But I think your second points deserves an even bigger mention: Emacs has the ability to apply undo only to a certain "region" - which in Emacs parlance is basically just a selection of text. For those of you who have never seen it: imagine two parts of a file you're editing, say one part at the top, one at the bottom. You start by editing the first part (top) and then then move your cursor somewhere down to the second part of the file (bottom) to do some more editing there. But then you realize that your edits in the first part of the file were baloney. In most other editors, if you wanted to undo them, you'd be forced to also undo the edits in the second part of the file. In Emacs, however, you can simply select the first part at the top of your file - if you hit undo then, it will only undo the last edits done inside that selection and leave all edits outside of that region untouched.
submeta|2 years ago
rodlette|2 years ago
undo-tree is a reimplementation of Emacs's undo/redo, that supports a tree visualization.
* undo-tree LOC: 4700. https://gitlab.com/tsc25/undo-tree/-/blob/master/undo-tree.e...
* vundo LOC: 1350. https://github.com/casouri/vundo/blob/master/vundo.el
eviks|2 years ago
linsomniac|2 years ago
funcDropShadow|2 years ago
Does it support restricting undo/redo to a selection? In Emacs you can select any region of text and just apply the undo history of the selection. That is extremely useful. Imagine working on to functions in the same file. You have are working on g() and realize you want to undo some change on f(), that you did before. Most editors don't support that. In Emacs you can just select the code of f() and press undo (C-_).
Several popular undo extension libraries break this feature.
g0xA52A2A|2 years ago
38529977thrw|2 years ago
TIL. Very cool. tnx
thomastjeffery|2 years ago
eviks|2 years ago
Modal editing isn't enough if you type whole sentences/paragraphs of text within a single insert session
Also undo in selection is required to "solve" it, as well as semantic points besides "last 15 minutes" (like "last saved session" or "last time you quit the editor")
Also UI with a diff is sometimes better than having to undo/redo to see changes
bee_rider|2 years ago
mlhpdx|2 years ago
In my case when state A transitioned to B, was undone and further changes made to get state C I would retain the XOR of the changed memory of the A->B transition as run length encoded bytes B’ and similarly C’ so it was lightweight and extremely fast to undo and redo (the latter being exactly the same as the former but applied to A rather than B, since that’s how XOR works). Cool stuff.
qwertox|2 years ago
See the doIt/undoIt methods in https://help.autodesk.com/view/MAYAUL/2022/ENU/?guid=Maya_SD...
vinkelhake|2 years ago
In the end, I switched to representing the entire document state using persistent data structures (using the immer library). This vastly simplified things and implementing undo/redo becomes absolutely trivial when using persistent data structures. It's probably not something that is suitable for all domains, but worth checking out.
https://github.com/arximboldi/immer
bsder|2 years ago
I've been pondering about calling your developers nasty names and what a dolt method is actually doing ...
Until I realized that they were DO-IT, UNDO-IT. <facepalm>
hasoleju|2 years ago
3dGrabber|2 years ago
Jetbrains’ IDEs have both of them and more. The feature is called “Local History”. [1] You can see the history of an file, a selected region of text, or even your entire project. It can undo file deletions/moves/renames. It feels like a personal “automated git without the git hassles”. It has got me out of some really bad situations.
[1] https://www.jetbrains.com/help/idea/local-history.html
PaulDavisThe1st|2 years ago
Maybe for programmer-oriented text editors the user reaction/experience might be different.
benj111|2 years ago
I infer from 'PieceTree'
That this is a binary tree based piece chain.
That makes undo really easy, especially character by character.
Nice explantation of piece chains
https://www.catch22.net/tuts/neatpad/piece-chains/
o11c|2 years ago
* The usual linked-list (or tree) implementation is very cache-unfriendly if you're undoing several steps at a time. Using "linked list inside a buffer" is better; this does not preclude trees, the back "pointer" just has to specify the offset as well as the previous buffer (when you reach the fixed-size allocation you will also have to do this). If you undo across a buffer change you'll also need to update the "most recent redo" backlink from the new buffer.
* SSO strings will usually beat external strings for small edits (this can be variable-size in the linked-list-in-a-buffer case); for large edits see if you can just incref part of the main editing buffer rope.
* It is highly useful to expose a few "shortcut" undo commands: undo to previous save, undo to previous build, etc. Manual tags is probably not very practical most of the time, and "save" is essentially one anyway.
boulos|2 years ago
https://online.stanford.edu/donald-e-knuth-lectures
lrivers|2 years ago
Say you have two documents open. You make a change in the first then change the second document then go back to the first and make a change. One document has two changes and the other has one.
First undo impacts document one. Second alters document two. Infuriating
EvanAnderson|2 years ago
It's worse than an undo that just wipes-out the document. In that scenario I'd just not use the feature.
The behavior in Excel tricks you into using the feature by working as you'd expect in a single document scenario. Then you open a second document and end up trashing one or the other when you undo the wrong thing.
I don't know how anybody ever thought this implementation was the right answer. Ever.
unknown|2 years ago
[deleted]
greentea23|2 years ago
karmakaze|2 years ago
johnea|2 years ago
kkpattern|2 years ago
[deleted]