[gnome-builder] langserv-symbol-tree: use node range for tree building

[Christian Hergert <chergert src gnome org>]

commit 7d6ae63bd31f5aa3e5fe7d7b59c0b100d7099357
Author: Christian Hergert <chergert redhat com>
Date:   Tue Nov 22 18:07:33 2016 -0800

    langserv-symbol-tree: use node range for tree building
    
    If the Language Server provides accurate information for the range of
    the symbol nodes, we can create an n-ary tree structure for the nodes.
    
    This is done by checking if a node contains, in entirety, a child node.
    If we discover a node that contains the other node, we rotate the tree
    around that replacement.
    
    Currently, rls does not support this due to giving us source ranges that
    map to the word/syntax of the document rather than its semantic range. This
    is mostly okay because its no worse than things were today where we have
    inconsistent "parentName" coming from symbol nodes.

 libide/langserv/ide-langserv-symbol-node-private.h |    7 ++
 libide/langserv/ide-langserv-symbol-node.c         |   50 ++++++++--
 libide/langserv/ide-langserv-symbol-node.h         |    2 +
 libide/langserv/ide-langserv-symbol-tree.c         |  112 ++++++++++++--------
 4 files changed, 120 insertions(+), 51 deletions(-)
---
diff --git a/libide/langserv/ide-langserv-symbol-node-private.h 
b/libide/langserv/ide-langserv-symbol-node-private.h
index 8482672..e66c698 100644
--- a/libide/langserv/ide-langserv-symbol-node-private.h
+++ b/libide/langserv/ide-langserv-symbol-node-private.h
@@ -23,6 +23,13 @@
 
 G_BEGIN_DECLS
 
+struct _IdeLangservSymbolNode
+{
+  IdeSymbolNode parent_instance;
+  GNode         gnode;
+};
+
+
 IdeLangservSymbolNode *ide_langserv_symbol_node_new (GFile       *file,
                                                      const gchar *name,
                                                      const gchar *parent_name,
diff --git a/libide/langserv/ide-langserv-symbol-node.c b/libide/langserv/ide-langserv-symbol-node.c
index dd43a21..6a7fe61 100644
--- a/libide/langserv/ide-langserv-symbol-node.c
+++ b/libide/langserv/ide-langserv-symbol-node.c
@@ -23,24 +23,37 @@
 #include "diagnostics/ide-source-location.h"
 #include "files/ide-file.h"
 #include "langserv/ide-langserv-symbol-node.h"
+#include "langserv/ide-langserv-symbol-node-private.h"
+
+typedef struct
+{
+  guint line;
+  guint column;
+} Location;
 
 typedef struct
 {
   GFile *file;
   gchar *parent_name;
   IdeSymbolKind kind;
-  struct {
-    guint line;
-    guint column;
-  } begin, end;
+  Location begin;
+  Location end;
 } IdeLangservSymbolNodePrivate;
 
-struct _IdeLangservSymbolNode
+G_DEFINE_TYPE_WITH_PRIVATE (IdeLangservSymbolNode, ide_langserv_symbol_node, IDE_TYPE_SYMBOL_NODE)
+
+static inline gint
+location_compare (const Location *a,
+                  const Location *b)
 {
-  IdeSymbolNode parent_instance;
-};
+  gint ret;
 
-G_DEFINE_TYPE_WITH_PRIVATE (IdeLangservSymbolNode, ide_langserv_symbol_node, IDE_TYPE_SYMBOL_NODE)
+  ret = (gint)a->line - (gint)b->line;
+  if (ret == 0)
+    ret = (gint)a->column - (gint)b->column;
+
+  return ret;
+}
 
 static void
 ide_langserv_symbol_node_get_location_async (IdeSymbolNode       *node,
@@ -113,6 +126,7 @@ ide_langserv_symbol_node_class_init (IdeLangservSymbolNodeClass *klass)
 static void
 ide_langserv_symbol_node_init (IdeLangservSymbolNode *self)
 {
+  self->gnode.data = self;
 }
 
 IdeLangservSymbolNode *
@@ -179,3 +193,23 @@ ide_langserv_symbol_node_get_parent_name (IdeLangservSymbolNode *self)
 
   return priv->parent_name;
 }
