[glib/wip/gdesktopappinfo: 13/13] Add g_desktop_app_info_search()

[Ryan Lortie <desrt src gnome org>]

commit eff3d1b175b421a962edd15555862e429d9fe2d1
Author: Ryan Lortie <desrt desrt ca>
Date:   Sun Jul 28 13:41:22 2013 -0400

    Add g_desktop_app_info_search()

 gio/gdesktopappinfo.c |  496 +++++++++++++++++++++++++++++++++++++++++++++++--
 gio/gdesktopappinfo.h |    5 +
 2 files changed, 481 insertions(+), 20 deletions(-)
---
diff --git a/gio/gdesktopappinfo.c b/gio/gdesktopappinfo.c
index e56cdc7..eec7366 100644
--- a/gio/gdesktopappinfo.c
+++ b/gio/gdesktopappinfo.c
@@ -147,6 +147,8 @@ G_DEFINE_TYPE_WITH_CODE (GDesktopAppInfo, g_desktop_app_info, G_TYPE_OBJECT,
 G_LOCK_DEFINE_STATIC (g_desktop_env);
 static gchar *g_desktop_env = NULL;
 
+/* DesktopFileDirIndex implementation {{{1 */
+
 /* DesktopFileDir implementation {{{1 */
 
 typedef struct
@@ -156,6 +158,10 @@ typedef struct
   GHashTable                 *app_names;
   gboolean                    is_setup;
   struct dfi_index           *dfi;
+  gint8                      *key_id_map;
+  guint16                     key_id_map_length;
+  guint16                     this_locale_id;
+  guint16                     desktop_entry_id;
 } DesktopFileDir;
 
 static DesktopFileDir *desktop_file_dirs;
@@ -335,39 +341,186 @@ desktop_file_dir_unindexed_get_all (DesktopFileDir *dir,
     }
 }
 
+static void
+desktop_file_dir_unindexed_search (DesktopFileDir *dir,
+                                   GSList         *categories,
+                                   const gchar    *term,
+                                   gint            max_hits)
+{
+  /* TODO */
+}
+
 /* Support for indexed DesktopFileDirs {{{2 */
 
-#if 0
 enum
 {
-  DFI_ID_THIS_LOCALE,
-
-  DFI_ID_Desktop_Entry,
+  DESKTOP_KEY_nil,
+
+  /* NB: must keep this list sorted */
+  DESKTOP_KEY_Actions,
+  DESKTOP_KEY_Categories,
+  DESKTOP_KEY_Comment,
+  DESKTOP_KEY_DBusActivatable,
+  DESKTOP_KEY_Exec,
+  DESKTOP_KEY_GenericName,
+  DESKTOP_KEY_Hidden,
+  DESKTOP_KEY_Icon,
+  DESKTOP_KEY_Keywords,
+  DESKTOP_KEY_MimeType,
+  DESKTOP_KEY_Name,
+  DESKTOP_KEY_NoDisplay,
+  DESKTOP_KEY_NotShowIn,
+  DESKTOP_KEY_OnlyShowIn,
+  DESKTOP_KEY_Path,
+  DESKTOP_KEY_StartupNotify,
+  DESKTOP_KEY_StartupWMClass,
+  DESKTOP_KEY_Terminal,
+  DESKTOP_KEY_TryExec,
+  DESKTOP_KEY_Type,
+  DESKTOP_KEY_Version,
+  DESKTOP_KEY_X_GNOME_FullName,
+
+  N_DESKTOP_KEYS
+};
 
-  DFI_ID_Name,
-  DFI_ID_Keywords,
-  DFI_ID_GenericName,
-  DFI_ID_X_GNOME_FullName,
-  DFI_ID_Comment,
+const gchar *desktop_key_names[N_DESKTOP_KEYS];
 
-  N_DFI_IDS
+const gchar desktop_key_match_category[N_DESKTOP_KEYS] = {
+  /* NB: no harm in repeating numbers in case of a tie */
+  [DESKTOP_KEY_Name]             = 1,
+  [DESKTOP_KEY_GenericName]      = 2,
+  [DESKTOP_KEY_Keywords]         = 3,
+  [DESKTOP_KEY_X_GNOME_FullName] = 4,
+  [DESKTOP_KEY_Comment]          = 5
 };
