feat(treesitter): async parsing

**Problem:** Parsing can be slow for large files, and it is a blocking
operation which can be disruptive and annoying.

**Solution:** Provide a function for asynchronous parsing, which accepts
a callback to be run after parsing completes.

Co-authored-by: Lewis Russell <lewis6991@gmail.com>
Co-authored-by: Luuk van Baal <luukvbaal@gmail.com>
Co-authored-by: VanaIgr <vanaigranov@gmail.com>

11 files changed, 395 insertions, 41 deletions

diff --git a/runtime/doc/news.txt b/runtime/doc/news.txt
index 4f4bfe9ecc..96f0ec1aa7 100644
--- a/runtime/doc/news.txt
+++ b/runtime/doc/news.txt
@@ -297,6 +297,8 @@ PERFORMANCE
 • Strong |treesitter-query| caching makes repeat  |vim.treesitter.query.get()|
   and |vim.treesitter.query.parse()| calls significantly faster for large
   queries.
+• Treesitter highlighting is now asynchronous. To force synchronous parsing,
+  use `vim.g._ts_force_sync_parsing = true`.
 
 PLUGINS
 
@@ -339,6 +341,8 @@ TREESITTER
 • New |TSNode:child_with_descendant()|, which is nearly identical to
   |TSNode:child_containing_descendant()| except that it can return the
   descendant itself.
+• |LanguageTree:parse()| optionally supports asynchronous invocation, which is
+  activated by passing the `on_parse` callback parameter.
 
 TUI
 
diff --git a/runtime/doc/options.txt b/runtime/doc/options.txt
index 80b391d8c9..8d171183d6 100644
--- a/runtime/doc/options.txt
+++ b/runtime/doc/options.txt
@@ -4657,8 +4657,8 @@ A jump table for the options with a short description can be found at |Q_op|.
 'redrawtime' 'rdt'	number	(default 2000)
 			global
 	Time in milliseconds for redrawing the display.  Applies to
-	'hlsearch', 'inccommand', |:match| highlighting and syntax
-	highlighting.
+	'hlsearch', 'inccommand', |:match| highlighting, syntax highlighting,
+	and async |LanguageTree:parse()|.
 	When redrawing takes more than this many milliseconds no further
 	matches will be highlighted.
 	For syntax highlighting the time applies per window.  When over the
diff --git a/runtime/doc/treesitter.txt b/runtime/doc/treesitter.txt
index 80d8f92af2..41679f80ca 100644
--- a/runtime/doc/treesitter.txt
+++ b/runtime/doc/treesitter.txt
@@ -1090,6 +1090,9 @@ start({bufnr}, {lang})                                *vim.treesitter.start()*
     required for some plugins. In this case, add `vim.bo.syntax = 'on'` after
     the call to `start`.
 