+
+gboolean
+ide_langserv_symbol_node_is_parent_of (IdeLangservSymbolNode *self,
+                                       IdeLangservSymbolNode *other)
+{
+  IdeLangservSymbolNodePrivate *priv = ide_langserv_symbol_node_get_instance_private (self);
+  IdeLangservSymbolNodePrivate *opriv = ide_langserv_symbol_node_get_instance_private (other);
+
+  g_return_val_if_fail (IDE_IS_LANGSERV_SYMBOL_NODE (self), FALSE);
+  g_return_val_if_fail (IDE_IS_LANGSERV_SYMBOL_NODE (other), FALSE);
+
+  g_print ("Compare\n");
+  g_print ("  self[begin] = %d %d\n", priv->begin.line, priv->begin.column);
+  g_print ("  self[end]   = %d %d\n", priv->end.line, priv->end.column);
+  g_print ("  other[begin] = %d %d\n", opriv->begin.line, opriv->begin.column);
+  g_print ("  other[end]   = %d %d\n", opriv->end.line, opriv->end.column);
+
+  return (location_compare (&priv->begin, &opriv->begin) <= 0) &&
+         (location_compare (&priv->end, &opriv->end) >= 0);
+}
diff --git a/libide/langserv/ide-langserv-symbol-node.h b/libide/langserv/ide-langserv-symbol-node.h
index 5501e9d..fda4ebc 100644
--- a/libide/langserv/ide-langserv-symbol-node.h
+++ b/libide/langserv/ide-langserv-symbol-node.h
@@ -28,6 +28,8 @@ G_BEGIN_DECLS
 G_DECLARE_FINAL_TYPE (IdeLangservSymbolNode, ide_langserv_symbol_node, IDE, LANGSERV_SYMBOL_NODE, 
IdeSymbolNode)
 
 const gchar *ide_langserv_symbol_node_get_parent_name (IdeLangservSymbolNode *self);
+gboolean     ide_langserv_symbol_node_is_parent_of    (IdeLangservSymbolNode *self,
+                                                       IdeLangservSymbolNode *other);
 
 G_END_DECLS
 
diff --git a/libide/langserv/ide-langserv-symbol-tree.c b/libide/langserv/ide-langserv-symbol-tree.c
index 1557f3c..269d28c 100644
--- a/libide/langserv/ide-langserv-symbol-tree.c
+++ b/libide/langserv/ide-langserv-symbol-tree.c
@@ -19,20 +19,18 @@
 #define G_LOG_DOMAIN "ide-langserv-symbol-tree"
 
 #include "ide-langserv-symbol-node.h"
+#include "ide-langserv-symbol-node-private.h"
 #include "ide-langserv-symbol-tree.h"
 
 typedef struct
 {
   GPtrArray *symbols;
+  GNode      root;
 } IdeLangservSymbolTreePrivate;
 
-struct _IdeLangservSymbolTree
-{
-  GObject parent_instance;
-};
-
 static void symbol_tree_iface_init (IdeSymbolTreeInterface *iface);
 
+struct _IdeLangservSymbolTree { GObject object; };
 G_DEFINE_TYPE_WITH_CODE (IdeLangservSymbolTree, ide_langserv_symbol_tree, G_TYPE_OBJECT,
                          G_ADD_PRIVATE (IdeLangservSymbolTree)
                          G_IMPLEMENT_INTERFACE (IDE_TYPE_SYMBOL_TREE, symbol_tree_iface_init))
