Textual content Editor Information Constructions – invoke::thought()

My Personal Piece Tree

The first aim for implementing my very own piece tree was to make it a purely purposeful information construction, which implies the underlying view of the textual content needs to be completely immutable and altering it will require a brand new partial tree.

The piece tree that VSCode applied makes use of a standard RB tree. After digging out my copy of Introduction to Algorithms ebook once more I shortly realized that making an attempt to reimplement the RB tree described within the ebook as a purely purposeful variant was not going to be simple for 2 causes:

1. The ebook makes heavy use of a sentinel node which represents the NIL node however it may be mutated like a daily node, besides there’s just one.
2. The algorithms within the ebook make heavy use of the mother or father pointer in every node. Mum or dad pointers in purely purposeful information constructions are a no go as a result of a change anyplace within the tree primarily invalidates the whole tree.

Any person needed to have applied an immutable RB tree, proper? Seems… yeah? Form of? In my search I discovered Functional Data Structures in C++: Trees by Bartosz Milewski wherein he covers a easy approach to implement a purely purposeful RB tree, however just for insertion. Insertion is is crucial to have however I additionally want deletion, I’ve to have deletion in any other case the piece tree merely won’t work. Within the feedback it was mentioned that deletion is difficult, very onerous, and that always you want a brand new node idea to even deal with it. I actually favored the strategy Milewski took for insertion, so I ended up beginning my RB tree with this information construction and applied the remainder of the piece tree round it, minus delete however we’ll get to that later.

The place I Diverge

Now that I’m implementing the textual content buffer as a tree this can be very essential that I design highly effective debugging instruments to accommodate my journey and consider what elements of the implementation want to vary as a way to resolve my particular issues. The unique VSCode textbuffer code may be seen right here: https://github.com/microsoft/vscode-textbuffer as a stand-alone repo. The actual textbuffer implementation (which isn’t actually a lot completely different from the stand-alone repo) may be seen right here: https://github.com/microsoft/vscode/tree/main/src/vs/editor/common/model/pieceTreeTextBuffer.

CRLF

My new implementation of this information construction doesn’t stray too removed from what VSCode’s model does. The place I begin to differ is within the determination not to codify CRLF line endings as a proper idea within the tree. I don’t just like the workarounds they’ve within the implementation to account for CRLF to be contained inside a single piece and I believe it massively complicates the info construction for a function which solely must be actually accounted for in a handful of eventualities. In my current textual content editor (with out the brand new textual content buffer implementation) I account for CRLF in a separate information construction on the facet which data line ranges. If the editor is in “CRLF mode” it’s going to rebuild the road ranges in a means that chops the carriage return when it’s adopted by a newline character. With my new textual content buffer I don’t report the place CRLFs are in any respect, I merely account for them if a buffer modification occurs which must delete each r and n or when transferring the cursor to retract its place to earlier than the r if it precedes a n.

See Also

Marines Check Hearth Robotic Canine Armed With Rocket Launcher

Right here’s an instance of what the person sees when “CRLF mode” is energetic and the cursor navigates earlier than/after a CRLF line:

Right here’s what the system does beneath to both skip the carriage return or retract to the character earlier than it (the ¶ character represents the r):

The information construction doesn’t have to report the CRLF as a result of restricted variety of instances the editor even wants to think about the carriage return character.

Debugging

Having the ability to debug a sophisticated information construction is crucial in case you intend to make any progress. If you happen to observe the stand-alone repo for the VSCode implementation you’ll be aware that the first means of validating the buffer contents is thru getLineContent, which is a elementary and essential API. For the needs of actually confirming the whole buffer I wanted a distinct strategy so I designed a tree walker with an iterator-like interface so I can use a for-each loop:

class TreeWalker
{
    char present();
    char subsequent();
    void search(CharOffset offset);
    bool exhausted() const;
    Size remaining() const;
    CharOffset offset() const;

    // For Iterator-like conduct.
    TreeWalker& operator++();
    char operator*();
    ...
};
struct WalkSentinel { };
inline TreeWalker start(const Tree& tree)
{
    return TreeWalker{ &tree };
}