-#endif
+
+#define DESKTOP_KEY_NUM_MATCH_CATEGORIES  5
+
+static void
+desktop_key_init (void)
+{
+  if G_LIKELY (desktop_key_names[1])
+    return;
+
+  desktop_key_names[DESKTOP_KEY_Actions]                = g_intern_static_string ("Actions");
+  desktop_key_names[DESKTOP_KEY_Categories]             = g_intern_static_string ("Categories");
+  desktop_key_names[DESKTOP_KEY_Comment]                = g_intern_static_string ("Comment");
+  desktop_key_names[DESKTOP_KEY_DBusActivatable]        = g_intern_static_string ("DBusActivatable");
+  desktop_key_names[DESKTOP_KEY_Exec]                   = g_intern_static_string ("Exec");
+  desktop_key_names[DESKTOP_KEY_GenericName]            = g_intern_static_string ("GenericName");
+  desktop_key_names[DESKTOP_KEY_Hidden]                 = g_intern_static_string ("Hidden");
+  desktop_key_names[DESKTOP_KEY_Icon]                   = g_intern_static_string ("Icon");
+  desktop_key_names[DESKTOP_KEY_Keywords]               = g_intern_static_string ("Keywords");
+  desktop_key_names[DESKTOP_KEY_MimeType]               = g_intern_static_string ("MimeType");
+  desktop_key_names[DESKTOP_KEY_Name]                   = g_intern_static_string ("Name");
+  desktop_key_names[DESKTOP_KEY_NoDisplay]              = g_intern_static_string ("NoDisplay");
+  desktop_key_names[DESKTOP_KEY_NotShowIn]              = g_intern_static_string ("NotShowIn");
+  desktop_key_names[DESKTOP_KEY_OnlyShowIn]             = g_intern_static_string ("OnlyShowIn");
+  desktop_key_names[DESKTOP_KEY_Path]                   = g_intern_static_string ("Path");
+  desktop_key_names[DESKTOP_KEY_StartupNotify]          = g_intern_static_string ("StartupNotify");
+  desktop_key_names[DESKTOP_KEY_StartupWMClass]         = g_intern_static_string ("StartupWMClass");
+  desktop_key_names[DESKTOP_KEY_Terminal]               = g_intern_static_string ("Terminal");
+  desktop_key_names[DESKTOP_KEY_TryExec]                = g_intern_static_string ("TryExec");
+  desktop_key_names[DESKTOP_KEY_Type]                   = g_intern_static_string ("Type");
+  desktop_key_names[DESKTOP_KEY_Version]                = g_intern_static_string ("Version");
+  desktop_key_names[DESKTOP_KEY_X_GNOME_FullName]       = g_intern_static_string ("X-GNOME-FullName");
+}
 
 static void
 desktop_file_dir_indexed_init (DesktopFileDir *dir)
 {
-  const struct dfi_string_list *app_names;
-  guint n_app_names, i;
+  desktop_key_init ();
 
-  dir->app_names = g_hash_table_new (g_str_hash, g_str_equal);
-  app_names = dfi_index_get_app_names (dir->dfi);
-  n_app_names = dfi_string_list_get_length (app_names);
+  /* Find the current locale */
+  {
+    const struct dfi_string_list *locale_names;
+    const gchar * const *language_names;
+    gint i;
+
+    locale_names = dfi_index_get_locale_names (dir->dfi);
+
+    language_names = g_get_language_names ();
+    locale_names = dfi_index_get_locale_names (dir->dfi);
+
+    /* If we don't get anything, the C locale is always zero, so set
+     * it as a default.
+     */
+    dir->this_locale_id = 0;
+
+    /* Iterate over our language names, in order of preference */
+    for (i = 0; language_names[i]; i++)
+      {
+        gint result = dfi_string_list_binary_search (locale_names, dir->dfi, language_names[i]);
+
+        if (result >= 0)
+          {
+            dir->this_locale_id = result;
+            break;
+          }
+      }
+
+    g_printerr ("found my locale is %d/%s\n", dir->this_locale_id, language_names[i]);
+  }
+
+  /* Populate the app names list. */
+  {
+    const struct dfi_string_list *app_names;
+    guint n_app_names, i;
+
+    app_names = dfi_index_get_app_names (dir->dfi);
+    n_app_names = dfi_string_list_get_length (app_names);
+
+    /* Store the index of each application so we don't need to do binary
+     * searches to find applications.
+     */
+    dir->app_names = g_hash_table_new (g_str_hash, g_str_equal);
+
+    for (i = 0; i < n_app_names; i++)
+      g_hash_table_insert (dir->app_names,
+                           (gchar *) dfi_string_list_get_string_at_index (app_names, dir->dfi, i),
+                           GUINT_TO_POINTER (i));
+  }
+
+  /* Find the ID of the [Desktop Entry] group */
+  {
+    const struct dfi_string_list *group_names;
 
-  for (i = 0; i < n_app_names; i++)
-    g_hash_table_insert (dir->app_names,
-                         (gchar *) dfi_string_list_get_string_at_index (app_names, dir->dfi, i),
-                         GUINT_TO_POINTER (i));
+    group_names = dfi_index_get_group_names (dir->dfi);
+
+    dir->desktop_entry_id = dfi_string_list_binary_search (group_names, dir->dfi, "Desktop Entry");
+  }
+
+  /* Populate the key id map */
+  {
+    const struct dfi_string_list *key_names;
+    guint n_key_names;
+    guint i = 0;
+    guint j = 1;
+
+    key_names = dfi_index_get_key_names (dir->dfi);
+    n_key_names = dfi_string_list_get_length (key_names);
+
+    dir->key_id_map = g_malloc0 (n_key_names);
+    dir->key_id_map_length = n_key_names;
+
+    while (i < n_key_names && j < N_DESKTOP_KEYS)
+      {
+        const gchar *keyname = dfi_string_list_get_string_at_index (key_names, dir->dfi, i);
+        gint cmp;
+
+        cmp = strcmp (keyname, desktop_key_names[j]);
+
+        if (cmp == 0)
+          {
+            g_printerr ("mapped keyname %s(%d) to %d\n", keyname, i, j);
+          dir->key_id_map[i++] = j++;
+          }
+        else if (cmp < 0)
+          i++;
+        else
+          j++;
+      }
+  }
 }
 
 static GDesktopAppInfo *
