9 ms·

Text Editor Data Structures: Rethinking Undo

216 points by starfreakclone 3y ago

linsomniac 3y ago
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.
- thomastjeffery 3y ago
  Don't forget about the Gundo plugin: it lets you navigate your tree of undo history.
  - JetSetIlly 3y ago
    Gundo is great. There is also mundo, which is a fork of gundo. And, undotree, which doesn't require python support.
- bee_rider 3y ago
  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…
  - thomastjeffery 3y ago
    As I mentioned elsewhere, gundo is really helpful for navigating the undo tree. My favorite thing about vim's flow is that it isn't just limited to undo/redo: you can re-perform your most recent action anywhere using the . key.
- 38529977thrw 3y ago
  > ":earlier 15 minutes" takes you to the code as it was 15 minutes ago. TIL. Very cool. tnx
  - 3abiton 3y ago
    Been using vim for few years, never hears of that feature. Still a student.
- g0xA52A2A 3y ago
  Just to emphasize part of your comment as I think a lot a people aren't fully aware - Vim has an undo tree https://vimhelp.org/usr_32.txt.html#usr_32.txt https://vimhelp.org/usr_32.txt.html#usr_32.txt
- eviks 3y ago
  Far from solved 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
  - linsomniac 3y ago
    >Modal editing isn't enough if you type whole sentences/paragraphs of text within a single insert session Why not? Honest question.
    - eviks 3y ago
      Because it's too coarse: undoing the whole paragraph instead of just the last word with a typo is too much, so you'd have to be always aware of this limitation and break flow to switch modes for no other reason than to insert "undo points", and these are unnecessary mental bookkeeping chores
      - miniupuchaty 3y ago
        I don't have this problem in practise. It's not "break flow to switch modes" for me. I don't type this way. There's always as much movement as there's typing, especially while programming. Even when writing prose I exit the insert mode each time I think of what to write next making this always a good "undo point". If I make a typo while in the insert mode I just remove last character or last word. I guess you could argue that this is something that undo should also cover but I don't see much need for that. I'm not in the insert mode, exiting to normal mode for movement and undo. I'm in the normal mode entering insert mode to write.
        eviks 3y ago
        While the inferiority of your workflow doesn't matter to you, it's still a point against undo being "solved" by vim
- funcDropShadow 3y 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.
globular-toast 3y ago
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.
- submeta 3y ago
  Wow, been using Emacs for decades and didn’t know about „undo in region“. Thanks for sharing!
  - ska 3y ago
    It's one of those things like rectangle commands; once you know they exist it's hard not to miss them in editors that don't support.
  - matt-attack 3y ago
    Emscs undo both both of those reasons is just on another planet than any other editor. Being able to undo your undo (as infinitum) is killer because it just means you can never lose state. Refional undoing is even more amazing.
- kleiba 3y ago
  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.
thomastjeffery 3y ago
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... [1] https://news.ycombinator.com/item?id=15381886 https://news.ycombinator.com/item?id=15381886
- trws 3y ago
  Consider my interest piqued. We’ve seen a couple of others in the space, notably Kakoune and Helix. What do you have in mind?
  - thomastjeffery 3y ago
    TL;DR: Most (if not all) of the same features, just not as tightly integrated. Every feature is a piece of the puzzle that is your user config. --- Picture Emacs without a default keymap. That's a start. The user builds their own UX from scratch; bringing each feature into their config explicitly. Alternatively, the user just grabs a curated config like Doom Emacs. The difference here is that they can read it: all of it. Instead of writing a bunch of imperative elisp (that becomes its own web of circular dependencies), let's structure the config with some kind of purely functional additive data structure. That Piece Table I wrote is a good start. Instead of just piecing together letters, let's piece together UI and functions. This idea can apply to everything. I envision it as the next generation of shells, of web browsers, of operating systems: everything. Imagine Blender, but you the user add one fruit at a time. Where's the button to extrude mesh? Exactly where you put it; or nowhere at all! Software is made of incompatibility, and I'm sick of it. Where we should have borders, we have walls. Just imagine what it could be like if we tore them all down.
johnea 3y ago
Sorry, but the page you were trying to view does not exist <-- ?
deleted 3y ago
[deleted]
hasoleju 3y ago
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.
- 3dGrabber 3y ago
  > Time travel and the regional undo 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 https://www.jetbrains.com/help/idea/local-history.html
benj111 3y ago
I'm surprised there isn't much discussion of data structures here, as that would inform an undo algorithm. 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/ https://www.catch22.net/tuts/neatpad/piece-chains/
lrivers 3y ago
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
- EvanAnderson 3y ago
  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.
  - melagonster 3y ago
    more interesting part is, when you find these are shared in powerpoint and word, too. there is not warning about I modified another file, if I dare to work on multiple task, everything probably wreck.
    - fomine3 3y ago
      Devil's advocate: For Excel, it makes a bit sense to have app global undo because sometimes Excel books refer other opened books' data. For Word and PowerPoint, it's hard to advocate because I've never seen referring other docs.
