[gnome-builder] ctags: implement fuzzy match and character highlighting

[Christian Hergert <chergert src gnome org>]

commit 2822864beb46778c160d92304a1e032431295918
Author: Christian Hergert <christian hergert me>
Date:   Mon Sep 28 06:24:00 2015 -0700

    ctags: implement fuzzy match and character highlighting
    
    To get the performance we want, while doing fuzzy matching, we've moved
    to using the new IdeCompletionResults which will try to replay upon
    existing queries for us.

 plugins/ctags/Makefile.am                          |    2 +
 plugins/ctags/ide-ctags-completion-item.c          |   66 +++---
 plugins/ctags/ide-ctags-completion-item.h          |   11 +-
 .../ctags/ide-ctags-completion-provider-private.h  |   39 +++
 plugins/ctags/ide-ctags-completion-provider.c      |  251 ++++++--------------
 5 files changed, 154 insertions(+), 215 deletions(-)
---
diff --git a/plugins/ctags/Makefile.am b/plugins/ctags/Makefile.am
index 5773681..3732ecd 100644
--- a/plugins/ctags/Makefile.am
+++ b/plugins/ctags/Makefile.am
@@ -11,6 +11,7 @@ libctags_plugin_la_SOURCES = \
        ide-ctags-completion-item.h \
        ide-ctags-completion-provider.c \
        ide-ctags-completion-provider.h \
+       ide-ctags-completion-provider-private.h \
        ide-ctags-highlighter.c \
        ide-ctags-highlighter.h \
        ide-ctags-index.c \
@@ -29,6 +30,7 @@ libctags_plugin_la_CFLAGS = \
        -I$(top_srcdir)/contrib/egg \
        -I$(top_srcdir)/libide \
        -I$(top_srcdir)/libide/util \
+       -I$(top_srcdir)/src/util \
        $(NULL)
 
 libctags_plugin_la_LDFLAGS = \
diff --git a/plugins/ctags/ide-ctags-completion-item.c b/plugins/ctags/ide-ctags-completion-item.c
index 99d0ff9..896741c 100644
--- a/plugins/ctags/ide-ctags-completion-item.c
+++ b/plugins/ctags/ide-ctags-completion-item.c
@@ -21,53 +21,44 @@
 #include <glib/gi18n.h>
 
 #include "egg-counter.h"
+#include "gb-string.h"
 
+#include "ide-completion-item.h"
 #include "ide-ctags-completion-item.h"
+#include "ide-ctags-completion-provider.h"
+#include "ide-ctags-completion-provider-private.h"
 #include "ide-ctags-index.h"
 
-EGG_DEFINE_COUNTER (instances, "IdeCtagsCompletionItem", "Instances",
-                    "Number of IdeCtagsCompletionItems")
-
 struct _IdeCtagsCompletionItem
 {
-  GObject                     parent_instance;
+  IdeCompletionItem           parent_instance;
   const IdeCtagsIndexEntry   *entry;
   IdeCtagsCompletionProvider *provider;
-  GtkSourceCompletionContext *context;
 };
 
 static void proposal_iface_init (GtkSourceCompletionProposalIface *iface);
 
 G_DEFINE_DYNAMIC_TYPE_EXTENDED (IdeCtagsCompletionItem,
                                 ide_ctags_completion_item,
-                                G_TYPE_OBJECT,
+                                IDE_TYPE_COMPLETION_ITEM,
                                 0,
-                                G_IMPLEMENT_INTERFACE (GTK_SOURCE_TYPE_COMPLETION_PROPOSAL,
-                                                       proposal_iface_init))
+                                G_IMPLEMENT_INTERFACE (GTK_SOURCE_TYPE_COMPLETION_PROPOSAL, 
proposal_iface_init))
+
+EGG_DEFINE_COUNTER (instances, "IdeCtagsCompletionItem", "Instances", "Number of IdeCtagsCompletionItems")
 