@@ -409,6 +562,177 @@ desktop_file_dir_indexed_get_all (DesktopFileDir *dir,
     }
 }
 
+static void
+insert_into_list (GSList      *categories,
+                  const gchar *item,
+                  gint         into_bucket,
+                  gint         max_hits)
+{
+  GSList *before_node;
+  GSList **ptr;
+  gint i = 0;
+
+  if (into_bucket < DESKTOP_KEY_NUM_MATCH_CATEGORIES - 1)
+    before_node = &categories[into_bucket + 1];
+  else
+    before_node = NULL;
+
+  for (ptr = &categories; *ptr != before_node; ptr = &(*ptr)->next)
+    {
+      GSList *node = *ptr;
+
+      if (node->data)
+        {
+          /* This item is already in the list, at higher priority.
+           *
+           * Note; pointer compare works for two reasons:
+           *
+           *  - within a given index, a string only appears once
+           *
+           *  - we use masking to prevent seeing the same application
+           *    from multiple different directories
+           */
+          if (node->data == item)
+            return;
+
+          g_assert_cmpstr (node->data, !=, item);
+
+          /* Some other item.  Count it. */
+          i++;
+        }
+
+      /* We already have enough higher-ranking hits */
+      if (i == max_hits)
+        return;
+    }
+
+  /* Add and count ourselves... */
+  *ptr = g_slist_prepend (*ptr, (gchar *) item);
+  ptr = &(*ptr)->next;
+  i++;
+
+  /* We may have to remove an item now:
+   *
+   *  - if the item we inserted already comes later in the list, we must
+   *    remove that one
+   *
+   *  - if we went over max_hits, we need to remove some other item
+   *
+   * This loop will skip past non-duplicates until we hit the maximum
+   * number of items (in which case the next item, duplicate-or-not will
+   * be the one we remove).
+   */
+  while (i != max_hits)
+    {
+      GSList *node = *ptr;
+
+      /* End of list before we had enough hits */
+      if (node == NULL)
+        return;
+
+      if (node->data == item)
+        {
+          /* A later version of ourselves.  Remove it. */
+          *ptr = g_slist_delete_link (node, node);
+
+          /* We added one item and removed one item, so we definitely
+           * didn't grow the list past the max.  We can stop now.
+           */
+          return;
+        }
+
+      if (node->data)
+        i++;
+
+      ptr = &node->next;
+    }
+
+  /* Now we delete the first item we find (if there is one) */
+  while (*ptr)
+    {
+      GSList *node = *ptr;
+
+      if (node->data)
+        {
+          *ptr = g_slist_delete_link (node, node);
+          return;
+        }
+
+      ptr = &(*ptr)->next;
+    }
+}
+
+static void
+desktop_file_dir_indexed_search (DesktopFileDir *dir,
+                                 GSList         *categories,
+                                 const gchar    *term,
+                                 gint            max_hits)
+{
+  const struct dfi_pointer_array *text_indexes;
+  const struct dfi_string_list *app_names;
+  const struct dfi_text_index *text_index;
+  const struct dfi_text_index_item *start;
+  const struct dfi_text_index_item *end;
+  const struct dfi_text_index_item *item;
+
+  text_indexes = dfi_index_get_text_indexes (dir->dfi);
+  text_index = dfi_text_index_from_pointer (dir->dfi,
+                                            dfi_pointer_array_get_pointer (text_indexes, 
dir->this_locale_id));
+  if (text_index == NULL)
+    return;
+
+  dfi_text_index_prefix_search (text_index, dir->dfi, term, &start, &end);
+
+  app_names = dfi_index_get_app_names (dir->dfi);
+
+  for (item = start; item < end; item++)
+    {
+      const dfi_id *ids;
+      guint n_ids;
+
+      gint j;
+
+      ids = dfi_text_index_item_get_ids (item, dir->dfi, &n_ids);
+      //n_ids = 0;
+      //ids = dfi_text_index_get_ids_for_exact_match (dir->dfi, text_index, term, (gint *) &n_ids);
+      g_printerr ("n_ids is %u\n", n_ids);
+
+      if (n_ids % 3 != 0)
+        continue;
+
+      for (j = 0; j < n_ids; j += 3)
+        {
+          guint16 app_id, group_id, key_id;
+          const gchar *app_name;
+          guint8 match_category;
+
+          app_id   = dfi_id_get (ids[j + 0]);
+          group_id = dfi_id_get (ids[j + 1]);
+          key_id   = dfi_id_get (ids[j + 2]);
+
+          app_name = dfi_string_list_get_string_at_index (app_names, dir->dfi, app_id);
+          if (!app_name)
+            continue;
+
+          if (desktop_file_dir_app_name_is_masked (dir, app_name))
+            continue;
+
+          if (group_id != dir->desktop_entry_id)
+            continue;
+
+          if (key_id >= dir->key_id_map_length)
+            continue;
+
+          match_category = desktop_key_match_category[dir->key_id_map[key_id]];
+
+          if (!match_category)
+            continue;
+
+          insert_into_list (categories, app_name, match_category - 1, max_hits);
+        }
+    }
+}
+
 /* DesktopFileDir "API" {{{2 */
 
 /*< internal >
@@ -458,6 +782,16 @@ desktop_file_dir_reset (DesktopFileDir *dir)
       dir->dfi = NULL;
     }
 
+  if (dir->key_id_map)
+    {
+      g_free (dir->key_id_map);
+      dir->key_id_map = NULL;
+    }
+
+  dir->key_id_map_length = 0;
+  dir->desktop_entry_id = 0;
+  dir->this_locale_id = 0;
+
   dir->is_setup = FALSE;
 }
 
@@ -536,6 +870,27 @@ desktop_file_dir_get_all (DesktopFileDir *dir,
     desktop_file_dir_unindexed_get_all (dir, apps);
 }
 
+#define N_SEARCH_BUCKETS 1
+
+/*< internal >
+ * desktop_file_dir_search:
+ * @dir: a #DesktopFilEDir
+ * @term: a normalised and casefolded search term
+ *
+ * Finds the names of applications in @dir that match @term.
+ */
+static void
+desktop_file_dir_search (DesktopFileDir *dir,
+                         GSList         *categories,
+                         const gchar    *term,
+                         gint            max_hits)
+{
+  if (dir->dfi)
+    desktop_file_dir_indexed_search (dir, categories, term, max_hits);
+  else
+    desktop_file_dir_unindexed_search (dir, categories, term, max_hits);
+}
+
 /* Lock/unlock and global setup API {{{2 */
 
 static void
