perf(treesitter): use child_containing_descendant() in has-ancestor? (#28512)

Problem: `has-ancestor?` is O(n²) for the depth of the tree since it iterates over each of the node's ancestors (bottom-up), and each ancestor takes O(n) time.
This happens because tree-sitter's nodes don't store their parent nodes, and the tree is searched (top-down) each time a new parent is requested.

Solution: Make use of new `ts_node_child_containing_descendant()` in tree-sitter v0.22.6 (which is now the minimum required version) to rewrite the `has-ancestor?` predicate in C to become O(n).

For a sample file, decreases the time taken by `has-ancestor?` from 360ms to 6ms.

2 files changed, 46 insertions, 1 deletions

diff --git a/src/nvim/CMakeLists.txt b/src/nvim/CMakeLists.txt
index d9cc695c55..937cfaaa31 100644
--- a/src/nvim/CMakeLists.txt
+++ b/src/nvim/CMakeLists.txt
@@ -33,7 +33,7 @@ find_package(Libuv 1.28.0 REQUIRED)
 find_package(Libvterm 0.3.3 REQUIRED)
 find_package(Lpeg REQUIRED)
 find_package(Msgpack 1.0.0 REQUIRED)
-find_package(Treesitter 0.20.9 REQUIRED)
+find_package(Treesitter 0.22.6 REQUIRED)
 find_package(Unibilium 2.0 REQUIRED)
 
 target_link_libraries(main_lib INTERFACE
diff --git a/src/nvim/lua/treesitter.c b/src/nvim/lua/treesitter.c
index 8befc6d32d..e87cf756a8 100644
--- a/src/nvim/lua/treesitter.c
+++ b/src/nvim/lua/treesitter.c
@@ -725,6 +725,8 @@ static struct luaL_Reg node_meta[] = {
   { "descendant_for_range", node_descendant_for_range },
   { "named_descendant_for_range", node_named_descendant_for_range },
   { "parent", node_parent },
+  { "__has_ancestor", __has_ancestor },
+  { "child_containing_descendant", node_child_containing_descendant },
   { "iter_children", node_iter_children },
   { "next_sibling", node_next_sibling },
   { "prev_sibling", node_prev_sibling },
@@ -1052,6 +1054,49 @@ static int node_parent(lua_State *L)
   return 1;
 }
 
+static int __has_ancestor(lua_State *L)
+{
+  TSNode descendant = node_check(L, 1);
+  if (lua_type(L, 2) != LUA_TTABLE) {
+    lua_pushboolean(L, false);
+    return 1;
+  }
+  int const pred_len = (int)lua_objlen(L, 2);
+
+  TSNode node = ts_tree_root_node(descendant.tree);
+  while (!ts_node_is_null(node)) {
+    char const *node_type = ts_node_type(node);
+    size_t node_type_len = strlen(node_type);
+
+    for (int i = 3; i <= pred_len; i++) {
+      lua_rawgeti(L, 2, i);
+      if (lua_type(L, -1) == LUA_TSTRING) {
+        size_t check_len;
+        char const *check_str = lua_tolstring(L, -1, &check_len);
+        if (node_type_len == check_len && memcmp(node_type, check_str, check_len) == 0) {
+          lua_pushboolean(L, true);
+          return 1;
+        }
+      }
+      lua_pop(L, 1);
+    }
+
+    node = ts_node_child_containing_descendant(node, descendant);
+  }
+
+  lua_pushboolean(L, false);
+  return 1;
+}
+
+static int node_child_containing_descendant(lua_State *L)
+{
+  TSNode node = node_check(L, 1);
+  TSNode descendant = node_check(L, 2);
+  TSNode child = ts_node_child_containing_descendant(node, descendant);
+  push_node(L, child, 1);
+  return 1;
+}
+
 static int node_next_sibling(lua_State *L)
 {
   TSNode node = node_check(L, 1);