qwertox 3y ago
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. See the doIt/undoIt methods in https://help.autodesk.com/view/MAYAUL/2022/ENU/?guid=Maya_SDK_cpp_ref_class_m_d_g_modifier_html https://help.autodesk.com/view/MAYAUL/2022/ENU/?guid=Maya_SD...
- bsder 3y ago
  Man, fonts sometimes really matter. 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>
  - genter 3y ago
    Bit of trivia: The first Macs (or maybe it was the Lisa) had DO IT instead of OK. The people in the focus groups testing it got annoyed that they were being called dolts.
    - Someone 3y ago
      Not the first Macs, the work-in-progress Lisas they used for user research https://www.folklore.org/StoryView.py?story=Do_It.txt https://www.folklore.org/StoryView.py?story=Do_It.txt: “Starting in the summer of 1981, Larry organized a series of user tests of the nascent Lisa software, recruiting friends and family to try out the software for the first time, while being observed by the Apple designers who recorded their reaction. […] Finally, the team noticed one user that was particularly flummoxed by the dialog box, who even seemed to be getting a bit angry. The moderator interrupted the test and asked him what the problem was. He replied, "I'm not a dolt, why is the software calling me a dolt?" It turns out he wasn't noticing the space between the 'o' and the 'I' in 'Do It'; in the sans-serif system font we were using, a capital 'I' looked very much like a lower case 'l', so he was reading 'Do It' as 'Dolt' and was therefore kind of offended. After a bit of consideration, we switched the positive confirmation button label to 'OK' (which was initially avoided, because we thought it was too colloquial), and from that point on people seemed to have fewer problems.”
PaulDavisThe1st 3y ago
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.
karmakaze 3y ago
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.
o11c 3y ago
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.
afc 3y ago
In my text editor (https://github.com/alefore/edge 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. In case someone finds this interesting, this is mostly implemented here: https://github.com/alefore/edge/blob/28c031230a8babe888ffe1a3be55742acdadc9d9/src/undo_state.cc#L19 https://github.com/alefore/edge/blob/28c031230a8babe888ffe1a...
- danybittel 3y ago
  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.
- phs2501 3y ago
  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.)
boulos 3y ago
I'm not sure if it was recorded, but I think Don Knuth's Christmas lecture last week was on a related topic. It's a follow-up to his 2018 lecture: https://online.stanford.edu/donald-e-knuth-lectures https://online.stanford.edu/donald-e-knuth-lectures
kkpattern 3y ago
[dead]
mlhpdx 3y ago
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.
greentea23 3y ago
https://github.com/mbbill/undotree https://github.com/mbbill/undotree

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.

thomastjeffery 3y ago
Don't forget about the Gundo plugin: it lets you navigate your tree of undo history.
- JetSetIlly 3y ago
  Gundo is great. There is also mundo, which is a fork of gundo. And, undotree, which doesn't require python support.
bee_rider 3y ago
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…
- thomastjeffery 3y ago
  As I mentioned elsewhere, gundo is really helpful for navigating the undo tree. My favorite thing about vim's flow is that it isn't just limited to undo/redo: you can re-perform your most recent action anywhere using the . key.
38529977thrw 3y ago
> ":earlier 15 minutes" takes you to the code as it was 15 minutes ago. TIL. Very cool. tnx
- 3abiton 3y ago
  Been using vim for few years, never hears of that feature. Still a student.
g0xA52A2A 3y ago
Just to emphasize part of your comment as I think a lot a people aren't fully aware - Vim has an undo tree https://vimhelp.org/usr_32.txt.html#usr_32.txt https://vimhelp.org/usr_32.txt.html#usr_32.txt
eviks 3y ago
Far from solved 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
- linsomniac 3y ago
  >Modal editing isn't enough if you type whole sentences/paragraphs of text within a single insert session Why not? Honest question.
  - eviks 3y ago
    Because it's too coarse: undoing the whole paragraph instead of just the last word with a typo is too much, so you'd have to be always aware of this limitation and break flow to switch modes for no other reason than to insert "undo points", and these are unnecessary mental bookkeeping chores
    - miniupuchaty 3y ago
      I don't have this problem in practise. It's not "break flow to switch modes" for me. I don't type this way. There's always as much movement as there's typing, especially while programming. Even when writing prose I exit the insert mode each time I think of what to write next making this always a good "undo point". If I make a typo while in the insert mode I just remove last character or last word. I guess you could argue that this is something that undo should also cover but I don't see much need for that. I'm not in the insert mode, exiting to normal mode for movement and undo. I'm in the normal mode entering insert mode to write.
      - eviks 3y ago
        While the inferiority of your workflow doesn't matter to you, it's still a point against undo being "solved" by vim
funcDropShadow 3y 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.

globular-toast 3y ago

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.

submeta 3y ago
Wow, been using Emacs for decades and didn’t know about „undo in region“. Thanks for sharing!
- ska 3y ago
  It's one of those things like rectangle commands; once you know they exist it's hard not to miss them in editors that don't support.