-GtkSourceCompletionProposal *
-ide_ctags_completion_item_new (const IdeCtagsIndexEntry   *entry,
-                               IdeCtagsCompletionProvider *provider,
-                               GtkSourceCompletionContext *context)
+IdeCtagsCompletionItem *
+ide_ctags_completion_item_new (IdeCtagsCompletionProvider *provider,
+                               const IdeCtagsIndexEntry   *entry)
 {
   IdeCtagsCompletionItem *self;
 
-  self= g_object_new (IDE_TYPE_CTAGS_COMPLETION_ITEM, NULL);
+  g_return_val_if_fail (entry != NULL, NULL);
 
-  /*
-   * use borrowed references to avoid the massive amount of reference counting.
-   * we don't need them since we know the provider will outlast us.
-   */
-  self->entry = entry;
+  self = g_object_new (IDE_TYPE_CTAGS_COMPLETION_ITEM, NULL);
   self->provider = provider;
+  self->entry = entry;
 
-  /*
-   * There is the slight chance the context will get disposed out of
-   * our control. I've seen this happen a few times now.
-   */
-  ide_set_weak_pointer (&self->context, context);
-
-  return GTK_SOURCE_COMPLETION_PROPOSAL (self);
+  return self;
 }
 
 gint
@@ -77,13 +68,20 @@ ide_ctags_completion_item_compare (IdeCtagsCompletionItem *itema,
   return ide_ctags_index_entry_compare (itema->entry, itemb->entry);
 }
 
-static void
-ide_ctags_completion_item_finalize (GObject *object)
+static gboolean
+ide_ctags_completion_item_match (IdeCompletionItem *item,
+                                 const gchar       *query,
+                                 const gchar       *casefold)
 {
-  IdeCtagsCompletionItem *self = (IdeCtagsCompletionItem *)object;
+  IdeCtagsCompletionItem *self = (IdeCtagsCompletionItem *)item;
+  IdeCompletionItemHead *head = (IdeCompletionItemHead *)item;
 
-  ide_clear_weak_pointer (&self->context);
+  return ide_completion_item_fuzzy_match (self->entry->name, casefold, &head->priority);
+}
 
+static void
+ide_ctags_completion_item_finalize (GObject *object)
+{
   G_OBJECT_CLASS (ide_ctags_completion_item_parent_class)->finalize (object);
 
   EGG_COUNTER_DEC (instances);
@@ -93,8 +91,11 @@ static void
 ide_ctags_completion_item_class_init (IdeCtagsCompletionItemClass *klass)
 {
   GObjectClass *object_class = G_OBJECT_CLASS (klass);
+  IdeCompletionItemClass *item_class = IDE_COMPLETION_ITEM_CLASS (klass);
 
   object_class->finalize = ide_ctags_completion_item_finalize;
+
+  item_class->match = ide_ctags_completion_item_match;
 }
 
 static void
@@ -109,10 +110,13 @@ ide_ctags_completion_item_init (IdeCtagsCompletionItem *self)
 }
 
 static gchar *
-get_label (GtkSourceCompletionProposal *proposal)
+get_markup (GtkSourceCompletionProposal *proposal)
 {
   IdeCtagsCompletionItem *self = (IdeCtagsCompletionItem *)proposal;
 
+  if (self->provider->current_word != NULL)
+    return gb_str_highlight (self->entry->name, self->provider->current_word);
+
   return g_strdup (self->entry->name);
 }
 
@@ -191,7 +195,7 @@ get_icon_name (GtkSourceCompletionProposal *proposal)
 static void
 proposal_iface_init (GtkSourceCompletionProposalIface *iface)
 {
-  iface->get_label = get_label;
+  iface->get_markup = get_markup;
   iface->get_text = get_text;
   iface->get_icon_name = get_icon_name;
 }
diff --git a/plugins/ctags/ide-ctags-completion-item.h b/plugins/ctags/ide-ctags-completion-item.h
index 65c3b28..87284ff 100644
--- a/plugins/ctags/ide-ctags-completion-item.h
+++ b/plugins/ctags/ide-ctags-completion-item.h
@@ -21,6 +21,7 @@
 
 #include <gtksourceview/gtksource.h>
 
