Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Text Editor Data Structures: Rethinking Undo

cdacamar.github.io

Post reply on HN
Print view View original

41–50 of 84 posts

Re: Text Editor Data Structures: Rethinking Undo

#41

Post by o11c »

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.

Re: Text Editor Data Structures: Rethinking Undo

#42

Post by vinkelhake »

qwertox wrote: post #36

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/…

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.

https://github.com/arximboldi/immer

Re: Text Editor Data Structures: Rethinking Undo

#43

Post by thomastjeffery »

alpaca128 wrote: post #35
thomastjeffery wrote: post #6

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 i…

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 wa…

The coolest feature of Vim is its macros. They bring the entire UX into one cohesive feature. The keymap has meaning, because every key symbol is a character, and a macro is just a string. You can paste them, edit them, copy them, then play them back; all without ever leaving Vim's primary UX. Macros are stories written, not in vimscript, but in the language of Vim itself.

Macros are also the reason I don't use Vim anymore. The keymap has meaning, and it shouldn't. Want to change your keymap? Good luck.

I spent years in Vim. I conceptualized all of it. I built my muscle memory around it. Then I learned a new keyboard layout.

I tried remapping the keys. Not only was that impossible (circular dependencies), it broke the conceptual map, too. I have offended the beast, and am welcome no more.

What I really want is to start fresh. No defaults: just user config. Give me the pieces, and the glue to hold them together: I'll do the rest.

Re: Text Editor Data Structures: Rethinking Undo

#44

Post by afc »

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.

In case someone finds this interesting, this is mostly implemented here: https://github.com/alefore/edge/blob/28c031230a8babe888ffe1a...

Re: Text Editor Data Structures: Rethinking Undo

#45

Post by soamv »

layer8 wrote: post #21
kleiba wrote: post #11

Earlier quoted context omitted.

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 see…

What happens when, for example, you atomically replace “mouse” by “elephant”, then select “epha”, and then region-undo? The reason most editors don’t implement this is probably that it’s hard to conceive of how it should behave in the general case. (That’s not to say that the way Emacs is implementing it isn’t good and useful.)

Great question. I tried it and I got `elephantmouse`. I was surprised by this, but FWIW I've never encountered this edge case in actual usage.

Re: Text Editor Data Structures: Rethinking Undo

#46

Post by linsomniac »

thomastjeffery wrote: post #43
alpaca128 wrote: post #35

Earlier quoted context omitted.

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 wa…

The coolest feature of Vim is its macros. They bring the entire UX into one cohesive feature. The keymap has meaning, because every key symbol is a character, and a macro is just a string. You can paste them, edit them, copy them, then play them back; all without ever leaving Vim's primary UX. Macros are stories written, not in vimscript, but in the language of Vim itself . Macros are also the reason I don't use Vim…

>Macros are stories written, not in vimscript, but in the language of Vim itself.

Last year I hit upon the idea that vim's commands are like a bytecode that my brain outputs and vim interprets. I guess that's true of any editor UI, but it just feels more appropriate in the vi case.

Re: Text Editor Data Structures: Rethinking Undo

#47

Post by linsomniac »

eviks wrote: post #19
linsomniac wrote: post #2

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 yo…

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

>Modal editing isn't enough if you type whole sentences/paragraphs of text within a single insert session

Why not? Honest question.

Re: Text Editor Data Structures: Rethinking Undo

#48

Post by thomastjeffery »

wolverine876 wrote: post #29
thomastjeffery wrote: post #6

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 i…

> 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 resear…

The "solution" is to simply leave insert mode more often. That works great if you are using Vim for editing. If you are using Vim for writing... well, not so much.

Then again, if I am writing in Vim, I generally prefer the flow of actively editing what I wrote rather than undoing it.

This really applies to Vim as a whole: if you enjoy its UX, it's damn near perfection. If you hate it, you can leave. If you love it, but want it to behave just a little differently...then you can probably accomplish that with a plugin/configuration.

...but if you want to change Vim's UX more than a little, you're fucked. It feels totally possible until you realize it just isn't.

Re: Text Editor Data Structures: Rethinking Undo

#49

Post by thomastjeffery »

trws wrote: post #23
thomastjeffery wrote: post #6

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 i…

Consider my interest piqued. We’ve seen a couple of others in the space, notably Kakoune and Helix. What do you have in mind?

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.

Re: Text Editor Data Structures: Rethinking Undo

#50

Post by fomine3 »

melagonster wrote: post #32
EvanAnderson wrote: post #26

Earlier quoted context omitted.

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 th…

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.

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.
Post reply on HN