Re: Tree-sitter integration on feature/tree-sitter

[Yuan Fu]

> 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