bug#28407: 26.0.50; xref should use imenu

bug#28407: 26.0.50; xref should use imenu

[Tom Tromey]

It would be nice if imenu were a back end for xref.
Then M-. could also use symbols found by imenu.

A further wrinkle on this would be if xref, project, and imenu worked
together, so that M-. would automatically know to look at imenu results
for other buffers in the same project.

Tom



In GNU Emacs 26.0.50 (build 18, x86_64-pc-linux-gnu, GTK+ Version 3.22.17)
 of 2017-09-09 built on bapiya
Repository revision: 4131f9785e30f2a31745125c714e922892113c62
Windowing system distributor 'Fedora Project', version 11.0.11903000
System Description:	Fedora release 25 (Twenty Five)

Recent messages:
Hunk already applied [3 times]
Mark saved where search started
user-error: No definitions found for: funlike_invocation_p
Quit
M-. runs the command xref-find-definitions
Type "q" in help window to restore its previous buffer.
uncompressing xref.el.gz...done
Mark saved where search started
uncompressing imenu.el.gz...done
Mark saved where search started [2 times]

Configured using:
 'configure --prefix=/home/tromey/Emacs/install'

Configured features:
XPM JPEG TIFF GIF PNG RSVG IMAGEMAGICK SOUND GPM DBUS GSETTINGS NOTIFY
LIBSELINUX GNUTLS LIBXML2 FREETYPE M17N_FLT LIBOTF XFT ZLIB
TOOLKIT_SCROLL_BARS GTK3 X11

Important settings:
  value of $LANG: en_US.utf8
  value of $XMODIFIERS: @im=ibus
  locale-coding-system: utf-8-unix

Major mode: Emacs-Lisp

Minor modes in effect:
  shell-dirtrack-mode: t
  diff-auto-refine-mode: t
  flyspell-mode: t
  which-function-mode: t
  erc-services-mode: t
  erc-list-mode: t
  erc-menu-mode: t
  erc-autojoin-mode: t
  erc-ring-mode: t
  erc-networks-mode: t
  erc-pcomplete-mode: t
  erc-track-mode: t
  erc-match-mode: t
  erc-netsplit-mode: t
  erc-hl-nicks-mode: t
  erc-button-mode: t
  erc-fill-mode: t
  erc-stamp-mode: t
  erc-irccontrols-mode: t
  erc-noncommands-mode: t
  erc-move-to-prompt-mode: t
  erc-readonly-mode: t
  savehist-mode: t
  tooltip-mode: t
  global-eldoc-mode: t
  eldoc-mode: t
  electric-indent-mode: t
  mouse-wheel-mode: t
  file-name-shadow-mode: t
  global-font-lock-mode: t
  font-lock-mode: t
  auto-composition-mode: t
  auto-encryption-mode: t
  auto-compression-mode: t
  column-number-mode: t
  line-number-mode: t
  auto-fill-function: do-auto-fill
  transient-mark-mode: t

Load-path shadows:
/home/tromey/.emacs.d/elpa/bubbles-0.5/bubbles hides /home/tromey/Emacs/install/share/emacs/26.0.50/lisp/play/bubbles

