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.

Sysprof and Podman

With the advent of immutable/re-provisional/read-only operating systems like Fedora’s Silverblue, people will be doing a lot more computing inside of containers on their desktops (as if they’re not already).

When you want to profile an entire system with tools like perf this can be problematic because the files that are mapped into memory could be coming from strange places like FUSE. In particular, fuse-overlayfs.

There doesn’t seem to be a good way to decode all this indirection which means in Sysprof, we’ve had broken ELF symbol decoding for your things running inside of podman containers (such as Fedora’s toolbox). For those of us who have to develop inside those containers, that can really be a drag.

The problem at the core is that Sysprof (and presumably other perf-based tooling) would think a file was mapped from somewhere like /usr/lib64/libglib-2.0.so according to the /proc/$pid/maps. Usually we translate that using /proc/$pid/mountinfo to the real mount or subvolume. But if fuse-overlayfs is in the picture, you don’t get any insight into that. When symbols are decoded, it looks at the host’s /usr/lib/libglib-2.0.so and finds an inode mismatch at which point it will stop trying to decode the instruction address.

But since we still have a limited number of container technologies to deal with today, we can just cheat. If we look at /proc/$pid/cgroup we can extract the libpod container identifier and use that to peek at ~/.local/share/containers/storage/overlay-containers/containers.json to get the overlayfs layer. With that, we can find the actual root for the container which might be something like ~/.local/share/containers/storage/overlay/$layer/diff.

It’s a nasty amount of indirection, and it’s brittle because it only works for the current user, but at least it means we can keep improving GNOME even if we have to do development in containers.

Obligatory screenshot of turtles. gtk4-demo running in jhbuild running in Fedora toolbox (podman) with a Fedora 34 image which uses fuse-overlayfs for file access within the container. Sysprof now can discover this and decode symbols appropriately alongside the rest of the system. Now if only we could get distributions to give up on omitting frame pointers everywhere just so their unjustifiable database benchmarks go up and to the right a pixel.

GTK 4 NGL Renderer

I spent a lot of time in 2020 working on projects tangential to what I’d consider my “main” projects. GtkSourceView got a port to GTK 4 and a load of new features, GTK 4 got a new macOS backend, and in December I started putting together a revamp of GTK 4’s GL renderer.

The nice thing about having multiple renderer backends in GTK 4 is that we still have Cairo rendering as an option. So while doing bring-up of the new GTK macOS backend I could just use that. Making software rendering fast enough to not be annoying is a good first step because it forces you to shake out performance issues pretty early.

But once that is working, the next step is to address how well the other backends can work there. We had two other backends. OpenGL (requiring 3.2 Core and up) and Vulkan. Right now, the OpenGL renderer is the best supported renderer for acceleration in terms of low bug count, so that seemed like the right way to go if you want to stay inline with Linux and Windows backends. Especially after you actually try to use MoltenVK on macOS and realize it’s a giant maze. The more work we can share across platforms (even if temporarily) the better we can make our Linux experience. Personally, that is something I care about.

From what I’ve seen, it looks like OpenGL on the M1 was built on top of Metal, so it seems fine to have chosen that route for now. People seem to think that OpenGL is going to magically go away just because Apple says they’ll remove it. First off, if they did, we’d just fallback to another renderer. Second, it’s likely that Zink will be a viable (and well funded) alternative soon. Third, they just released a brand new hardware architecture and it still works. That was the best point in time to drop it if there ever was one.

The NGL renderer makes full snapshots of uniforms and attachments while processing render nodes so that we can reorder batches going forward. Currently, we only reorder by render target, but that alone is a useful thing. We can start to do a lot more in the future as we have time. That might include tiling, executing batches on threads, and reordering batches within render targets based on programs so long as vertices do not overlap.

But anyway, my real motivation for cleaning up the GL renderer was so that someone who is interested in Metal can use it as a template for writing a renderer. Maybe that’s you?

Major shout-out to everyone that worked on the previous GL renderer in GTK. I learned so much from it and it’s really quite amazing to see GTK 4 ship with such interesting designs.

GTK 4 got a new macOS backend (now with OpenGL)

I’ve been busy the past few months writing a new GDK backend for macOS when not maintaining my other projects. Historically our macOS performance wasn’t something to rave about. But it’s getting better in GTK 4.

The new backend can do both software rendering with Cairo and hardware-based OpenGL rendering using the same OpenGL renderer as we use on GNU/Linux.

This was a fairly substantial “greenfield” rewrite of the backend because so much of it had bit-rotted during the development of GTK 4. GDK hardly looks the same as it did in previous releases and that is a good thing. It’s much easier to write a new backend these days.

