Support imenu-like feature

[casouri]

Currently the best idea I can come up with is to periodically query the whole buffer and refresh the tree view. For example, in a Python buffer

class Cat():
    def meow(self, pitch):
        pass
    def attack(self, force):
        pass
    def eat(self, food):
        pass

class Dog():
    def woof(self, pitch):
        pass
    def attack(self, force):
        pass
    def eat(self, food):
        pass

def main():
    pass

def error():
    pass

def celebrate():
    pass

Evaluating

(cl-flet ((get-name (n)
                    (tree-sitter-node-text
                     (tree-sitter-node-child-by-field-name n "name"))))
  (tree-sitter-get-buffer-create 'tree-sitter-python)
  (let ((classes (mapcar #'cdr
                         (tree-sitter-query-in
                          'tree-sitter-python
                          '((class_definition) @class))))
        (functions (mapcar #'cdr
                           (tree-sitter-query-in
                            'tree-sitter-python
                            '((function_definition) @func))))
        methods
        filtered-classes
        filtered-functions)
    (dolist (class classes)
      (let ((functions (mapcar #'cdr
                               (tree-sitter-query-in
                                class
                                '((function_definition) @func)))))
        (setq methods (append functions methods))
        (push (cons class functions) filtered-classes)))
    (setq filtered-functions
          (seq-difference functions methods #'tree-sitter-node-eq))
    (with-current-buffer (get-buffer-create "*tree*")
      (erase-buffer)
      (dolist (class (reverse filtered-classes))
        (insert (get-name (car class)) "\n")
        (dolist (func (cdr class))
          (insert "├─ " (get-name func) "\n"))
        (forward-line -1)
        (delete-char 1)
        (insert "└")
        (forward-line 1))
      (dolist (func filtered-functions)
        (insert (get-name func) "\n"))
      (display-buffer (current-buffer)))))

displays

Cat
├─ meow
├─ attack
└─ eat
Dog
├─ woof
├─ attack
└─ eat
main
error
celebrate

[casouri]

I duplicated the buffer content a bunch of times and got a 1k line buffer, then tried the code again. It is still pretty fast, took about 0.1 sec. I think we can probably get away with this approach :-) Add an idle-timer, while-no-input and double-buffering, and it should be smooth.

[mickeynp]

I will investigate if your code is faster than the dynamic module option. I mean, it almost certainly is. However, the example I gave is of course just a simplified version of the actual tree generator which is primarily -- but not only -- designed for echo area navigational aid as you traverse your code. See:

Now this is the hacky version; the original rendered a proper subset of the sparse tree but that of course (with ETS) turned out to have some performance bottlenecks. This simplified version is probably 'good enough' though.

[casouri]

Ah, I see, very interesting feature indeed. I'll wait for you result. If it is still not fast enough, you can describe what you do in more detail, and hopefully we can come up with something in C that can boost the performance for this type use use case.

[sebastiansturm]

while I'm excited to see tree-sitter getting integrated into the Emacs core, I'd very much like the default imenu integration to be synchronous (but fast) and not do anything in the background that might lead to ~100ms latency spikes.
I'm currently using a primitive custom imenu definition that uses the tree-sitter dynamic module to gather a simple list of method names; it's not as pretty as the hierarchical structure shown here, so having both to choose from would be the ideal solution IMO, but it's quick (~3 to 5 ms on files in the 1K line ballpark).

Note that I'm not currently trying to extract scopes, and I'm not sure if that can be done within tree-sitter's query mechanism or if one would have to manually traverse the AST starting from matched nodes (assuming that is supported by the API). Would that be a major performance bottleneck?

For completeness, this is the primitive implementation I'm using (hence the sebastian/ prefix, it's part of my private config):

(defmacro sebastian/define-tsc-index-function (fn-name query)
  `(defun ,fn-name ()
     (unless sebastian/tsc--imenu-query
       (setq sebastian/tsc--imenu-query (tsc-make-query tree-sitter-language ,query)))
     (tsc--without-restriction
      (let* ((matches
              (tsc-query-matches
               sebastian/tsc--imenu-query
               (tsc-root-node tree-sitter-tree) #'tsc--buffer-substring-no-properties)))
        (mapcar (lambda (match)
                  (pcase (cdr match)
                    (`[(name . ,name) (pars . ,pars)]
                     (cons
                      (string-replace
                       "( " "("
                       (s-collapse-whitespace
                        (string-join (list (tsc-node-text name) (tsc-node-text pars)))))
                      (tsc-node-start-position name)))))
                matches)))))

;; for C++ buffers:
(sebastian/define-tsc-index-function
 nq-cc-index-function
 [(function_declarator
   [(operator_name) (field_identifier) (scoped_identifier) (identifier)] @name
   (parameter_list) @pars)])

  (setq imenu-create-index-function #'nq-cc-index-function)

[casouri]

Yes, if we do provide a default tree-sitter imenu integration, it would be like what you showed here. I don't think imenu support scope anyway.

[mickeynp]

I mean, imenu was just an example, of course. It should be blazing fast; indeed, it all should, within the limits of what we can do with Emacs and so forth.

[sebastiansturm]

glad to hear that, no reason for me to worry then :)