Features:
(shadow emacsbug make-mode cc-awk texinfo log-edit cl-print debug nndoc
gnus-dup debbugs-gnu debbugs soap-client url-http url-auth url-gw
rng-xsd rng-dt rng-util xsd-regexp smerge-mode whitespace gnus-html
url-queue help-fns radix-tree url-cache mm-url url url-proxy url-privacy
url-expand url-methods url-history url-cookie url-domsuf goto-addr
log-view pcvs-util term/xterm xterm shell find-file copyright pulse
etags xref project vc-mtn vc-hg vc-bzr vc-src vc-sccs vc-svn vc-cvs
vc-rcs jka-compr shr-color url-util shr svg xml dom browse-url
find-dired add-log misearch multi-isearch bug-reference vc-git diff-mode
map cc-mode cc-fonts cc-guess cc-menus cc-cmds dabbrev supercite
easy-mmode regi mail-hist nnir flow-fill mm-archive mailalias sort
smiley gnus-cite gnus-async gnus-bcklg mail-extr gnus-ml disp-table
gnus-topic nndraft nnmh nnfolder utf-7 network-stream nsm starttls
gnus-agent gnus-srvr gnus-score score-mode nnvirtual gnus-msg nntp
gnus-cache gnus-registry registry ebdb-gnus gnus-art mm-uu mml2015
mm-view mml-smime smime dig mailcap gnus-sum gnus-group gnus-undo
smtpmail gnus-start gnus-cloud nnimap nnmail mail-source tls gnutls utf7
netrc nnoo parse-time gnus-spec gnus-int gnus-range gnus-win gnus
nnheader elec-pair flyspell ispell diminish edmacro kmacro projectile
grep compile ibuf-ext ibuffer ibuffer-loaddefs dash appt diary-lib
diary-loaddefs which-func imenu minimap autorevert filenotify cus-start
cus-load status erc-services erc-list erc-menu erc-join erc-ring
erc-networks erc-pcomplete pcomplete erc-track erc-match erc-netsplit
erc-hl-nicks color erc-button erc-fill erc-stamp wid-edit erc-goodies
erc erc-backend erc-compat thingatpt pp warnings advice vc-dir ewoc vc
vc-dispatcher cc-styles cc-align cc-engine cc-vars cc-defs ebdb-complete
ebdb-message sendmail message puny dired dired-loaddefs format-spec
rfc822 mml mml-sec epa derived epg gnus-util rmail rmail-loaddefs
mm-decode mm-bodies mm-encode mail-parse rfc2231 rfc2047 rfc2045 mm-util
ietf-drums mail-prsvr mail-utils gmm-utils mailheader ebdb-mua ebdb-com
crm mailabbrev ebdb-format qp ebdb cl-extra help-mode eieio-opt speedbar
sb-image ezimage dframe find-func eieio-base pcase subr-x cal-menu
calendar cal-loaddefs timezone ange-ftp comint ansi-color ring server
savehist finder-inf dwarf-mode-autoloads gdb-shell-autoloads
lisppaste-autoloads pydoc-info-autoloads info-look cl
weblogger-autoloads info package easymenu epg-config url-handlers
url-parse auth-source cl-seq eieio eieio-core cl-macs eieio-loaddefs
password-cache url-vars seq byte-opt gv bytecomp byte-compile cconv
cl-loaddefs cl-lib time-date mule-util tooltip eldoc electric uniquify
ediff-hook vc-hooks lisp-float-type mwheel term/x-win x-win
term/common-win x-dnd tool-bar dnd fontset image regexp-opt fringe
tabulated-list replace newcomment text-mode elisp-mode lisp-mode
prog-mode register page menu-bar rfn-eshadow isearch timer select
scroll-bar mouse jit-lock font-lock syntax facemenu font-core
term/tty-colors frame cl-generic cham georgian utf-8-lang misc-lang
vietnamese tibetan thai tai-viet lao korean japanese eucjp-ms cp51932
hebrew greek romanian slovak czech european ethiopic indian cyrillic
chinese composite charscript charprop case-table epa-hook jka-cmpr-hook
help simple abbrev obarray minibuffer cl-preloaded nadvice loaddefs
button faces cus-face macroexp files text-properties overlay sha1 md5
base64 format env code-pages mule custom widget hashtable-print-readable
backquote dbusbind inotify dynamic-setting system-font-setting
font-render-setting move-toolbar gtk x-toolkit x multi-tty
make-network-process emacs)

Memory information:
((conses 16 2205844 699201)
 (symbols 48 58822 76)
 (miscs 40 16108 11738)
 (strings 32 597642 63371)
 (string-bytes 1 15642233)
 (vectors 16 252143)
 (vector-slots 8 3921716 191337)
 (floats 8 4806 1815)
 (intervals 56 142400 1766)
 (buffers 992 191))

