From: Yuan Fu <casouri@gmail.com>
To: Theodor Thornhill <theo@thornhill.no>
Cc: Eli Zaretskii <eliz@gnu.org>,
Stefan Monnier <monnier@iro.umontreal.ca>,
Emacs Devel <emacs-devel@gnu.org>,
Daniel Colascione <dancol@dancol.org>
Subject: Re: Tree-sitter integration on feature/tree-sitter
Date: Wed, 18 May 2022 13:52:58 -0700 [thread overview]
Message-ID: <6EF70929-5759-4F1A-B878-0C1660FB6831@gmail.com> (raw)
In-Reply-To: <87k0ajygry.fsf@thornhill.no>
> On May 17, 2022, at 2:45 PM, Theodor Thornhill <theo@thornhill.no> wrote:
>
> Yuan Fu <casouri@gmail.com> writes:
>
>>> On May 13, 2022, at 10:03 PM, Theodor Thornhill <theo@thornhill.no> wrote:
>>>
>>>>
>>>> Now there is treesit-beginning/end-of-defun. You just need to set treesit-defun-query and everything else come for free. I needed to invent some heavy machinery for that, resulting in some new handy functions:
>>>>
>>>> - treesit-traverse-depth-first
>>>> - treesit-traverse-breadth-first
>>>> - treesit-traverse-forward-depth-first (maybe this should be named simply treesit-traverse-forward?)
>>>>
>>>> - treesit-search-forward
>>>> - treesit-search-beginning
>>>> They are untested & undocumented (in manual), so please play with them and report problems :-)
>>>>
>
> I've been testing the provided functionality for beginning/end-of-defun,
> and I have some thoughts I'd like to share.
>
> For starters, let me just give some context. The implementation I've
> used so far before the provided version looks something like
> ```
> (defun typescript-mode-move-to-node (fn)
> (when-let ((found-node
> (treesit-parent-until
> (treesit-node-at (point))
> (lambda (parent)
> (treesit-query-capture
> parent
> typescript-mode--defun-query)))))
> (goto-char (funcall fn found-node))))
>
> (defun typescript-mode-beginning-of-defun (&optional arg)
> (typescript-mode-move-to-node #'treesit-node-start))
>
> (defun typescript-mode-end-of-defun (&optional arg)
> (typescript-mode-move-to-node #'treesit-node-end))
> ```
>
> If this is given a query such as
>
> ```
> (defvar typescript-mode--defun-query
> "[(import_statement)
> (function_declaration)
> (type_alias_declaration)
> (interface_declaration)
> (lexical_declaration)] @defun")
> ```
>
> we would traverse parentwise and locate a node on match. This
> implementation is very fast, but has an issue - it will only match in
> the parentwise path, so siblings will not be found. This makes my
> function useful, but not general enough. The version provided in-tree
> right now uses the depth first approach, which has two big problems -
> performance and inconsistency.
>
> Its docstring notes:
> ```
> Traversing forward depth-first means, for a tree like the below
> where NODE is marked 1, traverse as numbered:
>
> 16
> |
> 3--------4-----------8
> | | |
> o--o-+--1 5--+--6 9---+-----12
> | | | | | |
> o o 2 7 +-+-+ +--+--+
> | | | | |
> 10 11 13 14 15
> ```
>
> This means that if we start at node 1, I'd expect us to navigate to the
> nodes 3 - 4 - 8 - 16, when repeatedly pressing the beginning-of-defun.
> However, because we go depth first, we can end up landing at say, node
> 14, which feels unnatural. This can happen for example in javascript if
> we add arrow_function to the nodes to match. If node 14 contains such a
> node, the traversing order would look like this: 3 - 4 - 8 - 14 - 16.
> This feels odd, or at least differs from how normal emacs operates. In
> addition, when the search gets long, it can take up to a second on my
> system to find the beginning of a defun, because of the amount of
> traversing required by the depth first algorithm.
>
> I have a suggestion for a solution that you may consider.
>
> Either add a new defcustom 'treesit-depth-first-go-deep', or add a new
> param to 'treesit-traverse-depth-first', like so:
> ```
> (defun treesit-traverse-depth-first (node pred &optional step go-deep)
> (if (funcall pred node)
> node
> (and go-deep
> (cl-loop for child in (if (or (null step) (>= step 0))
> (treesit-node-children node)
> (nreverse (treesit-node-children node)))
> if (treesit-traverse-depth-first child pred step)
> return child))))
> ```
>
> This way we can avoid traversing deep into the subtrees, which is a slow
> operation, _and_ makes for an inconsistent experience. Setting go-deep
> as nil makes the function really fast, and also keeps the benefit of
> finding siblings.
>
> Another option is to not provide a generic depth first algorithm, and
> only go for siblings and parents, but we may want the depth first for
> other things, such as a generic 'treesit-goto-thing' function.
>
> What do you think?
Thanks, I think it could be very useful. I can add an option for the user of treesit-traverse-depth-first to control the depth it goes. And same for treesit-traverse-forward-depth-first. A relative depth of 0 could mean only traverse siblings and parent, nil means traverse all the way, a positive number n means traverse n steps down.
Yuan
next prev parent reply other threads:[~2022-05-18 20:52 UTC|newest]
Thread overview: 150+ messages / expand[flat|nested] mbox.gz Atom feed top
2022-05-07 8:29 Tree-sitter integration on feature/tree-sitter Yuan Fu
2022-05-07 8:44 ` Yuan Fu
2022-05-07 8:47 ` Theodor Thornhill
2022-05-07 17:59 ` Yuan Fu
2022-05-07 18:16 ` Theodor Thornhill
2022-05-07 9:04 ` Eli Zaretskii
2022-05-07 9:34 ` Theodor Thornhill
2022-05-07 18:33 ` Yuan Fu
2022-05-07 19:02 ` Theodor Thornhill
2022-05-07 18:27 ` Yuan Fu
2022-05-07 18:48 ` Eli Zaretskii
2022-05-07 19:00 ` Theodor Thornhill
2022-05-07 19:21 ` Eli Zaretskii
2022-05-07 19:11 ` Yuan Fu
2022-05-07 19:25 ` Eli Zaretskii
2022-05-07 20:00 ` Yuan Fu
2022-05-07 20:12 ` Theodor Thornhill
2022-05-07 21:24 ` Stefan Monnier
2022-05-07 22:02 ` Theodor Thornhill
2022-05-08 6:18 ` Eli Zaretskii
2022-05-08 12:05 ` Dmitry Gutov
2022-05-08 12:16 ` Stefan Monnier
2022-05-08 13:23 ` Eli Zaretskii
2022-05-08 20:57 ` Dmitry Gutov
2022-05-08 13:21 ` Eli Zaretskii
2022-05-08 20:42 ` Dmitry Gutov
2022-05-09 11:18 ` Eli Zaretskii
2022-05-08 6:16 ` Eli Zaretskii
2022-05-08 6:49 ` Theodor Thornhill
2022-05-08 6:58 ` Eli Zaretskii
2022-05-08 9:02 ` Theodor Thornhill
2022-05-08 9:09 ` Theodor Thornhill
2022-05-08 9:10 ` Eli Zaretskii
2022-05-08 9:19 ` Theodor Thornhill
2022-05-08 10:33 ` Eli Zaretskii
2022-05-08 13:47 ` Theodor Thornhill
2022-05-08 13:58 ` Eli Zaretskii
2022-05-08 14:01 ` Stefan Monnier
2022-05-08 14:25 ` Theodor Thornhill
2022-05-08 14:42 ` Eli Zaretskii
2022-05-08 19:16 ` Theodor Thornhill
2022-05-08 21:14 ` Yuan Fu
2022-05-09 11:14 ` Eli Zaretskii
2022-05-09 12:20 ` Theodor Thornhill
2022-05-09 12:23 ` Eli Zaretskii
2022-05-09 21:10 ` Yuan Fu
2022-05-09 21:33 ` Theodor Thornhill
2022-05-14 0:03 ` Yuan Fu
2022-05-14 5:03 ` Theodor Thornhill
2022-05-14 5:13 ` Yuan Fu
2022-05-17 21:45 ` Theodor Thornhill
2022-05-18 20:52 ` Yuan Fu [this message]
2022-05-18 21:07 ` Theodor Thornhill
2022-06-16 19:09 ` Yuan Fu
2022-06-17 6:19 ` Eli Zaretskii
2022-06-17 7:32 ` Yuan Fu
2022-06-17 10:42 ` Eli Zaretskii
2022-06-18 0:20 ` Yuan Fu
2022-06-18 6:23 ` Eli Zaretskii
2022-06-20 14:20 ` Daniel Martín
2022-06-20 20:03 ` Yuan Fu
2022-06-17 18:12 ` Yoav Marco
2022-06-18 0:35 ` Yuan Fu
2022-06-18 8:15 ` Yoav Marco
2022-06-18 20:11 ` Yuan Fu
2022-05-08 22:42 ` Stephen Leake
2022-05-14 15:09 ` Daniel Martín
2022-05-14 15:55 ` Yuan Fu
2022-05-14 18:50 ` Daniel Martín
2022-05-14 19:09 ` Eli Zaretskii
2022-06-16 19:10 ` Yuan Fu
-- strict thread matches above, loose matches on Subject: below --
2022-05-09 17:50 Yoav Marco
2022-05-09 20:51 ` Yuan Fu
[not found] ` <87lev9wyll.fsf@gmail.com>
2022-05-10 15:20 ` Yoav Marco
2022-05-10 15:43 ` Yoav Marco
2022-05-10 17:54 ` Yuan Fu
2022-05-10 18:18 ` Yoav Marco
2022-05-10 19:58 ` Stefan Monnier
2022-05-10 23:11 ` Yuan Fu
2022-05-10 23:53 ` Yuan Fu
2022-05-11 11:10 ` Eli Zaretskii
2022-05-11 11:16 ` Yoav Marco
2022-05-11 14:20 ` Eli Zaretskii
2022-05-11 15:40 ` Yoav Marco
2022-05-11 16:27 ` Eli Zaretskii
2022-05-11 20:14 ` Yuan Fu
2022-05-11 20:25 ` Yuan Fu
2022-05-12 5:19 ` Eli Zaretskii
2022-05-12 6:10 ` Yuan Fu
2022-05-12 7:12 ` Eli Zaretskii
2022-05-12 15:18 ` Stefan Monnier
2022-05-12 15:53 ` Eli Zaretskii
2022-05-12 5:17 ` Eli Zaretskii
2022-05-12 6:07 ` Yuan Fu
2022-05-12 14:16 ` Yoav Marco
2022-05-12 16:04 ` Eli Zaretskii
2022-05-12 16:26 ` Yoav Marco
2022-05-12 17:18 ` Eli Zaretskii
2022-05-12 17:22 ` Yoav Marco
2022-05-13 6:34 ` Eli Zaretskii
2022-05-13 8:04 ` Theodor Thornhill
2022-05-13 8:36 ` Yoav Marco
2022-05-13 9:46 ` Theodor Thornhill
2022-05-13 10:37 ` Eli Zaretskii
2022-05-13 10:52 ` Theodor Thornhill
2022-05-13 8:42 ` Yoav Marco
2022-05-13 10:41 ` Eli Zaretskii
2022-05-14 0:04 ` Yuan Fu
2022-06-16 19:16 ` Yuan Fu
2022-06-16 21:57 ` yoavm448
2022-06-17 1:10 ` Yuan Fu
2022-05-12 15:15 ` Stefan Monnier
2022-05-15 19:20 ` chad
2022-05-15 19:26 ` Eli Zaretskii
2022-05-19 1:35 Kiong-Ge Liau
2022-05-20 2:01 ` Yuan Fu
2022-06-16 19:03 ` Yuan Fu
2022-06-17 1:24 ` Po Lu
2022-06-18 0:09 ` Yuan Fu
2022-06-17 2:00 ` Ihor Radchenko
2022-06-17 5:23 ` Eli Zaretskii
2022-06-17 10:40 ` Ihor Radchenko
2022-06-17 6:15 ` Eli Zaretskii
2022-06-17 7:17 ` Yuan Fu
2022-06-17 10:37 ` Eli Zaretskii
2022-06-18 0:14 ` Yuan Fu
2022-06-18 6:22 ` Eli Zaretskii
2022-06-18 8:25 ` Yuan Fu
2022-06-18 8:50 ` Eli Zaretskii
2022-06-18 20:07 ` Yuan Fu
2022-06-19 5:39 ` Eli Zaretskii
2022-06-20 3:00 ` Yuan Fu
2022-06-20 11:44 ` Eli Zaretskii
2022-06-20 20:01 ` Yuan Fu
2022-06-21 2:26 ` Eli Zaretskii
2022-06-21 4:39 ` Yuan Fu
2022-06-21 10:18 ` Eli Zaretskii
2022-06-22 0:34 ` Yuan Fu
2022-06-17 11:06 ` Jostein Kjønigsen
2022-06-18 0:28 ` Yuan Fu
2022-06-18 20:57 ` Jostein Kjønigsen
2022-05-19 1:35 Kiong-Ge Liau
2022-06-28 16:08 Yoav Marco
2022-06-28 19:35 ` Yoav Marco
2022-06-29 15:35 ` Yuan Fu
2022-06-29 16:51 Abin Simon
2022-06-29 17:43 ` Yoav Marco
2022-06-30 11:21 ` Yoav Marco
2022-06-30 14:29 ` Abin Simon
2022-06-30 14:37 ` Yoav Marco
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
List information: https://www.gnu.org/software/emacs/
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=6EF70929-5759-4F1A-B878-0C1660FB6831@gmail.com \
--to=casouri@gmail.com \
--cc=dancol@dancol.org \
--cc=eliz@gnu.org \
--cc=emacs-devel@gnu.org \
--cc=monnier@iro.umontreal.ca \
--cc=theo@thornhill.no \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
Code repositories for project(s) associated with this public inbox
https://git.savannah.gnu.org/cgit/emacs.git
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).