+#include "ide-completion-item.h"
 #include "ide-ctags-index.h"
 #include "ide-ctags-completion-provider.h"
 
@@ -28,13 +29,11 @@ G_BEGIN_DECLS
 
 #define IDE_TYPE_CTAGS_COMPLETION_ITEM (ide_ctags_completion_item_get_type())
 
-G_DECLARE_FINAL_TYPE (IdeCtagsCompletionItem, ide_ctags_completion_item, IDE, CTAGS_COMPLETION_ITEM, GObject)
+G_DECLARE_FINAL_TYPE (IdeCtagsCompletionItem, ide_ctags_completion_item, IDE, CTAGS_COMPLETION_ITEM, 
IdeCompletionItem)
 
-GtkSourceCompletionProposal *ide_ctags_completion_item_new     (const IdeCtagsIndexEntry   *entry,
-                                                                IdeCtagsCompletionProvider *provider,
-                                                                GtkSourceCompletionContext *context);
-gint                         ide_ctags_completion_item_compare (IdeCtagsCompletionItem     *itema,
-                                                                IdeCtagsCompletionItem     *itemb);
+IdeCtagsCompletionItem *
+ide_ctags_completion_item_new (IdeCtagsCompletionProvider *provider,
+                               const IdeCtagsIndexEntry   *entry);
 
 G_END_DECLS
 
diff --git a/plugins/ctags/ide-ctags-completion-provider-private.h 
b/plugins/ctags/ide-ctags-completion-provider-private.h
new file mode 100644
index 0000000..5370244
--- /dev/null
+++ b/plugins/ctags/ide-ctags-completion-provider-private.h
@@ -0,0 +1,39 @@
+/* ide-ctags-completion-provider-private.h
+ *
+ * Copyright (C) 2015 Christian Hergert <christian hergert me>
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ */
+
+#ifndef IDE_CTAGS_COMPLETION_PROVIDER_PRIVATE_H
+#define IDE_CTAGS_COMPLETION_PROVIDER_PRIVATE_H
+
+#include "ide-ctags-completion-provider.h"
+#include "ide-completion-results.h"
+
+G_BEGIN_DECLS
+
+struct _IdeCtagsCompletionProvider
+{
+  IdeObject             parent_instance;
+  gint                  minimum_word_size;
+  GSettings            *settings;
+  GPtrArray            *indexes;
+  IdeCompletionResults *results;
+  gchar                *current_word;
+};
+
+G_END_DECLS
+
+#endif /* IDE_CTAGS_COMPLETION_PROVIDER_PRIVATE_H */
diff --git a/plugins/ctags/ide-ctags-completion-provider.c b/plugins/ctags/ide-ctags-completion-provider.c
index acdb919..94ddf96 100644
--- a/plugins/ctags/ide-ctags-completion-provider.c
+++ b/plugins/ctags/ide-ctags-completion-provider.c
@@ -21,25 +21,17 @@
 #include <glib/gi18n.h>
 
 #include "ide-completion-provider.h"
+#include "ide-completion-item.h"
+#include "ide-completion-results.h"
 #include "ide-context.h"
 #include "ide-ctags-completion-item.h"
 #include "ide-ctags-completion-provider.h"
+#include "ide-ctags-completion-provider-private.h"
 #include "ide-ctags-service.h"
 #include "ide-ctags-util.h"
 #include "ide-debug.h"
 #include "ide-macros.h"
 
