[WIP PATCH] Adding keys to keymaps in alphabetical order (for use with `mode-line-mode-menu')

[WIP PATCH] Adding keys to keymaps in alphabetical order (for use with `mode-line-mode-menu')

[Jim Porter]

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

Currently, there's not a simple way of inserting a key binding into a
keymap in alphabetical order. This would be nice for
`mode-line-mode-menu'; to see the issue, you can run the following:

  emacs -Q
  <mouse-3> ;; on the mode name in the mode-line
  ;; See the nice alphabetical list
  M-x ruler-mode
  <mouse-3> ;; on the mode name in the mode-line again
  ;; "Ruler" is first(?!)

I believe `ruler-mode' is the only place in Emacs itself that has this
issue, but third-party packages (or user configs) might want to add to
`mode-line-mode-menu'. For example, I prefer to get rid of the
mode-line lighter for `company-mode' and put an item for it into
`mode-line-mode-menu' for the rare times I want to check/change its
status. Especially with packages that get loaded after startup, the
current behavior could be somewhat confusing since the order items are
added to the menu can vary.

I've attached a simple patch that fixes this by adding a
`define-key-sorted' function. I imagine it still needs some work to
handle more complex cases, but it works well enough for
`mode-line-mode-menu'.

- Jim

[-- Attachment #2: 0001-Add-define-key-sorted-to-simplify-entering-menu-item.patch --]
[-- Type: application/octet-stream, Size: 2260 bytes --]

From 880a83c661baff6890e0ba6fcb606d428a92b226 Mon Sep 17 00:00:00 2001
From: Jim Porter <jporterbugs@gmail.com>
Date: Thu, 17 Jun 2021 20:38:47 -0700
Subject: [PATCH] Add 'define-key-sorted' to simplify entering menu items in
 alphabetical order

* lisp/subr.el (define-key-sorted): New function.
* lisp/ruler-mode.el: Use 'define-key-sorted' instead of 'define-key'.
---
 lisp/ruler-mode.el |  2 +-
 lisp/subr.el       | 20 ++++++++++++++++++++
 2 files changed, 21 insertions(+), 1 deletion(-)

diff --git a/lisp/ruler-mode.el b/lisp/ruler-mode.el
index a0d4f6e96c..aba27930db 100644
--- a/lisp/ruler-mode.el
+++ b/lisp/ruler-mode.el
@@ -586,7 +586,7 @@ ruler-mode
     (remove-hook 'post-command-hook 'force-mode-line-update t)))
 \f
 ;; Add ruler-mode to the minor mode menu in the mode line
-(define-key mode-line-mode-menu [ruler-mode]
+(define-key-sorted mode-line-mode-menu [ruler-mode]
   '(menu-item "Ruler" ruler-mode
               :button (:toggle . ruler-mode)))
 
diff --git a/lisp/subr.el b/lisp/subr.el
index e49c277335..120c120ddb 100644
--- a/lisp/subr.el
+++ b/lisp/subr.el
@@ -1032,6 +1032,26 @@ define-key-after
 	    (setq inserted t)))
       (setq tail (cdr tail)))))
 
+(defun define-key-sorted (keymap key definition)
+  "Add binding in KEYMAP for KEY => DEFINITION, sorted in alphabetical order.
+This is like `define-key' except that the binding for KEY is placed
+in alphabetical order within the keymap.
+
+The order of bindings in a keymap matters only when it is used as
+a menu, so this function is not useful for non-menu keymaps."
+  (or (keymapp keymap)
+      (signal 'wrong-type-argument (list 'keymapp keymap)))
+  (let ((tail (cdr keymap)) prev found)
+    (while (and (not found) (listp (car tail)))
+      (let ((next (car tail)))
+        (setq found (string> (caddr next) (cadr definition)))
+        (unless found
+          (setq prev next
+                tail (cdr tail)))))
+    (if prev
+        (define-key-after keymap key definition (car prev))
+      (define-key keymap key definition))))
+
 (defun define-prefix-command (command &optional mapvar name)
   "Define COMMAND as a prefix command.  COMMAND should be a symbol.
 A new sparse keymap is stored as COMMAND's function definition and its
-- 
2.25.1

Re: [WIP PATCH] Adding keys to keymaps in alphabetical order (for use with `mode-line-mode-menu')

[Lars Ingebrigtsen]

Jim Porter <jporterbugs@gmail.com> writes:

> Currently, there's not a simple way of inserting a key binding into a
> keymap in alphabetical order. This would be nice for
> `mode-line-mode-menu'; to see the issue, you can run the following:
>
>   emacs -Q
>   <mouse-3> ;; on the mode name in the mode-line
>   ;; See the nice alphabetical list
>   M-x ruler-mode
>   <mouse-3> ;; on the mode name in the mode-line again
>   ;; "Ruler" is first(?!)

Yup; I can reproduce this issue, too.

> I've attached a simple patch that fixes this by adding a
> `define-key-sorted' function. I imagine it still needs some work to
> handle more complex cases, but it works well enough for
> `mode-line-mode-menu'.

Hm...  instead of adding a new function, perhaps it would make more
sense to just make the mode menu sort entries before displaying?

-- 
(domestic pets only, the antidote for overdose, milk.)
   bloggy blog: http://lars.ingebrigtsen.no

Re: [WIP PATCH] Adding keys to keymaps in alphabetical order (for use with `mode-line-mode-menu')

[Jim Porter]

On 6/19/2021 5:31 AM, Lars Ingebrigtsen wrote:
> Jim Porter <jporterbugs@gmail.com> writes:
> 
>> I've attached a simple patch that fixes this by adding a
>> `define-key-sorted' function. I imagine it still needs some work to
>> handle more complex cases, but it works well enough for
>> `mode-line-mode-menu'.
> 
> Hm...  instead of adding a new function, perhaps it would make more
> sense to just make the mode menu sort entries before displaying?

That would also work, and have the added benefit that it's resilient 
even if a package neglects to use `define-key-sorted'.

I'll look into the best way to trigger a sort just before opening the 
menu. Ideally, we could avoid re-sorting every time (unless the list has 
changed), but that might be more work than it's worth, given that the 
list is unlikely to be more than a few dozen elements.

- Jim

Re: [WIP PATCH] Adding keys to keymaps in alphabetical order (for use with `mode-line-mode-menu')

[Lars Ingebrigtsen]

Jim Porter <jporterbugs@gmail.com> writes:

> I'll look into the best way to trigger a sort just before opening the
> menu. Ideally, we could avoid re-sorting every time (unless the list
> has changed), but that might be more work than it's worth, given that
> the list is unlikely to be more than a few dozen elements.

Yeah, menus are usually short, so just sorting should be fine, I think.

-- 
(domestic pets only, the antidote for overdose, milk.)
   bloggy blog: http://lars.ingebrigtsen.no

Re: [WIP PATCH] Adding keys to keymaps in alphabetical order (for use with `mode-line-mode-menu')

[Jim Porter]

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

On 6/21/2021 5:31 AM, Lars Ingebrigtsen wrote:
> Jim Porter <jporterbugs@gmail.com> writes:
> 
>> I'll look into the best way to trigger a sort just before opening the
>> menu. Ideally, we could avoid re-sorting every time (unless the list
>> has changed), but that might be more work than it's worth, given that
>> the list is unlikely to be more than a few dozen elements.
> 
> Yeah, menus are usually short, so just sorting should be fine, I think.

Attached is a patch that I think should do this. I've only tested the 
new functions with `mode-line-mode-menu', so they might not work on all 
menus (hence, I've made them private for now). It's possible these 
functions would be more broadly useful, though.

Performance-wise, the cost is negligible for the default value of 
`mode-line-mode-menu': ~10ms for the first time and 0.02ms for 
subsequent calls.

- Jim

[-- Attachment #2: 0001-Sort-the-items-in-mode-line-mode-menu-before-display.patch --]
[-- Type: text/plain, Size: 3004 bytes --]

From f25ba15da1148ee24c70e44f3d144fdf879edb0e Mon Sep 17 00:00:00 2001
From: Jim Porter <jporterbugs@gmail.com>
Date: Tue, 22 Jun 2021 21:52:37 -0700
Subject: [PATCH] Sort the items in 'mode-line-mode-menu' before displaying the
 menu

* lisp/bindings.el (bindings--menu-item-string, bindings--sort-keymap):
New functions.
(mode-line-major-mode-keymap, mode-line-minor-mode-keymap):
Sort 'mode-line-mode-menu'.
---
 lisp/bindings.el | 37 +++++++++++++++++++++++++++++++++----
 1 file changed, 33 insertions(+), 4 deletions(-)

diff --git a/lisp/bindings.el b/lisp/bindings.el
index 4e5497cc79..f3c4f42f78 100644
--- a/lisp/bindings.el
+++ b/lisp/bindings.el
@@ -330,22 +330,51 @@ bindings--define-key
 (defvar mode-line-mode-menu (make-sparse-keymap "Minor Modes") "\
 Menu of mode operations in the mode line.")
 
+(defun bindings--menu-item-string (item)
+  "Return the menu-item string for ITEM, or nil if not a menu-item."
+  (cond
+   ((not (consp item)) nil)             ; Not a menu-item.
+   ((eq 'menu-item (car item))
+    (eval (cadr item)))
+   ((stringp (car item))
+    (car item))
+   (t nil)))                            ; Not a menu-item either.
+
+(defun bindings--sort-keymap (keymap)
+  "Sort the bindings in KEYMAP in alphabetical order.
+The order of bindings in a keymap matters only when it is used as
+a menu, so this function is not useful for non-menu keymaps."
+  (or (keymapp keymap)
+      (signal 'wrong-type-argument (list 'keymapp keymap)))
+  (let ((menu-items
+         (sort (cdr keymap)
+               (lambda (a b)
+                 (string< (bindings--menu-item-string (cdr-safe a))
+                          (bindings--menu-item-string (cdr-safe b)))))))
+    (setcdr keymap menu-items)
+    keymap))
+
 (defvar mode-line-major-mode-keymap
   (let ((map (make-sparse-keymap)))
     (bindings--define-key map [mode-line down-mouse-1]
       `(menu-item "Menu Bar" ignore
         :filter ,(lambda (_) (mouse-menu-major-mode-map))))
     (define-key map [mode-line mouse-2] 'describe-mode)
-    (define-key map [mode-line down-mouse-3] mode-line-mode-menu)
+    (bindings--define-key map [mode-line down-mouse-3]
+      `(menu-item "Menu Bar" ,mode-line-mode-menu
+        :filter bindings--sort-keymap))
     map) "\
 Keymap to display on major mode.")
 
 (defvar mode-line-minor-mode-keymap
-  (let ((map (make-sparse-keymap)))
+  (let ((map (make-sparse-keymap))
+        (mode-menu-binding
+         `(menu-item "Menu Bar" ,mode-line-mode-menu
+           :filter bindings--sort-keymap)))
     (define-key map [mode-line down-mouse-1] 'mouse-minor-mode-menu)
     (define-key map [mode-line mouse-2] 'mode-line-minor-mode-help)
-    (define-key map [mode-line down-mouse-3] mode-line-mode-menu)
-    (define-key map [header-line down-mouse-3] mode-line-mode-menu)
+    (define-key map [mode-line down-mouse-3] mode-menu-binding)
+    (define-key map [header-line down-mouse-3] mode-menu-binding)
     map) "\
 Keymap to display on minor modes.")
 
-- 
2.25.1

Re: [WIP PATCH] Adding keys to keymaps in alphabetical order (for use with `mode-line-mode-menu')

[Lars Ingebrigtsen]

Jim Porter <jporterbugs@gmail.com> writes:

> Performance-wise, the cost is negligible for the default value of
> `mode-line-mode-menu': ~10ms for the first time and 0.02ms for
> subsequent calls.

Thanks; looks good, so I've applied it to Emacs 28 (with some trivial
changes).

> +         (sort (cdr keymap)
> +               (lambda (a b)
> +                 (string< (bindings--menu-item-string (cdr-safe a))
> +                          (bindings--menu-item-string (cdr-safe b)))))))
> +    (setcdr keymap menu-items)

I'm slightly worried about this, though -- will altering the keymap
structure have any adverse side effects?  I don't think so, and testing
a bit doesn't seem to reveal anything obvious, but we should be on the
lookup.

-- 
(domestic pets only, the antidote for overdose, milk.)
   bloggy blog: http://lars.ingebrigtsen.no

Re: [WIP PATCH] Adding keys to keymaps in alphabetical order (for use with `mode-line-mode-menu')

[Stefan Monnier]

>> Performance-wise, the cost is negligible for the default value of
>> `mode-line-mode-menu': ~10ms for the first time and 0.02ms for
>> subsequent calls.
> Thanks; looks good, so I've applied it to Emacs 28 (with some trivial
> changes).

It might want to clarify that the sorting is based on the menu item
names (rather than, say, the name of the key sequence).
Maybe it should have "menu" somewhere in its name ;-)

>> +         (sort (cdr keymap)
>> +               (lambda (a b)
>> +                 (string< (bindings--menu-item-string (cdr-safe a))
>> +                          (bindings--menu-item-string (cdr-safe b)))))))
>> +    (setcdr keymap menu-items)
>
> I'm slightly worried about this, though -- will altering the keymap
> structure have any adverse side effects?  I don't think so, and testing
> a bit doesn't seem to reveal anything obvious, but we should be on the
> lookup.

Altering the keymap by side-effect is not dangerous in and of itself
(`define-key` does it as well).
But the above code will mess things up when applied to a keymap that has
a parent keymap.

It will also fail to do its job on menu keymaps which use a vector
rather or on composed keymaps (which can be
created "implicitly", e.g. when looking up `menu-bar` in a keymap which
has a `menu-bar` binding and which additionally inherits from a keymap
that also has a `menu-bar` binding).

To solve those issues I think one would have to `map-keymap` and return
a brand new keymap rather than modify it in-situ, AFAICT.

Note that in my example above of a composed keymap created implicitly by
`access_keymap`, the menu.c code currently deals very poorly with such
situations (the two composed keymaps get just "concatenated"; worse,
even though entries from the first keymap can hide/override elements
from the second, menu.c will show them all, so you can end up with menu
entries which can't actually be used).  The merging of the composed
keymaps would best be done according to directions embedded directly in
the keymaps themselves so a child keymap can insert new menu entries in
the middle of a parent menu.


        Stefan

Re: [WIP PATCH] Adding keys to keymaps in alphabetical order (for use with `mode-line-mode-menu')

[Lars Ingebrigtsen]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

> But the above code will mess things up when applied to a keymap that has
> a parent keymap.
>
> It will also fail to do its job on menu keymaps which use a vector
> rather or on composed keymaps (which can be
> created "implicitly", e.g. when looking up `menu-bar` in a keymap which
> has a `menu-bar` binding and which additionally inherits from a keymap
> that also has a `menu-bar` binding).

Ah, right.  I'll revert the commit then (for now).

-- 
(domestic pets only, the antidote for overdose, milk.)
   bloggy blog: http://lars.ingebrigtsen.no

[Updated Patch] Re: [WIP PATCH] Adding keys to keymaps in alphabetical order (for use with `mode-line-mode-menu')

[Jim Porter]

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

On 6/23/2021 6:58 AM, Stefan Monnier wrote:
>>> +         (sort (cdr keymap)
>>> +               (lambda (a b)
>>> +                 (string< (bindings--menu-item-string (cdr-safe a))
>>> +                          (bindings--menu-item-string (cdr-safe b)))))))
>>> +    (setcdr keymap menu-items)
>>
>> I'm slightly worried about this, though -- will altering the keymap
>> structure have any adverse side effects?  I don't think so, and testing
>> a bit doesn't seem to reveal anything obvious, but we should be on the
>> lookup.
> 
> Altering the keymap by side-effect is not dangerous in and of itself
> (`define-key` does it as well).
> But the above code will mess things up when applied to a keymap that has
> a parent keymap.
> 
> It will also fail to do its job on menu keymaps which use a vector
> rather or on composed keymaps (which can be
> created "implicitly", e.g. when looking up `menu-bar` in a keymap which
> has a `menu-bar` binding and which additionally inherits from a keymap
> that also has a `menu-bar` binding).
> 
> To solve those issues I think one would have to `map-keymap` and return
> a brand new keymap rather than modify it in-situ, AFAICT.

Attached is a patch that uses `map-keymap'. I've modeled the 
implementation on `keymap-canonicalize', so hopefully it's 
sufficiently-correct. The patch doesn't do anything special about 
char-ranges, but I'm not sure that matters for menus.

One difference in this patch is that `mode-line-mode-menu' itself is no 
longer updated after sorting. It just returns a new keymap. The 
performance is the same as before, which is good, and this is probably a 
bit safer too.

- Jim

[-- Attachment #2: 0001-Sort-the-items-in-mode-line-mode-menu-before-display.patch --]
[-- Type: text/plain, Size: 3290 bytes --]

From 034f10dd6f2e4cd55c6b5b6aa23fb93de17e10c7 Mon Sep 17 00:00:00 2001
From: Jim Porter <jporterbugs@gmail.com>
Date: Wed, 23 Jun 2021 09:43:37 -0700
Subject: [PATCH] Sort the items in 'mode-line-mode-menu' before displaying the
 menu

* lisp/bindings.el (bindings--menu-item-string, bindings--sort-keymap):
New functions.
(mode-line-major-mode-keymap, mode-line-minor-mode-keymap):
Sort 'mode-line-mode-menu'.
---
 lisp/bindings.el | 43 +++++++++++++++++++++++++++++++++++++++----
 1 file changed, 39 insertions(+), 4 deletions(-)

diff --git a/lisp/bindings.el b/lisp/bindings.el
index 4e5497cc79..8dda6db031 100644
--- a/lisp/bindings.el
+++ b/lisp/bindings.el
@@ -330,22 +330,57 @@ bindings--define-key
 (defvar mode-line-mode-menu (make-sparse-keymap "Minor Modes") "\
 Menu of mode operations in the mode line.")
 
+(defun bindings--menu-item-string (item)
+  "Return the menu-item string for ITEM, or nil if not a menu-item."
+  (cond
+   ((not (consp item)) nil)             ; Not a menu-item.
+   ((eq 'menu-item (car item))
+    (eval (cadr item)))
+   ((stringp (car item))
+    (car item))
+   (t nil)))                            ; Not a menu-item either.
+
+(defun bindings--sort-keymap (map)
+  "Sort the bindings in MAP in alphabetical order by menu-item string.
+The order of bindings in a keymap matters only when it is used as
+a menu, so this function is not useful for non-menu keymaps."
+  (let ((bindings nil)
+        (prompt (keymap-prompt map)))
+    (while (keymapp map)
+      (setq map (map-keymap
+                 (lambda (key item)
+                   ;; FIXME: Handle char-ranges here?
+                   (push (cons key item) bindings))
+                 map)))
+    ;; Sort the bindings and make a new keymap from them.
+    (setq bindings
+          (sort bindings
+                (lambda (a b)
+                  (string< (bindings--menu-item-string (cdr-safe a))
+                           (bindings--menu-item-string (cdr-safe b))))))
+    (nconc (make-sparse-keymap prompt) bindings)))
+
 (defvar mode-line-major-mode-keymap
   (let ((map (make-sparse-keymap)))
     (bindings--define-key map [mode-line down-mouse-1]
       `(menu-item "Menu Bar" ignore
         :filter ,(lambda (_) (mouse-menu-major-mode-map))))
     (define-key map [mode-line mouse-2] 'describe-mode)
-    (define-key map [mode-line down-mouse-3] mode-line-mode-menu)
+    (bindings--define-key map [mode-line down-mouse-3]
+      `(menu-item "Menu Bar" ,mode-line-mode-menu
+        :filter bindings--sort-keymap))
     map) "\
 Keymap to display on major mode.")
 
 (defvar mode-line-minor-mode-keymap
-  (let ((map (make-sparse-keymap)))
+  (let ((map (make-sparse-keymap))
+        (mode-menu-binding
+         `(menu-item "Menu Bar" ,mode-line-mode-menu
+           :filter bindings--sort-keymap)))
     (define-key map [mode-line down-mouse-1] 'mouse-minor-mode-menu)
     (define-key map [mode-line mouse-2] 'mode-line-minor-mode-help)
-    (define-key map [mode-line down-mouse-3] mode-line-mode-menu)
-    (define-key map [header-line down-mouse-3] mode-line-mode-menu)
+    (define-key map [mode-line down-mouse-3] mode-menu-binding)
+    (define-key map [header-line down-mouse-3] mode-menu-binding)
     map) "\
 Keymap to display on minor modes.")
 
-- 
2.25.1

Re: [Updated Patch] Re: [WIP PATCH] Adding keys to keymaps in alphabetical order (for use with `mode-line-mode-menu')

[Lars Ingebrigtsen]

Jim Porter <jporterbugs@gmail.com> writes:

> Attached is a patch that uses `map-keymap'. I've modeled the
> implementation on `keymap-canonicalize', so hopefully it's
> sufficiently-correct. The patch doesn't do anything special about
> char-ranges, but I'm not sure that matters for menus.

Thanks; applied to Emacs 28.

-- 
(domestic pets only, the antidote for overdose, milk.)
   bloggy blog: http://lars.ingebrigtsen.no