[gnome-builder/gnome-builder-3-18] clang: make clang autocompletion fast

[Christian Hergert <chergert src gnome org>]

commit 2ab78499d6aa8baf45a8c20e341ac502efa256dd
Author: Christian Hergert <christian hergert me>
Date:   Sun Sep 27 04:43:28 2015 -0700

    clang: make clang autocompletion fast
    
    Okay, so there is some dark wizardry going on here.
    
    There are two major shitstorms to optimize around here. The first, is that
    clang will basically give us everything in the world back that could be
    completed, regardless of if it is actually useful. For example, while
    writing this module, I was seeing an average of 30,000 entries. Of course,
    the are sorted in no particular order.
    
    The second shitstorm, is that GtkSourceCompletionContext takes a GList
    of items. I'm not particularly keen on allocating lots of GList items
    especially if it means we need to sort them.
    
    So instead, we have a double structure where we keep an array of
    completion items, of which embed a GList node in them. This way, we
    don't need to allocate any GList items at all, and have a single large
    contiguous array for each of our completion items.
    
    When drilling down in search, it makes sense to not requery any of the
    previous items. This is where that embedded GList really saves the
    day again. Instead of traversing the GPtrArray for all the matching items,
    we simply research the GList starting from our synthesized head. Therefore,
    each key press continually reduces N, the number of items to refilter.
    
    Upon each request to populate the completion set, we check to see if
    we can reuse the existing data set. This is done by looking backwards at
    the line and seeing if any character that could invalidate the set has
    been typed. If so, we go through the refilter step above.
    
    If we backspace, we won't match our linked list optimization, so we have
    to reset the linked list and refilter. This could be optimized a bit more,
    but we'll see if it is really an issue first. (To optimize it, avoid the
    rebuild of the linked list be fore rewalking the list to filter).
    
    This still doesn't sort items by their priority. We need to come up
    with a decent algorithm for determining that in a quick fashion, as
    we probably want to sort the whole list by that hueristic up front.
    
    Enjoy!

 plugins/clang/ide-clang-completion-item-private.h |   94 +++
 plugins/clang/ide-clang-completion-item.c         |   32 +-
 plugins/clang/ide-clang-completion-item.h         |    3 +-
 plugins/clang/ide-clang-completion-provider.c     |  661 ++++++++++++---------
 plugins/clang/ide-clang-completion-provider.h     |    5 +-
 5 files changed, 497 insertions(+), 298 deletions(-)
---
diff --git a/plugins/clang/ide-clang-completion-item-private.h 
b/plugins/clang/ide-clang-completion-item-private.h
new file mode 100644
index 0000000..b531291
--- /dev/null
+++ b/plugins/clang/ide-clang-completion-item-private.h
@@ -0,0 +1,94 @@
+/* ide-clang-completion-item-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_CLANG_COMPLETION_ITEM_PRIVATE_H
+#define IDE_CLANG_COMPLETION_ITEM_PRIVATE_H
+
+#include <clang-c/Index.h>
+#include <glib-object.h>
+#include <string.h>
+
+#include "ide-clang-completion-item.h"
+#include "ide-ref-ptr.h"
+
+G_BEGIN_DECLS
+
+struct _IdeClangCompletionItem
+{
+  GObject           parent_instance;
+
+  GList             link;
+
+  guint             index;
+  gint              typed_text_index;
+  guint             initialized : 1;
+
+  const gchar      *icon_name;
+  gchar            *brief_comment;
+  gchar            *markup;
+  IdeRefPtr        *results;
+  IdeSourceSnippet *snippet;
+  gchar            *typed_text;
+};
+
+static inline CXCompletionResult *
+ide_clang_completion_item_get_result (const IdeClangCompletionItem *self)
+{
+  return &((CXCodeCompleteResults *)ide_ref_ptr_get (self->results))->Results [self->index];
+}
+
+static inline gboolean
+ide_clang_completion_item_match (IdeClangCompletionItem *self,
+                                 const gchar            *lower_is_ascii)
+{
+  const gchar *haystack = self->typed_text;
+  const gchar *needle = lower_is_ascii;
+  const gchar *tmp;
+  char ch = *needle;
+
+  if (G_UNLIKELY (haystack == NULL))
+    haystack = ide_clang_completion_item_get_typed_text (self);
+
+  /*
+   * Optimization to require that we find the first character of
+   * needle within the first 4 characters of typed_text. Otherwise,
+   * we get way too many bogus results. It's okay to check past
+   * the trailing null byte since we know that malloc allocations
+   * are aligned to a pointer size (and therefore minimum allocation
+   * is 4 byte on 32-bit and 8 byte on 64-bit). If we hit a bogus
+   * condition, oh well, it's just one more compare below.
+   */
+  if (haystack [0] != ch && haystack [1] != ch && haystack [2] != ch && haystack [3] != ch)
+    return FALSE;
+
+  for (; *needle; needle++)
+    {
+      tmp = strchr (haystack, *needle);
+      if (tmp == NULL)
+        tmp = strchr (haystack, g_ascii_toupper (*needle));
+      if (tmp == NULL)
+        return FALSE;
+      haystack = tmp;
+    }
+
+  return TRUE;
+}
+
+G_END_DECLS
+
+#endif /* IDE_CLANG_COMPLETION_ITEM_PRIVATE_H */
diff --git a/plugins/clang/ide-clang-completion-item.c b/plugins/clang/ide-clang-completion-item.c
index 18196bb..e711e2d 100644
--- a/plugins/clang/ide-clang-completion-item.c
+++ b/plugins/clang/ide-clang-completion-item.c
@@ -22,28 +22,12 @@
 #include <glib/gi18n.h>
 
 #include "ide-clang-completion-item.h"
