After an evaluation, GNOME has moved from Bugzilla to GitLab. Learn more about GitLab.
No new issues can be reported in GNOME Bugzilla anymore.
To report an issue in a GNOME project, go to GNOME GitLab.
Do not go to GNOME Gitlab for: Bluefish, Doxygen, GnuCash, GStreamer, java-gnome, LDTP, NetworkManager, Tomboy.
Bug 764417 - Application search algorithm (g_desktop_app_info_search()) should use fuzzy matching
Application search algorithm (g_desktop_app_info_search()) should use fuzzy m...
Status: RESOLVED OBSOLETE
Product: glib
Classification: Platform
Component: gio
unspecified
Other Linux
: Normal normal
: ---
Assigned To: gtkdev
gtkdev
: 727341 764570 786522 (view as bug list)
Depends on:
Blocks:
 
 
Reported: 2016-03-31 14:57 UTC by Pierre-Eric Pelloux-Prayer
Modified: 2018-05-24 18:45 UTC
See Also:
GNOME target: ---
GNOME version: ---


Attachments
Adds a g_str_match_string_fuzzy function to glib (5.79 KB, patch)
2016-03-31 14:58 UTC, Pierre-Eric Pelloux-Prayer
none Details | Review
Use fuzzy matching in g_desktop_app_info_search (11.55 KB, patch)
2016-03-31 15:00 UTC, Pierre-Eric Pelloux-Prayer
none Details | Review
Adds a g_str_match_string_fuzzy function to glib v2 (7.11 KB, patch)
2016-03-31 15:44 UTC, Pierre-Eric Pelloux-Prayer
none Details | Review
Use fuzzy matching in g_desktop_app_info_search v2 (11.64 KB, patch)
2016-03-31 15:44 UTC, Pierre-Eric Pelloux-Prayer
none Details | Review

Description Pierre-Eric Pelloux-Prayer 2016-03-31 14:57:37 UTC
Currently characters entered by a user must match the beginning of an application name.
Using fuzzy matching (a la Sublime Text) would make the search easier.
Comment 1 Pierre-Eric Pelloux-Prayer 2016-03-31 14:58:56 UTC
Created attachment 325090 [details] [review]
Adds a g_str_match_string_fuzzy function to glib

Based on https://github.com/forrestthewoods/lib_fts/blob/master/code/fts_fuzzy_match.h

Modified slightly to fit the coding style.
Comment 2 Pierre-Eric Pelloux-Prayer 2016-03-31 15:00:03 UTC
Created attachment 325091 [details] [review]
Use fuzzy matching in g_desktop_app_info_search

Use g_str_match_string_fuzzy to search applications that match characters entered by the user
Comment 3 Florian Müllner 2016-03-31 15:04:14 UTC
Also see bug 753102.
Comment 4 Emmanuele Bassi (:ebassi) 2016-03-31 15:08:54 UTC
Review of attachment 325090 [details] [review]:

There are coding style issues, like using // for comments; wrong indentation levels; and references to the original C++ code.

These need to be fixed before a proper review is possible.

::: glib/gstrfuncs.h
@@ +305,3 @@
+GLIB_AVAILABLE_IN_2_48
+gint               		g_str_match_string_fuzzy (const gchar  *str,
+												  const gchar  *pattern);

The whitespace is all broken. Please, make sure you use spaces, not tabs.
Comment 5 Pierre-Eric Pelloux-Prayer 2016-03-31 15:10:25 UTC
Oh, sorry about the coding style issues, I should've double checked.
Comment 6 Pierre-Eric Pelloux-Prayer 2016-03-31 15:44:11 UTC
Created attachment 325095 [details] [review]
Adds a g_str_match_string_fuzzy function to glib v2

Fixed (hopefully) style issues
Comment 7 Pierre-Eric Pelloux-Prayer 2016-03-31 15:44:57 UTC
Created attachment 325097 [details] [review]
Use fuzzy matching in g_desktop_app_info_search v2