constexpr WalkSentinel finish(const Tree&)
{
    return WalkSentinel{ };
}

inline bool operator==(const TreeWalker& walker, WalkSentinel)
{
    return walker.exhausted();
}

This walker proved to be invaluable for validating edits and deletes and opened up a number of additional room to make sure that UTF-8 help was right since I wanted the flexibility to stroll particular codepoints at a given offset. Naturally, the opposite debugging instruments that comply with are a approach to print the tree nodes themselves in addition to the related items:

void print_piece(const Piece& piece, const Tree* tree, int stage);
void print_tree(const Tree& tree);

Undo/Redo

The VSCode implementation didn’t implement undo/redo straight as a textual content buffer operation, they did it by a system wherein edits utilized to the textual content buffer would report the sequence of ‘reverse’ operations wanted to undo the prior edit and go that to the caller which was then accountable for storing this data and accountable for making use of reverse edits in sequence. This technique is definitely one strategy and avoids having to repeat the whole tree once more, nevertheless it depends on allocating buffers of information equally to how we postulated undo/redo might be finished with the only string implementation. Right here’s my undo/redo routines:

UndoRedoResult Tree::try_undo(CharOffset op_offset)
{
    if (undo_stack.empty())
        return { .success = false, .op_offset = CharOffset{ } };
    redo_stack.push_front({ .root = root, .op_offset = op_offset });
    auto [node, undo_offset] = undo_stack.entrance();
    root = node;
    undo_stack.pop_front();
    compute_buffer_meta();
    return { .success = true, .op_offset = undo_offset };
}

UndoRedoResult Tree::try_redo(CharOffset op_offset)
{
    if (redo_stack.empty())
        return { .success = false, .op_offset = CharOffset{ } };
    undo_stack.push_front({ .root = root, .op_offset = op_offset });
    auto [node, redo_offset] = redo_stack.entrance();
    root = node;
    redo_stack.pop_front();
    compute_buffer_meta();
    return { .success = true, .op_offset = redo_offset };
}

Yep, that’s all you want. Two linked lists and a name to compute_buffer_meta() (which is a O(lg n) operation). When the whole information construction is immutable you’ll be able to snap again to any root you might have beforehand saved a reference to and the editor state might be utterly constant—which, I’ll point out, brings up the potential for making a UI for branching editor states (like a mini-source management system) the place the person might navigate an editor state graph to some state that they had beforehand, no extra messy git commit -am'testing' commits to solely be reverted later!

Revisiting Deletion

I stated I’d revisit delete operations as a result of they’re simply as elementary as an insertion operation when speaking about textual content editors. When happening the trail of implementing immutable RB tree deletion, I’ll be trustworthy, I practically gave up a number of instances. The algorithm talked about in my algorithms ebook was merely not workable as a result of it wanted to be transformed right into a recursive model the place we additionally in some way get rid of the sentinel nodes (which VSCode’s RB tree implementation makes use of, however that isn’t essentially a nasty factor). There is a wonderful RB tree algorithm visualizer offered by the University of San Francisco CS department that I strongly urge you to take a look at in case you’re desirous about exploring the algorithms in motion.

To get some thought of the problems behind why RB tree deletion is troublesome we have to peek into the instances that must be coated by the traditional RB tree deletion. Specifically the instances the place you introduce a double-black violation by deleting a crimson node leaves a number of room for error. Fortunately, another person thought that implementing an immutable RB tree was helpful and I discovered persistent-rbtree which was really tailored from the Rust Persistent Data Structures. This code had some dependable node deletion logic that I might adapt to my current RB tree and it ended up serving as the idea for my deletion routine. You may see how it’s finished within the last repo under.

Lastly, after implementing deletion I had my ‘good’ information construction (for me):

1. Environment friendly insertion/deletion.
2. Environment friendly undo/redo.
3. Have to be versatile sufficient to allow UTF-8 encoding.
4. Environment friendly multi-cursor enhancing.