-struct _IdeCtagsCompletionProvider
-{
-  IdeObject      parent_instance;
-
-  GSettings     *settings;
-  GPtrArray     *indexes;
-  GHashTable    *icons;
-
-  gint           minimum_word_size;
-};
-
 static void provider_iface_init (GtkSourceCompletionProviderIface *iface);
 
 G_DEFINE_DYNAMIC_TYPE_EXTENDED (IdeCtagsCompletionProvider,
@@ -84,17 +76,6 @@ ide_ctags_completion_provider_add_index (IdeCtagsCompletionProvider *self,
 }
 
 static void
-theme_changed_cb (IdeCtagsCompletionProvider *self,
-                  GParamSpec                 *pspec,
-                  GtkSettings                *settings)
-{
-  g_assert (IDE_IS_CTAGS_COMPLETION_PROVIDER (self));
-  g_assert (self->icons != NULL);
-
-  g_hash_table_remove_all (self->icons);
-}
-
-static void
 ide_ctags_completion_provider_constructed (GObject *object)
 {
   IdeCtagsCompletionProvider *self = (IdeCtagsCompletionProvider *)object;
@@ -127,8 +108,10 @@ ide_ctags_completion_provider_finalize (GObject *object)
 {
   IdeCtagsCompletionProvider *self = (IdeCtagsCompletionProvider *)object;
 
+  g_clear_pointer (&self->current_word, g_free);
   g_clear_pointer (&self->indexes, g_ptr_array_unref);
   g_clear_object (&self->settings);
+  g_clear_object (&self->results);
 
   G_OBJECT_CLASS (ide_ctags_completion_provider_parent_class)->finalize (object);
 }
@@ -151,96 +134,33 @@ ide_ctags_completion_provider_class_finalize (IdeCtagsCompletionProviderClass *k
 static void
 ide_ctags_completion_provider_init (IdeCtagsCompletionProvider *self)
 {
-  GtkSettings *settings;
-
   self->minimum_word_size = 3;
   self->indexes = g_ptr_array_new_with_free_func (g_object_unref);
   self->settings = g_settings_new ("org.gnome.builder.code-insight");
-  self->icons = g_hash_table_new_full (g_str_hash, g_str_equal, g_free, g_object_unref);
-
-  settings = gtk_settings_get_default ();
-
-  g_signal_connect_object (settings,
-                           "notify::gtk-theme-name",
-                           G_CALLBACK (theme_changed_cb),
-                           self,
-                           G_CONNECT_SWAPPED);
-
-  g_signal_connect_object (settings,
-                           "notify::gtk-application-prefer-dark-theme",
-                           G_CALLBACK (theme_changed_cb),
-                           self,
-                           G_CONNECT_SWAPPED);
 }
 
 static gchar *
 ide_ctags_completion_provider_get_name (GtkSourceCompletionProvider *provider)
 {
-  return g_strdup (_("CTags"));
-}
-
-static inline gboolean
-is_symbol_char (gunichar ch)
-{
-  switch (ch)
-    {
-    case '_':
-      return TRUE;
-
-    default:
-      return g_unichar_isalnum (ch);
-    }
+  return g_strdup (_("CTAGS"));
 }
 
-static gchar *
-get_word_to_cursor (const GtkTextIter *location)
+static const gchar * const *
+get_allowed_suffixes (GtkSourceCompletionContext *context)
 {
-  GtkTextIter iter = *location;
-  GtkTextIter end = *location;
-
-  if (!gtk_text_iter_backward_char (&end))
-    return NULL;
-
-  while (gtk_text_iter_backward_char (&iter))
-    {
-      gunichar ch;
-
-      ch = gtk_text_iter_get_char (&iter);
-
-      if (!is_symbol_char (ch))
-        break;
-    }
-
-  if (!is_symbol_char (gtk_text_iter_get_char (&iter)))
-    gtk_text_iter_forward_char (&iter);
+  GtkTextIter iter;
+  GtkSourceBuffer *buffer;
+  GtkSourceLanguage *language;
+  const gchar *lang_id = NULL;
 
-  if (gtk_text_iter_compare (&iter, &end) >= 0)
+  if (!gtk_source_completion_context_get_iter (context, &iter))
     return NULL;
 
-  return gtk_text_iter_get_slice (&iter, location);
-}
-
-static gint
-sort_wrapper (gconstpointer a,
-              gconstpointer b)
-{
-  IdeCtagsIndexEntry * const *enta = a;
-  IdeCtagsIndexEntry * const *entb = b;
-
-  return ide_ctags_index_entry_compare (*enta, *entb);
-}
-
-static inline gboolean
-too_similar (const IdeCtagsIndexEntry *a,
-             const IdeCtagsIndexEntry *b)
-{
-  if (a->kind == b->kind)
-    {
-      if (ide_str_equal0 (a->name, b->name))
-        return TRUE;
-    }
+  buffer = GTK_SOURCE_BUFFER (gtk_text_iter_get_buffer (&iter));
+  if ((language = gtk_source_buffer_get_language (buffer)))
+    lang_id = gtk_source_language_get_id (language);
 
-  return FALSE;
+  return ide_ctags_get_allowed_suffixes (lang_id);
 }
 
 static void
@@ -248,111 +168,83 @@ ide_ctags_completion_provider_populate (GtkSourceCompletionProvider *provider,
                                         GtkSourceCompletionContext  *context)
 {
   IdeCtagsCompletionProvider *self = (IdeCtagsCompletionProvider *)provider;
-  g_autofree gchar *word = NULL;
-  const IdeCtagsIndexEntry *entries;
   const gchar * const *allowed;
-  g_autoptr(GPtrArray) ar = NULL;
-  IdeCtagsIndexEntry *last = NULL;
-  GtkSourceBuffer *buffer;
-  GtkSourceLanguage *language;
-  const gchar *lang_id = NULL;
-  gsize n_entries;
-  GtkTextIter iter;
-  GList *list = NULL;
-  gsize i;
-  gsize j;
+  g_autofree gchar *casefold = NULL;
+  gint word_len;
+  guint i;
+  guint j;
 
   IDE_ENTRY;
 
   g_assert (IDE_IS_CTAGS_COMPLETION_PROVIDER (self));
   g_assert (GTK_SOURCE_IS_COMPLETION_CONTEXT (context));
 
-  if (!gtk_source_completion_context_get_iter (context, &iter))
-    IDE_GOTO (failure);
+  g_clear_pointer (&self->current_word, g_free);
+  self->current_word = ide_completion_provider_context_current_word (context);
 
-  buffer = GTK_SOURCE_BUFFER (gtk_text_iter_get_buffer (&iter));
-  if ((language = gtk_source_buffer_get_language (buffer)))
-    lang_id = gtk_source_language_get_id (language);
-  allowed = ide_ctags_get_allowed_suffixes (lang_id);
+  allowed = get_allowed_suffixes (context);
 
-  word = get_word_to_cursor (&iter);
-  if (ide_str_empty0 (word) || strlen (word) < self->minimum_word_size)
-    IDE_GOTO (failure);
+  if (self->results != NULL)
+    {
+      if (ide_completion_results_replay (self->results, self->current_word))
+        {
+          ide_completion_results_present (self->results, provider, context);
+          IDE_EXIT;
+        }
+      g_clear_pointer (&self->results, g_object_unref);
+    }
 
-  if (strlen (word) < 3)
-    IDE_GOTO (failure);
+  word_len = strlen (self->current_word);
+  if (word_len < self->minimum_word_size)
+    IDE_GOTO (word_too_small);
 
-  ar = g_ptr_array_new ();
+  casefold = g_utf8_casefold (self->current_word, -1);
 
-  IDE_TRACE_MSG ("Searching for %s", word);
+  self->results = ide_completion_results_new (self->current_word);
 
-  for (j = 0; j < self->indexes->len; j++)
+  for (i = 0; i < self->indexes->len; i++)
     {
-      IdeCtagsIndex *index = g_ptr_array_index (self->indexes, j);
+      g_autofree gchar *copy = g_strdup (self->current_word);
+      IdeCtagsIndex *index = g_ptr_array_index (self->indexes, i);
+      const IdeCtagsIndexEntry *entries = NULL;
+      guint tmp_len = word_len;
+      gsize n_entries = 0;
+
+      while (entries == NULL && *copy)
+        {
+          if (!(entries = ide_ctags_index_lookup_prefix (index, copy, &n_entries)))
+            copy [--tmp_len] = '\0';
+        }
 
-      entries = ide_ctags_index_lookup_prefix (index, word, &n_entries);
       if ((entries == NULL) || (n_entries == 0))
         continue;
 
-      for (i = 0; i < n_entries; i++)
+      for (j = 0; j < n_entries; j++)
         {
-          const IdeCtagsIndexEntry *entry = &entries [i];
+          const IdeCtagsIndexEntry *entry = &entries [j];
+          IdeCtagsCompletionItem *item;
 
-          if (ide_ctags_is_allowed (entry, allowed))
-            g_ptr_array_add (ar, (gpointer)entry);
-        }
-    }
+          if (!ide_ctags_is_allowed (entry, allowed))
+            continue;
 
-  g_ptr_array_sort (ar, sort_wrapper);
+          item = ide_ctags_completion_item_new (self, entry);
 
-  for (i = ar->len; i > 0; i--)
-    {
-      GtkSourceCompletionProposal *item;
-      IdeCtagsIndexEntry *entry = g_ptr_array_index (ar, i - 1);
-
-      /*
-       * NOTE:
-       *
-       * We walk backwards in this ptrarray so that we can use g_list_prepend() for O(1) access.
-       * I think everyone agrees that using GList for passing completion data around was not
-       * a great choice, but it is what we have to work with.
-       */
-
-      /*
-       * Ignore this item if the previous one looks really similar.
-       * We take the first item instead of the last since the first item (when walking backwards)
-       * tends to be more likely to be the one we care about (based on lexicographical
-       * ordering. For example, something in "gtk-2.0" is less useful than "gtk-3.0".
-       *
-       * This is done here instead of during our initial object creation so that
-       * we can merge items between different indexes. It often happens that the
-       * same headers are included in multiple tags files.
-       */
-      if ((last != NULL) && too_similar (entry, last))
-        continue;
+          if (!ide_completion_item_match (IDE_COMPLETION_ITEM (item), self->current_word, casefold))
+            {
+              g_object_unref (item);
+              continue;
+            }
 
-      /*
-       * NOTE:
-       *
-       * Autocompletion is very performance sensitive code. The smallest amount of
-       * extra work has a very negative impact on interactivity. We are trying to
-       * avoid a couple things here based on how completion works.
-       *
-       * 1) Avoiding referencing or copying things.
-       *    Since the provider will always outlive the completion item, we use
-       *    borrowed references for as much as we can.
-       * 2) We delay the work of looking up icons until they are requested.
-       *    No sense in doing that work before hand.
-       */
-      item = ide_ctags_completion_item_new (entry, self, context);
-      list = g_list_prepend (list, item);
-
-      last = entry;
+          ide_completion_results_take_proposal (self->results, IDE_COMPLETION_ITEM (item));
+        }
     }
 
-failure:
-  gtk_source_completion_context_add_proposals (context, provider, list, TRUE);
-  g_list_free_full (list, g_object_unref);
+  ide_completion_results_present (self->results, provider, context);
+
+  IDE_EXIT;
+
+word_too_small:
+  gtk_source_completion_context_add_proposals (context, provider, NULL, TRUE);
 
   IDE_EXIT;
 }
@@ -381,7 +273,7 @@ ide_ctags_completion_provider_match (GtkSourceCompletionProvider *provider,
 
   if (activation == GTK_SOURCE_COMPLETION_ACTIVATION_INTERACTIVE)
     {
-      if (!gtk_text_iter_starts_line (&iter) ||
+      if (gtk_text_iter_starts_line (&iter) ||
           !gtk_text_iter_backward_char (&iter) ||
           g_unichar_isspace (gtk_text_iter_get_char (&iter)))
         return FALSE;
@@ -390,6 +282,9 @@ ide_ctags_completion_provider_match (GtkSourceCompletionProvider *provider,
   if (!g_settings_get_boolean (self->settings, "ctags-autocompletion"))
     return FALSE;
 
+  if (ide_completion_provider_context_in_comment (context))
+    return FALSE;
+
   return TRUE;
 }