I tried to polish it off a bit too, teaching it to do CSD edge-snapping and more. If you’re unfortunate enough to be using the software renderer, it does have some tricks to make drawing a bit faster than in the past. We dropped our use of the quartz Cairo backend in favor of the image backend because, well, it’s faster. Additionally we get a bit clever with opaque regions to speed up CSD compositing.

It also uses the CVDisplayLink to get presentation timing information from the display server to drive our frame clock.

A screenshot of the macOS backend

Thanks again to my employer, Red Hat, for funding this work so we can all benefit from having our applications reach more users.

GtkSourceView gets a JIT

I just merged a new regex implementation for GtkSourceView’s language specifications. Previously it used GRegex (based on PCRE) and now it uses PCRE2 directly similar to what VTE did.

Not only does this get us on a more modern PCRE implementation, but it also allows us to use new features such as a JIT.

JITs are interesting in that you can trade a little bit of memory and time to generate executable code upfront for huge gains in execution time. Given that you only compile language specifications once per regex, but execute them many, many times, it’s a worthwhile feature for GtkSoureView.

Trying to highlight the minified HTML of google.com/ won’t even highlight (due to timeouts) with GRegex. But with PCRE2 and the JIT, it can get by.

In many cases, I found that the cost to JIT was about 4x vs PCRE2 without JIT. For execution times it is about 4x reduction to use the JIT (but sometimes many times faster than that). When you run these regexes millions of times across an edited file, it can really cut down on the amount of energy consumed as well as time taken away from doing things like rendering GTK’s scene graph.

I should note that it’s about 4x improvement on a per-regex basis, so when you run potentially thousands of those in one main loop cycle, the improvement can be much more drastic in what you can do.

If you have any issues with language specifications please let us know! It’s a very large change, so I wouldn’t be surprised if there is some fallout.

Regex Creation
Language Min (msec) Max (msec) Average (msec) # of Calls Notes
C .001 .104 .007 91 gtktreeview.c
C (with JIT) .004 .383 .031 91
Difference .003 .279 .024
CSS .001 .711 .022 197 gtk-contained.css
CSS (with JIT) .004 3.147 .101 198
Difference .003 2.436 .079
Regex Execution Loading File
Language Min (msec) Max (msec) Average (msec) # Calls
C .000 .196 .003 17698 gtktreeview.c
C (with JIT) .000 .061 .001 17698
Difference -.000 -.135 -.002 ~35 ms
CSS .000 .211 .022 84347 gtk-contained.css
CSS (with JIT) .000 .061 .001 74812
Difference -.000 -.135 -.002 ~150 ms

GtkSourceView Next

Earlier this year I started a branch to track GTK 4 development which is targeted for release by end-of-year. I just merged it which means that our recently released gtksourceview-4-8 branch is going to be our LTS for GTK 3. As you might remember from the previous maintainer, GtkSourceView 4.x is the continuation of the GtkSourceView 3.x API with all the deprecated API removed and a number of API improvements.

Currently, GtkSourceView.Next is 5.x targeting the GTK 4.x API. It’s a bit of an unfortunate number clash, but it’s been fine for WebKit so we’ll see how it goes.

It’s really important that we start getting solid testing because GtkSourceView is used all over the place and is one of those “must have” dependencies when moving to a new GTK major ABI.

Preparations in GTK 4

Since I also spend time contributing to GTK, I decided to help revamp GtkTextView for GTK 4. My goal was to move various moving parts into GtkTextView directly so that we could make them more resilient.

Undo Support

One feature was undo support. GTK 4 now has native support for undo by implementing text history in a compact form within GTK itself. You can now set the enable-undo properties to TRUE on GtkTextView, GtkEditable widgets like GtkText or GtkEntry, and others.

GPU Rendered Text (sort of)

Matthias Clasen and I sat down one afternoon last year and wrote a new PangoRenderer for GSK using render nodes and the texture atlas provided by the OpenGL and Vulkan renderers. Since then, GtkTextView gained a GtkTextLineDisplay cache so that we can keep these immutable render nodes around across multiple snapshots.

Text is still rendered on the CPU into a texture atlas, which is uploaded to the GPU and re-used when possible. Maybe someday things like pathfinder will provide a suitable future.

GtkTextView and Widgets

Previously, the gutters for GtkTextView were simply a GdkWindow which could be rendered to with Cairo. This didn’t fit well into the “everything should be a widget” direction for GTK 4. So now you can pack a widget into each of the 4 gutters around the edges of a GtkTextView. This means you can handle input better too using GtkGesture and GtkEventControllers. More importantly, though, it means you can improve performance of gutter rendering using snapshots and cached render nodes when it makes sense to do so.

Changes in GtkSourceView Next

Moving to a new major ABI is a great time to do cleanups too as it will cause the least amount of friction. So I took this opportunity to revamp much of the GtkSourceView code. We follow more modern GObject practices and have bumped our compiler requirements to closely match GTK 4 itself. This still means no g_autoptr() usage from within GtkSourceView sadly thanks to MSVC being … well the worse C compiler still in wide use.