bug#28407: 26.0.50; xref should use imenu

[Dmitry Gutov]

On 9/10/17 7:23 PM, Tom Tromey wrote:
> 
> It would be nice if imenu were a back end for xref.
> Then M-. could also use symbols found by imenu.
> 
> A further wrinkle on this would be if xref, project, and imenu worked
> together, so that M-. would automatically know to look at imenu results
> for other buffers in the same project.

Agreed. It could be a nice default for when no tags table is currently 
visited.

bug#28407: 26.0.50; xref should use imenu

[Visuwesh]

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

[திங்கள் செப்டம்பர் 11, 2017] Dmitry Gutov wrote:

> On 9/10/17 7:23 PM, Tom Tromey wrote:
>> It would be nice if imenu were a back end for xref.
>> Then M-. could also use symbols found by imenu.
>> A further wrinkle on this would be if xref, project, and imenu
>> worked
>> together, so that M-. would automatically know to look at imenu results
>> for other buffers in the same project.
>
> Agreed. It could be a nice default for when no tags table is currently
> visited.

I tried to write a general imenu backend in attached file (extracted
from my init.el) but I hit quite a few roadblocks,

  1. I activate the imenu backend iff there are no tags table defined
     for the buffer but this means that one cannot use the imenu
     backend to jump to definitions for symbols that TAGS do not know
     of currently.  I can think of two ways to solve this problem,

     (a) Check if the symbol is in TAGS table.
     (b) Modify the etags backend so that the user can say "I have no
     TAGS table for this file/project/whatever."

     (a) is definitely not clean, and (b) sounds feasible but similar
     situation can also exist with other backends (like elisp).

     I'm lost on how to solve this problem.

  2. I have not defined all the methods and the completion-table does
     not handle the nested case of the index alist.  AFAIU from `(elisp)
     Programmed Completion', completion "ends" when `try-completion'
     returns t but I seem to be mistaken.  I have to rewrite
     completion-table to be like `imenu--completion-buffer' but I don't
     know how to pull that off.

  3. `imenu-xref--in-alist' is mostly a 1-1 copy of `imenu--in-alist'
     with the only difference being my function returns all matches of
     the symbol instead of just the first one.  This should be easy
     enough to fix by adding an optional argument INCLUDE-ALL to
     `imenu--in-alist'.

I'm testing in python-mode with the following settings,

    (setq imenu-name-lookup-function (lambda (symbol item) (string-prefix-p symbol item))
          python-imenu-format-parent-item-jump-label-function (lambda (_ name) name))


[-- Attachment #2: imenu-xref.el --]
[-- Type: application/emacs-lisp, Size: 3130 bytes --]

bug#28407: 26.0.50; xref should use imenu

[Visuwesh]

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

[ஞாயிறு மே 15, 2022] Visuwesh wrote:

> [திங்கள் செப்டம்பர் 11, 2017] Dmitry Gutov wrote:
>
>> On 9/10/17 7:23 PM, Tom Tromey wrote:
>>> It would be nice if imenu were a back end for xref.
>>> Then M-. could also use symbols found by imenu.
>>> A further wrinkle on this would be if xref, project, and imenu
>>> worked
>>> together, so that M-. would automatically know to look at imenu results
>>> for other buffers in the same project.
>>
>> Agreed. It could be a nice default for when no tags table is currently
>> visited.
>
> I tried to write a general imenu backend in attached file (extracted
> from my init.el) but I hit quite a few roadblocks,
>
>   1. I activate the imenu backend iff there are no tags table defined
>      for the buffer but this means that one cannot use the imenu
>      backend to jump to definitions for symbols that TAGS do not know
>      of currently.  I can think of two ways to solve this problem,
>
>      (a) Check if the symbol is in TAGS table.
>      (b) Modify the etags backend so that the user can say "I have no
>      TAGS table for this file/project/whatever."
>
>      (a) is definitely not clean, and (b) sounds feasible but similar
>      situation can also exist with other backends (like elisp).
>
>      I'm lost on how to solve this problem.
>
>   2. I have not defined all the methods and the completion-table does
>      not handle the nested case of the index alist.  AFAIU from `(elisp)
>      Programmed Completion', completion "ends" when `try-completion'
>      returns t but I seem to be mistaken.  I have to rewrite
>      completion-table to be like `imenu--completion-buffer' but I don't
>      know how to pull that off.
>
>   3. `imenu-xref--in-alist' is mostly a 1-1 copy of `imenu--in-alist'
>      with the only difference being my function returns all matches of
>      the symbol instead of just the first one.  This should be easy
>      enough to fix by adding an optional argument INCLUDE-ALL to
>      `imenu--in-alist'.
>
> I'm testing in python-mode with the following settings,
>
>     (setq imenu-name-lookup-function (lambda (symbol item) (string-prefix-p symbol item))
>           python-imenu-format-parent-item-jump-label-function (lambda (_ name) name))

I solved (2) by using an affixation function.  I did (3) as well, and
I'm attaching my work as a patch against imenu.el.


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

diff --git a/lisp/imenu.el b/lisp/imenu.el
index 2636e77d08..69338d216a 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,61 @@ imenu-default-create-index-function
 	(t
          (imenu-unavailable-error "This buffer cannot use `imenu-default-create-index-function'"))))

