Bug 27443 – [Gtk] Open menulists should support typeahead find

• Status: RESOLVED
• Resolution: FIXED
• Component: WebKitGTK

[Reinout van Schouwen]

Comboboxes currently don't react to keyboard input to quickly select an item from a long list. Please add this functionality.

For the desired interaction model, please see the related Gtk+ bug http://bugzilla.gnome.org/show_bug.cgi?id=567141

[Xan Lopez]

*** Bug 30329 has been marked as a duplicate of this bug. ***

[Jens Petersen]

Works for me currently.

[Apelete Seketeli]

Created attachment 53605 [details]
PopupMenu "find as you type" search

Hi,

This is a rough patch intended to add find as you type functionalty to the PopupMenus: entries are searchable and automatically selected using the keyboard.
A few caveats though:
 - only works with flat PopupMenu list items, ie. PopupMenus containing tree list items does not work well (don't know if the explanation is clear enough)
 - only modifier keys are handled well for the moment, anything beyond alphanumerical keys and modifiers may have an unexpected behaviour
 - there is no feedback during the search, except for the automatic selection of the searched item if found

[Apelete Seketeli]

Created attachment 55503 [details]
PopupMenu "find as you type" search

Handling of modifiers and some special keys have been improved for the moment; should work better at least.
The search algorithm has been improved too, now filtering the list as the user enter more keys.

[Apelete Seketeli]

Created attachment 56039 [details]
PopupMenu "find as you type" search

I spotted a mistake in the search algorithm, making it not to work right. Put it right now, it should work ok :).
You can now reset the search without closing the popup by pressing the "Delete" key on the keyboard.

[Apelete Seketeli]

Created attachment 57170 [details]
Find-as-you-type proposed patch

Added searching inside indented "tree lists".
This should complete the patch, it nows seems to fix the bug.

[WebKit Review Bot]

Attachment 57170 [details] did not pass style-queue:

