Subject: bug#76669: read_key_sequence discards events without attempting remapping

From: Daniel Colascione <[email-masked]>
Date: Sun, 02 Mar 2025 12:15:58 -0500

Stefan Monnier <[email-masked]> writes:

>>>> Suppose we want to use local-function-key-map to translate
>>>> s-<down-mouse-3> to <down-mouse-3>.  If we don't have a concrete binding
>>>> for s-<down-mouse-3>, we never attempt to translate it: instead,
>>>> read_key_sequence discards the down event and skips right to
>>>> s-<mouse-3>, which we *can* translate.
>
> Hmm... to be honest, I'm surprised that this is what happens, because my
> recollection of the code was that dropping down/double/drag (and shift)
> is done "as late as possible".
>
> Maybe this is just a bug?
>
>>> I think it's ambiguous which one should come first: the discarding of
>>> 'down' modifier or translation via that map.  The ELisp manual says:
>
> Given that translation is "customizable" it's desirable to go through
> translation before deciding to drop `down`, but it's also desirable to
> go through translation after dropping `down`.
>
> FWIW, I have several times wished the `function-key-map`-style "remap if
> there's no binding" was applied repeatedly.
>
>> Wouldn't it be simpler and more powerful to get the modifier-munging
>> stuff out of the main read_key_sequence loop and implement the down
>> event dropping in access_keymap_keyremap?
>
> That would prevent applying remapping after the `down` thingy
> was dropped.

No --- I meant we'd have the remapping code *do* the dropping.
Apply the remapping in a loop until we reach a fixed point.

Remapping phases:

1. [s-down-mouse-1 s-mouse-1]
2. [down-mouse-1 mouse-1]
3. [mouse-1]

> In my wildest dreams, `read_key_sequence` has an `input-fallback-map`
> which is applied repeatedly, and keymaps can be functions so that they
> can do things like remap anything that looks like `FOO-mouse-1` to
> `FOO-mouse-2` (without having to list the hundreds of possible FOO) or
> remap anything that looks like `down-FOO` to `FOO`.
> Then `read_key_sequence` doesn't treat shift and `down` specially,
> instead that can be moved out to `input-fallback-map`.

Keymap entries can already be functions, and I think the function entry
would work with the fallback finding t too.  There's no good way to
compose such functions, though --- not without just clobbering them with
add-function and such.  Child keymap fallback entries will shadow those
of the parents.

> But, yeah, that still leaves open the question of whether we should drop
> `shift` before we drop `down` or the reverse, and whether the
> `FOO-mouse-1` to `FOO-mouse-2` remapping should happen before or after
> dropping `down`.  The only "principled" way to solve this problem,
> AFAICT, would be to consider those remapping and returning all the
> possibilities (as a set of possible keysequences) and then when we do
> the corresponding key lookup, we'd have to decide what to do if there's
> more than one binding for those keysequences.

If we're going to fix this, we might as well move read-key-sequence to
Lisp, where it's easier to express the right algorithm.

We can model the raw input event stream as a lazy infinite sequence with
lookahead.  The access-keymap operation would do another physical event
read if it wanted lookahead and we didn't have the physical event yet.

We can model key remapping with recursion, yes?  A remapping keymap
would just recursively try the whole key mapping sequence with its
new binding.

Here's a sketch.  (Real code would have much better style.)

(defvar all-keymaps ...)  ; global-map local-map function-key-map etc.

(def-defstruct candidate-keys
   ;; (- (length keys) nr-committed) is the
  ;; amount of lookahead we have
  (keys :type vector)
  (nr-committed :type integer))

(defun try-match-key-sequence (candidate-keys)
  ;; Go through all our keymaps.  If any of them returns
  ;; a concrete binding, use it immediately.  Otherwise,
  ;; return :want-lookahead if any keymap wants more lookahead.
  (cl-loop
    with want-lookahead = nil
    for keymap in all-keymaps
    for binding = (keymap-try-get-binding keymap candidate-keys)
    if (eq binding :want-lookahead)
    do (setf want-lookahead :want-lookahead)
    else if binding return binding
    finally return want-lookahead))

(defun keymap-try-get-binding (keymap candidate-keys)
  ;; See whether keymap has a binding for candidate-keys
  ;; If definitely no binding, return nil.  If we're not
  ;; sure and need to see more input (e.g. because
  ;; the committed part of candidate-keys names a non-empty prefix map)
  ;; returns :want-lookahead.
  (pcase (access-keymap keymap candidate-keys)
    (':want-lookahead  ; need more input
      :want-lookahead)
    (`(:remap ,translated-candidate-keys)
      ;; just retry the whole matching step with the
      ;; new candidate keys
      (try-match-key-sequence translated-candidate-keys))
    (r r)))

(defun read-key-sequence (...)
  ;; Match the shortest bound sequence.
  ;; Leave any remaining lookahead in
  ;; raw-event-queue to get picked up next time.
  (cl-loop
    with raw-event-queue = ()
    for nr-keys upfrom 0
    for binding = (cl-loop
      for maybe-binding = (try-match-key-sequence
        (make-candidate-keys
          :keys raw-event-queue
          :nr nr-keys))
      while (eq maybe-binding :want-lookahead)
      ;; Yes, I know appendf doesn't exist
      do (appendf raw-event-queue (read-char))
      finally return maybe-binding)
    until binding
    finally return (progn
      ;; Put any unconsumed readahead in the queue for the next
      ;; event.  BINDING here is (translated-keys . command) or
      ;; something like that
      (setf unread-command-events (seq-subseq raw-event-queue nr-keys))
      (setf this-command-keys (car binding))  ; translated
      (cdr binding)))