bug#38614: 26.3; Info completions in reverse order

bug#38614: 26.3; Info completions in reverse order

[Howard Melman]

When using ivy mode, Info-index shows me the list of
completions in reverse alphabetical order. Info-menu does too.
Both Info-index and Info-menu use completing-read with
Info-complete-menu-item as the collections argument. It
seems to generate the list in reverse order.

Sorry this isn't a formatted patch, but a one line fix solves it for me.

If after this line in Info-complete-menu-item:
		    (setq completions (delete-dups completions))
I add this line:
		    (setq completions (nreverse completions))
the index and menus are shown in alphabetical order.

Howard


In GNU Emacs 26.3 (build 1, x86_64-apple-darwin18.2.0, NS appkit-1671.20 Version 10.14.3 (Build 18D109))
of 2019-09-02 built on builder10-14.porkrind.org
Windowing system distributor 'Apple', version 10.3.1671
Recent messages:
Checking 70 files in /private/var/folders/q0/v8nhk8253wq275jzgwr2628c0000gs/T/AppTranslocation/3AF5DBC9-944F-4569-9CE5-149C53A27F04/d/Emacs.app/Contents/Resources/lisp/erc...
Checking 34 files in /private/var/folders/q0/v8nhk8253wq275jzgwr2628c0000gs/T/AppTranslocation/3AF5DBC9-944F-4569-9CE5-149C53A27F04/d/Emacs.app/Contents/Resources/lisp/emulation...
Checking 176 files in /private/var/folders/q0/v8nhk8253wq275jzgwr2628c0000gs/T/AppTranslocation/3AF5DBC9-944F-4569-9CE5-149C53A27F04/d/Emacs.app/Contents/Resources/lisp/emacs-lisp...
Checking 24 files in /private/var/folders/q0/v8nhk8253wq275jzgwr2628c0000gs/T/AppTranslocation/3AF5DBC9-944F-4569-9CE5-149C53A27F04/d/Emacs.app/Contents/Resources/lisp/cedet...
Checking 57 files in /private/var/folders/q0/v8nhk8253wq275jzgwr2628c0000gs/T/AppTranslocation/3AF5DBC9-944F-4569-9CE5-149C53A27F04/d/Emacs.app/Contents/Resources/lisp/calendar...
Checking 87 files in /private/var/folders/q0/v8nhk8253wq275jzgwr2628c0000gs/T/AppTranslocation/3AF5DBC9-944F-4569-9CE5-149C53A27F04/d/Emacs.app/Contents/Resources/lisp/calc...
Checking 105 files in /private/var/folders/q0/v8nhk8253wq275jzgwr2628c0000gs/T/AppTranslocation/3AF5DBC9-944F-4569-9CE5-149C53A27F04/d/Emacs.app/Contents/Resources/lisp/obsolete...
Checking for load-path shadows...done
Quit [2 times]
Mark set
Quit [2 times]
Configured using:
'configure --with-ns
'--enable-locallisppath=/Library/Application
Support/Emacs/${version}/site-lisp:/Library/Application
Support/Emacs/site-lisp' --with-modules'

Configured features:
NOTIFY ACL GNUTLS LIBXML2 ZLIB TOOLKIT_SCROLL_BARS NS
MODULES THREADS

Important settings:
  value of $LANG: en_US.UTF-8
  locale-coding-system: utf-8-unix

Major mode: Lisp Interaction

Minor modes in effect:
  ivy-mode: t
  wrap-region-global-mode: t
  wrap-region-mode: t
  beacon-mode: t
  magit-todos-mode: t
  global-magit-file-mode: t
  diff-auto-refine-mode: t
  magit-auto-revert-mode: t
  global-git-commit-mode: t
  async-bytecomp-package-mode: t
  outline-minor-mode: t
  pyvenv-mode: t
  shell-dirtrack-mode: t
  global-hl-todo-mode: t
  hl-todo-mode: t
  which-key-mode: t
  which-function-mode: t
  show-paren-mode: t
  recentf-mode: t
  diredfl-global-mode: t
  tooltip-mode: t
  global-eldoc-mode: t
  eldoc-mode: t
  electric-indent-mode: t
  mouse-wheel-mode: t
  menu-bar-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
  size-indication-mode: t
  column-number-mode: t
  line-number-mode: t
  transient-mark-mode: t