+#include "ide-clang-completion-item-private.h"
 #include "ide-debug.h"
 #include "ide-ref-ptr.h"
 #include "ide-source-snippet.h"
 #include "ide-source-snippet-chunk.h"
 
-
-struct _IdeClangCompletionItem
-{
-  GObject           parent_instance;
-
-  guint             index;
-  gint              typed_text_index;
-  guint             initialized : 1;
-
-  const gchar      *icon_name;
-  gchar            *brief_comment;
-  gchar            *markup;
-  IdeRefPtr        *results;
-  IdeSourceSnippet *snippet;
-  gchar            *typed_text;
-};
-
 static void completion_proposal_iface_init (GtkSourceCompletionProposalIface *);
 
 G_DEFINE_TYPE_WITH_CODE (IdeClangCompletionItem, ide_clang_completion_item, G_TYPE_OBJECT,
@@ -59,17 +43,6 @@ enum {
 
 static GParamSpec *gParamSpecs [LAST_PROP];
 
-static CXCompletionResult *
-ide_clang_completion_item_get_result (IdeClangCompletionItem *self)
-{
-  CXCodeCompleteResults *results;
-
-  g_assert (IDE_IS_CLANG_COMPLETION_ITEM (self));
-
-  results = ide_ref_ptr_get (self->results);
-  return &results->Results [self->index];
-}
-
 static void
 ide_clang_completion_item_lazy_init (IdeClangCompletionItem *self)
 {
@@ -409,6 +382,7 @@ ide_clang_completion_item_class_init (IdeClangCompletionItemClass *klass)
 static void
 ide_clang_completion_item_init (IdeClangCompletionItem *self)
 {
+  self->link.data = self;
   self->typed_text_index = -1;
 }
 
@@ -502,7 +476,7 @@ ide_clang_completion_item_get_typed_text (IdeClangCompletionItem *self)
        * This seems like an implausible result, but we are definitely
        * hitting it occasionally.
        */
-      return g_strdup ("");
+      return "";
     }
 
 #ifdef IDE_ENABLE_TRACE
diff --git a/plugins/clang/ide-clang-completion-item.h b/plugins/clang/ide-clang-completion-item.h
index 067f82a..4a555a9 100644
--- a/plugins/clang/ide-clang-completion-item.h
+++ b/plugins/clang/ide-clang-completion-item.h
@@ -27,8 +27,7 @@ G_BEGIN_DECLS
 
 #define IDE_TYPE_CLANG_COMPLETION_ITEM (ide_clang_completion_item_get_type())
 
-G_DECLARE_FINAL_TYPE (IdeClangCompletionItem, ide_clang_completion_item,
-                     IDE, CLANG_COMPLETION_ITEM, GObject)
+G_DECLARE_FINAL_TYPE (IdeClangCompletionItem, ide_clang_completion_item, IDE, CLANG_COMPLETION_ITEM, GObject)
 
 IdeSourceSnippet *ide_clang_completion_item_get_snippet       (IdeClangCompletionItem *self);
 const gchar      *ide_clang_completion_item_get_typed_text    (IdeClangCompletionItem *self);
diff --git a/plugins/clang/ide-clang-completion-provider.c b/plugins/clang/ide-clang-completion-provider.c
index 23ba020..6e9a7eb 100644
--- a/plugins/clang/ide-clang-completion-provider.c
+++ b/plugins/clang/ide-clang-completion-provider.c
@@ -16,277 +16,390 @@
  * along with this program.  If not, see <http://www.gnu.org/licenses/>.
  */
 
-#define G_LOG_DOMAIN "ide-clang-completion"
+#define G_LOG_DOMAIN "clang-completion-provider"
 
-#include <glib/gi18n.h>
+#include <string.h>
 
 #include "ide-buffer.h"
+#include "ide-completion-provider.h"
 #include "ide-clang-completion-item.h"
+#include "ide-clang-completion-item-private.h"
 #include "ide-clang-completion-provider.h"
 #include "ide-clang-service.h"
 #include "ide-clang-translation-unit.h"
-#include "ide-completion-provider.h"
-#include "ide-context.h"
-#include "ide-debug.h"
-#include "ide-file.h"
-#include "ide-source-snippet.h"
-#include "ide-source-view.h"
-
-#define MAX_COMPLETION_ITEMS 200
-
 
 struct _IdeClangCompletionProvider
 {
   IdeObject      parent_instance;
 
-  IdeSourceView *view;
-  GPtrArray     *last_results;
-  GtkWidget     *assistant;
   GSettings     *settings;
+  gchar         *last_line;
+  GPtrArray     *last_results;
+  gchar         *last_query;
+  /*
+   * As an optimization, the linked list for result nodes are
+   * embedded in the IdeClangCompletionItem structures and we
+   * do not allocate them. This is the pointer to the first item
+   * in the result set that matches our query. It is not allocated
+   * and do not tree to free it or perform g_list_*() operations
+   * upon it.
+   */
+  GList         *head;
+  /*
+   * We save a weak pointer to the view that performed the request
+   * so that we can push a snippet onto the view instead of inserting
+   * text into the buffer.
+   */
+  IdeSourceView *view;
 };
 
 typedef struct
 {
-  GCancellable                *cancellable;
-  GtkSourceCompletionProvider *provider;
-  GtkSourceCompletionContext  *context;
-  GFile                       *file;
-} AddProposalsState;
+  IdeClangCompletionProvider *self;
+  GtkSourceCompletionContext *context;
+  IdeFile *file;
+  GCancellable *cancellable;
+  gchar *line;
+  gchar *query;
+} IdeClangCompletionState;
 
-static void completion_provider_iface_init (GtkSourceCompletionProviderIface *);
+static void ide_clang_completion_provider_iface_init (GtkSourceCompletionProviderIface *iface);
 
 G_DEFINE_TYPE_EXTENDED (IdeClangCompletionProvider,
                         ide_clang_completion_provider,
                         IDE_TYPE_OBJECT,
                         0,
-                        G_IMPLEMENT_INTERFACE (GTK_SOURCE_TYPE_COMPLETION_PROVIDER, 
completion_provider_iface_init)
+                        G_IMPLEMENT_INTERFACE (GTK_SOURCE_TYPE_COMPLETION_PROVIDER,
+                                               ide_clang_completion_provider_iface_init)
                         G_IMPLEMENT_INTERFACE (IDE_TYPE_COMPLETION_PROVIDER, NULL))
 
 static void
-add_proposals_state_free (AddProposalsState *state)
+ide_clang_completion_state_free (IdeClangCompletionState *state)
 {
-  g_signal_handlers_disconnect_by_func (state->context,
-                                        G_CALLBACK (g_cancellable_cancel),
-                                        state->cancellable);
-
-  g_clear_object (&state->provider);
+  g_clear_object (&state->self);
+  g_clear_object (&state->cancellable);
   g_clear_object (&state->context);
   g_clear_object (&state->file);
-  g_clear_object (&state->cancellable);
-  g_free (state);
+  g_clear_pointer (&state->line, g_free);
+  g_clear_pointer (&state->query, g_free);
+  g_slice_free (IdeClangCompletionState, state);
 }
 
-static gboolean
-stop_on_predicate (gunichar ch,
-                   gpointer data)
+static gchar *
+ide_clang_completion_provider_get_name (GtkSourceCompletionProvider *provider)
 {
-  switch (ch)
-    {
-    case '_':
-      return FALSE;
-
-    case ')':
-    case '(':
-    case '&':
-    case '*':
-    case '{':
-    case '}':
-    case ' ':
-    case '\t':
-    case '[':
-    case ']':
-    case '=':
-    case '"':
-    case '\'':
-      return TRUE;
-
-    default:
-      return !g_unichar_isalnum (ch);
-    }
+  return g_strdup ("Clang");
 }
 
-static gboolean
-matches (IdeClangCompletionItem *item,
-         const gchar            *word)
+static gint
+ide_clang_completion_provider_get_priority (GtkSourceCompletionProvider *provider)
 {
-  const gchar *typed_text;
-
-  typed_text = ide_clang_completion_item_get_typed_text (item);
-  return !!strstr (typed_text, word);
+  return IDE_CLANG_COMPLETION_PROVIDER_PRIORITY;
 }
 
-static gchar *
-get_word (const GtkTextIter *location)
+static gboolean
+ide_clang_completion_provider_match (GtkSourceCompletionProvider *provider,
+                                     GtkSourceCompletionContext  *context)
 {
-  GtkTextIter iter = *location;
+  IdeClangCompletionProvider *self = (IdeClangCompletionProvider *)provider;
+  GtkSourceCompletionActivation activation;
   GtkTextBuffer *buffer;
-  GtkTextIter end;
+  IdeFile *file;
+  GtkTextIter iter;
+
+  g_return_val_if_fail (IDE_IS_CLANG_COMPLETION_PROVIDER (self), FALSE);
+  g_return_val_if_fail (GTK_SOURCE_IS_COMPLETION_CONTEXT (context), FALSE);
+
+  if (!gtk_source_completion_context_get_iter (context, &iter))
+    return FALSE;
 
-  end = iter;
   buffer = gtk_text_iter_get_buffer (&iter);
+  if (!IDE_IS_BUFFER (buffer) ||
+      !(file = ide_buffer_get_file (IDE_BUFFER (buffer))) ||
+      ide_file_get_is_temporary (file))
+    return FALSE;
+
+  activation = gtk_source_completion_context_get_activation (context);
 
-  if (!gtk_text_iter_backward_find_char (&iter, stop_on_predicate, NULL, NULL))
-    return gtk_text_buffer_get_text (buffer, &iter, &end, TRUE);
+  if (activation == GTK_SOURCE_COMPLETION_ACTIVATION_INTERACTIVE)
+    {
+      if (gtk_text_iter_starts_line (&iter) ||
+          !gtk_text_iter_backward_char (&iter) ||
+          g_unichar_isspace (gtk_text_iter_get_char (&iter)))
+        return FALSE;
+    }
 
-  gtk_text_iter_forward_char (&iter);
+  if (!g_settings_get_boolean (self->settings, "clang-autocompletion"))
+    return FALSE;
 
-  return gtk_text_iter_get_text (&iter, &end);
+  return TRUE;
 }
 
-static GList *
-filter_list (GPtrArray   *ar,
-             const gchar *word)
+static gboolean
+ide_clang_completion_provider_can_replay (IdeClangCompletionProvider *self,
+                                          const gchar                *line)
 {
-  g_autoptr(GPtrArray) matched = NULL;
-  GList *ret = NULL;
-  gsize i;
+  const gchar *suffix;
 
-  matched = g_ptr_array_new ();
+  g_assert (IDE_IS_CLANG_COMPLETION_PROVIDER (self));
 
-  for (i = 0; i < ar->len; i++)
-    {
-      IdeClangCompletionItem *item;
+  if (self->last_results == NULL)
+    { g_print (">>>> %s\n", G_STRLOC); return FALSE; }
 
-      item = g_ptr_array_index (ar, i);
-      if (matches (item, word))
-        {
-          g_ptr_array_add (matched, item);
-
-          /*
-           * FIXME:
-           *
-           * We should be a bit more intelligent about which items we accept.
-           * The results don't come to us in "most important" order.
-           */
-          if (G_UNLIKELY (matched->len == MAX_COMPLETION_ITEMS))
-            break;
-        }
-    }
+  if (line == NULL || self->last_line == NULL)
+    { g_print (">>>> %s\n", G_STRLOC); return FALSE; }
 
-  for (i = 0; i < matched->len; i++)
-    ret = g_list_prepend (ret, g_ptr_array_index (matched, i));
+  if (!g_str_has_prefix (line, self->last_line))
+    { g_print (">>>> %s\n", G_STRLOC); return FALSE; }
 
-  return ret;
+  suffix = line + strlen (self->last_line);
+
+  for (; *suffix; suffix = g_utf8_next_char (suffix))
+    {
+      gunichar ch = g_utf8_get_char (suffix);
+      if (!g_unichar_isalnum (ch) && (ch != '_'))
+        { g_print (">>>> %s\n", G_STRLOC); return FALSE; }
+    }
+
+  return TRUE;
 }
 
 static void
-ide_clang_completion_provider_finalize (GObject *object)
+ide_clang_completion_provider_save_results (IdeClangCompletionProvider *self,
+                                            GPtrArray                  *results,
+                                            const gchar                *line,
+                                            const gchar                *query)
 {
-  IdeClangCompletionProvider *self = (IdeClangCompletionProvider *)object;
+  IDE_ENTRY;
+
+  g_assert (IDE_IS_CLANG_COMPLETION_PROVIDER (self));
 
   g_clear_pointer (&self->last_results, g_ptr_array_unref);
-  g_clear_object (&self->settings);
+  g_clear_pointer (&self->last_line, g_free);
+  g_clear_pointer (&self->last_query, g_free);
+  self->head = NULL;
 
-  G_OBJECT_CLASS (ide_clang_completion_provider_parent_class)->finalize (object);
+  if (results != NULL)
+    {
+      self->last_line = g_strdup (line);
+      self->last_query = g_strdup (query);
+      self->last_results = g_ptr_array_ref (results);
+      if (results->len > 0)
+        {
+          IdeClangCompletionItem *head = g_ptr_array_index (results, 0);
+          self->head = &head->link;
+        }
+    }
+
+  IDE_EXIT;
 }
 
 static void
-ide_clang_completion_provider_class_init (IdeClangCompletionProviderClass *klass)
+ide_clang_completion_provider_update_links (IdeClangCompletionProvider *self,
+                                            GPtrArray                  *results)
 {
-  GObjectClass *object_class = G_OBJECT_CLASS (klass);
+  IdeClangCompletionItem *item;
+  IdeClangCompletionItem *next;
+  IdeClangCompletionItem *prev;
+  guint i;
 
-  object_class->finalize = ide_clang_completion_provider_finalize;
+  g_assert (IDE_IS_CLANG_COMPLETION_PROVIDER (self));
+  g_assert (results != NULL);
+
+  if (results->len == 0)
+    {
+      self->head = NULL;
+      return;
+    }
+
+  /* Unrolling loops for the gentoo crowd */
+
+  item = g_ptr_array_index (results, 0);
+  item->link.prev = NULL;
+  item->link.next = (results->len == 1) ? NULL : &((IdeClangCompletionItem*)g_ptr_array_index (results, 
1))->link;
+
+  self->head = &item->link;
+
+  prev = item;
+
+  for (i = 1; i < (results->len - 1); i++)
+    {
+      item = g_ptr_array_index (results, i);
+      next = g_ptr_array_index (results, i + 1);
+
+      item->link.prev = &prev->link;
+      item->link.next = &next->link;
+
+      prev = item;
+    }
+
+  if (results->len > 1)
+    {
+      item = g_ptr_array_index (results, results->len - 1);
+      item->link.prev = &((IdeClangCompletionItem*)g_ptr_array_index (results, results->len-2))->link;
+      item->link.next = NULL;
+    }
 }
 
 static void
-ide_clang_completion_provider_init (IdeClangCompletionProvider *self)
+ide_clang_completion_provider_refilter (IdeClangCompletionProvider *self,
+                                        GPtrArray                  *results,
+                                        const gchar                *query)
 {
-  self->settings = g_settings_new ("org.gnome.builder.code-insight");
-}
+  g_autofree gchar *lower = NULL;
 
-static gchar *
-ide_clang_completion_provider_get_name (GtkSourceCompletionProvider *provider)
-{
-  return g_strdup (_("Clang"));
+  g_assert (IDE_IS_CLANG_COMPLETION_PROVIDER (self));
+  g_assert (results != NULL);
+  g_assert (results->len > 0);
+  g_assert (query != NULL);
+
+  /*
+   * By traversing the linked list nodes instead of the array, we allow
+   * ourselves to avoid rechecking items we already know filtered.
+   * We do need to be mindful of this in case the user backspaced
+   * and our list is no longer a continual "deep dive" of matched items.
+   */
+  if ((self->last_query != NULL) && g_str_has_prefix (query, self->last_query))
+    ide_clang_completion_provider_update_links (self, results);
+
+  lower = g_utf8_strdown (query, -1);
+
+  if (!g_str_is_ascii (lower))
+    {
+      g_warning ("Item filtering requires ascii input.");
+      return;
+    }
+
+  for (GList *iter = self->head; iter; iter = iter->next)
+    {
+      IdeClangCompletionItem *item = iter->data;
+
+      if (!ide_clang_completion_item_match (item, lower))
+        {
+          if (iter->prev != NULL)
+            iter->prev->next = iter->next;
+          else
+            self->head = iter->next;
+
+          if (iter->next != NULL)
+            iter->next->prev = iter->prev;
+        }
+    }
+
+  g_free (self->last_query);
+  self->last_query = g_strdup (query);
 }
 
 static void
-ide_clang_completion_provider_complete_cb (GObject      *object,
-                                           GAsyncResult *result,
-                                           gpointer      user_data)
+ide_clang_completion_provider_code_complete_cb (GObject      *object,
+                                                GAsyncResult *result,
+                                                gpointer      user_data)
 {
-  IdeClangTranslationUnit *tu = (IdeClangTranslationUnit *)object;
-  IdeClangCompletionProvider *self;
-  AddProposalsState *state = user_data;
-  g_autofree gchar *word = NULL;
-  g_autoptr(GPtrArray) ar = NULL;
-  GtkTextIter iter;
+  IdeClangTranslationUnit *unit = (IdeClangTranslationUnit *)object;
+  IdeClangCompletionState *state = user_data;
+  g_autoptr(GPtrArray) results = NULL;
   GError *error = NULL;
-  GList *filtered = NULL;
 
-  self = (IdeClangCompletionProvider *)state->provider;
+  IDE_ENTRY;
 
-  ar = ide_clang_translation_unit_code_complete_finish (tu, result, &error);
+  g_assert (IDE_IS_CLANG_TRANSLATION_UNIT (unit));
+  g_assert (state != NULL);
+  g_assert (IDE_IS_CLANG_COMPLETION_PROVIDER (state->self));
+  g_assert (G_IS_CANCELLABLE (state->cancellable));
+  g_assert (IDE_IS_FILE (state->file));
+  g_assert (GTK_SOURCE_IS_COMPLETION_CONTEXT (state->context));
 
-  if (!ar)
+  if (!(results = ide_clang_translation_unit_code_complete_finish (unit, result, &error)))
     {
-      g_warning ("%s", error->message);
-      g_clear_error (&error);
-      goto failure;
+      g_debug ("%s", error->message);
+      if (!g_cancellable_is_cancelled (state->cancellable))
+        gtk_source_completion_context_add_proposals (state->context,
+                                                     GTK_SOURCE_COMPLETION_PROVIDER (state->self),
+                                                     NULL, TRUE);
+      ide_clang_completion_state_free (state);
+      IDE_EXIT;
     }
 
-  if (self->last_results != NULL)
-    g_ptr_array_unref (self->last_results);
-  self->last_results = g_ptr_array_ref (ar);
-
-  gtk_source_completion_context_get_iter (state->context, &iter);
-  word = get_word (&iter);
-
-  IDE_TRACE_MSG ("Current word: %s", word ?: "(null)");
+  ide_clang_completion_provider_save_results (state->self, results, state->line, state->query);
+  ide_clang_completion_provider_update_links (state->self, results);
 
-  if (word)
-    filtered = filter_list (ar, word);
-
-failure:
   if (!g_cancellable_is_cancelled (state->cancellable))
-    gtk_source_completion_context_add_proposals (state->context, state->provider, filtered, TRUE);
+    {
+      if (results->len > 0)
+        {
+          ide_clang_completion_provider_refilter (state->self, results, state->query);
+          gtk_source_completion_context_add_proposals (state->context,
+                                                       GTK_SOURCE_COMPLETION_PROVIDER (state->self),
+                                                       state->self->head, TRUE);
+        }
+      else
+        {
+          gtk_source_completion_context_add_proposals (state->context,
+                                                       GTK_SOURCE_COMPLETION_PROVIDER (state->self),
+                                                       NULL, TRUE);
+        }
+    }
 
-  g_list_free (filtered);
-  add_proposals_state_free (state);
+  ide_clang_completion_state_free (state);
+
+  IDE_EXIT;
 }
 
 static void
-ide_clang_completion_provider_tu_cb (GObject      *object,
-                                     GAsyncResult *result,
-                                     gpointer      user_data)
+ide_clang_completion_provider_get_translation_unit_cb (GObject      *object,
+                                                       GAsyncResult *result,
+                                                       gpointer      user_data)
 {
+  g_autoptr(IdeClangTranslationUnit) unit = NULL;
   IdeClangService *service = (IdeClangService *)object;
-  g_autoptr(IdeClangTranslationUnit) tu = NULL;
-  AddProposalsState *state = user_data;
-  GError *error = NULL;
+  IdeClangCompletionState *state = user_data;
   GtkTextIter iter;
+  GError *error = NULL;
+
+  IDE_ENTRY;
 
   g_assert (IDE_IS_CLANG_SERVICE (service));
-  g_assert (state);
-  g_assert (IDE_IS_CLANG_COMPLETION_PROVIDER (state->provider));
+  g_assert (state != NULL);
+  g_assert (IDE_IS_CLANG_COMPLETION_PROVIDER (state->self));
+  g_assert (G_IS_CANCELLABLE (state->cancellable));
+  g_assert (IDE_IS_FILE (state->file));
   g_assert (GTK_SOURCE_IS_COMPLETION_CONTEXT (state->context));
-  g_assert (G_IS_FILE (state->file));
 
-  tu = ide_clang_service_get_translation_unit_finish (service, result, &error);
+  if (!(unit = ide_clang_service_get_translation_unit_finish (service, result, &error)))
+    {
+      g_debug ("%s", error->message);
+      if (!g_cancellable_is_cancelled (state->cancellable))
+        gtk_source_completion_context_add_proposals (state->context,
+                                                     GTK_SOURCE_COMPLETION_PROVIDER (state->self),
+                                                     NULL, TRUE);
+      ide_clang_completion_state_free (state);
+      IDE_EXIT;
+    }
 
-  if (!tu)
+  /*
+   * It's like we are racing with our future self, which coallesced the
+   * compile request into a single delayed query. Use the cancellable
+   * to detect if we were cancelled and short-circuit early.
+   */
+  if (g_cancellable_is_cancelled (state->cancellable))
     {
-      g_warning ("%s", error->message);
-      g_clear_error (&error);
-      goto cleanup;
+      gtk_source_completion_context_add_proposals (state->context,
+                                                   GTK_SOURCE_COMPLETION_PROVIDER (state->self),
+                                                   NULL, TRUE);
+      ide_clang_completion_state_free (state);
+      IDE_EXIT;
     }
 
-  if (!gtk_source_completion_context_get_iter (state->context, &iter))
-    goto cleanup;
+  gtk_source_completion_context_get_iter (state->context, &iter);
 
-  ide_clang_translation_unit_code_complete_async (tu,
-                                                  state->file,
+  ide_clang_translation_unit_code_complete_async (unit,
+                                                  ide_file_get_file (state->file),
                                                   &iter,
                                                   NULL,
-                                                  ide_clang_completion_provider_complete_cb,
+                                                  ide_clang_completion_provider_code_complete_cb,
                                                   state);
 
-  return;
-
-cleanup:
-  if (!g_cancellable_is_cancelled (state->cancellable))
-    gtk_source_completion_context_add_proposals (state->context, state->provider, NULL, TRUE);
-  add_proposals_state_free (state);
+  IDE_EXIT;
 }
 
 static void
@@ -294,77 +407,118 @@ ide_clang_completion_provider_populate (GtkSourceCompletionProvider *provider,
                                         GtkSourceCompletionContext  *context)
 {
   IdeClangCompletionProvider *self = (IdeClangCompletionProvider *)provider;
-  AddProposalsState *state;
-  IdeClangService *service;
-  GtkSourceCompletion *completion;
-  g_autofree gchar *word = NULL;
-  GtkSourceView *view;
+  IdeClangCompletionState *state;
+  g_autoptr(GtkSourceCompletion) completion = NULL;
+  g_autofree gchar *line = NULL;
+  g_autofree gchar *prefix = NULL;
+  GtkTextIter stop;
+  gunichar ch;
   GtkTextBuffer *buffer;
-  IdeContext *icontext;
+  IdeClangService *service;
   GtkTextIter iter;
-  IdeFile *file;
+  GtkTextIter begin;
 
-  g_assert (IDE_IS_CLANG_COMPLETION_PROVIDER (self));
+  IDE_ENTRY;
 
-  if (!gtk_source_completion_context_get_iter (context, &iter))
-    goto failure;
+  g_return_if_fail (IDE_IS_CLANG_COMPLETION_PROVIDER (self));
+  g_return_if_fail (GTK_SOURCE_IS_COMPLETION_CONTEXT (context));
 
-  word = get_word (&iter);
-  if (!word || !word [0] || !word [1])
-    goto failure;
+  if (!gtk_source_completion_context_get_iter (context, &iter))
+    {
+      gtk_source_completion_context_add_proposals (context, provider, NULL, TRUE);
+      return;
+    }
 
   buffer = gtk_text_iter_get_buffer (&iter);
-  g_assert (IDE_IS_BUFFER (buffer));
 
-  /* stash the view for later */
-  if (G_UNLIKELY (!self->view))
+  /* Get the line text up to the insertion mark */
+  begin = iter;
+  gtk_text_iter_set_line_offset (&begin, 0);
+  line = gtk_text_iter_get_slice (&begin, &iter);
+
+  /* Move to the just inserted character */
+  stop = iter;
+  if (!gtk_text_iter_starts_line (&stop))
+    gtk_text_iter_backward_char (&stop);
+
+  /*
+   * Walk backwards to locate the first character after a stop character.
+   * A stop character is anything that can't go in a function/type.
+   */
+  while (!gtk_text_iter_starts_line (&stop) &&
+         (ch = gtk_text_iter_get_char (&stop)) &&
+         (g_unichar_isalnum (ch) || (ch == '_')) &&
+         gtk_text_iter_backward_char (&stop))
     {
-      g_object_get (context, "completion", &completion, NULL);
-      g_assert (GTK_SOURCE_IS_COMPLETION (completion));
-      view = gtk_source_completion_get_view (completion);
-      g_assert (IDE_IS_SOURCE_VIEW (view));
-      g_assert ((self->view == NULL) || (self->view == (IdeSourceView *)view));
-      self->view = IDE_SOURCE_VIEW (view);
-      g_clear_object (&completion);
+      /* Do nothing */
     }
 
-  file = ide_buffer_get_file (IDE_BUFFER (buffer));
-  if (file == NULL)
-    goto failure;
+  ch = gtk_text_iter_get_char (&stop);
 
-  g_assert (IDE_IS_FILE (file));
+  /* Move forward if we moved past the last matching char */
+  if (!g_unichar_isalnum (ch) &&
+      (ch != '_') &&
+      (gtk_text_iter_compare (&stop, &iter) < 0))
+    gtk_text_iter_forward_char (&stop);
 
-  icontext = ide_buffer_get_context (IDE_BUFFER (buffer));
-  if (icontext == NULL)
-    goto failure;
+  prefix = g_strstrip (gtk_text_iter_get_slice (&stop, &iter));
 
-  g_assert (IDE_IS_CONTEXT (icontext));
+  g_print ("RESULTS: %p (%d)\n", self->last_results, self->last_results? self->last_results->len : 0);
+  g_print ("  last_line = %s\n", self->last_line ?: "<null>");
+  g_print ("  last_query = %s\n", self->last_query ?: "<null>");
 
-  service = ide_context_get_service_typed (icontext, IDE_TYPE_CLANG_SERVICE);
-  g_assert (IDE_IS_CLANG_SERVICE (service));
+  /*
+   * We might be able to reuse the results from our previous query if
+   * the buffer is sufficiently similar. If so, possibly just rearrange
+   * some things and redisplay those results.
+   */
+  if (ide_clang_completion_provider_can_replay (self, line))
+    {
+      IDE_PROBE;
+
+      /*
+       * Filter the items that no longer match our query.
+       * We save a little state so that we can optimize further
+       * passes of this operation by traversing the already filtered
+       * linked list instead of all items.
+       */
+      ide_clang_completion_provider_refilter (self, self->last_results, prefix);
+      gtk_source_completion_context_add_proposals (context, provider, self->head, TRUE);
+
+      IDE_EXIT;
+    }
 
-  state = g_new0 (AddProposalsState, 1);
-  state->provider = g_object_ref (provider);
+  /* Save the view so we can push a snippet later */
+  g_object_get (context, "completion", &completion, NULL);
+  self->view = IDE_SOURCE_VIEW (gtk_source_completion_get_view (completion));
+
+  ide_buffer_sync_to_unsaved_files (IDE_BUFFER (buffer));
+
+  service = ide_context_get_service_typed (ide_object_get_context (IDE_OBJECT (self)),
+                                           IDE_TYPE_CLANG_SERVICE);
+
+  state = g_slice_new0 (IdeClangCompletionState);
+  state->self = g_object_ref (self);
   state->context = g_object_ref (context);
-  state->file = g_object_ref (ide_file_get_file (file));
+  state->file = g_object_ref (ide_buffer_get_file (IDE_BUFFER (buffer)));
   state->cancellable = g_cancellable_new ();
+  state->query = prefix, prefix = NULL;
+  state->line = line, line = NULL;
 
-  g_signal_connect_swapped (context,
-                            "cancelled",
-                            G_CALLBACK (g_cancellable_cancel),
-                            state->cancellable);
+  g_signal_connect_object (context,
+                           "cancelled",
+                           G_CALLBACK (g_cancellable_cancel),
+                           state->cancellable,
+                           G_CONNECT_SWAPPED);
 
   ide_clang_service_get_translation_unit_async (service,
-                                                file,
+                                                state->file,
                                                 0,
-                                                state->cancellable,
-                                                ide_clang_completion_provider_tu_cb,
+                                                NULL,
+                                                ide_clang_completion_provider_get_translation_unit_cb,
                                                 state);
 
-  return;
-
-failure:
-  gtk_source_completion_context_add_proposals (context, provider, NULL, TRUE);
+  IDE_EXIT;
 }
 
 static gboolean
@@ -396,7 +550,8 @@ get_start_iter (GtkSourceCompletionProvider *provider,
 
       while (*text)
         {
-          if (gtk_text_iter_forward_search (&begin, text, GTK_TEXT_SEARCH_TEXT_ONLY, &match_start, 
&match_end, &end))
+          if (gtk_text_iter_forward_search (&begin, text, GTK_TEXT_SEARCH_TEXT_ONLY,
+                                            &match_start, &match_end, &end))
             {
               *iter = match_start;
               return TRUE;
@@ -456,66 +611,42 @@ ide_clang_completion_provider_activate_proposal (GtkSourceCompletionProvider *pr
   IDE_RETURN (TRUE);
 }
 
-static gint
-ide_clang_completion_provider_get_interactive_delay (GtkSourceCompletionProvider *provider)
+static void
+ide_clang_completion_provider_finalize (GObject *object)
 {
-  return -1;
-}
+  IdeClangCompletionProvider *self = (IdeClangCompletionProvider *)object;
 
-static gint
-ide_clang_completion_provider_get_priority (GtkSourceCompletionProvider *provider)
-{
-  return IDE_CLANG_COMPLETION_PROVIDER_PRIORITY;
+  g_clear_pointer (&self->last_results, g_ptr_array_unref);
+  g_clear_pointer (&self->last_line, g_free);
+  g_clear_pointer (&self->last_query, g_free);
+  g_clear_object (&self->settings);
+
+  G_OBJECT_CLASS (ide_clang_completion_provider_parent_class)->finalize (object);
 }
 
-static gboolean
-ide_clang_completion_provider_match (GtkSourceCompletionProvider *provider,
-                                     GtkSourceCompletionContext  *context)
+static void
+ide_clang_completion_provider_class_init (IdeClangCompletionProviderClass *klass)
 {
-  IdeClangCompletionProvider *self = (IdeClangCompletionProvider *)provider;
-  GtkSourceCompletionActivation activation;
-  GtkTextIter iter;
-  GtkTextBuffer *buffer;
-  IdeFile *file;
-
-  if (!g_settings_get_boolean (self->settings, "clang-autocompletion"))
-    return FALSE;
-
-  if (gtk_source_completion_context_get_iter (context, &iter))
-    return FALSE;
-
-  buffer = gtk_text_iter_get_buffer (&iter);
-  if (!IDE_IS_BUFFER (buffer))
-    return FALSE;
-
-  file = ide_buffer_get_file (IDE_BUFFER (buffer));
-  if (file == NULL || ide_file_get_is_temporary (file))
-    return FALSE;
-
-  activation = gtk_source_completion_context_get_activation (context);
-
-  /*
-   * Do not show activation interactively if we are currently on a space.
-   */
-  if (activation == GTK_SOURCE_COMPLETION_ACTIVATION_INTERACTIVE)
-    {
-      if (gtk_text_iter_starts_line (&iter) ||
-          !gtk_text_iter_backward_char (&iter) ||
-          g_unichar_isspace (gtk_text_iter_get_char (&iter)))
-        return FALSE;
-    }
+  GObjectClass *object_class = G_OBJECT_CLASS (klass);
 
-  return TRUE;
+  object_class->finalize = ide_clang_completion_provider_finalize;
 }
 
 static void
-completion_provider_iface_init (GtkSourceCompletionProviderIface *iface)
+ide_clang_completion_provider_iface_init (GtkSourceCompletionProviderIface *iface)
 {
   iface->activate_proposal = ide_clang_completion_provider_activate_proposal;
-  iface->get_interactive_delay = ide_clang_completion_provider_get_interactive_delay;
   iface->get_name = ide_clang_completion_provider_get_name;
-  iface->get_start_iter = ide_clang_completion_provider_get_start_iter;
-  iface->populate = ide_clang_completion_provider_populate;
   iface->get_priority = ide_clang_completion_provider_get_priority;
+  iface->get_start_iter = ide_clang_completion_provider_get_start_iter;
   iface->match = ide_clang_completion_provider_match;
+  iface->populate = ide_clang_completion_provider_populate;
+}
+
+static void
+ide_clang_completion_provider_init (IdeClangCompletionProvider *self)
+{
+  IDE_ENTRY;
+  self->settings = g_settings_new ("org.gnome.builder.code-insight");
+  IDE_EXIT;
 }
diff --git a/plugins/clang/ide-clang-completion-provider.h b/plugins/clang/ide-clang-completion-provider.h
index 85e4d0a..e50a60e 100644
--- a/plugins/clang/ide-clang-completion-provider.h
+++ b/plugins/clang/ide-clang-completion-provider.h
@@ -19,7 +19,9 @@
 #ifndef IDE_CLANG_COMPLETION_PROVIDER_H
 #define IDE_CLANG_COMPLETION_PROVIDER_H
 
+#include <glib-object.h>
 #include <gtksourceview/gtksourcecompletionprovider.h>
+#include <ide.h>
 
 G_BEGIN_DECLS
 
@@ -27,8 +29,7 @@ G_BEGIN_DECLS
 
 #define IDE_TYPE_CLANG_COMPLETION_PROVIDER (ide_clang_completion_provider_get_type())
 
-G_DECLARE_FINAL_TYPE (IdeClangCompletionProvider, ide_clang_completion_provider,
-                      IDE, CLANG_COMPLETION_PROVIDER, IdeObject)
+G_DECLARE_FINAL_TYPE (IdeClangCompletionProvider, ide_clang_completion_provider, IDE, 
CLANG_COMPLETION_PROVIDER, IdeObject)
 
 G_END_DECLS