+    Note: By default, the highlighter parses code asynchronously, using a
+    segment time of 3ms.
+
     Example: >lua
         vim.api.nvim_create_autocmd( 'FileType', { pattern = 'tex',
             callback = function(args)
@@ -1401,8 +1404,8 @@ Query:iter_captures({node}, {source}, {start}, {stop})
                   Defaults to `node:end_()`.
 
     Return: ~
-        (`fun(end_line: integer?): integer, TSNode, vim.treesitter.query.TSMetadata, TSQueryMatch`)
-        capture id, capture node, metadata, match
+        (`fun(end_line: integer?): integer, TSNode, vim.treesitter.query.TSMetadata, TSQueryMatch, TSTree`)
+        capture id, capture node, metadata, match, tree
 
                                                         *Query:iter_matches()*
 Query:iter_matches({node}, {source}, {start}, {stop}, {opts})
@@ -1447,8 +1450,8 @@ Query:iter_matches({node}, {source}, {start}, {stop}, {opts})
                     compatibility and will be removed in a future release.
 
     Return: ~
-        (`fun(): integer, table<integer, TSNode[]>, vim.treesitter.query.TSMetadata`)
-        pattern id, match, metadata
+        (`fun(): integer, table<integer, TSNode[]>, vim.treesitter.query.TSMetadata, TSTree`)
+        pattern id, match, metadata, tree
 
 set({lang}, {query_name}, {text})                 *vim.treesitter.query.set()*
     Sets the runtime query named {query_name} for {lang}
@@ -1611,7 +1614,7 @@ LanguageTree:node_for_range({range}, {opts})
     Return: ~
         (`TSNode?`)
 
-LanguageTree:parse({range})                             *LanguageTree:parse()*
+LanguageTree:parse({range}, {on_parse})                 *LanguageTree:parse()*
     Recursively parse all regions in the language tree using
     |treesitter-parsers| for the corresponding languages and run injection
     queries on the parsed trees to determine whether child trees should be
@@ -1622,14 +1625,27 @@ LanguageTree:parse({range})                             *LanguageTree:parse()*
     if {range} is `true`).
 
     Parameters: ~
-      • {range}  (`boolean|Range?`) Parse this range in the parser's source.
-                 Set to `true` to run a complete parse of the source (Note:
-                 Can be slow!) Set to `false|nil` to only parse regions with
-                 empty ranges (typically only the root tree without
-                 injections).
+      • {range}     (`boolean|Range?`) Parse this range in the parser's
+                    source. Set to `true` to run a complete parse of the
+                    source (Note: Can be slow!) Set to `false|nil` to only
+                    parse regions with empty ranges (typically only the root
+                    tree without injections).
+      • {on_parse}  (`fun(err?: string, trees?: table<integer, TSTree>)?`)
+                    Function invoked when parsing completes. When provided and
+                    `vim.g._ts_force_sync_parsing` is not set, parsing will
+                    run asynchronously. The first argument to the function is
+                    a string respresenting the error type, in case of a
+                    failure (currently only possible for timeouts). The second
+                    argument is the list of trees returned by the parse (upon
+                    success), or `nil` if the parse timed out (determined by
+                    'redrawtime').
+
+                    If parsing was still able to finish synchronously (within
+                    3ms), `parse()` returns the list of trees. Otherwise, it
+                    returns `nil`.
 
     Return: ~
-        (`table<integer, TSTree>`)
+        (`table<integer, TSTree>?`)
 
                                                  *LanguageTree:register_cbs()*
 LanguageTree:register_cbs({cbs}, {recursive})
diff --git a/runtime/lua/vim/_meta/options.lua b/runtime/lua/vim/_meta/options.lua
index 940441a849..c9871c8660 100644
--- a/runtime/lua/vim/_meta/options.lua
+++ b/runtime/lua/vim/_meta/options.lua
@@ -4845,8 +4845,8 @@ vim.go.redrawdebug = vim.o.redrawdebug
 vim.go.rdb = vim.go.redrawdebug
 
 --- Time in milliseconds for redrawing the display.  Applies to
---- 'hlsearch', 'inccommand', `:match` highlighting and syntax
---- highlighting.
+--- 'hlsearch', 'inccommand', `:match` highlighting, syntax highlighting,
+--- and async `LanguageTree:parse()`.
 --- When redrawing takes more than this many milliseconds no further
 --- matches will be highlighted.
 --- For syntax highlighting the time applies per window.  When over the
diff --git a/runtime/lua/vim/treesitter.lua b/runtime/lua/vim/treesitter.lua
index 89dc4e289a..9b7c8233d8 100644
--- a/runtime/lua/vim/treesitter.lua
+++ b/runtime/lua/vim/treesitter.lua
@@ -61,7 +61,7 @@ function M._create_parser(bufnr, lang, opts)
     { on_bytes = bytes_cb, on_detach = detach_cb, on_reload = reload_cb, preview = true }
   )
 
-  self:parse()
+  self:parse(nil, function() end)
 
   return self
 end
@@ -397,6 +397,8 @@ end
 --- Note: By default, disables regex syntax highlighting, which may be required for some plugins.
 --- In this case, add `vim.bo.syntax = 'on'` after the call to `start`.
 ---
