From 4b029163345333a2c6975cd0dace6613b036ae47 Mon Sep 17 00:00:00 2001 From: vanaigr Date: Thu, 16 May 2024 09:57:58 -0500 Subject: perf(treesitter): use child_containing_descendant() in has-ancestor? (#28512) MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit 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. --- test/functional/treesitter/node_spec.lua | 26 ++++++++++++++++++++++++++ 1 file changed, 26 insertions(+) (limited to 'test/functional/treesitter/node_spec.lua') 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) -- cgit