A Piece+Tree (Augmented B+Tree)

Most of my career I’ve been working on a text editor product in either a hobby or professional capacity. Years ago I had an idea to combine a B+Tree with a PieceTable and put together a quick prototype. However, it didn’t do the nasty part which was removal and compaction of the B+Tree (so just another unfinished side-project).

Now that we’re between GNOME cycles, I had the chance to catch up on that data structure and finish it off.

Just for a bit of background, a B+Tree is a B-Tree (N-ary tree) where you link the leaves (and often the branches) in a doubly-linked list from left-to-right. This is handy when you need to do in-order/reverse-order table-scans as you don’t need to traverse the internal nodes of the tree. Unsurprisingly, editors do this a lot. Since B+Trees only grow from the root, maintaining these linked-lists is pretty easy.

And a PieceTable is essentially an array of tuples where each tuple tells you the length of a run of text, what buffer it came from (read-only original buffer or append-only change buffer), and the offset in that buffer. They are very handy but can become expensive to manage as you gain a lot of changes over time. They are fantastic when you want to support infinite undo as you can keep an append-only file for individual changes along with one for the transaction log. You can use that for crash recovery as well.

This augmented B+Tree works by storing pointers to children branch-or-leaves along with their combined run-length. This is handy because as you mutate runs in the leaves, you only need to adjust lengths as you traverse back up the tree.

Another bit of fun trickery when writing B-trees of various forms is to break your branches-or-leaves into two sections. One section is for the items to be inserted. On the other, you have a fixed array of integers. After you insert an item into a free slot, you update a linked list of integers (as opposed to pointers) on the other end. Doing so allows you to do most inserts/removals in O(1) once you know the proper slot and avoid a whole series of memmove()s. Scanning requires traversing the integer linked-list instead of your typical for (i=0; i<n_items; i++) scenario. Easily resolved with a FOREACH macro.

Anyway, here it is, and it seems to work. Finally I can move on from having that bit of data-structure on my mind.

Auto-indenters for GtkSourceView

One of the last features from Builder I really wanted to get upstream for the 5.0 release (and the beginning of a new ABI stream) is our auto-indenter interface. It, however, was a product of the times in GTK 3 and was rather clunky by necessity.

Now that we are on GTK 4, I could significantly clean up the implementation by putting it in GtkSourceView directly.

Toggling GtkSourceView:auto-indent still does the same thing as before. However, you can now set the GtkSourceView:indenter property to your own indenter and GtkSourceView will happily use that instead.

The interface is rather simple, and focused purely on indentation as you type. Note that we may add additional functions or interfaces in the future for reformatting text similar to what LSPs can do on save.

struct GtkSourceIndenterInterface {
	GTypeInterface parent_iface;

	gboolean (*is_trigger) (GtkSourceIndenter *self,
	                        GtkSourceView     *view,
	                        const GtkTextIter *location,
	                        GdkModifierType    state,
	                        guint              keyval);
	void     (*indent)     (GtkSourceIndenter  *self,
	                        GtkSourceView     *view,
	                        GtkTextIter       *iter);
};

Thanks to a bit of GtkIMContext trickery we can avoid making the indenters have to translate keyvals like GDK_KEY_Return into strings to be inserted into the buffer. That was always a complex bit of code when input methods and alternate keymappings are in play.

So this is about as minimal of an interface as I could get, and that is generally what I strive for.

GtkSourceView Interactive Tooltips

During the past years (and especially last cycle) I’ve worked to push a number of features upstream from Builder into GtkSourceView. Not only does this improve the ecosystem for all applications, but it reduces the number of things we need to maintain downstream in Builder as we move to GTK 4.

That included a new completion engine, a new snippet engine with tooltips based on expansion points, updated gutter and gutter renderer designs, the editor overview map, background patterns, sysprof tracing integration, and most recently interactive tooltips.

You can read our nightly generated documentation to learn about it. In particular, GtkSourceHover is attached to the GtkSourceView and can have GtkSourceHoverProviders registered with it. Implementing that interface will be familiar to those who’ve implemented completion providers, as they work in a similar way.

This came from Builder where we have interactive tooltips for things like breakpoints, documentation, and symbol information. Other applications using GtkSourceView may find it useful when implementing Language Server Protocol’s hover providers.

A GTK 4 based Text Editor

It started as an application for me to verify the correctness of the GtkSourceView 5 API (which targets GTK 4). After that it helped me implement JIT support for GtkSourceView languages. Once that was done it became my test case while I wrote the GTK 4 macOS backend and revamped the GL renderer.

It is a simple and humble text editor. It does not have all the corner cases you’d expect from a text editor yet. It does not have aspirations to be a programmers text editor.

Now that you know this is very much a technology preview release only, you might be tempted to keep your important data away from it.

What it can do

  • Simple interface designed by the GNOME design team. You can find the mockups in the traditional places
  • Search and Replace
  • Typical GtkSourceView features
  • Quick access to recent documents
  • Multiple windows
  • Automatic discovery of .editorconfig and modelines settings
  • Light and dark mode
  • Automatically save files to drafts, restored in case of crash
  • Printing
  • Can be run from within a Flatpak sandbox and uses document portal for access to host files

What it cannot do

  • It doesn’t protect you from trying to open really large files
  • Support your custom GTK 4 theme
  • Auto-completion or snippets
  • Plugins
  • Custom file encodings
  • Spell check
  • Change style schemes beyond light and dark
  • Translations or Help of any kind

Building

Here is a release tarball.

If you’d like to test it out, one way is to clone the repository from GNOME Builder and click Run. Additionally, you can find a Flatpak in the gnome-nightly Flatpak repository.

Rust and GNOME Builder

I still spend most of my day writing C and I doubt that is going to change any time soon. But that doesn’t mean you should have to!

Builder got a number of late arriving improvements around Rust support, so now would be a good time to go test them before the 40 release is out.

Yesterday I landed a long awaited feature that will find the common Flatpak SDK ancestors. This was needed to resolve the branch name for SDK extensions like org.freedesktop.Sdk.Extension.rust-stable. Your project might use org.gnome.Sdk//3.38 but the branch for rust-stable is 20.08 (coming from org.freedesktop.Sdk//20.08). Terribly annoying, but hey, now it’s fixed.

Furthermore, Builder can use rust-analyzer¹ as bundled by the org.freedesktop.Sdk.Extension.rust-stable SDK so that is one less thing you need to install or manage. It will pick up all the same dependencies as your project because it will run from within your projects build container. It will see everything your build system does, and in the same way.

Just create a new project using the “GNOME Application” template, select “Rust” as the language, and Run.

¹ rust-analyzer provides diagnostics, auto-completion, and more.