Re: Tree-sitter navigation time grows as sqrt(line-number)

[JD Smith <jdtsmith@gmail.com>]

> On Aug 21, 2023, at 9:41 PM, Yuan Fu <casouri@gmail.com> wrote:
> 
> 
> 
>> On Aug 20, 2023, at 1:26 PM, Dmitry Gutov <dmitry@gutov.dev> wrote:
>> 
>> On 20/08/2023 15:40, JD Smith wrote:
>>> Looks like a winner (see below, or the gist)!  Thanks all.
>> 
>> Same here, thanks all indeed.
> 
> Let’s run with this patch for sometime. If all goes well, I’ll push to emacs-29. 
> 
>> 
>>> I do think we should consider a treesit-node-ancestors function that collects all the parent (of parent) nodes in one go into an (emacs) list, since you basically have to descend the whole tree from root to find the 1st parent anyway.   Then people who want to know, e.g., “am I in an if block?” can just test node type down the full ancestor list.  Of course, also, node-parent-until/while could be re-written to use node-ancestors, for some additional efficiency.
>> 
>> Should be useful, but the speedup from traversing only once might be negated by the work of allocating the full list of Lisp objects. So it might improve only certain applications.
>> 
>> OTOH, node-parent-until/while could be rewritten in a way that only allocates Lisp on-demand.
> 
> Yeah, node-parent is already fast, and a tree’s height mostly doesn’t grow higher than, say, 30 levels, so I won’t worry about it until some real scenario pops up.
> 

Sounds good.  In the meantime I have discovered treesit-query-capture, which is already very fast and can generate a list of all parents (of a certain type etc.):

(let* ((qry (treesit-query-compile 'python '([(argument_list) (parameters) (list) (dictionary)
     (parenthesized_expression) (subscript)]
    @ctx)))
       (n (treesit-node-at (point)))
       (bg (treesit-node-start n))
       (en (treesit-node-end n)))
  (treesit-query-capture 'python qry bg en t))

It is key to compile the query in advance.  It’s actually pretty similar in speed to the parent navigation.