unofficial mirror of emacs-devel@gnu.org 
 help / color / mirror / code / Atom feed
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



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