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.

3 files changed, 8 insertions, 11 deletions

diff --git a/runtime/doc/treesitter.txt b/runtime/doc/treesitter.txt
index e105d06ebb..0b84bb60d4 100644
--- a/runtime/doc/treesitter.txt
+++ b/runtime/doc/treesitter.txt
@@ -78,6 +78,8 @@ An instance `TSNode` of a treesitter node supports the following methods.
 
 TSNode:parent()                                         *TSNode:parent()*
     Get the node's immediate parent.
+    Prefer |TSNode:child_containing_descendant()|
+    for iterating over the node's ancestors.
 
 TSNode:next_sibling()                                   *TSNode:next_sibling()*
     Get the node's next sibling.
@@ -114,6 +116,9 @@ TSNode:named_child({index})                              *TSNode:named_child()*
     Get the node's named child at the given {index}, where zero represents the
     first named child.
 
+TSNode:child_containing_descendant({descendant})  *TSNode:child_containing_descendant()*
+    Get the node's child that contains {descendant}.
+
 TSNode:start()                                          *TSNode:start()*
     Get the node's start position. Return three values: the row, column and
     total byte count (all zero-based).
diff --git a/runtime/lua/vim/treesitter/_meta.lua b/runtime/lua/vim/treesitter/_meta.lua
index 34a51e42f6..177699a207 100644
--- a/runtime/lua/vim/treesitter/_meta.lua
+++ b/runtime/lua/vim/treesitter/_meta.lua
@@ -20,6 +20,7 @@ error('Cannot require a meta file')
 ---@field descendant_for_range fun(self: TSNode, start_row: integer, start_col: integer, end_row: integer, end_col: integer): TSNode?
 ---@field named_descendant_for_range fun(self: TSNode, start_row: integer, start_col: integer, end_row: integer, end_col: integer): TSNode?
 ---@field parent fun(self: TSNode): TSNode?
+---@field child_containing_descendant fun(self: TSNode, descendant: TSNode): TSNode?
 ---@field next_sibling fun(self: TSNode): TSNode?
 ---@field prev_sibling fun(self: TSNode): TSNode?
 ---@field next_named_sibling fun(self: TSNode): TSNode?
diff --git a/runtime/lua/vim/treesitter/query.lua b/runtime/lua/vim/treesitter/query.lua
index 36c78b7f1d..ef5c2143a7 100644
--- a/runtime/lua/vim/treesitter/query.lua
+++ b/runtime/lua/vim/treesitter/query.lua
@@ -457,17 +457,8 @@ local predicate_handlers = {
     end
 
     for _, node in ipairs(nodes) do
-      local ancestor_types = {} --- @type table<string, boolean>
-      for _, type in ipairs({ unpack(predicate, 3) }) do
-        ancestor_types[type] = true
-      end
-
-      local cur = node:parent()
-      while cur do
-        if ancestor_types[cur:type()] then
-          return true
-        end
-        cur = cur:parent()
+      if node:__has_ancestor(predicate) then
+        return true
       end
     end
     return false