diff options
| author | vanaigr <vanaigranov@gmail.com> | 2024-05-16 09:57:58 -0500 |
|---|---|---|
| committer | GitHub <noreply@github.com> | 2024-05-16 16:57:58 +0200 |
| commit | 4b029163345333a2c6975cd0dace6613b036ae47 (patch) | |
| tree | ef4b6f914f6415d019e0a6fb64f1e8fd355aa5bc /runtime/lua/vim/treesitter/_meta.lua | |
| parent | 31dc6279693886a628119cd6c779e580faab32fd (diff) | |
| download | rneovim-4b029163345333a2c6975cd0dace6613b036ae47.tar.gz rneovim-4b029163345333a2c6975cd0dace6613b036ae47.tar.bz2 rneovim-4b029163345333a2c6975cd0dace6613b036ae47.zip | |
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.
Diffstat (limited to 'runtime/lua/vim/treesitter/_meta.lua')
| -rw-r--r-- | runtime/lua/vim/treesitter/_meta.lua | 1 |
1 files changed, 1 insertions, 0 deletions
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? |