The Journey to Auto-Completion

Published on Fri 19 July 2013 in Nepomuk, (Comments)

Sometimes, features are simple to describe, and their implementation also ends up being simple and small. However, the reflection needed to come with the implementation can be quite substantial. This blog post relates my journey to the auto-completion feature of the Nepomuk query parser, a feature described as “show to the user want he/she wants” and implemented in less than 1000 lines (empty lines and license headers included), but that took a whole week to implement.


Before explaining how the auto-completion works, let’s start with the parsing itself. As described in previous blog posts, the Nepomuk query parser tries to find in the user query lists of contiguous terms that match a certain pattern. For instance, if the query is “mails sent to Jimmy”, “sent to Jimmy” is matched against “sent to %1”.

The idea of the auto-completer is to use these patterns. What the user wants is to be able to type the beginning of a pattern, and to have all of it auto-completed. When what the user has entered corresponds to the beginning of a pattern, this pattern is shown as an auto-completion proposal. When the user selects a proposal, the pattern is put into the query builder and the user can continue its input.

Auto-completion of patterns

When there is only one possible pattern, that is to say when the user is unambiguous about what he or she wants, then a more intelligent auto-completion can be used. As you can see, the auto-completer knows the type of the value associated with a pattern. “tagged as %1” for instance expects that the user will enter a valid tag name. So, when there is only one possible pattern, a one-item list is not shown (it would be useless), but instead an auto-completion box adapted to the type is displayed.

Auto-completion of patterns

Auto-completion of patterns

You see that tag names and date-times use a different auto-completion widget. As this is still preliminary work, the list is not sorted, there is no search interface (it would be difficult to do in a popup, by the way), and contacts are not yet handled. This is not because it is technically difficult (contacts can be enumerated just like tags), but because I don’t know how Akonadi stores contacts in Nepomuk, if it does, and if it is what most of our users want (the majority of users nowadays use web-based email clients and proprietary instant messaging services).

Auto-Completion in the Parser

My work on auto-completion has been split between the parser and the query builder widget. The parser is responsible for finding the auto-completion proposals. It knows the list of all the possible patterns, their types, etc.

The first step was to add a CompletionProposal class (in the Nepomuk2::Query namespace). This class simply stores a a pattern (a string list of terms that must be matched), a type (whether the user needs to enter a tag name, a date-time, or a simple string), a textual and localized description, and positional information. This positional information tells what part of the user query needs to be replaced with the auto-completion if the user selects it. For instance, an auto-completion for “sent to” in “mails sent” will preserve “mails”, but will replace “sent” by “sent to |”, with the bar representing the text cursor.

As auto-completion proposals are dependent of where the text cursor is, I’ve added a third overload of QueryParser::parse. This method takes a user query, flags, and the position of the cursor that will be used to find auto-completion proposals. It is a bit special that the parser has to know the position of the cursor, but it greatly simplifies things and avoids generating too many auto-completion proposals, that will later be rejected because they are too far from the cursor.

With all that done, the actual implementation is quite simple, less than 40 lines long. When the pattern matcher (the class responsible for matching “sent to Jimmy” against “sent to %1”) is done with a pattern, it checks if the cursor is contained in the pattern, or very near. If it is the case, a new completion proposal is created.

Auto-Completion in the Query Builder

The implementation in the query builder widget is a bit bigger, because I had to add an auto-completion popup (the thing that displays the auto-completion proposals and looks like the drop-down menu of a combo box) and the widgets used to display the proposals, the tag list and the calendar (the calendar itself is a QCalendarWidget).

After the user query has been parsed (with the position of the text cursor passed to the query parser), the query builder widget enumerates the auto-completion proposals. If the list is empty, the auto-completer is hidden. If the list contains only one entry, then a datatype-specific completer is shown. In all the other cases, each completion proposal is added to the completer, and finally displayed in a QListWidget with custom item widgets (to have the description in bold and the pattern below).

The end result is not so bad but not yet perfect. For instance, there is no border around the drop-down completion box. I’ve looked at the QCompleter and QComboBox code but I have not found how they manage to have rounded styled corners and a small 3D effect.

When the user selects a value (a tag name, or a date-time), the value is put into the query builder widget:

Auto-completion of patterns

Future plans

Having the auto-completion in place is a nice thing because my GSoC proposal is now “bullet-point complete”. That means that I proposed a query parser able to parse queries in near-natural language, and a query builder widget with syntax-highlighting and auto-completion. These three features are now present.

But even if they are present, I no way near to the end of my GSoC. Many things need to be polished. For instance, I’m not quite satisfied of my “grouped line edit”. Some things don’t work exactly as I want, and the architecture is a bit special.

There are also small bugs in the parser itself that need to be resolved, and the auto-completer is not very nice. The mockups of Ivan also contain a nice feature I would never have thought of: the translation of the parsed query back to natural language. That means than in his mockup, when he enters “music +instrumental”, the auto-completer displays “looking for music tagged as instrumental”. I think it is a good idea to show to the user what the query really means.

All in all, there is still work to do and I will fix as many bugs as I can in the coming weeks. My goal is to have a very nice query builder widget, that works well and that has a code of great quality.

« A Nicer Query Builder Widget   Integrating the Query Builder into Dolphin »