@@ -43,31 +41,14 @@ ide_langserv_symbol_tree_get_n_children (IdeSymbolTree *tree,
 {
   IdeLangservSymbolTree *self = (IdeLangservSymbolTree *)tree;
   IdeLangservSymbolTreePrivate *priv = ide_langserv_symbol_tree_get_instance_private (self);
-  const gchar *parent_name = NULL;
-  guint n_children = 0;
 
   g_assert (IDE_IS_LANGSERV_SYMBOL_TREE (self));
-  g_assert (!parent || IDE_IS_SYMBOL_NODE (parent));
-
-  if (IDE_IS_LANGSERV_SYMBOL_NODE (parent))
-    parent_name = ide_symbol_node_get_name (parent);
+  g_assert (!parent || IDE_IS_LANGSERV_SYMBOL_NODE (parent));
 
-  /*
-   * This is all O(n) below, but with the size of trees we are working with
-   * it's not all that bad. If it becomes an issue, we can move to something
-   * like a hashtable.
-   */
+  if (parent == NULL)
+    return g_node_n_children (&priv->root);
 
-  for (guint i = 0; i < priv->symbols->len; i++)
-    {
-      IdeLangservSymbolNode *node = g_ptr_array_index (priv->symbols, i);
-      const gchar *node_parent_name = ide_langserv_symbol_node_get_parent_name (node);
-
-      if (g_strcmp0 (node_parent_name, parent_name) == 0)
-        n_children++;
-    }
-
-  return n_children;
+  return g_node_n_children (&IDE_LANGSERV_SYMBOL_NODE (parent)->gnode);
 }
 
 static IdeSymbolNode *
@@ -77,29 +58,18 @@ ide_langserv_symbol_tree_get_nth_child (IdeSymbolTree *tree,
 {
   IdeLangservSymbolTree *self = (IdeLangservSymbolTree *)tree;
   IdeLangservSymbolTreePrivate *priv = ide_langserv_symbol_tree_get_instance_private (self);
-  const gchar *parent_name = NULL;
 
   g_return_val_if_fail (IDE_IS_LANGSERV_SYMBOL_TREE (self), NULL);
-  g_return_val_if_fail (!parent || IDE_IS_SYMBOL_NODE (parent), NULL);
-  g_return_val_if_fail (nth < priv->symbols->len, NULL);
+  g_return_val_if_fail (!parent || IDE_IS_LANGSERV_SYMBOL_NODE (parent), NULL);
 
-  if (IDE_IS_LANGSERV_SYMBOL_NODE (parent))
-    parent_name = ide_symbol_node_get_name (parent);
-
-  for (guint i = 0; i < priv->symbols->len; i++)
+  if (parent == NULL)
     {
-      IdeLangservSymbolNode *node = g_ptr_array_index (priv->symbols, i);
-      const gchar *node_parent_name = ide_langserv_symbol_node_get_parent_name (node);
-
-      if (g_strcmp0 (node_parent_name, parent_name) == 0)
-        {
-          if (nth == 0)
-            return g_object_ref (node);
-          nth--;
-        }
+      g_return_val_if_fail (nth < g_node_n_children (&priv->root), NULL);
+      return g_object_ref (g_node_nth_child (&priv->root, nth)->data);
     }
 
-  return NULL;
+  g_return_val_if_fail (nth < g_node_n_children (&IDE_LANGSERV_SYMBOL_NODE (parent)->gnode), NULL);
+  return g_object_ref (g_node_nth_child (&IDE_LANGSERV_SYMBOL_NODE (parent)->gnode, nth)->data);
 }
 
 static void
@@ -133,6 +103,60 @@ ide_langserv_symbol_tree_init (IdeLangservSymbolTree *self)
 {
 }
 
+static void
+add_to_node (GNode                 *node,
+             IdeLangservSymbolNode *symbol)
+{
+  /* First, check to see if any of the children are parents of the range of
+   * this symbol. If so, we will defer to adding it to that node.
+   */
+
+  for (GNode *iter = node->children; iter != NULL; iter = iter->next)
+    {
+      IdeLangservSymbolNode *child = iter->data;
+
+      /*
+       * If this node is an ancestor of ours, then we can defer to
+       * adding to that node.
+       */
+      if (ide_langserv_symbol_node_is_parent_of (child, symbol))
+        {
+          add_to_node (iter, symbol);
+          return;
+        }
+
+      /*
+       * If we are the parent of the child, then we need to insert
+       * ourselves in its place and add it to our node.
+       */
+      if (ide_langserv_symbol_node_is_parent_of (symbol, child))
+        {
+          /* Add this node to our children */
+          g_node_unlink (&child->gnode);
+          g_node_append (&symbol->gnode, &child->gnode);
+
+          /* add ourselves to the tree at this level */
+          g_node_append (node, &symbol->gnode);
+
+          return;
+        }
+    }
+
+  g_node_append (node, &symbol->gnode);
+}
+
+static void
+ide_langserv_symbol_tree_build (IdeLangservSymbolTree *self)
+{
+  IdeLangservSymbolTreePrivate *priv = ide_langserv_symbol_tree_get_instance_private (self);
+
+  g_assert (IDE_IS_LANGSERV_SYMBOL_TREE (self));
+  g_assert (priv->symbols != NULL);
+
+  for (guint i = 0; i < priv->symbols->len; i++)
+    add_to_node (&priv->root, g_ptr_array_index (priv->symbols, i));
+}
+
 /**
  * ide_langserv_symbol_tree_new:
  * @symbols: (transfer container) (element-type Ide.LangservSymbolNode): The symbols
@@ -153,5 +177,7 @@ ide_langserv_symbol_tree_new (GPtrArray *symbols)
   priv = ide_langserv_symbol_tree_get_instance_private (self);
   priv->symbols = symbols;
 
+  ide_langserv_symbol_tree_build (self);
+
   return self;
 }