neovim

commit 64847fbdc908bf0a301b8f1e1814ff71bd425bae
parent 921dc22fc0909bd0fdec2ebf42bb39de26347944
Author: Riley Bruins <ribru17@hotmail.com>
Date:   Wed, 25 Sep 2024 11:33:14 -0700

perf(treesitter): use `child_containing_descendant()` in `is_ancestor()`

**Problem:** `is_ancestor()` uses a slow, bottom-up parent lookup which
has performance pitfalls detailed in #28512.

**Solution:** Take `is_ancestor()` from $O(n^2)$ to $O(n)$ by
incorporating the use of the `child_containing_descendant()` function

Diffstat:
M
runtime/lua/vim/treesitter.lua
 | 
12
++----------
M
test/functional/treesitter/utils_spec.lua
 | 
8
++++++--

2 files changed, 8 insertions(+), 12 deletions(-)
diff --git a/runtime/lua/vim/treesitter.lua b/runtime/lua/vim/treesitter.lua
@@ -159,16 +159,8 @@ function M.is_ancestor(dest, source)
     return false
   end
 
-  local current = source ---@type TSNode?
-  while current ~= nil do
-    if current == dest then
-      return true
-    end
-
-    current = current:parent()
-  end
-
-  return false
+  -- child_containing_descendant returns nil if dest is a direct parent
+  return source:parent() == dest or dest:child_containing_descendant(source) ~= nil
 end
 
 --- Returns the node's range or an unpacked range table
diff --git a/test/functional/treesitter/utils_spec.lua b/test/functional/treesitter/utils_spec.lua
@@ -21,12 +21,16 @@ describe('treesitter utils', function()
       local parser = vim.treesitter.get_parser(0, 'c')
       local tree = parser:parse()[1]
       local root = tree:root()
-      _G.ancestor = root:child(0)
-      _G.child = _G.ancestor:child(0)
+      _G.ancestor = assert(root:child(0))
+      _G.child = assert(_G.ancestor:named_child(1))
+      _G.child_sibling = assert(_G.ancestor:named_child(2))
+      _G.grandchild = assert(_G.child:named_child(0))
     end)
 
     eq(true, exec_lua('return vim.treesitter.is_ancestor(_G.ancestor, _G.child)'))
+    eq(true, exec_lua('return vim.treesitter.is_ancestor(_G.ancestor, _G.grandchild)'))
     eq(false, exec_lua('return vim.treesitter.is_ancestor(_G.child, _G.ancestor)'))
+    eq(false, exec_lua('return vim.treesitter.is_ancestor(_G.child, _G.child_sibling)'))
   end)
 
   it('can detect if a position is contained in a node', function()