Modern Text Editor Design

I’ve been fascinated about a few technologies in my career. I have a fondness for finding the right data-structure for a problem. Maybe it was because of all those years playing with cars that gave me the “I wanna go fast” mentality. It lead me to various jobs, including working on databases.

Another technology I love are text editors. There is some really fascinating technology going on behind the scenes.

Gtk4 development is heating up, and we are starting to see a toolkit built like a game engine. That’s pretty cool. But how will that change how we write editors? Should it?

In the Gtk3 cycle, I added support to GtkTextView that would render using Alex’s GtkPixelCache. It helped us amortize the cost of rendering into mostly just an XCopyArea() when drawing a frame. It’s why we have that nice 60fps two-finger-scrolling.

But now that we can have GPU textures, do we want to start doing paginated rendering like Apple did with Preview to make PDF rendering ultra fast? Do we want to focus on just sending text data to the GPU to render from an glyph atlas? How about layout? And intermixing right-aligned with left-aligned text? What if we just focus on code editing and not generic editing with rich font support. How about inserting widgets in-between rows? Do we want unlimited undo? How about crash recovery?

These are all questions that can inform the design of a text editor, and they are things I’m starting to think about.

To inform myself on the problem domain better, I started writing a piecetable implementation with various tweaks to outperform those I’ve seen previously. What I’ve come up with is a combination of a b+tree (bplus tree) and a piecetable. The neat thing about it is the high-density you get per-cacheline as compared to something in a RBTree or SplayTree (Atom recently did this, and AbiWord did it a decade ago). It’s at least as fast as those, but with much less malloc overhead because you need fewer, but densely packed allocations.

I prefer dense-cacheline packed structures over pointer chasing (dereferencing pointers) because the CPU can crunch through numbers in a cacheline much faster than it can load another cacheline (as it may not yet be in L1-3 caches). So while it looks like you’re doing more work, you may in fact be saving time.

On my 10 year old 1.2ghz ThinkPad, I can do 1.5 to 2 million random inserts per-second. So I think it’s “good enough” to move on to solving the next layer of problems.

One neat thing about using the linked-leaves from a b+tree is that you get a “next pointer” from each leaf to the next sequential leaf. So if you need to reconstruct the buffer, it’s a simple scan without tree traversal. This is a common problem in a text editor, because we’re sending out text data to diagnostic engines constantly and it needs to be optimized for.

Part of the piecetable design is that you have two buffers. The original data (file state at loading) and change data (append only buffer if each character typed by the user). The piece table is just pointing to ranges in each buffer set to reconstruct the final buffer.

If you log all of your operations to a log file, you can fairly quickly get yourself a crash recovery mechanism. Additionally, you can create unlimited undo.

One thing I don’t like about GtkTextBuffer today is that you cannot open “very large files” with it. It can certainly handle 100mb text files, but it has to load all of that data into memory. And that means that opening a 10gb SQL dump is going to be fairly difficult. But if we implemented on-demand, paginated data loading (reading from disk when that portion of the file is needed), we can get a fixed memory overhead for a file.

One downside to that approach is that if the file is modified behind the scenes, you are basically screwed. (A proper rename() would not affect things since the old FD would still be valid). One way to work around this is to copy the file before editing (a swap file). If your filesystem has reflink support, that copy is even “free”.

Some files are in encodings that require conversion to UTF-8. If a character encoding crossed the page/block boundary, we’d not be able to convert it without locating the neighboring page. So it seems somewhat at odds with this design. But if we just do the iconv (or similar) encoding conversion as part of the copy to our swap file, you can ensure you have valid UTF-8 to begin with. It’s also a convenient place to count new lines so that you can get relatively accurate document height from the start (otherwise you have to scan the data and count newlines which will jump the scrollbar around).

Another thing that might be an interesting trick is to keep around PangoLayouts for each of the cursor lines. It might allow us to mutate the layout immediately upon the key-press-event and render the content out of order (without going through layout cycles). This is somewhat similar to what other editors do to make things “feel” more interactive. It guarantees you render the key event on the next frame, even if slightly incorrect.

In short, writing a good, fast, modern text editor today is the combination of writing a database and a graphics engine. Btrees, low-cardinality indexes, page caches, write ahead logs, transaction replays, memory pooling, GPU dispatching, texture atlases, layout, and more.

https://github.com/chergert/pieceplustree

Implementing GActionGroup

Gtk applications are more and more using GAction and GActionGroup and it’s easy to see why. They are stateful, allow parameters when activating, and can be inserted into the widget hierarchy using gtk_widget_insert_action_group(). The latter is useful so that you only activate actions (or toggle button sensitivity) in the portion of the user interface that makes sense.

