[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Tree-sitter navigation time grows as sqrt(line-number)
From: |
JD Smith |
Subject: |
Re: Tree-sitter navigation time grows as sqrt(line-number) |
Date: |
Tue, 22 Aug 2023 17:07:19 -0400 |
> 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.
- Re: Tree-sitter navigation time grows as sqrt(line-number), (continued)
- Re: Tree-sitter navigation time grows as sqrt(line-number), Dmitry Gutov, 2023/08/17
- Re: Tree-sitter navigation time grows as sqrt(line-number), Dmitry Gutov, 2023/08/17
- Re: Tree-sitter navigation time grows as sqrt(line-number), JD Smith, 2023/08/19
- Re: Tree-sitter navigation time grows as sqrt(line-number), Yuan Fu, 2023/08/19
- Re: Tree-sitter navigation time grows as sqrt(line-number), JD Smith, 2023/08/19
- Re: Tree-sitter navigation time grows as sqrt(line-number), Dmitry Gutov, 2023/08/19
- Re: Tree-sitter navigation time grows as sqrt(line-number), Yuan Fu, 2023/08/19
- Re: Tree-sitter navigation time grows as sqrt(line-number), JD Smith, 2023/08/20
- Re: Tree-sitter navigation time grows as sqrt(line-number), Dmitry Gutov, 2023/08/20
- Re: Tree-sitter navigation time grows as sqrt(line-number), Yuan Fu, 2023/08/21
- Re: Tree-sitter navigation time grows as sqrt(line-number),
JD Smith <=
- Re: Tree-sitter navigation time grows as sqrt(line-number), Yuan Fu, 2023/08/31
- Re: Tree-sitter navigation time grows as sqrt(line-number), Eli Zaretskii, 2023/08/31
- Re: Tree-sitter navigation time grows as sqrt(line-number), Dmitry Gutov, 2023/08/31
- Re: Tree-sitter navigation time grows as sqrt(line-number), Po Lu, 2023/08/31
- Re: Tree-sitter navigation time grows as sqrt(line-number), Dmitry Gutov, 2023/08/31
- Re: Tree-sitter navigation time grows as sqrt(line-number), Eli Zaretskii, 2023/08/31
- Re: Tree-sitter navigation time grows as sqrt(line-number), JD Smith, 2023/08/31
- Re: Tree-sitter navigation time grows as sqrt(line-number), Dmitry Gutov, 2023/08/31
- Re: Tree-sitter navigation time grows as sqrt(line-number), Yuan Fu, 2023/08/31
- Re: Tree-sitter navigation time grows as sqrt(line-number), Eli Zaretskii, 2023/08/31