Load-path shadows:
/Users/hmelman/.emacs.d/elpa/seq-20151121.1017/seq hides /private/var/folders/q0/v8nhk8253wq275jzgwr2628c0000gs/T/AppTranslocation/3AF5DBC9-944F-4569-9CE5-149C53A27F04/d/Emacs.app/Contents/Resources/lisp/emacs-lisp/seq
/Users/hmelman/.emacs.d/elpa/let-alist-1.0.6/let-alist hides /private/var/folders/q0/v8nhk8253wq275jzgwr2628c0000gs/T/AppTranslocation/3AF5DBC9-944F-4569-9CE5-149C53A27F04/d/Emacs.app/Contents/Resources/lisp/emacs-lisp/let-alist

Features:
(ange-ftp tramp-ftp magit-bookmark bookmark pp shadow sort
mail-extr emacsbug sendmail counsel xdg swiper jka-compr
face-remap lisp-mnt notes ivy-rich ivy delsel colir color
ivy-overlay ace-link avy rg vc vc-dispatcher rg-info-hack
rg-menu rg-ibuffer rg-result wgrep-rg wgrep rg-history
rg-header ibuf-ext ibuffer ibuffer-loaddefs wrap-region
expand-region text-mode-expansions the-org-mode-expansions
python-el-fgallina-expansions er-basic-expansions
expand-region-core expand-region-custom beacon
symbol-overlay magit-todos pcre2el rxt re-builder
magit-submodule magit-obsolete magit-popup magit-blame
magit-stash magit-reflog magit-bisect magit-push magit-pull
magit-fetch magit-clone magit-remote magit-commit
magit-sequence magit-notes magit-worktree magit-tag
magit-merge magit-branch magit-reset magit-files magit-refs
magit-status magit magit-repos magit-apply magit-wip
magit-log magit-diff smerge-mode diff-mode magit-core
magit-autorevert autorevert filenotify magit-margin
magit-transient magit-process magit-mode git-commit
magit-git magit-section magit-utils crm log-edit message rmc
puny rfc822 mml mml-sec epa derived epg mm-decode mm-bodies
mm-encode mail-parse rfc2231 mailabbrev gmm-utils mailheader
pcvs-util add-log with-editor async-bytecomp server f async
org-element avl-tree generator org-location-google-maps
org-agenda google-maps google-maps-static url-util
google-maps-geocode google-maps-base org org-macro
org-footnote org-pcomplete org-list org-faces org-entities
noutline outline easy-mmode org-version ob-R ob-emacs-lisp
ob ob-tangle org-src ob-ref ob-lob ob-table ob-keys ob-exp
ob-comint ob-core ob-eval org-compat org-macs org-loaddefs
cal-menu calendar cal-loaddefs visual-regexp
dired-quick-sort hydra lv savehist ls-lisp dired-x
python-black reformatter yasnippet elec-pair flymake-proc
flymake warnings thingatpt company-capf company pcase
help-fns radix-tree elpy edmacro kmacro elpy-rpc pyvenv
esh-var esh-io esh-cmd esh-opt esh-ext esh-proc esh-arg
esh-groups eshell esh-module esh-mode esh-util elpy-shell
elpy-profile elpy-django s elpy-refactor subr-x python
tramp-sh tramp tramp-compat tramp-loaddefs trampver shell
pcomplete parse-time json map ido grep compile comint
ansi-color files-x etags xref project ring cus-edit hl-todo
which-key dim transient cl-extra help-mode format-spec
browse-url exec-path-from-shell find-func dash saveplace
which-func imenu paren recentf tree-widget gnus nnheader
gnus-util rmail rmail-loaddefs rfc2047 rfc2045 ietf-drums
mail-utils mm-util mail-prsvr wid-edit diredfl dired
dired-loaddefs cus-start cus-load finder-inf rx advice 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 tooltip
eldoc electric uniquify ediff-hook vc-hooks lisp-float-type
mwheel term/ns-win ns-win ucs-normalize mule-util
term/common-win 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 threads kqueue cocoa ns multi-tty
make-network-process emacs)

Memory information:
((conses 16 611063 284115)
(symbols 48 50893 46)
(miscs 40 1505 180)
(strings 32 163440 32697)
(string-bytes 1 4837255)
(vectors 16 80740)
(vector-slots 8 1508008 87522)
(floats 8 415 609)
(intervals 56 4828 0)
(buffers 992 15))

bug#38614: 26.3; Info completions in reverse order

[Eli Zaretskii]

