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

[JD Smith]

> 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.