Style issues fixed
Comment 8 Matthias Clasen 2016-04-05 22:58:32 UTC
Before we go any further with this, please get Allison to chime in here wrt to plans for desktop file indexing that existed at some point
Comment 9 Pierre-Eric Pelloux-Prayer 2016-04-06 08:07:55 UTC
(In reply to Matthias Clasen from comment #8)
> Before we go any further with this, please get Allison to chime in here wrt
> to plans for desktop file indexing that existed at some point

Ok.

In the meantime, would it make sense to discuss the addition of the g_str_match_string_fuzzy to glib?
I believe it's a useful addition to glib, regardless of the whether or not g_desktop_app_info_search uses it.

Also, is it worth asking feedback to gnome usability/design team to see if there's interest in having gnome-shell supporting fuzzy search for apps?
Comment 10 Matthias Clasen 2016-04-06 14:12:09 UTC
(In reply to Pierre-Eric Pelloux-Prayer from comment #9)

> In the meantime, would it make sense to discuss the addition of the
> g_str_match_string_fuzzy to glib?

I'd rather not add api, at least initially. It is really not clear what the use cases are, beyond the one we are discussing here.
Comment 11 Pierre-Eric Pelloux-Prayer 2016-04-08 08:13:47 UTC
(In reply to Matthias Clasen from comment #10)
> (In reply to Pierre-Eric Pelloux-Prayer from comment #9)
> 
> > In the meantime, would it make sense to discuss the addition of the
> > g_str_match_string_fuzzy to glib?
> 
> I'd rather not add api, at least initially. It is really not clear what the
> use cases are, beyond the one we are discussing here.

Other potential use cases: epiphany's address bar, gimp's action search dialog, Polari's tab completion, etc
Comment 12 Allison Karlitskaya (desrt) 2016-04-27 07:45:06 UTC
I am slightly against this for the reasons that Matthias allude to -- our current approach to handling the search is very very dumb (because it was easy and it works "good enough" for the number of desktop files we have and the hardware we run on).  If we ever want to optimise this in the future, we may regret having made this change...

In particular, the choice to match on prefixes only was made in order to allow binary search over the tokens in a sorted list.
Comment 13 Pierre-Eric Pelloux-Prayer 2016-04-27 08:28:53 UTC
Noted.

Should this bug be marked as won't fix then?
Comment 14 Philip Withnall 2017-09-13 11:59:55 UTC
*** Bug 786522 has been marked as a duplicate of this bug. ***
Comment 15 Philip Withnall 2017-09-13 12:03:43 UTC
*** Bug 764570 has been marked as a duplicate of this bug. ***
Comment 16 Philip Withnall 2017-09-13 12:04:29 UTC
I think there is definitely work to do here. We shouldn’t let performance concerns stand in the way of fixing search results which don’t match the users’ expectations.

Some more examples of suboptimal search results from bug #786522:
 • Search for ‘power’, expect the ‘Power’ control panel to be listed first, but it’s ranked as equal with LibreOffice Impress.
 • Search for ‘R’ (as in the statistics language), expect that app to be listed first, but actually the first result is ‘Sound Recorder’. R is listed fourth.
 • Search for ‘Sound’, expect that the control panel is listed first, but it’s listed after ‘Sound Recorder’.
Comment 17 Philip Withnall 2017-09-13 12:06:26 UTC
*** Bug 727341 has been marked as a duplicate of this bug. ***
Comment 18 Philip Withnall 2017-09-13 12:07:31 UTC
Bug #727341 mentions the need for including punctuation in the search tokens: they want searching for ‘+’ to match ‘Google+’. That seems reasonable, given the search string is entirely punctuation.
Comment 19 GNOME Infrastructure Team 2018-05-24 18:45:45 UTC
-- GitLab Migration Automatic Message --

This bug has been migrated to GNOME's GitLab instance and has been closed from further activity.

You can subscribe and participate further through the new bug through this link to our GitLab instance: https://gitlab.gnome.org/GNOME/glib/issues/1152.