+--- Note: By default, the highlighter parses code asynchronously, using a segment time of 3ms.
+---
 --- Example:
 ---
 --- ```lua
@@ -408,8 +410,8 @@ end
 --- })
 --- ```
 ---
----@param bufnr (integer|nil) Buffer to be highlighted (default: current buffer)
----@param lang (string|nil) Language of the parser (default: from buffer filetype)
+---@param bufnr integer? Buffer to be highlighted (default: current buffer)
+---@param lang string? Language of the parser (default: from buffer filetype)
 function M.start(bufnr, lang)
   bufnr = vim._resolve_bufnr(bufnr)
   local parser = assert(M.get_parser(bufnr, lang, { error = false }))
diff --git a/runtime/lua/vim/treesitter/highlighter.lua b/runtime/lua/vim/treesitter/highlighter.lua
index 96503c38ea..04e6ee8a9e 100644
--- a/runtime/lua/vim/treesitter/highlighter.lua
+++ b/runtime/lua/vim/treesitter/highlighter.lua
@@ -69,6 +69,7 @@ end
 ---@field private _queries table<string,vim.treesitter.highlighter.Query>
 ---@field tree vim.treesitter.LanguageTree
 ---@field private redraw_count integer
+---@field parsing boolean true if we are parsing asynchronously
 local TSHighlighter = {
   active = {},
 }
@@ -147,7 +148,7 @@ function TSHighlighter.new(tree, opts)
     vim.opt_local.spelloptions:append('noplainbuffer')
   end)
 
-  self.tree:parse()
+  self.tree:parse(nil, function() end)
 
   return self
 end
@@ -384,19 +385,23 @@ function TSHighlighter._on_spell_nav(_, _, buf, srow, _, erow, _)
 end
 
 ---@private
----@param _win integer
 ---@param buf integer
 ---@param topline integer
 ---@param botline integer
-function TSHighlighter._on_win(_, _win, buf, topline, botline)
+function TSHighlighter._on_win(_, _, buf, topline, botline)
   local self = TSHighlighter.active[buf]
-  if not self then
+  if not self or self.parsing then
     return false
   end
-  self.tree:parse({ topline, botline + 1 })
-  self:prepare_highlight_states(topline, botline + 1)
+  self.parsing = self.tree:parse({ topline, botline + 1 }, function(_, trees)
+    if trees and self.parsing then
+      self.parsing = false
+      api.nvim__redraw({ buf = buf, valid = false, flush = false })
+    end
+  end) == nil
   self.redraw_count = self.redraw_count + 1
