Fuzzy search menu in Qt

Graphics applications are complex, and often provide hundreds of “nodes” or “commands” to choose from. To provide the user with a convenient way to navigate this long, and often hierarchical list, many modern applications implement a “fuzzy search”, filtering a list of items based on user inputs.

Classic examples of this UI include the TAB “create node” menu of Houdini, Maya or Nuke, or the command palette of Blender. In the programming world, many editors provide a similar interface to search through context-sensitive code completion lists, or through lists of files to edit.

This little article describes how to implement such a menu in Qt, to be used in your own applications. To see the final output, just scroll to the end of this article.

What is a fuzzy search menu?

Fuzzy search allows to navigate potentially large and/or hierarchical lists of data by typing only a part of the name of desired object. As an example, this is how fuzzy search is implemented in Sublime Text and Blender:

A classic implementation of fuzzy search simply iterates over the input string by character, and attempts to find a matching character in each item’s name, starting from the last matched character. The item is included in the resulting list only if all input characters were found it it’s name before reaching the end of the name string.

A simple demonstration of how the fuzzy search algorithm progresses can be made using the following table:

word test testing something
e word te te some
et word test test somet ✔
est word test test something
set word test testing somet

The red characters have been matched with user input, and the tick demonstrates which work has been accepted and how many characters were tested. Notice that a positive result might lead to early termination (no need to test all characters), while a negative one will always test all characters.

This algorithm has a number of user-friendly features:

  • there is no need to remember precisely the name or location of an item – with each new character, the number of items in the list is reduced significantly, helping with the search
  • the input characters are matched in order they were input by the user, leading to an intuitive behaviour
  • it is possible to devise a metric that allows to sort the resulting set, presenting the user with a list that starts with the most likely option (e.g., by preferring to match longer strings)

Implementation

To keep the tutorial generic, we will use only basic Qt classes, with no extensions or special features. The code is primarily aimed at Qt5 (with a bit of C++11), but can be relatively easily adopted to work with Qt4 as well.

Starting point

We start with a hierarchical QMenu instance (example from Possumwood’s “new node” menu):

Base menu

To simplify things, we will assume that there are no complex items in this menu – the only item types are:

  • QAction items, with a callback connected to triggered() signal, and
  • QMenu items, containing other nested menus and actions.

Tutorials on how to build simple menus in Qt are available in Qt docs, and not covered here.

Search textbox

Menus in Qt can contain other widgets, by using instances of classes derived from QWidgetAction. This base class differs from most other item classes in Qt by its two distinct modes of operation:

  1. As an Item, it can only be used in a single displayable container (most QAction instances can be shared between containers – toolbars, menus, context menus…), and owns the widget it contains.
  2. As a Factory, it can be used in multiple containers – for each container, the item will generate a new widgets instance, without taking ownership of the resulting widget.

In our particular example, we will only ever use a search box in a single menu instance, so we opt for the first option. As our new menu should be as similar to standard QMenu implementation, to avoid replicating a large amount of code, we simply derive from it. The public/protected interface of our class ends up quite trivial:

The only overriden virtual method is the showEvent(), which gets called whenever our new menu is displayed.

In its first iteration, we aim at instantiating a QWidgetAction as the first menu item (only when the menu is shown for the first time, or after it was rebuilt). This action is not going to be shared between multiple containers, which allows us to instantiate the QLineEdit instance as its “default widget”.

After instancing the action, we just need to make sure that all keyboard input is sent to the line edit. The easiest option is to simply move focus to it via setFocus(). However, some of the keystrokes should be still forwarded to the menu – we will need to deal with that later.

Filtering implementation

The implementation of fuzzy matching is relatively straightforward – we just try to match all characters in the fuzzy string with an input, in order.

The fuzzy matches should be re-evaluated on each change of the fuzzy text line edit, and alter the list of items displayed in the menu accordingly. For sensible number of items, the speed of evaluation is not a problem – the fuzzy search has linear complexity for each item, and each item is evaluated only once per change.

Initialisation

To simplify the search, it is often good to create an indexing structure. In this case, I’ve opt for a simple std::map:

From inside SearchableMenu::showEvent(), we run the initialisation (inserted below setFocus() call):

The initialisation itself just iterates over all actions in a menu, and adds them to the m_actions map. If another submenu is encountered, the init() method is run recursively:

Submenu

In SearchableMenu::showEvent(), we need to make sure that a menu instance exists (inserted below init() call):

This menu is filled with items in a slot, connected to the line edit box. Based on current fuzzy match string, it re-creates matched items, and displays the result. Each new item of this menu simply triggers a callback of the original action:

Now we have a menu implementation that changes context according to the content of a search box. Unfortunately, though, when the new menu is displayed, it has modal focus, and handles all keystrokes. This means that until this menu is closed, the user cannot enter another letter or delete one. To handle this problem, we need to redirect appropriate key events from the menu to the edit box.

Key forwarding

There are several ways in Qt to redirect user input events to another widget. One of the most generic ones is to use event filters, which allow to filter all events via a custom function before they are evaluated by a particular widget. In our case, we need all keystrokes not handled by the menu to be redirected to the line edit widget. Specifically, we want to keep only up and down arrow, enter (return) key and escape key to be handled by the menu:

A new event filter then needs to be installed on the menu after its creation (in the showEvent() call):

Conclusion

The final implementation behaves is a manner very similar to popular VFX applications like Maya, Houdini, Clarisse or Nuke:

Final result

The full implementation (header and source) can be seen in the Possumwood project, where it is used to create a context-sensitive menu for creating new node instances.

Let me know what you think!