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

[Dmitry Gutov]

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;
 }