-  return true
+  self:prepare_highlight_states(topline, botline)
+  return #self._highlight_states > 0
 end
 
 api.nvim_set_decoration_provider(ns, {
diff --git a/runtime/lua/vim/treesitter/languagetree.lua b/runtime/lua/vim/treesitter/languagetree.lua
index 330eb45749..945a2301a9 100644
--- a/runtime/lua/vim/treesitter/languagetree.lua
+++ b/runtime/lua/vim/treesitter/languagetree.lua
@@ -44,6 +44,8 @@ local query = require('vim.treesitter.query')
 local language = require('vim.treesitter.language')
 local Range = require('vim.treesitter._range')
 
+local default_parse_timeout_ms = 3
+
 ---@alias TSCallbackName
 ---| 'changedtree'
 ---| 'bytes'
@@ -76,6 +78,10 @@ local TSCallbackNames = {
 ---@field private _injections_processed boolean
 ---@field private _opts table Options
 ---@field private _parser TSParser Parser for language
+---Table of regions for which the tree is currently running an async parse
+---@field private _ranges_being_parsed table<string, boolean>
+---Table of callback queues, keyed by each region for which the callbacks should be run
+---@field private _cb_queues table<string, fun(err?: string, trees?: table<integer, TSTree>)[]>
 ---@field private _has_regions boolean
 ---@field private _regions table<integer, Range6[]>?
 ---List of regions this tree should manage and parse. If nil then regions are
@@ -130,6 +136,8 @@ function LanguageTree.new(source, lang, opts)
     _injections_processed = false,
     _valid = false,
     _parser = vim._create_ts_parser(lang),
+    _ranges_being_parsed = {},
+    _cb_queues = {},
     _callbacks = {},
     _callbacks_rec = {},
   }
@@ -232,6 +240,7 @@ end
 ---@param reload boolean|nil
 function LanguageTree:invalidate(reload)
   self._valid = false
+  self._parser:reset()
 
   -- buffer was reloaded, reparse all trees
   if reload then
@@ -334,10 +343,12 @@ end
 
 --- @private
 --- @param range boolean|Range?
+--- @param timeout integer?
 --- @return Range6[] changes
 --- @return integer no_regions_parsed
 --- @return number total_parse_time
-function LanguageTree:_parse_regions(range)
+--- @return boolean finished whether async parsing still needs time
+function LanguageTree:_parse_regions(range, timeout)
   local changes = {}
   local no_regions_parsed = 0
   local total_parse_time = 0
@@ -357,9 +368,14 @@ function LanguageTree:_parse_regions(range)
       )
     then
       self._parser:set_included_ranges(ranges)
+      self._parser:set_timeout(timeout and timeout * 1000 or 0) -- ms -> micros
       local parse_time, tree, tree_changes =
         tcall(self._parser.parse, self._parser, self._trees[i], self._source, true)
 
+      if not tree then
+        return changes, no_regions_parsed, total_parse_time, false
+      end
+
       -- Pass ranges if this is an initial parse
       local cb_changes = self._trees[i] and tree_changes or tree:included_ranges(true)
 
@@ -373,7 +389,7 @@ function LanguageTree:_parse_regions(range)
     end
   end
 
-  return changes, no_regions_parsed, total_parse_time
+  return changes, no_regions_parsed, total_parse_time, true
 end
 
 --- @private
@@ -409,6 +425,82 @@ function LanguageTree:_add_injections()
   return query_time
 end
 
+--- @param range boolean|Range?
+--- @return string
+local function range_to_string(range)
+  return type(range) == 'table' and table.concat(range, ',') or tostring(range)
+end
+
+--- @private
+--- @param range boolean|Range?
+--- @param callback fun(err?: string, trees?: table<integer, TSTree>)
+function LanguageTree:_push_async_callback(range, callback)
+  local key = range_to_string(range)
+  self._cb_queues[key] = self._cb_queues[key] or {}
+  local queue = self._cb_queues[key]
+  queue[#queue + 1] = callback
+end
+
+--- @private
+--- @param range boolean|Range?
+--- @param err? string
+--- @param trees? table<integer, TSTree>
+function LanguageTree:_run_async_callbacks(range, err, trees)
+  local key = range_to_string(range)
+  for _, cb in ipairs(self._cb_queues[key]) do
+    cb(err, trees)
+  end
+  self._ranges_being_parsed[key] = false
+  self._cb_queues[key] = {}
+end
+
+--- Run an asynchronous parse, calling {on_parse} when complete.
+---
+--- @private
+--- @param range boolean|Range?
+--- @param on_parse fun(err?: string, trees?: table<integer, TSTree>)
+--- @return table<integer, TSTree>? trees the list of parsed trees, if parsing completed synchronously
+function LanguageTree:_async_parse(range, on_parse)
+  self:_push_async_callback(range, on_parse)
+
+  -- If we are already running an async parse, just queue the callback.
+  local range_string = range_to_string(range)
+  if not self._ranges_being_parsed[range_string] then
+    self._ranges_being_parsed[range_string] = true
+  else
+    return
+  end
+
+  local buf = vim.b[self._source]
+  local ct = buf.changedtick
+  local total_parse_time = 0
+  local redrawtime = vim.o.redrawtime
+  local timeout = not vim.g._ts_force_sync_parsing and default_parse_timeout_ms or nil
+
+  local function step()
+    -- If buffer was changed in the middle of parsing, reset parse state
+    if buf.changedtick ~= ct then
+      ct = buf.changedtick
+      total_parse_time = 0
+    end
+
+    local parse_time, trees, finished = tcall(self._parse, self, range, timeout)
+    total_parse_time = total_parse_time + parse_time
+
+    if finished then
+      self:_run_async_callbacks(range, nil, trees)
+      return trees
+    elseif total_parse_time > redrawtime then
+      self:_run_async_callbacks(range, 'TIMEOUT', nil)
+      return nil
+    else
+      vim.schedule(step)
+    end
+  end
+
+  return step()
+end
+
 --- Recursively parse all regions in the language tree using |treesitter-parsers|
 --- for the corresponding languages and run injection queries on the parsed trees
 --- to determine whether child trees should be created and parsed.
@@ -420,11 +512,33 @@ end
 ---     Set to `true` to run a complete parse of the source (Note: Can be slow!)
 ---     Set to `false|nil` to only parse regions with empty ranges (typically
 ---     only the root tree without injections).
---- @return table<integer, TSTree>
-function LanguageTree:parse(range)
+--- @param on_parse fun(err?: string, trees?: table<integer, TSTree>)? Function invoked when parsing completes.
+---     When provided and `vim.g._ts_force_sync_parsing` is not set, parsing will run
+---     asynchronously. The first argument to the function is a string respresenting the error type,
+---     in case of a failure (currently only possible for timeouts). The second argument is the list
+---     of trees returned by the parse (upon success), or `nil` if the parse timed out (determined
+---     by 'redrawtime').
+---
+---     If parsing was still able to finish synchronously (within 3ms), `parse()` returns the list
+---     of trees. Otherwise, it returns `nil`.
+--- @return table<integer, TSTree>?
+function LanguageTree:parse(range, on_parse)
+  if on_parse then
+    return self:_async_parse(range, on_parse)
+  end
+  local trees, _ = self:_parse(range)
+  return trees
+end
+
+--- @private
+--- @param range boolean|Range|nil
+--- @param timeout integer?
+--- @return table<integer, TSTree> trees
+--- @return boolean finished
+function LanguageTree:_parse(range, timeout)
   if self:is_valid() then
     self:_log('valid')
-    return self._trees
+    return self._trees, true
   end
 
   local changes --- @type Range6[]?
@@ -433,10 +547,15 @@ function LanguageTree:parse(range)
   local no_regions_parsed = 0
   local query_time = 0
   local total_parse_time = 0
+  local is_finished --- @type boolean
 
   -- At least 1 region is invalid
   if not self:is_valid(true) then
-    changes, no_regions_parsed, total_parse_time = self:_parse_regions(range)
+    changes, no_regions_parsed, total_parse_time, is_finished = self:_parse_regions(range, timeout)
+    timeout = timeout and math.max(timeout - total_parse_time, 0)
+    if not is_finished then
+      return self._trees, is_finished
+    end
     -- Need to run injections when we parsed something
     if no_regions_parsed > 0 then
       self._injections_processed = false
@@ -457,10 +576,17 @@ function LanguageTree:parse(range)
   })
 
   for _, child in pairs(self._children) do
