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, 5 insertions, 0 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).