Failed to run "['WebKitTools/Scripts/check-webkit-style', '--no-squash']" exit_code: 1
WebCore/platform/gtk/PopupMenuGtk.cpp:34:  Streams are highly discouraged.  [readability/streams] [3]
WebCore/platform/gtk/PopupMenuGtk.cpp:168:  Extra space before ( in function call  [whitespace/parens] [4]
WebCore/platform/gtk/PopupMenuGtk.cpp:211:  Tests for true/false, null/non-null, and zero/non-zero should all be done without equality comparisons.  [readability/comparison_to_zero] [5]
WebCore/platform/gtk/PopupMenuGtk.cpp:231:  Use 0 instead of NULL.  [readability/null] [5]
WebCore/platform/gtk/PopupMenuGtk.cpp:243:  Tests for true/false, null/non-null, and zero/non-zero should all be done without equality comparisons.  [readability/comparison_to_zero] [5]
WebCore/platform/gtk/PopupMenuGtk.cpp:262:  Use 0 instead of NULL.  [readability/null] [5]
WebCore/platform/gtk/PopupMenuGtk.cpp:273:  Missing space before {  [whitespace/braces] [5]
WebCore/platform/PopupMenu.h:53:  Alphabetical sorting problem.  [build/include_order] [4]
Total errors found: 8 in 3 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[WebKit Review Bot]

Attachment 57170 [details] did not build on chromium:
Build output: http://webkit-commit-queue.appspot.com/results/2460044

[WebKit Review Bot]

Attachment 57170 [details] did not build on win:
Build output: http://webkit-commit-queue.appspot.com/results/2506055

[Alexander Butenko]

(In reply to comment #6)
> Created an attachment (id=57170) [details]
> Find-as-you-type proposed patch
> 
> Added searching inside indented "tree lists".
> This should complete the patch, it nows seems to fix the bug.

Im not a reviewer, but as a quick followup:

--- a/WebCore/platform/PopupMenu.h
+++ b/WebCore/platform/PopupMenu.h
@@ -50,7 +50,10 @@ typedef struct _GtkMenuItem GtkMenuItem;
 typedef struct _GtkWidget GtkWidget;
 #include "GRefPtrGtk.h"
 #include <wtf/HashMap.h>
+#include <gdk/gdk.h>
 #include <glib.h>
+#include <list>
+#include <string>


u cant include gdk.h in platform independent files without platform guard coz it will break all the platforms except gtk.

patch is awesome, will simplify life a lot.

[Gustavo Noronha (kov)]

Comment on attachment 57170 [details]
Find-as-you-type proposed patch

WebCore/platform/gtk/PopupMenuGtk.cpp:31
 +  #include <algorithm>
Includes must be ordered, please take a look at http://webkit.org/coding/coding-style.html

WebCore/platform/PopupMenu.h:77
 +  void trim(std::string&);
We should protect all of the code with the platform checks. Having said that, I don't like having a trim implementation solely for this case. Aren't there other trim implementations in standard libraries we can use? I know pango has pango_trim_string, for example, could we not use it? In case there is no, I'd prefer having that code go into one of WebKit's string classes, and that class should be used here instead of std::string.

WebCore/platform/gtk/PopupMenuGtk.cpp:236
 +           ++i) {
This construct is very unusual in WebKit, please use a single line for code like this.

WebCore/platform/gtk/PopupMenuGtk.cpp:266
 +              searchDomain = GTK_MENU_SHELL(that->m_popup.get())->children;
We are avoiding using struct fields directly. Please use the same method used here: http://trac.webkit.org/changeset/61206

Have you considered contributing something similar to GTK+ directly?

[Apelete Seketeli]

Created attachment 60537 [details]
Find-as-you-type proposed patch

I hope this one build on all platforms :).

About contibuting to something similar in GTK+ I actually thought the feature was missing in GTK+ at first, but I was told to implement it directly inside WebKit.
Is it okay for me to continue working on the patch in order to get it approved in WebKit ?

[Philippe Normand]

Comment on attachment 60537 [details]
Find-as-you-type proposed patch


>+// Test keypresses to see if they are to be passed to the event handler
>+bool PopupMenu::isKeyPressToZap(GdkEventKey* event, PopupMenu* that)
>+{
>+    guint keyval = gdk_unicode_to_keyval(event->keyval);
>+
>+    if (keyval == (event->keyval | 0x01000000)) {
>+        if (event->keyval == GDK_Delete)
>+            resetWord(that);
>+        return true;
>+    }
>+
>+    return false;
>+}

I'm not sure to understand the purpose of the first test, maybe adding a comment about it would be good?


> 
>+// Search the word typed on the keyboard in the PopupMenu and select the
>+// correspnding menuItem if found
>+bool PopupMenu::menuSearchItem(GtkWidget* widget, GdkEventKey* event, PopupMenu* that)
>+{
>+    ASSERT(that->m_popup);
>+
>+    GList* searchDomain = 0, *searchDomainNext = 0;
>+
>+    if (!isKeyPressToZap(event, that)) {
>+        if (that->searchedWord.empty()) {
>+            searchDomain = gtk_container_get_children(GTK_CONTAINER(that->m_popup.get()));
>+            that->searchDomainList.push_front(searchDomain);
>+        }
>+
>+        that->searchedWord += event->keyval;
>+        std::list<GList*>::iterator it = that->searchDomainList.begin();
>+
>+        if (search(*it, that->searchedWord, searchDomain)) {
>+            GList* p = searchDomain;
>+            gtk_menu_shell_select_item(GTK_MENU_SHELL(that->m_popup.get()), GTK_WIDGET(p->data));
>+            if (buildDomain(searchDomain, that->searchedWord, *it, searchDomainNext))
>+                that->searchDomainList.push_front(searchDomainNext);
>+            return true;
>+        }
>+    }
>+
>+    return false;
>+}

what about an early check here? Something like

if (isKeyPressToZap(event, that))
    return false;

I'm no reviewer, this is just some feedback on your patch :)

[Gustavo Noronha (kov)]

Comment on attachment 60537 [details]
Find-as-you-type proposed patch

 181     std::string searchedWord;
 182     std::list<GList*> searchDomainList;

As you can see from the other member variables, these should have m_ preffixing their names.

 144     resetWord(that);

This could be turned into that->resetWord();, which would make this look much more natural:

[...]
 160 // Clear the search and the associated domain list
 161 void PopupMenu::resetWord(PopupMenu* that)
 162 {
 163     that->searchedWord.clear();
 164     that->searchDomainList.clear();
 165 }

So you'd make this be a non-static private method, remove the argument, and use the member variables directly instead of through "that". The same could be the case for all the other functions that are coded like this only because they are callbacks. I would prefer having the callbacks be small, and just cause the object methods to be called. So you would have a keyPressEventCallback static method that would do if (!that->isKeyPressToZap(event)) { that->searchItem(event), which should make the bulk of the code more natural.

 167 // Test keypresses to see if they are to be passed to the event handler
 168 bool PopupMenu::isKeyPressToZap(GdkEventKey* event, PopupMenu* that)
 169 {
 170     guint keyval = gdk_unicode_to_keyval(event->keyval);
 171 
 172     if (keyval == (event->keyval | 0x01000000)) {
 173         if (event->keyval == GDK_Delete)
 174             resetWord(that);
 175         return true;
 176     }
 177 
 178     return false;
 179 }

It doesn't make too much sense to have a "conditional" call actually change stuff. The call to resetWord should go in the else block in the code that calls isKeyPressToZap. Also, this function seems to be overloaded for its name, as the comment above it implies. It's more a function to decide whether the press should be passed to the handler or not, though I am not positive what you're trying to do by returning true on this condition: keyval == (event->keyval | 0x01000000), what is that testing?

Is this code based on some other code, btw? I'll say r- so we can get those issues resolved, thanks!

[Apelete Seketeli]

Created attachment 62186 [details]
Find-as-you-type proposed patch

Submitting again after taking into account the feedback above, thanks everyone.

The patch was written from scratch, it's not based on some other code AFAIC.

[Xan Lopez]

Comment on attachment 62186 [details]
Find-as-you-type proposed patch

>+    std::string m_searchedWord;

I don't think std::string is commonly used in WebKit, check CString in WTF.

>+    std::list<GList*> m_searchDomainList;

Same for this, mixing two list implementations seems a bit weird. Maybe just stick to GList?

>+// Test keypresses to see if they are to be passed to the event handler
>+bool PopupMenu::isKeyPressToZap(GdkEventKey* event)

The method name should be what the method does, not what it's used for IMHO. Since you seem to check if it's a modifier, the name should go along those lines.

>+{
>+    guint keyval = gdk_unicode_to_keyval(event->keyval);

So... isn't this already a key symbol? I'm confused.

>+
>+    // If the key is a modifier it should be zapped
>+    if (keyval == (event->keyval | 0x01000000))
>+        return true;

In any case you should mention that this is what the function returns if there's no corresponding symbol, otherwise it's difficult to know what's going on.

>+
>+    return false;
>+}
>+
>+// Search for a menuItem in a domain and returns the menuItem if found
>+// searchDomain: the domain searched
>+// word: the menuItem label
>+// resultItem: the menuItem if found
>+bool PopupMenu::search(GList* searchDomain, const std::string& word, GList*& resultItem)
>+{
>+    ASSERT(searchDomain);
>+
>+    std::string label;
>+    unsigned int size = g_list_length(searchDomain);
>+
>+    for (unsigned int i = 0; i < size; ++i) {
>+        label = gtk_menu_item_get_label(GTK_MENU_ITEM(searchDomain->data));
>+        if (!label.empty())
>+            label = pango_trim_string(label.c_str());
>+        if (label.size() > word.size())
>+            label.erase(word.size());
>+
>+        if ((label.c_str() && word.c_str()) && !strcasecmp(label.c_str(), word.c_str())) {
>+            resultItem = searchDomain;
>+            return true;
>+        }

I think you should use the GLib UTF8 collate functions here, and just compare by prefix using the word length, seems more straightforward.

>+        searchDomain = g_list_next(searchDomain);
>+    }

Micro-optimization time! You don't really need to go through the list once to get the size and then iterate again, just iterate until NEXT is NULL.

>+
>+    return false;
>+}
>+
>+// Build a search domain containing menuItems starting with 'word'
>+// startingFrom: starting position in the current search domain
>+// word: prefix of menuItem label looked for
>+// currentDomain: current search domain
>+// result: builded search domain if currentDomain has been reduced
>+bool PopupMenu::buildDomain(GList* startingFrom, const std::string& word, GList* currentDomain, GList*& result)
>+{
>+    ASSERT(startingFrom);
>+
>+    std::string label;
>+    GList* newDomain = 0;
>+    unsigned int size = g_list_length(startingFrom);
>+
>+    for (unsigned int i = g_list_index(startingFrom, startingFrom->data); i < size; ++i) {
>+        label = gtk_menu_item_get_label(GTK_MENU_ITEM(startingFrom->data));
>+        if (!label.empty())
>+            label = pango_trim_string(label.c_str());
>+        if (label.size() > word.size())
>+            label.erase(word.size());
>+
>+        if ((label.c_str() && word.c_str()) && !strcasecmp(label.c_str(), word.c_str()))
>+            newDomain = g_list_prepend(newDomain, startingFrom->data);
>+        startingFrom = g_list_next(startingFrom);
>+    }

All the comments for the previous method apply.

>+
>+    if (g_list_length(newDomain) < g_list_length(currentDomain)) {
>+        result = g_list_reverse(newDomain);

Mmm, why do we need to reverse it?

>+        return true;
>+    }
>+
>+    return false;
>+}
>+
>+// Search the word typed on the keyboard in the PopupMenu and select the
>+// correspnding menuItem if found

typo in 'correspnding'.

[Xan Lopez]

Another comment: not sure why we need a list of search domains, seems to me just the current one should be more than enough, at least for what this patch does.

[Apelete Seketeli]

Created attachment 63496 [details]
Find-as-you-type proposed patch

Now using GLib types instead of STL ones, plus the few changes suggested above.

[Martin Robinson]

Comment on attachment 63496 [details]
Find-as-you-type proposed patch

Thanks for working on this patch. I agree that this functionality is very
important to have and I'm glad you're tackling it.

>  #elif PLATFORM(GTK)
> +    GList* m_searchDomain;
> +    GString* m_searchedWord;

Please use GOwnPtr for these types and be sure to write template
specializations for them if they do not exist yet. This will reduce
the risk of memory leaks greatly.

I'm not sure I understand exactly why you are caching the menu items
here (m_searchDomain), is the performance gain worth it? If you didn't,
it seems like you could get rid of the filterDomain method. Take a look
at PopupListBox::typeAheadFind in the chromium directory for where they
implement this same behavior in one method. Maybe we should match that?

> +    void resetWord();
> +    bool isPrintable(GdkEventKey*);
> +    bool search(GList*, GString*&, GList*&);
> +    bool filterDomain(GList*, GString*&, GList*, GList*&);
> +    void searchItem(GdkEventKey*, PopupMenu*);
> +    static bool keyPressEventCallback(GtkWidget*, GdkEventKey*, PopupMenu*);

In my opinion, these method names are too general. There is no way to tell
by looking at them they pertain to find-as-you-type. I don't mean to nit
too hard, but "Domain" has a fairly overloaded meaning in web browsers.
Maybe it could be "PossibleTypeAheadFindResults." Bytes are very cheap! :)

> +        g_list_free(m_searchDomain);
> +        g_string_free(m_searchedWord, TRUE);

This kind of stuff can be omitted entirely if you switch to
GOwnPtr, or even switching to using WebCore types (though I
know that you just switched it to GObject types, so maybe that
kind of change could happen in a later cleanup).

>      g_list_free(children);
>      gtk_menu_popup(m_popup.get(), 0, 0, reinterpret_cast<GtkMenuPositionFunc>(menuPositionFunction), this, 0, gtk_get_current_event_time());
> +    m_searchedWord = g_string_new(NULL);

Isn't it possible at this point for m_searchWord to already exist?
Again using GOwnPtr here would prevent a memory leak.

> +    for (; searchDomain; searchDomain = g_list_next(searchDomain)) {
> +        g_string_assign(label, gtk_menu_item_get_label(GTK_MENU_ITEM(searchDomain->data)));
> +        if (label->len)
> +            g_string_assign(label, pango_trim_string(label->str));

In my opinion, it isn't worth using pango here, just to use pango_trim_string.
It probably makes much more sense to use WebCore::String and just call
stripWhiteSpace(). You would avoid any need for manual memory management that way.
Remember to handle the conversion from UTF8 properly (fromUTF8).

Including here:
> +            g_string_free(label, TRUE);
and here:
> +    g_string_free(label, TRUE);

:)

> +bool PopupMenu::filterDomain(GList* startingFrom, GString*& word, GList* currentDomain, GList*& result)

I'm still not convinced this is necessary. What happens if the menu changes while
the user is typing? Is that possible? Why is the "word" parameter a reference to a
pointer? That's very confusing and could lead to errors.

> +// Search the word typed on the keyboard in the PopupMenu and select the
> +// corresponding menuItem if found
> +void PopupMenu::searchItem(GdkEventKey* event, PopupMenu* that)

Why are you passing in "that" to the method here? that == this!

> +bool PopupMenu::keyPressEventCallback(GtkWidget* widget, GdkEventKey* event, PopupMenu* that)
> +{
> +    if (that->isPrintable(event)) {
> +        that->searchItem(event, that);
> +        return true;
> +    }
> +    // Reset the search on Delete key press
> +    if (event->keyval == GDK_Delete)
> +        that->resetWord();

I feel like these if statement should be folded into searchItem,
since this effectively splits up the logic of find-as-you-type
between the outside of the class and the inside. You could just
give the method a more general name, much like Chromium's typeAheadFind.

So you could just do:
> +bool PopupMenu::keyPressEventCallback(GtkWidget* widget, GdkEventKey* event, PopupMenu* that)
> +{
> +     return that->typeAheadFind(event);

[Xan Lopez]

(In reply to comment #19)
> >  #elif PLATFORM(GTK)
> > +    GList* m_searchDomain;
> > +    GString* m_searchedWord;
> 
> Please use GOwnPtr for these types and be sure to write template
> specializations for them if they do not exist yet. This will reduce
> the risk of memory leaks greatly.
> 

(...)

> > +        g_list_free(m_searchDomain);
> > +        g_string_free(m_searchedWord, TRUE);
> 
> This kind of stuff can be omitted entirely if you switch to
> GOwnPtr, or even switching to using WebCore types (though I
> know that you just switched it to GObject types, so maybe that
> kind of change could happen in a later cleanup).

I suggested moving to glib string types (from a previous suggestion where I said to use the WebCore types :D)), because here we are going to be doing substring comparison against glib utf8 C strings all the time, and going back and forth between webcore types and that seems a bit pointless. I think using GString + GOwnPtr is the best compromise.

> I'm not sure I understand exactly why you are caching the menu items
> here (m_searchDomain), is the performance gain worth it? If you didn't,
> it seems like you could get rid of the filterDomain method. Take a look
> at PopupListBox::typeAheadFind in the chromium directory for where they
> implement this same behavior in one method. Maybe we should match that?
> 

I'm not sure if the gain is noticeable (it might be in big combos, since this code should be filtering the list in ~real-time) but now that this is written, and since it's not that complex, I think it's reasonable to just keep it. We could do a first version without it and then add the optimization in a follow-up (I think I might have suggested this at some point), but no strong feelings here.

[Martin Robinson]

> I'm not sure if the gain is noticeable (it might be in big combos, since this code should be filtering the list in ~real-time) but now that this is written, and since it's not that complex, I think it's reasonable to just keep it. We could do a first version without it and then add the optimization in a follow-up (I think I might have suggested this at some point), but no strong feelings here.

There's an out-standing bug about big combos that's related, by the way: https://bugzilla.gnome.org/show_bug.cgi?id=153605

[Martin Robinson]

Comment on attachment 63496 [details]
Find-as-you-type proposed patch

r- for the issues I mentioned before.

[Martin Robinson]

Created attachment 75127 [details]
Patch for this issue

[Xan Lopez]

Comment on attachment 75127 [details]
Patch for this issue

View in context: https://bugs.webkit.org/attachment.cgi?id=75127&action=review

> WebCore/platform/gtk/PopupMenuGtk.cpp:168
> +    bool repeatingCharacter = unicodeCharacter != m_previousKeyEventCharacter;

Can we mention here we are matching the WebCore behavior when the menulist is closed?

[Martin Robinson]

Committed r73025: <http://trac.webkit.org/changeset/73025>