@@ -3202,6 +3557,107 @@ g_app_info_get_default_for_uri_scheme (const char *uri_scheme)
 
 /* "Get all" API {{{2 */
 
+gchar **
+g_desktop_app_info_search (const char *token,
+                           gint        max_hits)
+{
+  GSList categories[DESKTOP_KEY_NUM_MATCH_CATEGORIES];
+  GSList *node;
+  gchar **results;
+  gint i, n;
+
+  for (i = 0; i < DESKTOP_KEY_NUM_MATCH_CATEGORIES; i++)
+    {
+      categories[i].next = &categories[i + 1];
+      categories[i].data = NULL;
+    }
+  categories[DESKTOP_KEY_NUM_MATCH_CATEGORIES - 1].next = NULL;
+
+  desktop_file_dirs_lock ();
+
+  for (i = 0; i < n_desktop_file_dirs; i++)
+    desktop_file_dir_search (&desktop_file_dirs[i], categories, token, max_hits);
+
+  /* Must hold lock while processing results because otherwise strings
+   * could go missing out from under us.
+   */
+  node = &categories[0];
+  n = g_slist_length (categories) - DESKTOP_KEY_NUM_MATCH_CATEGORIES;
+  results = g_new (gchar *, n + 1);
+  i = 0;
+  while (node)
+    {
+      GSList *next = node->next;
+
+      if (node->data)
+        {
+          results[i++] = g_strdup (node->data);
+          g_slist_free_1 (node);
+        }
+
+      node = next;
+    }
+
+  g_assert_cmpint (i, ==, n);
+  results[i] = NULL;
+
+  desktop_file_dirs_unlock ();
+
+  return results;
+}
+
+gchar ***
+g_desktop_app_info_search_full (const gchar *token,
+                                gint         max_hits)
+{
+  GSList categories[DESKTOP_KEY_NUM_MATCH_CATEGORIES];
+  gchar ***results;
+  gint i, j;
+
+  for (i = 0; i < DESKTOP_KEY_NUM_MATCH_CATEGORIES; i++)
+    {
+      categories[i].next = &categories[i + 1];
+      categories[i].data = NULL;
+    }
+  categories[DESKTOP_KEY_NUM_MATCH_CATEGORIES - 1].next = NULL;
+
+  desktop_file_dirs_lock ();
+
+  for (i = 0; i < n_desktop_file_dirs; i++)
+    desktop_file_dir_search (&desktop_file_dirs[i], categories, token, max_hits);
+
+  /* As above, must hold the lock. */
+  results = g_new (gchar **, DESKTOP_KEY_NUM_MATCH_CATEGORIES + 1);
+  j = 0;
+
+  for (i = 0; i < DESKTOP_KEY_NUM_MATCH_CATEGORIES; i++)
+    {
+      gchar **list;
+      GSList *node;
+      gint n;
+
+      n = 0;
+      for (node = categories[i].next; node && node->data; node = node->next)
+        n++;
+
+      if (n == 0)
+        continue;
+
+      list = g_new (gchar *, n + 1);
+      n = 0;
+      for (node = categories[i].next; node && node->data; node = node->next)
+        list[n++] = g_strdup (node->data);
+      list[n] = NULL;
+
+      results[j++] = list;
+    }
+  results[j] = NULL;
+
+  desktop_file_dirs_unlock ();
+
+  return results;
+}
+
 /**
  * g_app_info_get_all:
  *
diff --git a/gio/gdesktopappinfo.h b/gio/gdesktopappinfo.h
index 5f7f68a..749dfb1 100644
--- a/gio/gdesktopappinfo.h
+++ b/gio/gdesktopappinfo.h
@@ -165,6 +165,11 @@ gboolean    g_desktop_app_info_launch_uris_as_manager (GDesktopAppInfo
                                                       GError                    **error);
 
 
+GLIB_AVAILABLE_IN_2_30
+gchar ** g_desktop_app_info_search (const gchar *term, gint max_hits);
+GLIB_AVAILABLE_IN_2_30
+gchar *** g_desktop_app_info_search_full (const gchar *term, gint max_hits);
+
 G_END_DECLS
 
 #endif /* __G_DESKTOP_APP_INFO_H__ */