One thing to consider is what your strategy will be for using GActionGroup. One way is to encapsulate the GActionGroup by using GSimpleActionGroup. Another, which I prefer, is to implement the GActionGroupInterface. Although, this requires much more boilerplate code.

Until now…

In libdazzle, I added a header-only helper to ease creating action groups with much less effort on your part.

It goes something like this.

#include <dazzle.h>

#include "foo-bar.h"

static void foo_bar_action_frobnicate (FooBar   *self,
                                       GVariant *param);

DZL_DEFINE_ACTION_GROUP (FooBar, foo_bar, {
  { "frobnicate", foo_bar_action_frobnicate },
})

G_DEFINE_TYPE_WITH_CODE (FooBar, foo_bar, G_TYPE_OBJECT,
                         G_IMPLEMENT_INTERFACE (G_TYPE_ACTION_GROUP, foo_bar_init_action_group))

There are a few niceties when defining action groups this way.

  • Your function signatures get your proper class type as parameter 1.
  • You no longer need to instantiate a GSimpleAction for every action.
  • No unnecessary parameters (like user_data) need to be provided anymore.
  • It uses GActionGroupInterface.query_action to optimize for certain queries.
  • You can change action state with ${prefix}_set_action_state().
  • You can change if an action is enabled with ${prefix}_set_action_enabled().
  • You can take your new GActionGroup and gtk_widget_insert_action_group() directly.

That’s it for now, happy hacking!

Builder 3.25.5

Like every year, GUADEC has snuck up on me. I’ll be heading out to Manchester in a handful of days which means things are going to get hectic any moment now.

We just reached another milestone in our development phase towards 3.26. I’ve landed two important components which will have important roles in Builder’s future. The new visual layout, and the new shortcut engine. Neither are complete yet, but they are good enough to land on master and allow us to iterate without giant branches.

The new layout is based upon a design iteration lead by Allan which Andreas, Jakub, and myself took part. Not everything is implemented but the parts which most heavily contribute to user workflow are in place.

The new shortcut engine has also landed. This is a monumental amount of work because it completely overhauls the keyboard input model within Builder. We’ve moved to a “capture and bubble” event delivery for keyboard input so that we have more flexibility in how shortcuts are activated.

The event delivery is in one of three phases. Capture, Dispatch, or Bubble. The capture phase allows the widget hierarchy (starting from the toplevel) to handle an input event before the destination widget. Dispatch is delivery to the expected destination, where GtkBindingSets are activated. Finally, the bubble phase allows the hierarchy to handle the event if nothing handled it previously.

This also includes a whole swath of features around it for user-modifiable shortcut themes, custom keyboard controllers, a shortcut editor and more. To simplify the process of merging into Builder it has a compatibility interface to support CSS-based -gtk-key-bindings properties.

Effectively, bubble/capture allows us to have keyboard shortcuts that only activate if the source editor or terminal have not stolen the input. A convincing Vim implementation for our source editor can really benefit from this.

Enjoy some screenshots

This week in Builder

  • 3.25.3 releases of Builder, jsonrpc-glib, libdazzle, and template-glib.
  • Work is progressing for shortcuts and UI redesign on wip/chergert/layout
  • Features that the UI redesign depends on have landed in libdazzle. This includes animated widget transitions and more.
  • Builder’s Flatpak of Stable and Nightly channels now bundle OSTree 2017.7 and Flatpak 0.9.6 which should improve situations where we were failing to load summary files from the host.
  • A painful bug where Builder (Nightly Flatpak channel) would crash when launched from the Activities menu was fixed. This was a race condition that seemed to not happen when run from the command line. After some manual debugging the issue was fixed.
  • To simplify future debugging, we’ve added a “Bug Buddy” like feature. If you remember bug-buddy, you’re old like me. If Builder receives a SIGSEGV, we try to fork()/exec() an instance of gdb to inspect our process. It will dump a lot of useful information for us like where files are mapped in memory, instruction pointer addresses, and any callstack that can be discovered.
  • Libdazzle gained some new action muxer helpers to clean up action visibility.
  • The new editor (perspective, grid, columns, and view) design will help us drastically simplify some of Builder’s code. But this also needs forward-porting a bunch of plugins to the new design.
  • The new libdazzle based menu joiner landed to help us integrate contextual menus based on file content-type as GMenu does not support “conditionals” when displaying menus.
  • meson test should work again for running Builder’s unit tests under the Meson build system.
  • Anoop blogged about his work to add a code indexer to Builder here.
  • Lucie blogged about her work to make documentation easily accessible while you code here.
  • Umang blogged about his work to improve our word completion engine here.

Cross-Widget Transitions

You can do some pretty flashy things with Dazzle. Tonight I added the missing pieces to be able to make widgets look like they transition between parents.

