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. --- runtime/lua/vim/treesitter/_meta.lua | 1 + runtime/lua/vim/treesitter/query.lua | 13 ++----------- 2 files changed, 3 insertions(+), 11 deletions(-) (limited to 'runtime/lua') 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 - 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 -- cgit