GtkSourceGutterRenderer is now a GtkWidget

Now that we have margins which can contain widgets and contribute to the render node tree, both GtkSourceGutter and GtkSourceGutterRenderer are GtkWidget. This will mean you need to change custom gutter renderers a bit, but in practice it means a lot less code than they previously contained. It also makes supporting HiDPI much easier.

GtkSourceCompletion Revamp

I spent a lot of time making completion a pleasing experience in GNOME Builder and that work has finally made it upstream. To improve performance and simplicity of implementation, this has changed the GtkSourceCompletionProvider and GtkSourceCompletionProposal interfaces in significant ways.

GtkSourceCompletionProposal is now a mostly superfluous type used to denote a specialized GObject. It doesn’t have any functions in the vtable nor any properties currently and the goal is to avoid adding them. Simply G_IMPLEMENT_INTERFACE (GTK_SOURCE_TYPE_COMPLETION_PROPOSAL, NULL) when defining your proposal object GType.

This is because all of the completion provider implementation can now be performed from GtkSourceCompletionProvider. This interface focus on using interfaces like GListModel (like the rest of GTK 4) and how to asynchronously generate and refine the results with additional key-presses.

The completion window has been revamped and now allows proposals to fill a number of columns including an icon, return-type (Left Hand Side), Typed Text, and supplementary text. It resizes with content and ensures that we only inflate the number of GObjects necessary to view the current set. A fixed number of widgets are also created to reduce CSS and measurement costs.

Further, proposals may now have “alternates” which allows for providers to keep all of the DoSomething() proposals with 20 overloaded forms for each base type in whatever language of the day is being used from clogging up the suggestions.

The new GtkSourceCompletionCell widget is a generic container used throughout completion for everything from containing icons, text, or even custom widgetry for the completion details popover.

Completion Preview

GtkSourceGutterLines

A new abstraction, GtkSourceGutterLines, was added to help reduce overhead in generation of content in the gutter. The design of gutters lead to an exorbitant amount of measurement work on every frame. This was actually the biggest hurdle in making GTK 3 applications scroll smoothly. The new design allows for all the renderers to collect information about lines in one pass (along with row height measurements) and then snapshot in their second pass. Combined with the ability to cache render nodes, gutter renderers should have what they need to remain fast even in HiDPI environments.

The implementation of this also has a few nice details to further reduce overhead, but I’ll leave that to those interested in reading the code.

GtkSourceBuffer::cursor-moved

GtkSourceBuffer now has a cursor-moved signal. This seemed to be something implemented all over the place so we might as well have it upstream.

Reduce signal emission overhead

A number of places have had signal emission overhead reduced. Especially in property notifications.

Spaces Drawing

The GtkSourceSpaceDrawer now caches render nodes for drawing spaces. This should improve the performance in the vast majority of cases. However, one case still could be improved upon: tabs when the tab width changes (generally when used after text or spaces).

New Features

Snippets

A new snippet engine has landed based on a much improved version from GNOME Builder. You can provide bundles using an XML snippets file. You can also create them dynamically from your application and insert them into the GtkSourceView. In fact, many completion providers are expected to do this.

The snippet language is robust and shares many features and implementation details from GNOME Builder.

Assistants

A new subsystem, GtkSourceAssistant is used to provide accessory information in a GtkSourceView. Currently this type is private and an implementation detail. However, GtkSourceCompletion and GtkSourceSnippet build upon it to provide some of their features. In the long term, we expect hover providers to also take advantage of this subsystem.

Sysprof Support

GtkSourceView now uses the Sysprof collector API just like GTK 4 does (among many other GNOME projects). This means you can get profiling information about renderings right in the Sysprof visualizer along other data.

Future Work

PCRE2

With GRegex on the chopping block for deprecation, it’s time to start moving to PCRE2 much like VTE did. Doing so will not only make us more deprecation safe, but ensure that we can actually use the JIT feature of the regex engine. With how much regexes are used by the highligting engine, this should be a fairly sizable improvement.

This has now been implemented.

Hover Providers

In GNOME Builder, we added an abstraction for “Hover Providers”. This is also a thing in the Language Server Protocol realm. Nothing exists upstream in GtkSourceView for this and that should probably change. Otherwise all the trickyness in making transient popovers work is put on application authors.

Style Schemes

I would like to remove or revamp some of our default style schemes. They do not handle the world of dyanmic GTK themes so well and become a constant source of bug reports by applications that want a “one size fits all” style scheme. I’m not sure yet on the complete right answer long term here, but my expectation is that we’d want to move toward a default style scheme that is mostly font changes rather than color changes which eventually fall apart on the more … interesting themes.

Anyway, that’s all for now!