bug/feature - emacs doesn't tell you about keys with multiple prefixes

bug/feature - emacs doesn't tell you about keys with multiple prefixes

[Karl Chen]

With the code below, if you do "C-h k M-b M-a" , Emacs will tell you that
mark-paragraph is on "M-h, M-a, M-b" ; it will not tell you that it is also on
M-b M-a or M-b M-b (even though you just pressed those keys to get to this
screen!). Same goes with the "matched:" message when you type M-x
mark-paragraph (before you hit RET).

Regardless of bad coding style etc I it is useful to have aliases for prefixes
- for example I like using M-v instead of/in addition to C-x v and the easiest
way to do this is to (global-set-key [ (meta v) ] vc-prefix-map). This
confusing behavior of displaying only keys under the first key bound to a
keymap exists in Emacs 21 for the "M-x ... [matched; <keys>]" message and in
Emacs CVS for describe-key as well.



(global-set-key [(meta a)] nil)
(global-set-key [(meta b)] nil)

(global-set-key [(meta a) (meta a)] 'mark-paragraph)
(global-set-key [(meta a) (meta b)] 'mark-paragraph)

;;; >>>>>>>>>>>>>>>>>>>>>
(global-set-key [(meta b)] (lookup-key (current-global-map) [(meta a)]))
;;; <<<<<<<<<<<<<<<<<<<<<

;; after the previos line, these two lines have no effect on the reverse key lookups.
(global-set-key [(meta b) (meta a)] 'mark-paragraph)
(global-set-key [(meta b) (meta b)] 'mark-paragraph)


-- 
Karl Chen / quarl@quarl.org

Re: bug/feature - emacs doesn't tell you about keys with multiple prefixes

[Stefan Monnier]

> With the code below, if you do "C-h k M-b M-a" , Emacs will tell you that
> mark-paragraph is on "M-h, M-a, M-b" ; it will not tell you that it is also on
> M-b M-a or M-b M-b (even though you just pressed those keys to get to this
> screen!). Same goes with the "matched:" message when you type M-x
> mark-paragraph (before you hit RET).
> 
> Regardless of bad coding style etc I it is useful to have aliases for prefixes
> - for example I like using M-v instead of/in addition to C-x v and the easiest
> way to do this is to (global-set-key [ (meta v) ] vc-prefix-map). This
> confusing behavior of displaying only keys under the first key bound to a
> keymap exists in Emacs 21 for the "M-x ... [matched; <keys>]" message and in
> Emacs CVS for describe-key as well.
> 
> 
> 
> (global-set-key [(meta a)] nil)
> (global-set-key [(meta b)] nil)
> 
> (global-set-key [(meta a) (meta a)] 'mark-paragraph)
> (global-set-key [(meta a) (meta b)] 'mark-paragraph)
> 
> ;;; >>>>>>>>>>>>>>>>>>>>>
> (global-set-key [(meta b)] (lookup-key (current-global-map) [(meta a)]))
> ;;; <<<<<<<<<<<<<<<<<<<<<
> 
> ;; after the previos line, these two lines have no effect on the reverse key lookups.
> (global-set-key [(meta b) (meta a)] 'mark-paragraph)
> (global-set-key [(meta b) (meta b)] 'mark-paragraph)

It seems that it is done "on purpose".

In accessible-keymaps (used by where-is-internal), there is an explicit check
to remove any duplicate keymaps (i.e. the same keymap appearing under another
prefix).  Look for Frassq in accessible_keymaps_1 in keymap.c.

I'm not sure why it's there, but it's been there "for ever"
(i.e. since revision 1.1 of the file).  One benefit of removing duplicates
is that it prevents us from getting stuck in a cycle, although I'm not sure
how important this is.


	Stefan

Re: Re: bug/feature - emacs doesn't tell you about keys with multiple prefixes

[Richard Stallman]

    In accessible-keymaps (used by where-is-internal), there is an explicit check
    to remove any duplicate keymaps (i.e. the same keymap appearing under another
    prefix).

I don't remember the reason for this.  Perhaps the idea was that it is
supposed to tell you all the keymaps, not all the prefixes.
Preventing cycles is also necessary.

There could be an optional 3rd arg ALLOW-DUPLICATES which, if non-nil,
means that it only rejects actual cycles (where the prefix already
recorded for the same keymap is an initial segment of the new prefix).

Re: bug/feature - emacs doesn't tell you about keys with multiple prefixes

[Stefan Monnier]

>     In accessible-keymaps (used by where-is-internal), there is an explicit check
>     to remove any duplicate keymaps (i.e. the same keymap appearing under another
>     prefix).
> 
> I don't remember the reason for this.  Perhaps the idea was that it is
> supposed to tell you all the keymaps, not all the prefixes.
> Preventing cycles is also necessary.
> 
> There could be an optional 3rd arg ALLOW-DUPLICATES which, if non-nil,
> means that it only rejects actual cycles (where the prefix already
> recorded for the same keymap is an initial segment of the new prefix).

Grepping through Emacs' code I discovered that accessible-keymap
is never called from elisp and that it's only ever called from
where-is-internal, so I think we can safely change its
behavior without adding a new argument.

How about the patch below ?


	Stefan


Index: src/keymap.c
===================================================================
RCS file: /cvsroot/emacs/emacs/src/keymap.c,v
retrieving revision 1.277
diff -c -b -r1.277 keymap.c
*** src/keymap.c	16 Mar 2003 00:06:59 -0000	1.277
--- src/keymap.c	17 Mar 2003 16:32:29 -0000
***************
*** 1659,1676 ****
  {
    Lisp_Object tem;
  
!   cmd = get_keyelt (cmd, 0);
    if (NILP (cmd))
      return;
  
!   tem = get_keymap (cmd, 0, 0);
!   if (CONSP (tem))
!     {
!       cmd = tem;
!       /* Ignore keymaps that are already added to maps.  */
!       tem = Frassq (cmd, maps);
!       if (NILP (tem))
  	{
  	  /* If the last key in thisseq is meta-prefix-char,
  	     turn it into a meta-ized keystroke.  We know
  	     that the event we're about to append is an
--- 1659,1689 ----
  {
    Lisp_Object tem;
  
!   cmd = get_keymap (get_keyelt (cmd, 0), 0, 0);
    if (NILP (cmd))
      return;
  
!   /* Look for and break cycles.  */
!   while (!NILP (tem = Frassq (cmd, maps)))
      {
+       Lisp_Object prefix = XCAR (tem);
+       int lim = XINT (Flength (XCAR (tem)));
+       if (lim <= XINT (Flength (thisseq)))
+ 	{ /* This keymap was already seen with a smaller prefix.  */
+ 	  int i = 0;
+ 	  while (i < lim && EQ (Faref (prefix, make_number (i)),
+ 				Faref (thisseq, make_number (i))))
+ 	    i++;
+ 	  if (i >= lim)
+ 	    /* `prefix' is a prefix of `thisseq' => there's a cycle.  */
+ 	    return;
+ 	}
+       /* This occurrence of `cmd' in `maps' does not correspond to a cycle,
+ 	 but maybe `cmd' occurs again further down in `maps', so keep
+ 	 looking.  */
+       maps = XCDR (Fmemq (tem, maps));
+     }
+ 
    /* If the last key in thisseq is meta-prefix-char,
       turn it into a meta-ized keystroke.  We know
       that the event we're about to append is an
***************
*** 1694,1701 ****
  	    {
  	      tem = append_key (thisseq, key);
  	      nconc2 (tail, Fcons (Fcons (tem, cmd), Qnil));
- 	    }
- 	}
      }
  }
  
--- 1707,1712 ----

Re: bug/feature - emacs doesn't tell you about keys with multiple prefixes

[Richard Stallman]

The new code has a bug: it finds just the last occurrence of the same
keymap and tests whether the prefix for that occurrence is an initial
segment.  What if the last occurrence isn't but another occurrence is?
In that case, it won't detect the cycle.  I suspect that when M-a,
M-b, and M-a M-b are the same keymap, this code won't compare the M-a
with the M-a M-b.

It can't use rassq now; it has to check each previous occurrence of the same
keymap.

Re: bug/feature - emacs doesn't tell you about keys with multiple prefixes

[Stefan Monnier]

> The new code has a bug: it finds just the last occurrence of the same
> keymap and tests whether the prefix for that occurrence is an initial
> segment.  What if the last occurrence isn't but another occurrence is?
> In that case, it won't detect the cycle.  I suspect that when M-a,
> M-b, and M-a M-b are the same keymap, this code won't compare the M-a
> with the M-a M-b.
> 
> It can't use rassq now; it has to check each previous occurrence of the same
> keymap.

Huh?! That's exactly what the code does.  I verified it correcly
breaks such cycles before posting the message.
And there's even a comment about it.


	Stefan

Re: bug/feature - emacs doesn't tell you about keys with multiple prefixes

[Richard Stallman]

    > It can't use rassq now; it has to check each previous occurrence of the same
    > keymap.

    Huh?! That's exactly what the code does.  I verified it correcly
    breaks such cycles before posting the message.

Now I see why that is so--it is because you update MAPS at the
end of the loop.

But the result is that the code is both more complex and slower
than a simple loop that looks at each element of MAPS.  So would
you please change it to work that way?