+;;;
+;;; Xref backend
+;;;
+
+;;;###autoload
+(defun imenu-xref-backend ()
+  (unless imenu--index-alist
+    (imenu--make-index-alist))
+  (when (and imenu--index-alist
+             (not (progn (require 'etags) tags-table-files)))
+    'imenu))
+
+(cl-defmethod xref-backend-identifier-at-point ((_backend (eql 'imenu)))
+  (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)))))
+
+(cl-defmethod xref-backend-definitions ((_backend (eql 'imenu)) symbol)
+  (let ((res (imenu--in-alist symbol imenu--index-alist t))
+        defs)
+    (dolist (item res)
+      (push (xref-make (imenu-xref--make-summary (cdr item))
+                       (xref-make-buffer-location (marker-buffer (cdr item))
+                                                  (marker-position (cdr item))))
+            defs))
+    defs))
+
+(cl-defmethod xref-backend-identifier-completion-ignore-case ((_backend (eql 'imenu)))
+  imenu-case-fold-search)
+
+(defun imenu-xref--make-affixations (alist &optional prefix)
+  (let (res)
+    (dolist (item alist)
+      (if (imenu--subalist-p item)
+          (setq res (append res (imenu-xref--make-affixations
+                                 (cdr item)
+                                 (concat prefix (when prefix imenu-level-separator) (car item)))))
+        (push (list (car item) (concat prefix (when prefix imenu-level-separator)) "") res)))
+    res))
+
+(cl-defmethod xref-backend-identifier-completion-table ((_backend (eql 'imenu)))
+  (let ((affixations (imenu-xref--make-affixations imenu--index-alist)))
+    (lambda (string pred action)
+      (if (eq action 'metadata)
+          `(metadata (affixation-function
+                      . ,(lambda (cmp) (mapcar (lambda (c) (assoc c affixations #'equal)) cmp))))
+        ;; This works since (car AFFIXATIONS) is the completion
+        ;; candidate.
+        (complete-with-action action affixations string pred)))))
+
 ;;;
 ;;; Generic index gathering function.
 ;;;

bug#28407: 26.0.50; xref should use imenu

[Dmitry Gutov]

Hi Visuwesh,

On 16.05.2022 09:59, Visuwesh wrote:
> [ஞாயிறு மே 15, 2022] Visuwesh wrote:
> 
>> [திங்கள் செப்டம்பர் 11, 2017] Dmitry Gutov wrote:
>>
>>> On 9/10/17 7:23 PM, Tom Tromey wrote:
>>>> It would be nice if imenu were a back end for xref.
>>>> Then M-. could also use symbols found by imenu.
>>>> A further wrinkle on this would be if xref, project, and imenu
>>>> worked
>>>> together, so that M-. would automatically know to look at imenu results
>>>> for other buffers in the same project.
>>>
>>> Agreed. It could be a nice default for when no tags table is currently
>>> visited.
>>
>> I tried to write a general imenu backend in attached file (extracted
>> from my init.el) but I hit quite a few roadblocks,
>>
>>    1. I activate the imenu backend iff there are no tags table defined
>>       for the buffer but this means that one cannot use the imenu
>>       backend to jump to definitions for symbols that TAGS do not know
>>       of currently.  I can think of two ways to solve this problem,
>>
>>       (a) Check if the symbol is in TAGS table.
>>       (b) Modify the etags backend so that the user can say "I have no
>>       TAGS table for this file/project/whatever."
>>
>>       (a) is definitely not clean, and (b) sounds feasible but similar
>>       situation can also exist with other backends (like elisp).
>>
>>       I'm lost on how to solve this problem.
>>
>>    2. I have not defined all the methods and the completion-table does
>>       not handle the nested case of the index alist.  AFAIU from `(elisp)
>>       Programmed Completion', completion "ends" when `try-completion'
>>       returns t but I seem to be mistaken.  I have to rewrite
>>       completion-table to be like `imenu--completion-buffer' but I don't
>>       know how to pull that off.
>>
>>    3. `imenu-xref--in-alist' is mostly a 1-1 copy of `imenu--in-alist'
>>       with the only difference being my function returns all matches of
>>       the symbol instead of just the first one.  This should be easy
>>       enough to fix by adding an optional argument INCLUDE-ALL to
>>       `imenu--in-alist'.
>>
>> I'm testing in python-mode with the following settings,
>>
>>      (setq imenu-name-lookup-function (lambda (symbol item) (string-prefix-p symbol item))
>>            python-imenu-format-parent-item-jump-label-function (lambda (_ name) name))
> 
> I solved (2) by using an affixation function.  I did (3) as well, and
> I'm attaching my work as a patch against imenu.el.

(1) sounds reasonable because the reference might easily be in another 
file. If you wanted to add extra customizations (for the user to be able 
to indicated things like "use imenu for xref in these files"), maybe add 
it to this backend's options. 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).

I would leave that to a later revision, though. Some testing for 
performance regressions in large projects would be nice too.

(2) Could you try to explain the problem that you were solving here? 
affixation-function is normally about how the completions look (I 
think). Would 'completion-table-with-predicate' help? Or maybe you just 
need to pre-process the nested structure into a "flat" completion table 
first.

bug#28407: 26.0.50; xref should use imenu

[Visuwesh]

[திங்கள் மே 30, 2022] Dmitry Gutov wrote:

> Hi Visuwesh,
>

Hi Dmitry!

> On 16.05.2022 09:59, Visuwesh wrote:
>> [ஞாயிறு மே 15, 2022] Visuwesh wrote:
>> 
>>> [திங்கள் செப்டம்பர் 11, 2017] Dmitry Gutov wrote:
>>>
>>>> On 9/10/17 7:23 PM, Tom Tromey wrote:
>>>>> It would be nice if imenu were a back end for xref.
>>>>> Then M-. could also use symbols found by imenu.
>>>>> A further wrinkle on this would be if xref, project, and imenu
>>>>> worked
>>>>> together, so that M-. would automatically know to look at imenu results
>>>>> for other buffers in the same project.
>>>>
>>>> Agreed. It could be a nice default for when no tags table is currently
>>>> visited.
>>>
>>> I tried to write a general imenu backend in attached file (extracted
>>> from my init.el) but I hit quite a few roadblocks,
>>>
>>>    1. I activate the imenu backend iff there are no tags table defined
>>>       for the buffer but this means that one cannot use the imenu
>>>       backend to jump to definitions for symbols that TAGS do not know
>>>       of currently.  I can think of two ways to solve this problem,
>>>
>>>       (a) Check if the symbol is in TAGS table.
>>>       (b) Modify the etags backend so that the user can say "I have no
>>>       TAGS table for this file/project/whatever."
>>>
>>>       (a) is definitely not clean, and (b) sounds feasible but similar
>>>       situation can also exist with other backends (like elisp).
>>>
>>>       I'm lost on how to solve this problem.
>>>
>>>    2. I have not defined all the methods and the completion-table does
>>>       not handle the nested case of the index alist.  AFAIU from `(elisp)
>>>       Programmed Completion', completion "ends" when `try-completion'
>>>       returns t but I seem to be mistaken.  I have to rewrite
>>>       completion-table to be like `imenu--completion-buffer' but I don't
>>>       know how to pull that off.
>>>
>>>    3. `imenu-xref--in-alist' is mostly a 1-1 copy of `imenu--in-alist'
>>>       with the only difference being my function returns all matches of
>>>       the symbol instead of just the first one.  This should be easy
>>>       enough to fix by adding an optional argument INCLUDE-ALL to
>>>       `imenu--in-alist'.
>>>
>>> I'm testing in python-mode with the following settings,
>>>
>>>      (setq imenu-name-lookup-function (lambda (symbol item) (string-prefix-p symbol item))
>>>            python-imenu-format-parent-item-jump-label-function (lambda (_ name) name))
>> I solved (2) by using an affixation function.  I did (3) as well,
>> and
>> I'm attaching my work as a patch against imenu.el.
>
> (1) sounds reasonable because the reference might easily be in another
> file. If you wanted to add extra customizations (for the user to be
> able to indicated things like "use imenu for xref in these files"),
> maybe add it to this backend's options. 

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?

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)

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

> I would leave that to a later revision, though. Some testing for
> performance regressions in large projects would be nice too.

Indeed.  Unfortunately, I don't have any large projects on hand.  All
the testing I did was in a small python script of mine.

> (2) Could you try to explain the problem that you were solving here?
> affixation-function is normally about how the completions look (I
> think). Would 'completion-table-with-predicate' help? Or maybe you
> just need to pre-process the nested structure into a "flat" completion
> table first.

I did the pre-processing but I hit a block wrt how the
xref-backend-definitions method worked.  To illustrate, in the test file
that I had I have a function that goes like

    def do1():
        ...
        
        def checkforlink1():
        ...

        def checkforlink2():
        ...

        def sortlinks():
        ...
            def weight():
            ...

        def checkforlink():
        ...

and the imenu--index-alist for this part looks like

    ("do1 (def)"
      ("do1" . #<marker at 2413 in rdscrape.py>)
      ("checkforlink1 (def)" . #<marker at 2850 in rdscrape.py>)
      ("checkforlink2 (def)" . #<marker at 3363 in rdscrape.py>)
      ("sortlinks (def)"
       ("sortlinks" . #<marker at 3721 in rdscrape.py>)
       ("weight (def)" . #<marker at 3747 in rdscrape.py>))
      ("checkforlink (def)" . #<marker at 4121 in rdscrape.py>))

I wrote the flatten function so that it would produce completion
candidates like

"do1:do1" "do1:checkforlink1 (def)" "do1:checkforlink2 (def)" ... and so
on.

But the xref-backend-definitions method can only handle the last part of
it (i.e., "do1" "checkforlink1 (def)").  Since I didn't feel like
parsing this "path-tree" (for a lack of a better word) would be
appropriate for xref-backend-definitions, I slapped this "path-tree" as
cosmetics in the affixation-function instead.  Hopefully, this makes
sense.

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.

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?

    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?

bug#28407: 26.0.50; xref should use imenu

[Dmitry Gutov]

On 30.05.2022 07:18, Visuwesh wrote:
> [திங்கள் மே 30, 2022] Dmitry Gutov wrote:
> 
>> Hi Visuwesh,
>>
> 
> Hi Dmitry!
> 
>> On 16.05.2022 09:59, Visuwesh wrote:
>>> [ஞாயிறு மே 15, 2022] Visuwesh wrote:
>>>
>>>> [திங்கள் செப்டம்பர் 11, 2017] Dmitry Gutov wrote:
>>>>
>>>>> On 9/10/17 7:23 PM, Tom Tromey wrote:
>>>>>> It would be nice if imenu were a back end for xref.
>>>>>> Then M-. could also use symbols found by imenu.
>>>>>> A further wrinkle on this would be if xref, project, and imenu
>>>>>> worked
>>>>>> together, so that M-. would automatically know to look at imenu results
>>>>>> for other buffers in the same project.
>>>>>
>>>>> Agreed. It could be a nice default for when no tags table is currently
>>>>> visited.
>>>>
>>>> I tried to write a general imenu backend in attached file (extracted
>>>> from my init.el) but I hit quite a few roadblocks,
>>>>
>>>>     1. I activate the imenu backend iff there are no tags table defined
>>>>        for the buffer but this means that one cannot use the imenu
>>>>        backend to jump to definitions for symbols that TAGS do not know
>>>>        of currently.  I can think of two ways to solve this problem,
>>>>
>>>>        (a) Check if the symbol is in TAGS table.
>>>>        (b) Modify the etags backend so that the user can say "I have no
>>>>        TAGS table for this file/project/whatever."
>>>>
>>>>        (a) is definitely not clean, and (b) sounds feasible but similar
>>>>        situation can also exist with other backends (like elisp).
>>>>
>>>>        I'm lost on how to solve this problem.
>>>>
>>>>     2. I have not defined all the methods and the completion-table does
>>>>        not handle the nested case of the index alist.  AFAIU from `(elisp)
>>>>        Programmed Completion', completion "ends" when `try-completion'
>>>>        returns t but I seem to be mistaken.  I have to rewrite
>>>>        completion-table to be like `imenu--completion-buffer' but I don't
>>>>        know how to pull that off.
>>>>
>>>>     3. `imenu-xref--in-alist' is mostly a 1-1 copy of `imenu--in-alist'
>>>>        with the only difference being my function returns all matches of
>>>>        the symbol instead of just the first one.  This should be easy
>>>>        enough to fix by adding an optional argument INCLUDE-ALL to
>>>>        `imenu--in-alist'.
>>>>
>>>> I'm testing in python-mode with the following settings,
>>>>
>>>>       (setq imenu-name-lookup-function (lambda (symbol item) (string-prefix-p symbol item))
>>>>             python-imenu-format-parent-item-jump-label-function (lambda (_ name) name))
>>> I solved (2) by using an affixation function.  I did (3) as well,
>>> and
>>> I'm attaching my work as a patch against imenu.el.
>>
>> (1) sounds reasonable because the reference might easily be in another
>> file. If you wanted to add extra customizations (for the user to be
>> able to indicated things like "use imenu for xref in these files"),
>> maybe add it to this backend's options.
> 
> 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.

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

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

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.

Yes another approach, would be to program a "backend combinator" 
function. Then people would be able to slap together a bunch of 
backends, but all of them would be queried together eagerly, so it's not 
a failover-like solution.

>> I would leave that to a later revision, though. Some testing for
>> performance regressions in large projects would be nice too.
> 
> Indeed.  Unfortunately, I don't have any large projects on hand.  All
> the testing I did was in a small python script of mine.
> 
>> (2) Could you try to explain the problem that you were solving here?
>> affixation-function is normally about how the completions look (I
>> think). Would 'completion-table-with-predicate' help? Or maybe you
>> just need to pre-process the nested structure into a "flat" completion
>> table first.
> 
> I did the pre-processing but I hit a block wrt how the
> xref-backend-definitions method worked.  To illustrate, in the test file
> that I had I have a function that goes like
> 
>      def do1():
>          ...
>          
>          def checkforlink1():
>          ...
> 
>          def checkforlink2():
>          ...
> 
>          def sortlinks():
>          ...
>              def weight():
>              ...
> 
>          def checkforlink():
>          ...
> 
> and the imenu--index-alist for this part looks like
> 
>      ("do1 (def)"
>        ("do1" . #<marker at 2413 in rdscrape.py>)
>        ("checkforlink1 (def)" . #<marker at 2850 in rdscrape.py>)
>        ("checkforlink2 (def)" . #<marker at 3363 in rdscrape.py>)
>        ("sortlinks (def)"
>         ("sortlinks" . #<marker at 3721 in rdscrape.py>)
>         ("weight (def)" . #<marker at 3747 in rdscrape.py>))
>        ("checkforlink (def)" . #<marker at 4121 in rdscrape.py>))
> 
> I wrote the flatten function so that it would produce completion
> candidates like
> 
> "do1:do1" "do1:checkforlink1 (def)" "do1:checkforlink2 (def)" ... and so
> on.
> 
> But the xref-backend-definitions method can only handle the last part of
> it (i.e., "do1" "checkforlink1 (def)").  Since I didn't feel like
> parsing this "path-tree" (for a lack of a better word) would be
> appropriate for xref-backend-definitions, I slapped this "path-tree" as
> cosmetics in the affixation-function instead.  Hopefully, this makes
> sense.

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.

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

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

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

bug#28407: 26.0.50; xref should use imenu

[Visuwesh]

[-- 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

bug#28407: 26.0.50; xref should use imenu

[Eli Zaretskii]

> Cc: Tom Tromey <tom@tromey.com>, 28407@debbugs.gnu.org
> From: Visuwesh <visuweshm@gmail.com>
> Date: Sat, 25 Jun 2022 19:34:48 +0530
> 
> [ 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.  ]

In general, when you visit a new TAGS file, etags asks you whether to
replace the previous one or to keep them both.  Maybe the way you
"switch to another project" somehow hides that prompt/decision?

bug#28407: 26.0.50; xref should use imenu

[Visuwesh]

[சனி ஜூன் 25, 2022] Eli Zaretskii wrote:

>> Cc: Tom Tromey <tom@tromey.com>, 28407@debbugs.gnu.org
>> From: Visuwesh <visuweshm@gmail.com>
>> Date: Sat, 25 Jun 2022 19:34:48 +0530
>> 
>> [ 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.  ]
>
> In general, when you visit a new TAGS file, etags asks you whether to
> replace the previous one or to keep them both.  Maybe the way you
> "switch to another project" somehow hides that prompt/decision?

It does ask me to replace the previous one but I expected Emacs to
restrict the TAGS file to the buffer I selected it from, mostly because
I was mislead to believe the check (or tags-table-files tags-file-name)
would work that way.
[ The check is from a previous revision of my patch.  ]

bug#28407: 26.0.50; xref should use imenu

[Eli Zaretskii]

> From: Visuwesh <visuweshm@gmail.com>
> Cc: tom@tromey.com,  28407@debbugs.gnu.org,  dgutov@yandex.ru
> Date: Sat, 25 Jun 2022 20:07:25 +0530
> 
> [சனி ஜூன் 25, 2022] Eli Zaretskii wrote:
> 
> > In general, when you visit a new TAGS file, etags asks you whether to
> > replace the previous one or to keep them both.  Maybe the way you
> > "switch to another project" somehow hides that prompt/decision?
> 
> It does ask me to replace the previous one but I expected Emacs to
> restrict the TAGS file to the buffer I selected it from

That'd be against the purpose of TAGS tables: their explicit purpose
is to allow you to find definitions in _other_ files.  And Emacs
cannot know whether the fact that you loaded another TAGS table means
that you want to "forget" about the previous one, as long as you keep
it loaded.