> From: Howard Melman <hmelman@gmail.com>
> Date: Sat, 14 Dec 2019 12:18:54 -0500
> 
> When using ivy mode, Info-index shows me the list of
> completions in reverse alphabetical order. Info-menu does too.
> Both Info-index and Info-menu use completing-read with
> Info-complete-menu-item as the collections argument. It
> seems to generate the list in reverse order.
> 
> Sorry this isn't a formatted patch, but a one line fix solves it for me.
> 
> If after this line in Info-complete-menu-item:
> 		    (setq completions (delete-dups completions))
> I add this line:
> 		    (setq completions (nreverse completions))
> the index and menus are shown in alphabetical order.

Sorry, I don't understand: when I type "i SUBJECT" and press TAB in
Info, I get completions in alphabetical order, so how come with ivy
you get the reverse order?

bug#38614: 26.3; Info completions in reverse order

[Howard Melman]

(Sorry if this is a resend, I don't think I included debbugs in my original reply)

> On Dec 15, 2019, at 11:06 AM, Eli Zaretskii <eliz@gnu.org> wrote:
> 
>> From: Howard Melman <hmelman@gmail.com>
>> Date: Sat, 14 Dec 2019 12:18:54 -0500
>> 
>> When using ivy mode, Info-index shows me the list of
>> completions in reverse alphabetical order. Info-menu does too.
>> Both Info-index and Info-menu use completing-read with
>> Info-complete-menu-item as the collections argument. It
>> seems to generate the list in reverse order.
>> 
>> Sorry this isn't a formatted patch, but a one line fix solves it for me.
>> 
>> If after this line in Info-complete-menu-item:
>> 		    (setq completions (delete-dups completions))
>> I add this line:
>> 		    (setq completions (nreverse completions))
>> the index and menus are shown in alphabetical order.
> 
> Sorry, I don't understand: when I type "i SUBJECT" and press TAB in
> Info, I get completions in alphabetical order, so how come with ivy
> you get the reverse order?

I tried that in Emacs 26.3 with -Q and and I see an alphabetical list. I'm not sure what mechanism that's using and I don't particularly know icomplete or ido, though I tried enabling each and saw the same alphabetical list. 

Note that's not quite the same thing as I was describing. Ivy has two sort mechanisms. Ivy displays a list of possible completions (from the collections argument of completing-read) BEFORE you enter any text (SUBJECT in your case). There's no need to hit TAB to see the completions. Then after you enter text it displays completions that are sorted via a different mechanism (because the various matching mechanisms and what you type might indicate a different sort order from the original completions list such as: shorter matches first, prefix matches first, or just alphabetical). AFAIK, Ivy usually doesn't do a sort of the initial list because often it's in a useful order other than alphabetical.

It's clearer in the Info-menu case, where my desired order is the order of the menu items in the info buffer. Using emacs -Q, Info-menu and TAB shows me an alphabetical list. That tells me that whatever mechanism it's using is sorting the list alphabetically and not using the original order of the collection list. 

Ivy shows me the menu items in reverse buffer order because the original collection list presented to ivy (via completing-read) is in reverse order as found in the buffer. Info-complete-menu-item is clearly pushing onto a list and then not nreversing it as is the common idiom. 

I got a bit lost following the elisp docs for Programmed Completion but didn't see any guidelines about the order of the collections intially returned (Info-complete-menu-item doesn't seem to be setting a display-sort-function which I think is the mechanism but I got lost).

Info uses the same function to build the collection list for both Info-menu and Info-index. In the Info-index case the order from the buffer is alphabetical, so Info-complete-menu-item is returning a collection list in reverse alphabetical order. 

Info-complete-menu-item is saving the cost of an nreverse. It would be useful if it returned the items in the order as found in the buffer, because that order isn't always easily recreated after sorting. In the Info-menu case, that's a logical order of the menu items. In the Info-index case, that happens to be alphabetical without the need for an additional sort.

buffer-list returns the buffers in most recently displayed order because it's useful. I think Info-complete-menu-item should return it's items in a logical order too (and not the reverse of one) even if some popular completion mechanisms hide this by always sorting the list alphabetically before display. 

Ivy seems to show other initial completions in a useful order, to me it seems only it's display of Info commands is wrong, because of this missing idomatic nreverse.

Howard

bug#38614: 26.3; Info completions in reverse order

[Howard Melman]

I wrote on Sat, 14 Dec 2019:

> When using ivy mode, Info-index shows me the list of
> completions in reverse alphabetical order. Info-menu does too.
> Both Info-index and Info-menu use completing-read with
> Info-complete-menu-item as the collections argument. It
> seems to generate the list in reverse order.
> 
> Sorry this isn't a formatted patch, but a one line fix solves it for me.
> 
> If after this line in Info-complete-menu-item:
> 		    (setq completions (delete-dups completions))
> I add this line:
> 		    (setq completions (nreverse completions))
> the index and menus are shown in alphabetical order.


My original fix was in the wrong place. It only worked for info files that had a single index node (e.g., elisp.info). To work more generally with files with several index nodes (e.g., emacs.info) the new line should be just before the cache is updated:

              (setq completions (nreverse completions))  ; added fix
              ;; Update the cache.
              (setq Info-complete-cache
		    (list Info-current-file Info-current-node
			  Info-complete-next-re string completions
			  Info-complete-nodes)))
		
I still hope this is considered. The cost of the nreverse here is small, and if completion mechanisms sort the list later, they'll find an already sorted list will sort faster than the degenerate case of sorting a list already in reverse order.

Howard

bug#38614: 26.3; Info completions in reverse order

[Stefan Kangas]

Howard Melman <hmelman@gmail.com> writes:

>>> When using ivy mode, Info-index shows me the list of
>>> completions in reverse alphabetical order. Info-menu does too.
>>> Both Info-index and Info-menu use completing-read with
>>> Info-complete-menu-item as the collections argument. It
>>> seems to generate the list in reverse order.
>>>
>>> Sorry this isn't a formatted patch, but a one line fix solves it for me.
>>>
>>> If after this line in Info-complete-menu-item:
>>> 		    (setq completions (delete-dups completions))
>>> I add this line:
>>> 		    (setq completions (nreverse completions))
>>> the index and menus are shown in alphabetical order.

Won't the proposed change:

  a) Not delete duplicates.
  b) Reverse the list of completions for everyone else (ido, etc.)?

>> Sorry, I don't understand: when I type "i SUBJECT" and press TAB in
>> Info, I get completions in alphabetical order, so how come with ivy
>> you get the reverse order?
>
> I tried that in Emacs 26.3 with -Q and and I see an alphabetical
> list. I'm not sure what mechanism that's using and I don't
> particularly know icomplete or ido, though I tried enabling each and
> saw the same alphabetical list.

Shouldn't this bug be reported to the ivy developers first then?  It
sounds a lot like there is something that ido and icomplete is doing
that ivy is not.

Best regards,
Stefan Kangas

bug#38614: 26.3; Info completions in reverse order

[Howard Melman]

> On Aug 25, 2020, at 7:09 PM, Stefan Kangas <stefan@marxist.se> wrote:
> 
> Howard Melman <hmelman@gmail.com> writes:
> 
>>>> When using ivy mode, Info-index shows me the list of
>>>> completions in reverse alphabetical order. Info-menu does too.
>>>> Both Info-index and Info-menu use completing-read with
>>>> Info-complete-menu-item as the collections argument. It
>>>> seems to generate the list in reverse order.
>>>> 
>>>> Sorry this isn't a formatted patch, but a one line fix solves it for me.
>>>> 
>>>> If after this line in Info-complete-menu-item:
>>>> 		    (setq completions (delete-dups completions))
>>>> I add this line:
>>>> 		    (setq completions (nreverse completions))
>>>> the index and menus are shown in alphabetical order.
> 
> Won't the proposed change:
> 
>  a) Not delete duplicates.

No, it adds a line, it doesn't replace it.  (Also note my correction of 3 Jan 2020 that puts the reverse just before the ";; Update the cache."

>  b) Reverse the list of completions for everyone else (ido, etc.)?

No, and I tried to explain it in a previous reply.

While I don't particularly know ido code and only know a little of ivy, I think understand what's happening here.  Both ivy and standard emacs facilities use the list of candidates passed to completing-read, in this case that's code that's part of info-mode and not an ivy function or an ido function. 

Ivy will show a list of candidates immediately, before you type any input, and once you start typing input, will narrow and sort that list of candidates (using some criteria).  ido (or whatever emacs' default is) AFAIU doesn't show candidates before you hit TAB and once you do, it shows a sorted list of matching candidates.

The bug here, is that the initial list, generated by info-mode code, the one ivy shows and ido doesn't, returns the candidates in list in the reverse order it found them in the buffer (unlike other places that generate candidate lists).  I agree, there's no requirement about the order of the initial candidates list, but it would be reasonable for the list, in this case, generated from an info page, to be in the order they appear in the page, and while base emacs doesn't make use of that order, ivy would (and possibly helm, I'm not sure).  

