From: Theodor Thornhill <theo@thornhill.no>
To: Yuan Fu <casouri@gmail.com>
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: Tue, 17 May 2022 23:45:53 +0200 [thread overview]
Message-ID: <87k0ajygry.fsf@thornhill.no> (raw)
In-Reply-To: <1179E1EC-90EF-4989-BE1D-115498F77F60@gmail.com>
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?
Theodor
next prev parent reply other threads:[~2022-05-17 21:45 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 [this message]
2022-05-18 20:52 ` Yuan Fu
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=87k0ajygry.fsf@thornhill.no \
--to=theo@thornhill.no \
--cc=casouri@gmail.com \
--cc=dancol@dancol.org \
--cc=eliz@gnu.org \
--cc=emacs-devel@gnu.org \
--cc=monnier@iro.umontreal.ca \
/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).