- matt-attack 3y ago
  Emscs undo both both of those reasons is just on another planet than any other editor. Being able to undo your undo (as infinitum) is killer because it just means you can never lose state. Refional undoing is even more amazing.
kleiba 3y ago
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.

thomastjeffery 3y ago

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... [1] https://news.ycombinator.com/item?id=15381886 https://news.ycombinator.com/item?id=15381886

trws 3y ago
Consider my interest piqued. We’ve seen a couple of others in the space, notably Kakoune and Helix. What do you have in mind?
- thomastjeffery 3y ago
  TL;DR: Most (if not all) of the same features, just not as tightly integrated. Every feature is a piece of the puzzle that is your user config. --- Picture Emacs without a default keymap. That's a start. The user builds their own UX from scratch; bringing each feature into their config explicitly. Alternatively, the user just grabs a curated config like Doom Emacs. The difference here is that they can read it: all of it. Instead of writing a bunch of imperative elisp (that becomes its own web of circular dependencies), let's structure the config with some kind of purely functional additive data structure. That Piece Table I wrote is a good start. Instead of just piecing together letters, let's piece together UI and functions. This idea can apply to everything. I envision it as the next generation of shells, of web browsers, of operating systems: everything. Imagine Blender, but you the user add one fruit at a time. Where's the button to extrude mesh? Exactly where you put it; or nowhere at all! Software is made of incompatibility, and I'm sick of it. Where we should have borders, we have walls. Just imagine what it could be like if we tore them all down.

johnea 3y ago

Sorry, but the page you were trying to view does not exist <-- ?

deleted 3y ago

[deleted]

hasoleju 3y ago

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.

3dGrabber 3y ago
> Time travel and the regional undo 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 https://www.jetbrains.com/help/idea/local-history.html

benj111 3y ago

I'm surprised there isn't much discussion of data structures here, as that would inform an undo algorithm. 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/ https://www.catch22.net/tuts/neatpad/piece-chains/

lrivers 3y ago

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

EvanAnderson 3y ago
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.
- melagonster 3y ago
  more interesting part is, when you find these are shared in powerpoint and word, too. there is not warning about I modified another file, if I dare to work on multiple task, everything probably wreck.
  - fomine3 3y ago
    Devil's advocate: For Excel, it makes a bit sense to have app global undo because sometimes Excel books refer other opened books' data. For Word and PowerPoint, it's hard to advocate because I've never seen referring other docs.

qwertox 3y ago

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. See the doIt/undoIt methods in https://help.autodesk.com/view/MAYAUL/2022/ENU/?guid=Maya_SDK_cpp_ref_class_m_d_g_modifier_html https://help.autodesk.com/view/MAYAUL/2022/ENU/?guid=Maya_SD...

bsder 3y ago
Man, fonts sometimes really matter. 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>
- genter 3y ago
  Bit of trivia: The first Macs (or maybe it was the Lisa) had DO IT instead of OK. The people in the focus groups testing it got annoyed that they were being called dolts.
  - Someone 3y ago
    Not the first Macs, the work-in-progress Lisas they used for user research https://www.folklore.org/StoryView.py?story=Do_It.txt https://www.folklore.org/StoryView.py?story=Do_It.txt: “Starting in the summer of 1981, Larry organized a series of user tests of the nascent Lisa software, recruiting friends and family to try out the software for the first time, while being observed by the Apple designers who recorded their reaction. […] Finally, the team noticed one user that was particularly flummoxed by the dialog box, who even seemed to be getting a bit angry. The moderator interrupted the test and asked him what the problem was. He replied, "I'm not a dolt, why is the software calling me a dolt?" It turns out he wasn't noticing the space between the 'o' and the 'I' in 'Do It'; in the sans-serif system font we were using, a capital 'I' looked very much like a lower case 'l', so he was reading 'Do It' as 'Dolt' and was therefore kind of offended. After a bit of consideration, we switched the positive confirmation button label to 'OK' (which was initially avoided, because we thought it was too colloquial), and from that point on people seemed to have fewer problems.”

PaulDavisThe1st 3y ago

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.

karmakaze 3y ago

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.

o11c 3y ago

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.

afc 3y ago

In my text editor (https://github.com/alefore/edge 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. In case someone finds this interesting, this is mostly implemented here: https://github.com/alefore/edge/blob/28c031230a8babe888ffe1a3be55742acdadc9d9/src/undo_state.cc#L19 https://github.com/alefore/edge/blob/28c031230a8babe888ffe1a...

danybittel 3y ago
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.
phs2501 3y ago
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.)

boulos 3y ago

I'm not sure if it was recorded, but I think Don Knuth's Christmas lecture last week was on a related topic. It's a follow-up to his 2018 lecture: https://online.stanford.edu/donald-e-knuth-lectures https://online.stanford.edu/donald-e-knuth-lectures

kkpattern 3y ago

[dead]

mlhpdx 3y ago

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.

greentea23 3y ago

https://github.com/mbbill/undotree https://github.com/mbbill/undotree