The following is a video of moving a GtkTextView from one GtkStack to another and flying between those containers. Compare this to GtkStack transitions that can only transition between their children, not their ancestors. Fun!

Dazzle spotlight – Multi Paned and Action Muxing

There really is a lot of code in libdazzle already. So occasionally it makes sense to spotlight some things you might be interested in using.

Action Muxing

Today, while working on various Builder redesigns, I got frustrated with a common downfall of GAction as used in Gtk applications. Say you have a UI split up into two sections: A Header Bar and Content Area. Very typical of a window. But it’s also very typical of an editor where you have the code editor below widgetry describing and performing actions on that view.

The way the GtkActionMuxer works is by following the widget hierarchy to resolve GActions. Since the HeaderBar is a sibling to the content area (and not a direct ancestor) you cannot activate those actions. It would be nice for the muxer to gain more complex support, but until then… Dazzle.

It does what most of us do already, copy the action groups between widgets so they can be activated.

// my_countainer should be either your headerbar or parent of it
// my_view is your view containing the attached action groups
// the mux key is used to remove old action groups
dzl_gtk_widget_mux_action_groups (my_container,
                                  my_view,
                                  "a mux key");

Exciting, I know.

Multi Paned

The number of times I’ve been asked if Gtk has a GtkPaned that can have multiple handles is pretty high. So last year, while working on Builder’s panel engine, I made one. It also gained some new features this week as part of our Builder redesign.

It knows how to handle minimum sizes, natural sizes, expanding, dragging, and lots of other tricky bits. There are lots of really annoying bits about GtkPaned from it’s early days that make it a pain when dealing with window resizes. MultiPaned tries to address many of those and do the right thing by default.

It should be strictly a step up from using GtkPaned of GtkPaned of GtkPaned.

Hello world in a handful of languages

The other day, Sri asked me for a quick Gtk example for a talk. Basically he just needed a window with a header bar. So I put together this repo on github with some examples in a variety of languages. After a few contributions from our community, we have even more examples.

I think it would be neat if people submitted pull requests for more languages. Take a peek and see if something you know about is missing. Ideally the example should use GtkApplication, Gtk templates (and resources if possible), and a window with a header bar.

Having these available will make it easier for me to make templates in Builder for more exotic languages.

Library Documentation

Now that gtk-doc is getting updates and integration with Meson, I decided to give it another shot. So here is some work-in-progress documentation for libdazzle, template-glib, and jsonrpc-glib.

There is plenty of work to do, but this makes it easier for others to come along and help me do the hard part, the documentation.

I’m sort of impressed, in hindsight, at the staggering amount of things we’ve built around Builder in the last couple of years.

This week in Builder

Given the success of this pattern of project-related updates in Gtk, maybe we can try to do this for Builder too. We’ve had lots of updates this past week in Builder and related projects.

  • Builder has switched to meson for building Builder. Autotools has been removed. This does NOT affect build systems supported by Builder.
  • Non-builder related widgets and utilities have moved into libdazzle. Roughly 50k fewer lines of code in Builder.
  • template-glib and jsonrpc-glib are now external projects. Our meson-based build system will automatically install them if necessary.
  • libdazzle’s DzlApplication now handles theme loading, menu merging, and icon loading. It also simplifies widget theming for non-Adwaita themes.
  • Builder’s panel engine was revamped and moved to libdazzle. Various CSS fallbacks were added, including Arc theme.
  • New releases (3.25.2) of gnome-builder, template-glib, jsonrpc-glib, and libdazzle.
  • Builder has switched to DzlSuggestionEntry for search. This design is not final by any means, so I expect further changes.
  • Shortcut engine development continues.
  • libdazzle’s fuzzy search has been vastly improved, while keeping overhead low.
  • Lots of widgets have been moved into libdazzle.
    • DzlThreeGrid — This is a three-column layout (with centered column) and rows.
    • Preferences ­— Copy the Builder style preferences in your app
    • Menu merging — Automatic menus.ui merging and management, handy for plugins.
    • StackList — Make your list boxes fly around
    • CPU graphs
    • Panels
    • MultiPaned — No more nested GtkPaned, deals with resizing, expanding, min and natural sizes appropriately.
    • RadioBox — Fancy joined buttons that act like radio boxes. Easily extendable for dynamic content.
    • Empty State ­— Your standard empty state helper
    • Progress Buttons — Both GNOME Software and Epiphany style animated download buttons.
    • Chromium and Firefox web-browser style auto-completion.
    • Lazy Tree Builders — These really simplify building large tree views with dynamic content.
    • Lots of utilities, data structures, and miscellaneous library glue.
  • A whole bunch of tests have been added to libdazzle. More are always needed.

If you’d like to help with the development of Builder or any of it’s associated libraries, come join us in #gnome-builder on irc.gnome.org.