bug#28407: 26.0.50; xref should use imenu

[Visuwesh <visuweshm@gmail.com>]

[-- Attachment #1: Type: text/plain, Size: 5769 bytes --]

[சனி ஜூன் 04, 2022] Dmitry Gutov wrote:

Hello Dmitry,

It took me too long to reply since I did not have the immediate need of
this backend and so wasn't too interested in writing it.  Sorry about
that.

>> Do we really need something like this?  Can we not let the user
>> handle
>> it themselves by adding/removing the imenu backend in .dir-locals.el?
>
> IDK, .dir-locals.el is per-directory. To have per-file effect one
> would need to use the file-locals section inside the file, which some
> might find undesirable.
>
> Anyway, the kind of defcustoms I was talking about are something to be
> considered for a later addition.
>

OK, I will leave it for the future.

>> Also what's the right way to check if a TAGS table is defined for the
>> current buffer?  I currently have,
>>      (or tags-table-files tags-file-name)
>
> Seems okay.
>
>>> As long as it comes before etags in xref-backend-functions, it should
>>> have all the power. Another possible direction for its development
>>> would be to always try to combine the locations coming from both etags
>>> and imenu (in the current file).
>> Yes, this sounds attractive but then we would be limiting ourselves
>> to
>> etags.  IMO, xref trying another backend when one fails to produce a
>> match would be a better solution in the long term.
>> [ I, for one, would like to have imenu and elisp backends working at the
>>    same time.  ]
>
> As an alternative, the IMenu backend could look inside the list of
> backends that follow it and try to combine itself with the next one
> manually.
>

I tried this and the results really depend on the imenu indices.  As for
example, python-mode really loves to add junk to the index name so this
combine-all thingy does not place too nicely but, it is still usable.

> A feature like "always use the next one" has been requested before,
> but so far no implementation that everybody would like has been
> proposed.
>

My combination thingy works along these lines.  Currently, if the
identifier is not found in imenu indices, then I check the backends
following the imenu one.  It works satisfactorily.  Although, there
might be a problem with deleting duplicates: a simple `delete-dups' does
not work.  I'm not sure how to compare two xref items independently of
their type (type as in buffer location, etc.).

One problem right now though is the TAGS table used by the etags backend
and the one actually corresponding to the focused file might be
different.  Maybe I should specially handle the etags backend?  WDYT?

[ To elaborate, say that I visited the TAGS residing in Emacs' src/
  directory then switched to another project.  Now, if I do C-u
  M-. Fplist_get RET, then it will take me to the Emacs project!!  This
  seems to be a general problem with the etags backend tho.  ]

> Also note that such approach is difficult to make behave
> consistently. E.g. we have identifier completion -- and it would
> (probably) only work for the first backend, but then navigation,
> somehow, would still be able to jump to the symbols indexed by the
> following backends. No matter which one comes first (etags or imenu),
> that doesn't sound ideal.
>

Looks like my logic can handle this case just fine.  In xdisp.c, I tried
C-u M-. Fplist_get RET and the imenu backend used the etags backend to
jump to the definition.  

>
> I think converting it to a simpler structure would indeed be a better
> choice. I am concerned about this code being to stay
> language-agnostic, though.
>
> If you have entries like "checkforlink (def)", how do you reliably
> extract the actual method name from it? Or if you don't it wouldn't
> match what xref-backend-identifier-at-point returns.
>

I don't think you have to worry about the backend staying language
agnostic.  In the case of python, I have a few imenu customisations:

    (defun vz/python-imenu-hook ()
      (setq imenu-name-lookup-function (lambda (symbol item) (string-prefix-p symbol item))
            python-imenu-format-parent-item-jump-label-function (lambda (_ name) name)
            imenu-create-index-function
            (lambda () (vz/imenu-create-index-function #'python-imenu-create-index))))

The `string-prefix-p' ensures that the imenu xref backend does not choke
on the " (def)" part.

>> But perhaps handling this "path-tree" in xref-backend-definitions would
>> not hurt after all.  I can spin this up if you think this is better
>> moving forward.
>
> Thanks.
>

Now done.

>> Some other questions follow:
>>      1. I was thinking about adding a buffer-local function for the
>>         identifier-at-point instead of hard-coding (thing-at-point 'symbol)
>>         to let major-modes like org-mode and auctex-mode behave more
>>         smartly. WDYT?
>
> See what etags does in find-tag--default. Maybe you could just
> delegate to it, just like etags's xref-backend-identifier-at-point
> override does.
>

I added a variable `imenu-xref-identifier-function'.  If this is not
what you had in mind, do tell.


>>      2. When implementing the apropos method for the backend, should we
>>         let pattern match against the whole "path-tree" or just the last
>>         part of it?
>
> Can't say for sure. Depends on how hard that would be to implement, I guess.

I'm leaving the apropos bit to the future™ as well.

On the performance part, it does not seem to be too bad but the only
large file I tested it on was xdisp.c: the imenu backend performed
really well once the initial hiccup of generating the imenu index alist
was done.

Hopefully, I covered everything that needed to be addressed.

Attaching updated patch.


[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: 0001-Add-imenu-xref-backend.patch --]
[-- Type: text/x-diff, Size: 5970 bytes --]

From 43779948d064453942dc97cacd3e8a4be8048f19 Mon Sep 17 00:00:00 2001
From: Visuwesh <visuweshm@gmail.com>
Date: Sat, 25 Jun 2022 19:32:49 +0530
Subject: [PATCH] Add imenu xref backend

* imenu.el (imenu--in-alist): Add new optional argument.
(imenu-xref-backend): New xref backend.
(imenu-xref-identifier-function, imenu-xref--following-backends): Add.
(imenu-xref--make-summary, imenu-xref--make-location)
(imenu-xref--flatten): Add helper functions.
(xref-backend-identifier-at-point, xref-backend-definitions)
(xref-backend-identifier-completion-ignore-case)
(xref-backend-identifier-completion-table): Add 'imenu' method.

(bug#28407)
---
 lisp/imenu.el | 101 +++++++++++++++++++++++++++++++++++++++++++++++---
 1 file changed, 96 insertions(+), 5 deletions(-)

diff --git a/lisp/imenu.el b/lisp/imenu.el
index 4393c6ed6c..9820de54e3 100644
--- a/lisp/imenu.el
+++ b/lisp/imenu.el
@@ -52,6 +52,7 @@
 ;;; Code:
 
 (require 'cl-lib)
+(require 'xref)
 
 ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
 ;;;
@@ -473,8 +474,10 @@ imenu--create-keymap
                         (if cmd (funcall cmd item) item))))))
               alist)))
 
-(defun imenu--in-alist (str alist)
-  "Check whether the string STR is contained in multi-level ALIST."
+(defun imenu--in-alist (str alist &optional all)
+  "Check whether the string STR is contained in multi-level ALIST.
+If the optional argument ALL is non-nil, then return all matches
+of STR in ALIST."
   (let (elt head tail res)
     (setq res nil)
     (while alist
@@ -491,12 +494,18 @@ imenu--in-alist
       ;; We are only interested in the bottom-level elements, so we need to
       ;; recurse if TAIL is a nested ALIST.
       (cond ((imenu--subalist-p elt)
-	     (if (setq res (imenu--in-alist str tail))
-		 (setq alist nil)))
+             (let ((r (imenu--in-alist str tail all)))
+               (if all
+                   (setq res (append res (if (listp (cdr r)) r (list r))))
+                 (setq res r)
+                 (when r
+                   (setq alist nil)))))
 	    ((if imenu-name-lookup-function
                  (funcall imenu-name-lookup-function str head)
                (string= str head))
-	     (setq alist nil res elt))))
+             (if all
+                 (push elt res)
+               (setq alist nil res elt)))))
     res))
 
 ;;;###autoload
@@ -550,6 +559,88 @@ imenu-default-create-index-function
 	(t
          (imenu-unavailable-error "This buffer cannot use `imenu-default-create-index-function'"))))
 
+;;;
+;;; Xref backend
+;;;
+
+(defvar-local imenu-xref-identifier-function nil
+  "Function to fetch the identifier for xref.")
+
+;;;###autoload
+(defun imenu-xref-backend ()
+  (unless imenu--index-alist
+    (imenu--make-index-alist))
+  (and imenu--index-alist 'imenu))
+
+(defun imenu-xref--following-backends ()
+  "Return the xref backends following the imenu one."
+  (let (backends)
+    (dolist (b (cdr (memq 'imenu-xref-backend xref-backend-functions)))
+      (when-let ((backend (and (functionp b) (funcall b))))
+        (push backend backends)))
+    (setq backends (nreverse backends))
+    backends))
+
+(cl-defmethod xref-backend-identifier-at-point ((_backend (eql 'imenu)))
+  (or (and imenu-xref-identifier-function
+           (funcall imenu-xref-identifier-function))
+      (thing-at-point 'symbol)))
+
+(defun imenu-xref--make-summary (marker)
+  (with-current-buffer (marker-buffer marker)
+    (save-excursion
+      (goto-char marker)
+      (back-to-indentation)
+      (buffer-substring (point) (point-at-eol)))))
+
+(defun imenu-xref--make-location (item)
+  (xref-make (imenu-xref--make-summary (cdr item))
+             (xref-make-buffer-location (marker-buffer (cdr item))
+                                        (marker-position (cdr item)))))
+
+(cl-defmethod xref-backend-definitions ((_backend (eql 'imenu)) identifier)
+  (if-let ((pos (string-search imenu-level-separator identifier)))
+      ;; We only care about the exact match here so ALL is nil.
+      (let ((alist (imenu--in-alist (substring identifier 0 pos) imenu--index-alist)))
+        (while (and (listp alist) (listp (cdr alist)))
+          (setq identifier (substring identifier (1+ pos))
+                pos (string-search imenu-level-separator identifier)
+                alist (imenu--in-alist (substring identifier 0 pos) imenu--index-alist)))
+        (list (imenu-xref--make-location alist)))
+    (let ((res (imenu--in-alist identifier imenu--index-alist t))
+          defs)
+      (dolist (item res)
+        (push (imenu-xref--make-location item) defs))
+      (unless defs
+        (dolist (b (imenu-xref--following-backends))
+          (ignore-errors
+            ;; FIXME: This does not catch duplicates!
+            (setq defs (append defs (xref-backend-definitions b identifier))))))
+      defs)))
+
+(cl-defmethod xref-backend-identifier-completion-ignore-case ((_backend (eql 'imenu)))
+  imenu-case-fold-search)
+
+(defun imenu-xref--flatten (alist &optional prefix)
+  (let (res)
+    (dolist (item alist)
+      (if (imenu--subalist-p item)
+          (setq res (append res (imenu-xref--flatten
+                                 (cdr item)
+                                 (concat prefix (when prefix imenu-level-separator) (car item)))))
+        (push (cons (concat prefix (when prefix imenu-level-separator) (car item))
+                    (cdr item))
+              res)))
+    res))
+
+(cl-defmethod xref-backend-identifier-completion-table ((_backend (eql 'imenu)))
+  (let ((collection (imenu-xref--flatten imenu--index-alist)))
+    (apply #'completion-table-merge
+           (append (list (lambda (string pred action)
+                           (complete-with-action action collection string pred)))
+                   (mapcar #'xref-backend-identifier-completion-table
+                           (imenu-xref--following-backends))))))
+
 ;;;
 ;;; Generic index gathering function.
 ;;;
-- 
2.35.1