-    child:parse(range)
+    if timeout == 0 then
+      return self._trees, false
+    end
+    local ctime, _, child_finished = tcall(child._parse, child, range, timeout)
+    timeout = timeout and math.max(timeout - ctime, 0)
+    if not child_finished then
+      return self._trees, child_finished
+    end
   end
 
-  return self._trees
+  return self._trees, true
 end
 
 --- Invokes the callback for each |LanguageTree| recursively.
@@ -907,6 +1033,7 @@ function LanguageTree:_edit(
     )
   end
 
+  self._parser:reset()
   self._regions = nil
 
   local changed_range = {
diff --git a/runtime/lua/vim/treesitter/query.lua b/runtime/lua/vim/treesitter/query.lua
index b0b0fecd38..66ab0d52f0 100644
--- a/runtime/lua/vim/treesitter/query.lua
+++ b/runtime/lua/vim/treesitter/query.lua
@@ -913,8 +913,8 @@ end
 ---@param start? integer Starting line for the search. Defaults to `node:start()`.
 ---@param stop? integer Stopping line for the search (end-exclusive). Defaults to `node:end_()`.
 ---
----@return (fun(end_line: integer|nil): integer, TSNode, vim.treesitter.query.TSMetadata, TSQueryMatch):
----        capture id, capture node, metadata, match
+---@return (fun(end_line: integer|nil): integer, TSNode, vim.treesitter.query.TSMetadata, TSQueryMatch, TSTree):
+---        capture id, capture node, metadata, match, tree
 ---
 ---@note Captures are only returned if the query pattern of a specific capture contained predicates.
 function Query:iter_captures(node, source, start, stop)
@@ -924,6 +924,8 @@ function Query:iter_captures(node, source, start, stop)
 
   start, stop = value_or_node_range(start, stop, node)
 
+  -- Copy the tree to ensure it is valid during the entire lifetime of the iterator
+  local tree = node:tree():copy()
   local cursor = vim._create_ts_querycursor(node, self.query, start, stop, { match_limit = 256 })
 
   -- For faster checks that a match is not in the cache.
@@ -970,7 +972,7 @@ function Query:iter_captures(node, source, start, stop)
       match_cache[match_id] = metadata
     end
 
-    return capture, captured_node, metadata, match
+    return capture, captured_node, metadata, match, tree
   end
   return iter
 end
@@ -1011,7 +1013,7 @@ end
 ---   (last) node instead of the full list of matching nodes. This option is only for backward
 ---   compatibility and will be removed in a future release.
 ---
----@return (fun(): integer, table<integer, TSNode[]>, vim.treesitter.query.TSMetadata): pattern id, match, metadata
+---@return (fun(): integer, table<integer, TSNode[]>, vim.treesitter.query.TSMetadata, TSTree): pattern id, match, metadata, tree
 function Query:iter_matches(node, source, start, stop, opts)
   opts = opts or {}
   opts.match_limit = opts.match_limit or 256
@@ -1022,6 +1024,8 @@ function Query:iter_matches(node, source, start, stop, opts)
 
   start, stop = value_or_node_range(start, stop, node)
 
+  -- Copy the tree to ensure it is valid during the entire lifetime of the iterator
+  local tree = node:tree():copy()
   local cursor = vim._create_ts_querycursor(node, self.query, start, stop, opts)
 
   local function iter()
@@ -1059,7 +1063,7 @@ function Query:iter_matches(node, source, start, stop, opts)
     end
 
     -- TODO(lewis6991): create a new function that returns {match, metadata}
-    return pattern_i, captures, metadata
+    return pattern_i, captures, metadata, tree
   end
   return iter
 end
diff --git a/src/nvim/lua/treesitter.c b/src/nvim/lua/treesitter.c
index 28ad2cf4d3..9bd2baad27 100644
--- a/src/nvim/lua/treesitter.c
+++ b/src/nvim/lua/treesitter.c
@@ -489,7 +489,11 @@ static int parser_parse(lua_State *L)
   // Sometimes parsing fails (timeout, or wrong parser ABI)
   // In those case, just return an error.
   if (!new_tree) {
-    return luaL_error(L, "An error occurred when parsing.");
+    if (ts_parser_timeout_micros(p) == 0) {
+      // No timeout set, must have had an error
+      return luaL_error(L, "An error occurred when parsing.");
+    }
+    return 0;
   }
 
   // The new tree will be pushed to the stack, without copy, ownership is now to the lua GC.
diff --git a/src/nvim/options.lua b/src/nvim/options.lua
index 863f875d9d..15a4e8ddc2 100644
--- a/src/nvim/options.lua
+++ b/src/nvim/options.lua
@@ -6520,8 +6520,8 @@ return {
       defaults = { if_true = 2000 },
       desc = [=[
         Time in milliseconds for redrawing the display.  Applies to
-        'hlsearch', 'inccommand', |:match| highlighting and syntax
-        highlighting.
+        'hlsearch', 'inccommand', |:match| highlighting, syntax highlighting,
+        and async |LanguageTree:parse()|.
         When redrawing takes more than this many milliseconds no further
         matches will be highlighted.
         For syntax highlighting the time applies per window.  When over the
diff --git a/test/functional/treesitter/parser_spec.lua b/test/functional/treesitter/parser_spec.lua
index 2f80cee226..6f9faddbe3 100644
--- a/test/functional/treesitter/parser_spec.lua
+++ b/test/functional/treesitter/parser_spec.lua
@@ -10,6 +10,7 @@ local exec_lua = n.exec_lua
 local pcall_err = t.pcall_err
 local feed = n.feed
 local run_query = ts_t.run_query
+local assert_alive = n.assert_alive
 
 describe('treesitter parser API', function()
   before_each(function()
@@ -90,6 +91,197 @@ describe('treesitter parser API', function()
     eq(true, exec_lua('return parser:parse()[1] == tree2'))
   end)
 
+  it('parses buffer asynchronously', function()
+    insert([[
+      int main() {
+        int x = 3;
+      }]])
+
+    exec_lua(function()
+      _G.parser = vim.treesitter.get_parser(0, 'c')
+      _G.lang = vim.treesitter.language.inspect('c')
+      _G.parser:parse(nil, function(_, trees)
+        _G.tree = trees[1]
+        _G.root = _G.tree:root()
+      end)
+      vim.wait(100, function() end)
+    end)
+
+    eq('<tree>', exec_lua('return tostring(tree)'))
+    eq('<node translation_unit>', exec_lua('return tostring(root)'))
+    eq({ 0, 0, 3, 0 }, exec_lua('return {root:range()}'))
+
+    eq(1, exec_lua('return root:child_count()'))
+    exec_lua('child = root:child(0)')
+    eq('<node function_definition>', exec_lua('return tostring(child)'))
+    eq({ 0, 0, 2, 1 }, exec_lua('return {child:range()}'))
+
+    eq('function_definition', exec_lua('return child:type()'))
+    eq(true, exec_lua('return child:named()'))
+    eq('number', type(exec_lua('return child:symbol()')))
+    eq(true, exec_lua('return lang.symbols[child:type()]'))
+
+    exec_lua('anon = root:descendant_for_range(0,8,0,9)')
+    eq('(', exec_lua('return anon:type()'))
+    eq(false, exec_lua('return anon:named()'))
+    eq('number', type(exec_lua('return anon:symbol()')))
+    eq(false, exec_lua([=[return lang.symbols[string.format('"%s"', anon:type())]]=]))
+
+    exec_lua('descendant = root:descendant_for_range(1,2,1,12)')
+    eq('<node declaration>', exec_lua('return tostring(descendant)'))
+    eq({ 1, 2, 1, 12 }, exec_lua('return {descendant:range()}'))
+    eq(
+      '(declaration type: (primitive_type) declarator: (init_declarator declarator: (identifier) value: (number_literal)))',
+      exec_lua('return descendant:sexpr()')
+    )
+
+    feed('2G7|ay')
+    exec_lua(function()
+      _G.parser:parse(nil, function(_, trees)
+        _G.tree2 = trees[1]
+        _G.root2 = _G.tree2:root()
+        _G.descendant2 = _G.root2:descendant_for_range(1, 2, 1, 13)
+      end)
+      vim.wait(100, function() end)
+    end)
+    eq(false, exec_lua('return tree2 == tree1'))
+    eq(false, exec_lua('return root2 == root'))
+    eq('<node declaration>', exec_lua('return tostring(descendant2)'))
+    eq({ 1, 2, 1, 13 }, exec_lua('return {descendant2:range()}'))
+
+    eq(true, exec_lua('return child == child'))
+    -- separate lua object, but represents same node
+    eq(true, exec_lua('return child == root:child(0)'))
+    eq(false, exec_lua('return child == descendant2'))
+    eq(false, exec_lua('return child == nil'))
+    eq(false, exec_lua('return child == tree'))
+
+    eq('string', exec_lua('return type(child:id())'))
+    eq(true, exec_lua('return child:id() == child:id()'))
+    -- separate lua object, but represents same node
+    eq(true, exec_lua('return child:id() == root:child(0):id()'))
+    eq(false, exec_lua('return child:id() == descendant2:id()'))
+    eq(false, exec_lua('return child:id() == nil'))
+    eq(false, exec_lua('return child:id() == tree'))
+
+    -- unchanged buffer: return the same tree
+    eq(true, exec_lua('return parser:parse()[1] == tree2'))
+  end)
+
+  it('does not crash when editing large files', function()
+    insert([[printf("%s", "some text");]])
+    feed('yy49999p')
+
+    exec_lua(function()
+      _G.parser = vim.treesitter.get_parser(0, 'c')
+      _G.done = false
+      vim.treesitter.start(0, 'c')
+      _G.parser:parse(nil, function()
+        _G.done = true
+      end)
+      while not _G.done do
+        -- Busy wait until async parsing has completed
+        vim.wait(100, function() end)
+      end
+    end)
+
+    eq(true, exec_lua([[return done]]))
+    exec_lua(function()
+      vim.api.nvim_input('Lxj')
+    end)
+    exec_lua(function()
+      vim.api.nvim_input('xj')
+    end)
+    exec_lua(function()
+      vim.api.nvim_input('xj')
+    end)
+    assert_alive()
+  end)
+
+  it('resets parsing state on tree changes', function()
+    insert([[vim.api.nvim_set_hl(0, 'test2', { bg = 'green' })]])
+    feed('yy1000p')
+
+    exec_lua(function()
+      vim.cmd('set ft=lua')
+
+      vim.treesitter.start(0)
+      local parser = assert(vim.treesitter.get_parser(0))
+
+      parser:parse(true, function() end)
+      vim.api.nvim_buf_set_lines(0, 1, -1, false, {})
+      parser:parse(true)
+    end)
+  end)
+
+  it('resets when buffer was editing during an async parse', function()
+    insert([[printf("%s", "some text");]])
+    feed('yy49999p')
+    feed('gg4jO// Comment<Esc>')
+
+    exec_lua(function()
+      _G.parser = vim.treesitter.get_parser(0, 'c')
+      _G.done = false
+      vim.treesitter.start(0, 'c')
+      _G.parser:parse(nil, function()
+        _G.done = true
+      end)
+    end)
+
+    exec_lua(function()
+      vim.api.nvim_input('ggdj')
+    end)
+
+    eq(false, exec_lua([[return done]]))
+    exec_lua(function()
+      while not _G.done do
+        -- Busy wait until async parsing finishes
+        vim.wait(100, function() end)
+      end
+    end)
+    eq(true, exec_lua([[return done]]))
+    eq('comment', exec_lua([[return parser:parse()[1]:root():named_child(2):type()]]))
+    eq({ 2, 0, 2, 10 }, exec_lua([[return {parser:parse()[1]:root():named_child(2):range()}]]))
+  end)
+
+  it('handles multiple async parse calls', function()
+    insert([[printf("%s", "some text");]])
+    feed('yy49999p')
+
+    exec_lua(function()
+      -- Spy on vim.schedule
+      local schedule = vim.schedule
+      vim.schedule = function(fn)
+        _G.schedules = _G.schedules + 1
+        schedule(fn)
+      end
+      _G.schedules = 0
+      _G.parser = vim.treesitter.get_parser(0, 'c')
+      for i = 1, 5 do
+        _G['done' .. i] = false
+        _G.parser:parse(nil, function()
+          _G['done' .. i] = true
+        end)
+      end
+      schedule(function()
+        _G.schedules_snapshot = _G.schedules
+      end)
+    end)
+
+    eq(2, exec_lua([[return schedules_snapshot]]))
+    eq(
+      { false, false, false, false, false },
+      exec_lua([[return { done1, done2, done3, done4, done5 }]])
+    )
+    exec_lua(function()
+      while not _G.done1 do
+        -- Busy wait until async parsing finishes
+        vim.wait(100, function() end)
+      end
+    end)
+    eq({ true, true, true, true, true }, exec_lua([[return { done1, done2, done3, done4, done5 }]]))
+  end)
+
   local test_text = [[
 void ui_refresh(void)
 {