Re: Tree-sitter navigation time grows as sqrt(line-number)

[Dmitry Gutov <dmitry@gutov.dev>]

On 17/08/2023 15:34, Dmitry Gutov wrote:
> On 17/08/2023 15:21, JD Smith wrote:
>> I provided the test code and target file in the hopes that others 
>> could confirm the scaling behavior and then experiment with algorithm 
>> tweaks, if anything obvious presented itself.
> 
> I experimented a little bit with benchmarking (treesit-node-parent) 
> calls, and the patch came from that.

In case somebody else here wants to try it:

diff --git a/src/treesit.c b/src/treesit.c
index 1f694e47201..4b35e5ee2e5 100644
--- a/src/treesit.c
+++ b/src/treesit.c
@@ -52,6 +52,7 @@ Copyright (C) 2021-2023 Free Software Foundation, Inc.
  #undef ts_node_named_descendant_for_byte_range
  #undef ts_node_next_named_sibling
  #undef ts_node_next_sibling
+#undef ts_node_parent
  #undef ts_node_prev_named_sibling
  #undef ts_node_prev_sibling
  #undef ts_node_start_byte
@@ -1899,16 +1900,27 @@ DEFUN ("treesit-node-parent",

    TSNode treesit_node = XTS_NODE (node)->node;
    Lisp_Object parser = XTS_NODE (node)->parser;
-  TSTreeCursor cursor;
-  if (!treesit_cursor_helper (&cursor, treesit_node, parser))
-    return return_value;

-  if (ts_tree_cursor_goto_parent (&cursor))
-  {
-    TSNode parent = ts_tree_cursor_current_node (&cursor);
-    return_value = make_treesit_node (parser, parent);
-  }
-  ts_tree_cursor_delete (&cursor);
+  if (treesit_node_uptodate_p(node))
+    {
+      TSNode parent = ts_node_parent (treesit_node);
+      return_value = make_treesit_node (parser, parent);
+    }
+  else
+    {
+      Lisp_Object parser = XTS_NODE (node)->parser;
+      TSTreeCursor cursor;
+      if (!treesit_cursor_helper (&cursor, treesit_node, parser))
+	return return_value;
+
+      if (ts_tree_cursor_goto_parent (&cursor))
+	{
+	  TSNode parent = ts_tree_cursor_current_node (&cursor);
+	  return_value = make_treesit_node (parser, parent);
+	}
+      ts_tree_cursor_delete (&cursor);
+    }
+
    return return_value;
  }