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.

1 files changed, 26 insertions, 0 deletions

diff --git a/test/functional/treesitter/node_spec.lua b/test/functional/treesitter/node_spec.lua
index 8adec82774..96579f296b 100644
--- a/test/functional/treesitter/node_spec.lua
+++ b/test/functional/treesitter/node_spec.lua
@@ -143,4 +143,30 @@ describe('treesitter node API', function()
     eq(28, lua_eval('root:byte_length()'))
     eq(3, lua_eval('child:byte_length()'))
   end)
+
+  it('child_containing_descendant() works', function()
+    insert([[
+      int main() {
+        int x = 3;
+      }]])
+
+    exec_lua([[
+      tree = vim.treesitter.get_parser(0, "c"):parse()[1]
+      root = tree:root()
+      main = root:child(0)
+      body = main:child(2)
+      statement = body:child(1)
+      declarator = statement:child(1)
+      value = declarator:child(1)
+    ]])
+
+    eq(lua_eval('main:type()'), lua_eval('root:child_containing_descendant(value):type()'))
+    eq(lua_eval('body:type()'), lua_eval('main:child_containing_descendant(value):type()'))
+    eq(lua_eval('statement:type()'), lua_eval('body:child_containing_descendant(value):type()'))
+    eq(
+      lua_eval('declarator:type()'),
+      lua_eval('statement:child_containing_descendant(value):type()')
+    )
+    eq(vim.NIL, lua_eval('declarator:child_containing_descendant(value)'))
+  end)
 end)