AFAIK users of the standard emacs facilities will see no functional change by this.  There's just the cost of the nreverse, which given the number of menu entries in an info page should be negligible and in some cases, like info indexes that are in alphabetical order initially, this should be faster, because for a list already in reverse alphabetical order, nreverse and sort could be faster than just sort.

Howard

bug#38614: 26.3; Info completions in reverse order

[Stefan Kangas]

close 38614 28.1
thanks

Howard Melman <hmelman@gmail.com> writes:

> While I don't particularly know ido code and only know a little of
> ivy, I think understand what's happening here.  Both ivy and standard
> emacs facilities use the list of candidates passed to completing-read,
> in this case that's code that's part of info-mode and not an ivy
> function or an ido function.
>
> Ivy will show a list of candidates immediately, before you type any
> input, and once you start typing input, will narrow and sort that list
> of candidates (using some criteria).  ido (or whatever emacs' default
> is) AFAIU doesn't show candidates before you hit TAB and once you do,
> it shows a sorted list of matching candidates.
>
> The bug here, is that the initial list, generated by info-mode code,
> the one ivy shows and ido doesn't, returns the candidates in list in
> the reverse order it found them in the buffer (unlike other places
> that generate candidate lists).  I agree, there's no requirement about
> the order of the initial candidates list, but it would be reasonable
> for the list, in this case, generated from an info page, to be in the
> order they appear in the page, and while base emacs doesn't make use
> of that order, ivy would (and possibly helm, I'm not sure).
>
> AFAIK users of the standard emacs facilities will see no functional
> change by this.  There's just the cost of the nreverse, which given
> the number of menu entries in an info page should be negligible and in
> some cases, like info indexes that are in alphabetical order
> initially, this should be faster, because for a list already in
> reverse alphabetical order, nreverse and sort could be faster than
> just sort.

Thanks for the explanation.  I think your reasoning here makes sense.

I made the change and tested the default, ido-mode, fido-mode and
icomplete.  I did not observe any regressions in terms of performance or
sort order for any of them.

In addition, I have also been bothered by this issue in the past using
Ivy, and can confirm that the proposed fix solves the issue.

So I have now made that change on the master branch (commit 5a1785d58a).
If anyone notices any adverse effects from this change, feel free to
revert it.

I'm closing this bug report with this message.

Best regards,
Stefan Kangas

bug#38614: 26.3; Info completions in reverse order

[Howard Melman]

> On Aug 26, 2020, at 7:20 PM, Stefan Kangas <stefan@marxist.se> wrote:
> 
> I made the change and tested the default, ido-mode, fido-mode and
> icomplete.  I did not observe any regressions in terms of performance or
> sort order for any of them.
> 
> In addition, I have also been bothered by this issue in the past using
> Ivy, and can confirm that the proposed fix solves the issue.
> 
> So I have now made that change on the master branch (commit 5a1785d58a).
> If anyone notices any adverse effects from this change, feel free to
> revert it.

Thank you for doing this.

I have one small comment on your patch.  The comment "Sort list alphabetically." is not correct.  The result of adding the call to nreverse means the list will be in the order the items were found in the info node.  In the case of an index node that will be alphabetically, in the case of other nodes, it is unlikely to be.

Is it the case that this won't show up until Emacs 28.1?

Howard

bug#38614: 26.3; Info completions in reverse order

[Stefan Kangas]

Howard Melman <hmelman@gmail.com> writes:

> I have one small comment on your patch.  The comment "Sort list
> alphabetically." is not correct.  The result of adding the call to
> nreverse means the list will be in the order the items were found in
> the info node.  In the case of an index node that will be
> alphabetically, in the case of other nodes, it is unlikely to be.

Hmm, indeed.  I do want some kind of explanation for why we want to do
an nreverse there.  Would this be more accurate?

;; Arrange list to be in order found in node.

> Is it the case that this won't show up until Emacs 28.1?

Yes.

bug#38614: 26.3; Info completions in reverse order

[Howard Melman]

> On Aug 26, 2020, at 8:04 PM, Stefan Kangas <stefan@marxist.se> wrote:
> 
> Hmm, indeed.  I do want some kind of explanation for why we want to do
> an nreverse there.  Would this be more accurate?
> 
> ;; Arrange list to be in order found in node.

Perfect.

Howard

bug#38614: 26.3; Info completions in reverse order

[Stefan Kangas]

Howard Melman <hmelman@gmail.com> writes:

>> ;; Arrange list to be in order found in node.
>
> Perfect.

Thanks, pushed.