Textual content Editor Information Buildings: Rethinking Undo
Undo and redo have been a staple operation of textual content editors most likely for the reason that first typo was ever made, but there has not been numerous innovation round refining the thought of what undo and redo might be. Let’s discover what I imply…
On The Topic of Undo
Undo
As a way to perceive tips on how to change undo we first want to know what the basic operation of ‘undo’ is meant to do. I’ve at all times realized greatest by means of instance so let’s assume you begin with the string "Howdy" and also you begin typing the sequence " World!":
Howdy
Within the situation above, when the undo operation is invoked (sometimes CTRL+z) what’s the typical expectation? There are a myriad of prospects:
- Undo would delete the complete string
" World!"because it was all a part of the identical insert operation. - Undo would delete solely the final character added,
'!' - Undo would delete the sequence of characters inside a while threshold of every keystroke.
There are lots of approaches to what the undo operation ought to do and each has its personal deserves. The strategy I exploit is near #1 the place the undo operation will undo blocks of the identical fashion of edit. I discover this strategy to be helpful for my workflow. If you’re taken with studying a bit extra about how fashionable textual content editors extra concretely implement undo/redo I encourage you to take a look at Undo/redo implementations in text editors by Matt Duck who very fastidiously breaks down the approaches of a number of editors.
There are a number of properties of undo which are very good to have:
- The undo operation ought to create a corresponding redo operation, extra on redo later.
- If undo is utilized to the start of edit historical past, the system ought to report that an undo is just not doable and do nothing consequently.
- In the event you undo (or redo) to the purpose of the final save of the doc the system ought to acknowledge that there’s nothing to save lots of.
Having #3 is essential to me as a result of it helps me perceive the place my final ‘dedicated’ work was throughout an edit session. It looks as if a small “good to have characteristic” however the system recognizing varied factors in historical past is crucial for the characteristic we’re about to implement.
Redo
Redo is absolutely fairly just like undo in some ways. Let’s take our instance of "Howdy World!", and apply an undo operation (utilizing the popular implementation above):
Howdy
Redo is the complement to undo and it ought to carry out the identical operation that the undo operation simply eliminated. Since there’s a dependency on undo in an effort to redo it implies that the redo operation can’t be utilized on a doc which has had no undo operations carried out. Moreover, a redo operation ought to inherit all the identical properties that undo has, e.g. the system ought to concentrate on redo operations as a second in time fairly than an everyday operation.
Perils of Undo and Redo
Undo and redo are incredible operations to have in our editor toolbox, in truth in the way in which I edit paperwork immediately I might argue that undo and redo are a basic operation. There are some drawbacks in the way in which that undo and redo are inclined to work in most textual content editors although. To assist illustrate what I imply, let’s return to our "Howdy World!" instance yet one more time:
Howdy
If we apply undo to take away " World!" and begin typing once more, most editors will take away the redo state. There are some attention-grabbing approaches to assist fight this drawback, one which involves thoughts is the Emacs undo system which retains undo operations in a separate buffer after you edit once more so you may undo that undo and get again to the purpose the place you may redo after an preliminary undo.
To get a greater thought of precisely what occurs in most editors, let’s see a small graph of the state of affairs above:
In our preliminary state, all we’ve performed is inserted the textual content " World!". Once we apply the undo operation we get:
Nevertheless, after we insert the brand new string " Cameron!" we find yourself orphaning the unique " World!" node as a result of the historical past in most editors is meant to be linear:
Maybe with fredbuf we might do higher…
Rethinking Undo
Primary Thought
Since fredbuf is a purely purposeful information construction, we’ve got the power to very cheaply retailer any reference to an editor buffer state. So what if we created a graph out of it? What if as a substitute of getting a linear record of undos and redos that fredbuf presently has as a builtin, maybe we might handle a graph of editor states ourself so we might then use some form of system of UI to navigate it and ‘snap’ again to any of those states.
Think about we now retailer the undo/redo information within the following kind of construction:
struct UndoRedoNode;
utilizing UndoRedoNodePtr = std::unique_ptr<UndoRedoNode>;
utilizing UndoRedoChildren = std::vector<UndoRedoNodePtr>;
struct UndoRedoNode {
UndoRedoChildren youngsters;
PieceTree::RedBlackTree level;
};
Utilizing the definition above, we are able to create a graph of undo/redo nodes. There could be a query of, why do we’d like youngsters to be an array? This comes again to our final instance the place we confirmed the string " Cameron!" inserted. If the undo operation had been utilized but once more and a brand new string entered, we’d create one more department on the root node, so we’d like the potential of the construction above to discuss with all doable states.
Visualization
Now that we all know how we have to mannequin the information, how will we view it? Graph visualization is an enormous matter and there are a lot of intuitive methods to view varied kinds of graphs. The graph we’re constructing with our undo information is nearer to a tree (however we are able to discuss tips on how to flip this into one thing like a DAG sooner or later). Whereas modifying I’ve at all times discovered it helpful to affiliate timestamps with historic information, as they assist me get a greater thought for roughly what that change might need been, so visualizing the time the change was made is wise to me. Moreover, for the reason that tree is a sequence revamped time it made sense to me to put out the tree horizontally with branches transferring in direction of the fitting of the display, considerably like a git branch structure visualization.
When an undo graph specifically it’s typically not ample for me to easily see the nodes, I additionally must see what these nodes comprise so I could make an knowledgeable resolution about whether or not or not I really wish to apply that undo/redo operation. Enter, the diffing methodology. Essentially the most pure method for me to see deltas in edits is sweet ol’ diff. Let’s take a look at a diff of including " World!" to "Howdy":
Since I work with git extensively, that is precisely the form of factor I wish to see within the UI as I navigate from the present edit to another edit up to now. It permits me to cause concerning the modifications the soar will trigger. This implies there is just one final drawback to unravel: implementing the diff algorithm within the editor for varied kinds of snap factors. Fortunately for us, there’s a incredible collection of posts by James Coglan (“The Myers diff algorithm”) which matches over all of the gory particulars of tips on how to implement the favored Myers diff algorithm—I can’t suggest this collection sufficient for anybody taken with implementing their very own diff algorithm.
Placing It All Collectively
Now that we’ve got the information construction and the visualization technique down, let’s see the way it appears all collectively. Let’s return to that instance the place we branched the UI states however had no method to recuperate the redo of "Howdy":
Howdy
And right here’s that very same collection of edits made in fred:
Once you enter the undo/redo graph mode the editor means that you can navigate to any edit made at any cut-off date. Moreover, the UI will show the diff from the present edit to the chosen node within the higher left-hand nook. It kind of turns your editor right into a small supply management system!
Conclusion
What did I be taught from this?
- Immutable information buildings stay an enchanting focal point for me. They allow so many attention-grabbing avenues to unravel issues.
- The Myers diff algorithm is extremely simple to implement, however takes numerous time to know what is occurring so as to render it correctly.
- It’s going to be laborious for me to return to linear undo/redo of most editors
.
.
In the event you’re additionally taken with textual content editor design, the C++ language, or compilers have a chat with me over on Twitter. I’m at all times taken with studying and sharing any data that might show to be helpful to others.
Till subsequent time!