Fix keyboard macro key lookup (Bug#5481).
[bpt/emacs.git] / src / keymap.c
index 88b63e4..88e0687 100644 (file)
@@ -1,14 +1,14 @@
 /* Manipulation of keymaps
    Copyright (C) 1985, 1986, 1987, 1988, 1993, 1994, 1995,
                  1998, 1999, 2000, 2001, 2002, 2003, 2004,
-                 2005, 2006, 2007 Free Software Foundation, Inc.
+                 2005, 2006, 2007, 2008, 2009, 2010 Free Software Foundation, Inc.
 
 This file is part of GNU Emacs.
 
-GNU Emacs is free software; you can redistribute it and/or modify
+GNU Emacs is free software: you can redistribute it and/or modify
 it under the terms of the GNU General Public License as published by
-the Free Software Foundation; either version 3, or (at your option)
-any later version.
+the Free Software Foundation, either version 3 of the License, or
+(at your option) any later version.
 
 GNU Emacs is distributed in the hope that it will be useful,
 but WITHOUT ANY WARRANTY; without even the implied warranty of
@@ -16,19 +16,19 @@ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 GNU General Public License for more details.
 
 You should have received a copy of the GNU General Public License
-along with GNU Emacs; see the file COPYING.  If not, write to
-the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
-Boston, MA 02110-1301, USA.  */
+along with GNU Emacs.  If not, see <http://www.gnu.org/licenses/>.  */
 
 
 #include <config.h>
 #include <stdio.h>
+#include <setjmp.h>
 #if HAVE_ALLOCA_H
 # include <alloca.h>
 #endif
 #include "lisp.h"
 #include "commands.h"
 #include "buffer.h"
+#include "character.h"
 #include "charset.h"
 #include "keyboard.h"
 #include "frame.h"
@@ -75,7 +75,7 @@ Lisp_Object Vminibuffer_local_filename_completion_map;
 
 /* keymap used for minibuffers when doing completion in filenames
    with require-match*/
-Lisp_Object Vminibuffer_local_must_match_filename_map;
+Lisp_Object Vminibuffer_local_filename_must_match_map;
 
 /* keymap used for minibuffers when doing completion and require a match */
 /* was MinibufLocalMustMatchMap */
@@ -98,6 +98,7 @@ Lisp_Object Vemulation_mode_map_alists;
 Lisp_Object Vdefine_key_rebound_commands;
 
 Lisp_Object Qkeymapp, Qkeymap, Qnon_ascii, Qmenu_item, Qremap;
+Lisp_Object QCadvertised_binding;
 
 /* Alist of elements like (DEL . "\d").  */
 static Lisp_Object exclude_keys;
@@ -169,7 +170,11 @@ in case you use it as a menu with `x-popup-menu'.  */)
      Lisp_Object string;
 {
   if (!NILP (string))
-    return Fcons (Qkeymap, Fcons (string, Qnil));
+    {
+      if (!NILP (Vpurify_flag))
+       string = Fpurecopy (string);
+      return Fcons (Qkeymap, Fcons (string, Qnil));
+    }
   return Fcons (Qkeymap, Qnil);
 }
 
@@ -186,7 +191,7 @@ initial_define_key (keymap, key, defname)
      int key;
      char *defname;
 {
-  store_in_keymap (keymap, make_number (key), intern (defname));
+  store_in_keymap (keymap, make_number (key), intern_c_string (defname));
 }
 
 void
@@ -195,7 +200,7 @@ initial_define_lispy_key (keymap, keyname, defname)
      char *keyname;
      char *defname;
 {
-  store_in_keymap (keymap, intern (keyname), intern (defname));
+  store_in_keymap (keymap, intern_c_string (keyname), intern_c_string (defname));
 }
 
 DEFUN ("keymapp", Fkeymapp, Skeymapp, 1, 1, 0,
@@ -292,7 +297,7 @@ get_keymap (object, error, autoload)
                  goto autoload_retry;
                }
              else
-               return Qt;
+               return object;
            }
        }
     }
@@ -328,7 +333,8 @@ keymap_parent (keymap, autoload)
 }
 
 DEFUN ("keymap-parent", Fkeymap_parent, Skeymap_parent, 1, 1, 0,
-       doc: /* Return the parent keymap of KEYMAP.  */)
+       doc: /* Return the parent keymap of KEYMAP.
+If KEYMAP has no parent, return nil.  */)
      (keymap)
      Lisp_Object keymap;
 {
@@ -422,11 +428,7 @@ Return PARENT.  PARENT should be nil or another keymap.  */)
 
       if (CHAR_TABLE_P (XCAR (list)))
        {
-         int indices[3];
-
-         map_char_table (fix_submap_inheritance, Qnil,
-                         XCAR (list), XCAR (list),
-                         keymap, 0, indices);
+         map_char_table (fix_submap_inheritance, Qnil, XCAR (list), keymap);
        }
     }
 
@@ -566,11 +568,6 @@ access_keymap (map, idx, t_ok, noinherit, autoload)
 
     GCPRO4 (map, tail, idx, t_binding);
 
-    /* If `t_ok' is 2, both `t' and generic-char bindings are accepted.
-       If it is 1, only generic-char bindings are accepted.
-       Otherwise, neither are.  */
-    t_ok = t_ok ? 2 : 0;
-
     for (tail = XCDR (map);
         (CONSP (tail)
          || (tail = get_keymap (tail, 0, autoload), CONSP (tail)));
@@ -592,29 +589,11 @@ access_keymap (map, idx, t_ok, noinherit, autoload)
 
            if (EQ (key, idx))
              val = XCDR (binding);
-           else if (t_ok
-                    && INTEGERP (idx)
-                    && (XINT (idx) & CHAR_MODIFIER_MASK) == 0
-                    && INTEGERP (key)
-                    && (XINT (key) & CHAR_MODIFIER_MASK) == 0
-                    && !SINGLE_BYTE_CHAR_P (XINT (idx))
-                    && !SINGLE_BYTE_CHAR_P (XINT (key))
-                    && CHAR_VALID_P (XINT (key), 1)
-                    && !CHAR_VALID_P (XINT (key), 0)
-                    && (CHAR_CHARSET (XINT (key))
-                        == CHAR_CHARSET (XINT (idx))))
+           else if (t_ok && EQ (key, Qt))
              {
-               /* KEY is the generic character of the charset of IDX.
-                  Use KEY's binding if there isn't a binding for IDX
-                  itself.  */
                t_binding = XCDR (binding);
                t_ok = 0;
              }
-           else if (t_ok > 1 && EQ (key, Qt))
-             {
-               t_binding = XCDR (binding);
-               t_ok = 1;
-             }
          }
        else if (VECTORP (binding))
          {
@@ -678,30 +657,29 @@ map_keymap_char_table_item (args, key, val)
     {
       map_keymap_function_t fun = XSAVE_VALUE (XCAR (args))->pointer;
       args = XCDR (args);
+      /* If the key is a range, make a copy since map_char_table modifies
+        it in place.  */
+      if (CONSP (key))
+       key = Fcons (XCAR (key), XCDR (key));
       map_keymap_item (fun, XCDR (args), key, val,
                       XSAVE_VALUE (XCAR (args))->pointer);
     }
 }
 
-/* Call FUN for every binding in MAP.
-   FUN is called with 4 arguments: FUN (KEY, BINDING, ARGS, DATA).
-   AUTOLOAD if non-zero means that we can autoload keymaps if necessary.  */
-void
-map_keymap (map, fun, args, data, autoload)
-     map_keymap_function_t fun;
-     Lisp_Object map, args;
-     void *data;
-     int autoload;
+/* Call FUN for every binding in MAP and stop at (and return) the parent.
+   FUN is called with 4 arguments: FUN (KEY, BINDING, ARGS, DATA).  */
+Lisp_Object
+map_keymap_internal (Lisp_Object map,
+                    map_keymap_function_t fun,
+                    Lisp_Object args,
+                    void *data)
 {
   struct gcpro gcpro1, gcpro2, gcpro3;
-  Lisp_Object tail;
+  Lisp_Object tail
+    = (CONSP (map) && EQ (Qkeymap, XCAR (map))) ? XCDR (map) : map;
 
-  tail = Qnil;
   GCPRO3 (map, args, tail);
-  map = get_keymap (map, 1, autoload);
-  for (tail = (CONSP (map) && EQ (Qkeymap, XCAR (map))) ? XCDR (map) : map;
-       CONSP (tail) || (tail = get_keymap (tail, 0, autoload), CONSP (tail));
-       tail = XCDR (tail))
+  for (; CONSP (tail) && !EQ (Qkeymap, XCAR (tail)); tail = XCDR (tail))
     {
       Lisp_Object binding = XCAR (tail);
 
@@ -721,15 +699,14 @@ map_keymap (map, fun, args, data, autoload)
        }
       else if (CHAR_TABLE_P (binding))
        {
-         int indices[3];
-         map_char_table (map_keymap_char_table_item, Qnil, binding, binding,
+         map_char_table (map_keymap_char_table_item, Qnil, binding,
                          Fcons (make_save_value (fun, 0),
                                 Fcons (make_save_value (data, 0),
-                                       args)),
-                         0, indices);
+                                       args)));
        }
     }
   UNGCPRO;
+  return tail;
 }
 
 static void
@@ -740,13 +717,66 @@ map_keymap_call (key, val, fun, dummy)
   call2 (fun, key, val);
 }
 
+/* Same as map_keymap_internal, but doesn't traverses parent keymaps as well.
+   A non-zero AUTOLOAD indicates that autoloaded keymaps should be loaded.  */
+void
+map_keymap (map, fun, args, data, autoload)
+     map_keymap_function_t fun;
+     Lisp_Object map, args;
+     void *data;
+     int autoload;
+{
+  struct gcpro gcpro1;
+  GCPRO1 (args);
+  map = get_keymap (map, 1, autoload);
+  while (CONSP (map))
+    {
+      map = map_keymap_internal (map, fun, args, data);
+      map = get_keymap (map, 0, autoload);
+    }
+  UNGCPRO;
+}
+
+Lisp_Object Qkeymap_canonicalize;
+
+/* Same as map_keymap, but does it right, properly eliminating duplicate
+   bindings due to inheritance.   */
+void
+map_keymap_canonical (map, fun, args, data)
+     map_keymap_function_t fun;
+     Lisp_Object map, args;
+     void *data;
+{
+  struct gcpro gcpro1;
+  GCPRO1 (args);
+  /* map_keymap_canonical may be used from redisplay (e.g. when building menus)
+     so be careful to ignore errors and to inhibit redisplay.  */
+  map = safe_call1 (Qkeymap_canonicalize, map);
+  /* No need to use `map_keymap' here because canonical map has no parent.  */
+  map_keymap_internal (map, fun, args, data);
+  UNGCPRO;
+}
+
+DEFUN ("map-keymap-internal", Fmap_keymap_internal, Smap_keymap_internal, 2, 2, 0,
+       doc: /* Call FUNCTION once for each event binding in KEYMAP.
+FUNCTION is called with two arguments: the event that is bound, and
+the definition it is bound to.  The event may be a character range.
+If KEYMAP has a parent, this function returns it without processing it.  */)
+     (function, keymap)
+     Lisp_Object function, keymap;
+{
+  struct gcpro gcpro1;
+  GCPRO1 (function);
+  keymap = get_keymap (keymap, 1, 1);
+  keymap = map_keymap_internal (keymap, map_keymap_call, function, NULL);
+  UNGCPRO;
+  return keymap;
+}
+
 DEFUN ("map-keymap", Fmap_keymap, Smap_keymap, 2, 3, 0,
        doc: /* Call FUNCTION once for each event binding in KEYMAP.
 FUNCTION is called with two arguments: the event that is bound, and
-the definition it is bound to.  If the event is an integer, it may be
-a generic character (see Info node `(elisp)Splitting Characters'), and
-that means that all actual character events belonging to that generic
-character are bound to the definition.
+the definition it is bound to.  The event may be a character range.
 
 If KEYMAP has a parent, the parent's bindings are included as well.
 This works recursively: if the parent has itself a parent, then the
@@ -755,12 +785,8 @@ usage: (map-keymap FUNCTION KEYMAP)  */)
      (function, keymap, sort_first)
      Lisp_Object function, keymap, sort_first;
 {
-  if (INTEGERP (function))
-    /* We have to stop integers early since map_keymap gives them special
-       significance.  */
-    xsignal1 (Qinvalid_function, function);
   if (! NILP (sort_first))
-    return call3 (intern ("map-keymap-internal"), function, keymap, Qt);
+    return call2 (intern ("map-keymap-sorted"), function, keymap);
 
   map_keymap (keymap, map_keymap_call, function, NULL, 1);
   return Qnil;
@@ -881,10 +907,15 @@ store_in_keymap (keymap, idx, def)
   if (!CONSP (keymap) || !EQ (XCAR (keymap), Qkeymap))
     error ("attempt to define a key in a non-keymap");
 
-  /* If idx is a list (some sort of mouse click, perhaps?),
-     the index we want to use is the car of the list, which
-     ought to be a symbol.  */
-  idx = EVENT_HEAD (idx);
+  /* If idx is a cons, and the car part is a character, idx must be of
+     the form (FROM-CHAR . TO-CHAR).  */
+  if (CONSP (idx) && CHARACTERP (XCAR (idx)))
+    CHECK_CHARACTER_CDR (idx);
+  else
+    /* If idx is a list (some sort of mouse click, perhaps?),
+       the index we want to use is the car of the list, which
+       ought to be a symbol.  */
+    idx = EVENT_HEAD (idx);
 
   /* If idx is a symbol, it might have modifiers, which need to
      be put in the canonical order.  */
@@ -921,6 +952,19 @@ store_in_keymap (keymap, idx, def)
                ASET (elt, XFASTINT (idx), def);
                return def;
              }
+           else if (CONSP (idx) && CHARACTERP (XCAR (idx)))
+             {
+               int from = XFASTINT (XCAR (idx));
+               int to = XFASTINT (XCDR (idx));
+
+               if (to >= ASIZE (elt))
+                 to = ASIZE (elt) - 1;
+               for (; from <= to; from++)
+                 ASET (elt, from, def);
+               if (to == XFASTINT (XCDR (idx)))
+                 /* We have defined all keys in IDX.  */
+                 return def;
+             }
            insertion_point = tail;
          }
        else if (CHAR_TABLE_P (elt))
@@ -937,6 +981,11 @@ store_in_keymap (keymap, idx, def)
                       NILP (def) ? Qt : def);
                return def;
              }
+           else if (CONSP (idx) && CHARACTERP (XCAR (idx)))
+             {
+               Fset_char_table_range (elt, idx, NILP (def) ? Qt : def);
+               return def;
+             }
            insertion_point = tail;
          }
        else if (CONSP (elt))
@@ -947,6 +996,19 @@ store_in_keymap (keymap, idx, def)
                XSETCDR (elt, def);
                return def;
              }
+           else if (CONSP (idx) && CHARACTERP (XCAR (idx)))
+             {
+               int from = XFASTINT (XCAR (idx));
+               int to = XFASTINT (XCDR (idx));
+
+               if (from <= XFASTINT (XCAR (elt))
+                   && to >= XFASTINT (XCAR (elt)))
+                 {
+                   XSETCDR (elt, def);
+                   if (from == to)
+                     return def;
+                 }
+             }
          }
        else if (EQ (elt, Qkeymap))
          /* If we find a 'keymap' symbol in the spine of KEYMAP,
@@ -961,9 +1023,22 @@ store_in_keymap (keymap, idx, def)
   keymap_end:
     /* We have scanned the entire keymap, and not found a binding for
        IDX.  Let's add one.  */
-    CHECK_IMPURE (insertion_point);
-    XSETCDR (insertion_point,
-            Fcons (Fcons (idx, def), XCDR (insertion_point)));
+    {
+      Lisp_Object elt;
+
+      if (CONSP (idx) && CHARACTERP (XCAR (idx)))
+       {
+         /* IDX specifies a range of characters, and not all of them
+            were handled yet, which means this keymap doesn't have a
+            char-table.  So, we insert a char-table now.  */
+         elt = Fmake_char_table (Qkeymap, Qnil);
+         Fset_char_table_range (elt, idx, NILP (def) ? Qt : def);
+       }
+      else
+       elt = Fcons (idx, def);
+      CHECK_IMPURE (insertion_point);
+      XSETCDR (insertion_point, Fcons (elt, XCDR (insertion_point)));
+    }
   }
 
   return def;
@@ -1049,7 +1124,7 @@ static void
 copy_keymap_1 (chartable, idx, elt)
      Lisp_Object chartable, idx, elt;
 {
-  Faset (chartable, idx, copy_keymap_item (elt));
+  Fset_char_table_range (chartable, idx, copy_keymap_item (elt));
 }
 
 DEFUN ("copy-keymap", Fcopy_keymap, Scopy_keymap, 1, 1, 0,
@@ -1072,9 +1147,8 @@ is not copied.  */)
       Lisp_Object elt = XCAR (keymap);
       if (CHAR_TABLE_P (elt))
        {
-         int indices[3];
          elt = Fcopy_sequence (elt);
-         map_char_table (copy_keymap_1, Qnil, elt, elt, elt, 0, indices);
+         map_char_table (copy_keymap_1, Qnil, elt, elt);
        }
       else if (VECTORP (elt))
        {
@@ -1171,8 +1245,15 @@ binding KEY to DEF is added at the front of KEYMAP.  */)
     {
       c = Faref (key, make_number (idx));
 
-      if (CONSP (c) && lucid_event_type_list_p (c))
-       c = Fevent_convert_list (c);
+      if (CONSP (c))
+       {
+         /* C may be a Lucid style event type list or a cons (FROM .
+            TO) specifying a range of characters.  */
+         if (lucid_event_type_list_p (c))
+           c = Fevent_convert_list (c);
+         else if (CHARACTERP (XCAR (c)))
+           CHECK_CHARACTER_CDR (c);
+       }
 
       if (SYMBOLP (c))
        silly_event_symbol_error (c);
@@ -1193,7 +1274,10 @@ binding KEY to DEF is added at the front of KEYMAP.  */)
          idx++;
        }
 
-      if (!INTEGERP (c) && !SYMBOLP (c) && !CONSP (c))
+      if (!INTEGERP (c) && !SYMBOLP (c)
+         && (!CONSP (c)
+             /* If C is a range, it must be a leaf.  */
+             || (INTEGERP (XCAR (c)) && idx != length)))
        error ("Key sequence contains invalid event");
 
       if (idx == length)
@@ -1549,13 +1633,13 @@ like in the respective argument of `key-binding'. */)
   /* If a mouse click position is given, our variables are based on
      the buffer clicked on, not the current buffer.  So we may have to
      switch the buffer here. */
-  
+
   if (CONSP (position))
     {
       Lisp_Object window;
-      
+
       window = POSN_WINDOW (position);
-         
+
       if (WINDOWP (window)
          && BUFFERP (XWINDOW (window)->buffer)
          && XBUFFER (XWINDOW (window)->buffer) != current_buffer)
@@ -1567,14 +1651,14 @@ like in the respective argument of `key-binding'. */)
             would not be a problem here, but it is easier to keep
             things the same.
          */
-             
+
          record_unwind_protect (Fset_buffer, Fcurrent_buffer ());
-         
+
          set_buffer_internal (XBUFFER (XWINDOW (window)->buffer));
        }
     }
 
-  keymaps = Fcons (current_global_map, Qnil);  
+  keymaps = Fcons (current_global_map, Qnil);
 
   if (!NILP (olp))
     {
@@ -1601,8 +1685,8 @@ like in the respective argument of `key-binding'. */)
       /* Get the buffer local maps, possibly overriden by text or
         overlay properties */
 
-      local_map = get_local_map (pt, current_buffer, Qlocal_map); 
-      keymap = get_local_map (pt, current_buffer, Qkeymap); 
+      local_map = get_local_map (pt, current_buffer, Qlocal_map);
+      keymap = get_local_map (pt, current_buffer, Qkeymap);
 
       if (CONSP (position))
        {
@@ -1610,7 +1694,7 @@ like in the respective argument of `key-binding'. */)
 
          /* For a mouse click, get the local text-property keymap
             of the place clicked on, rather than point.  */
-         
+
          if (POSN_INBUFFER_P (position))
            {
              Lisp_Object pos;
@@ -1621,7 +1705,7 @@ like in the respective argument of `key-binding'. */)
                {
                  local_map = get_local_map (XINT (pos),
                                             current_buffer, Qlocal_map);
-                 
+
                  keymap = get_local_map (XINT (pos),
                                          current_buffer, Qkeymap);
                }
@@ -1632,12 +1716,12 @@ like in the respective argument of `key-binding'. */)
             string displayed via the `display' property,
             consider `local-map' and `keymap' properties of
             that string.  */
-         
+
          if (string = POSN_STRING (position),
              (CONSP (string) && STRINGP (XCAR (string))))
            {
              Lisp_Object pos, map;
-             
+
              pos = XCDR (string);
              string = XCAR (string);
              if (INTEGERP (pos)
@@ -1653,7 +1737,7 @@ like in the respective argument of `key-binding'. */)
                    keymap = map;
                }
            }
-         
+
        }
 
       if (!NILP (local_map))
@@ -2014,7 +2098,8 @@ If KEYMAP is nil, that means no local keymap.  */)
 }
 
 DEFUN ("current-local-map", Fcurrent_local_map, Scurrent_local_map, 0, 0, 0,
-       doc: /* Return current buffer's local keymap, or nil if it has none.  */)
+       doc: /* Return current buffer's local keymap, or nil if it has none.
+Normally the local keymap is set by the major mode with `use-local-map'.  */)
      ()
 {
   return current_buffer->keymap;
@@ -2270,7 +2355,7 @@ spaces are put between sequence elements, etc.  */)
        }
       else if (VECTORP (list))
        {
-         key = AREF (list, i++);
+         key = AREF (list, i); i++;
        }
       else
        {
@@ -2313,15 +2398,13 @@ push_key_description (c, p, force_multibyte)
      int force_multibyte;
 {
   unsigned c2;
-  int valid_p;
 
   /* Clear all the meaningless bits above the meta bit.  */
   c &= meta_modifier | ~ - meta_modifier;
   c2 = c & ~(alt_modifier | ctrl_modifier | hyper_modifier
             | meta_modifier | shift_modifier | super_modifier);
 
-  valid_p = SINGLE_BYTE_CHAR_P (c2) || char_valid_p (c2, 0);
-  if (! valid_p)
+  if (! CHARACTERP (make_number (c2)))
     {
       /* KEY_DESCRIPTION_SIZE is large enough for this.  */
       p += sprintf (p, "[%d]", c);
@@ -2415,25 +2498,12 @@ push_key_description (c, p, force_multibyte)
     }
   else
     {
-      if (force_multibyte)
-       {
-         if (SINGLE_BYTE_CHAR_P (c))
-           c = unibyte_char_to_multibyte (c);
-         p += CHAR_STRING (c, p);
-       }
-      else if (NILP (current_buffer->enable_multibyte_characters))
-       {
-         int bit_offset;
-         *p++ = '\\';
-         /* The biggest character code uses 19 bits.  */
-         for (bit_offset = 18; bit_offset >= 0; bit_offset -= 3)
-           {
-             if (c >= (1 << bit_offset))
-               *p++ = ((c & (7 << bit_offset)) >> bit_offset) + '0';
-           }
-       }
+      /* Now we are sure that C is a valid character code.  */
+      if (NILP (current_buffer->enable_multibyte_characters)
+         && ! force_multibyte)
+       *p++ = multibyte_char_to_unibyte (c, Qnil);
       else
-       p += CHAR_STRING (c, p);
+       p += CHAR_STRING (c, (unsigned char *) p);
     }
 
   return p;
@@ -2457,56 +2527,10 @@ around function keys and event symbols.  */)
 
   if (INTEGERP (key))          /* Normal character */
     {
-      unsigned int charset, c1, c2;
-      int without_bits = XINT (key) & ~((-1) << CHARACTERBITS);
+      char tem[KEY_DESCRIPTION_SIZE];
 
-      if (SINGLE_BYTE_CHAR_P (without_bits))
-       charset = 0;
-      else
-       SPLIT_CHAR (without_bits, charset, c1, c2);
-
-      if (! CHAR_VALID_P (without_bits, 1))
-       {
-         char buf[256];
-
-         sprintf (buf, "Invalid char code %ld", (long) XINT (key));
-         return build_string (buf);
-       }
-      else if (charset
-              && ((c1 == 0 && c2 == -1) || c2 == 0))
-       {
-         /* Handle a generic character.  */
-         Lisp_Object name;
-         char buf[256];
-
-         name = CHARSET_TABLE_INFO (charset, CHARSET_SHORT_NAME_IDX);
-         CHECK_STRING (name);
-         if (c1 == 0)
-           /* Only a charset is specified.   */
-           sprintf (buf, "Generic char %d: all of ", without_bits);
-         else
-           /* 1st code-point of 2-dimensional charset is specified.   */
-           sprintf (buf, "Generic char %d: row %d of ", without_bits, c1);
-         return concat2 (build_string (buf), name);
-       }
-      else
-       {
-         char tem[KEY_DESCRIPTION_SIZE], *end;
-         int nbytes, nchars;
-         Lisp_Object string;
-
-         end = push_key_description (XUINT (key), tem, 1);
-         nbytes = end - tem;
-         nchars = multibyte_chars_in_text (tem, nbytes);
-         if (nchars == nbytes)
-           {
-             *end = '\0';
-             string = build_string (tem);
-           }
-         else
-           string = make_multibyte_string (tem, nchars, nbytes);
-         return string;
-       }
+      *push_key_description (XUINT (key), tem, 1) = 0;
+      return build_string (tem);
     }
   else if (SYMBOLP (key))      /* Function key or event-symbol */
     {
@@ -2572,7 +2596,7 @@ See Info node `(elisp)Describing Characters' for examples.  */)
   CHECK_NUMBER (character);
 
   c = XINT (character);
-  if (!SINGLE_BYTE_CHAR_P (c))
+  if (!ASCII_CHAR_P (c))
     {
       int len = CHAR_STRING (c, str);
 
@@ -2584,14 +2608,18 @@ See Info node `(elisp)Describing Characters' for examples.  */)
   return build_string (str);
 }
 
-/* Return non-zero if SEQ contains only ASCII characters, perhaps with
-   a meta bit.  */
+static int where_is_preferred_modifier;
+
+/* Return 0 if SEQ uses non-preferred modifiers or non-char events.
+   Else, return 2 if SEQ uses the where_is_preferred_modifier,
+   and 1 otherwise.  */
 static int
-ascii_sequence_p (seq)
+preferred_sequence_p (seq)
      Lisp_Object seq;
 {
   int i;
   int len = XINT (Flength (seq));
+  int result = 1;
 
   for (i = 0; i < len; i++)
     {
@@ -2600,27 +2628,35 @@ ascii_sequence_p (seq)
       XSETFASTINT (ii, i);
       elt = Faref (seq, ii);
 
-      if (!INTEGERP (elt)
-         || (XUINT (elt) & ~CHAR_META) >= 0x80)
+      if (!INTEGERP (elt))
        return 0;
+      else
+       {
+         int modifiers = XUINT (elt) & (CHAR_MODIFIER_MASK & ~CHAR_META);
+         if (modifiers == where_is_preferred_modifier)
+           result = 2;
+         else if (modifiers)
+           return 0;
+       }
     }
 
-  return 1;
+  return result;
 }
 
 \f
 /* where-is - finding a command in a set of keymaps.                   */
 
-static Lisp_Object where_is_internal ();
 static void where_is_internal_1 P_ ((Lisp_Object key, Lisp_Object binding,
                                     Lisp_Object args, void *data));
 
 /* Like Flookup_key, but uses a list of keymaps SHADOW instead of a single map.
-   Returns the first non-nil binding found in any of those maps.  */
+   Returns the first non-nil binding found in any of those maps.
+   If REMAP is true, pass the result of the lookup through command
+   remapping before returning it.  */
 
 static Lisp_Object
-shadow_lookup (shadow, key, flag)
-     Lisp_Object shadow, key, flag;
+shadow_lookup (Lisp_Object shadow, Lisp_Object key, Lisp_Object flag,
+              int remap)
 {
   Lisp_Object tail, value;
 
@@ -2635,7 +2671,15 @@ shadow_lookup (shadow, key, flag)
            return Qnil;
        }
       else if (!NILP (value))
-       return value;
+       {
+         Lisp_Object remapping;
+         if (remap && SYMBOLP (value)
+             && (remapping = Fcommand_remapping (value, Qnil, shadow),
+                 !NILP (remapping)))
+           return remapping;
+         else
+           return value;
+       }
     }
   return Qnil;
 }
@@ -2643,23 +2687,49 @@ shadow_lookup (shadow, key, flag)
 static Lisp_Object Vmouse_events;
 
 struct where_is_internal_data {
-  Lisp_Object definition, noindirect, this, last;
-  int last_is_meta;
+  Lisp_Object definition, this, last;
+  int last_is_meta, noindirect;
   Lisp_Object sequences;
 };
 
-/* This function can GC if Flookup_key autoloads any keymaps.  */
+/* This function can't GC, AFAIK.  */
+/* Return the list of bindings found.  This list is ordered "longest
+   to shortest".  It may include bindings that are actually shadowed
+   by others, as well as duplicate bindings and remapping bindings.
+   The list returned is potentially shared with where_is_cache, so
+   be careful not to modify it via side-effects.  */
 
 static Lisp_Object
-where_is_internal (definition, keymaps, firstonly, noindirect, no_remap)
-     Lisp_Object definition, keymaps;
-     Lisp_Object firstonly, noindirect, no_remap;
+where_is_internal (Lisp_Object definition, Lisp_Object keymaps,
+                  int noindirect, int nomenus)
 {
   Lisp_Object maps = Qnil;
-  Lisp_Object found, sequences;
-  struct gcpro gcpro1, gcpro2, gcpro3, gcpro4, gcpro5;
-  /* 1 means ignore all menu bindings entirely.  */
-  int nomenus = !NILP (firstonly) && !EQ (firstonly, Qnon_ascii);
+  Lisp_Object found;
+  struct where_is_internal_data data;
+
+  /* Only important use of caching is for the menubar
+     (i.e. where-is-internal called with (def nil t nil nil)).  */
+  if (nomenus && !noindirect)
+    {
+      /* Check heuristic-consistency of the cache.  */
+      if (NILP (Fequal (keymaps, where_is_cache_keymaps)))
+       where_is_cache = Qnil;
+
+      if (NILP (where_is_cache))
+       {
+         /* We need to create the cache.  */
+         Lisp_Object args[2];
+         where_is_cache = Fmake_hash_table (0, args);
+         where_is_cache_keymaps = Qt;
+       }
+      else
+       /* We can reuse the cache.  */
+       return Fgethash (definition, where_is_cache, Qnil);
+    }
+  else
+    /* Kill the cache so that where_is_internal_1 doesn't think
+       we're filling it up.  */
+    where_is_cache = Qnil;
 
   found = keymaps;
   while (CONSP (found))
@@ -2670,22 +2740,11 @@ where_is_internal (definition, keymaps, firstonly, noindirect, no_remap)
       found = XCDR (found);
     }
 
-  GCPRO5 (definition, keymaps, maps, found, sequences);
-  found = Qnil;
-  sequences = Qnil;
-
-  /* If this command is remapped, then it has no key bindings
-     of its own.  */
-  if (NILP (no_remap)
-      && SYMBOLP (definition)
-      && !NILP (Fcommand_remapping (definition, Qnil, keymaps)))
-    RETURN_UNGCPRO (Qnil);
-
+  data.sequences = Qnil;
   for (; CONSP (maps); maps = XCDR (maps))
     {
       /* Key sequence to reach map, and the map that it reaches */
       register Lisp_Object this, map, tem;
-      struct where_is_internal_data data;
 
       /* In order to fold [META-PREFIX-CHAR CHAR] sequences into
         [M-CHAR] sequences, check if last character of the sequence
@@ -2699,7 +2758,7 @@ where_is_internal (definition, keymaps, firstonly, noindirect, no_remap)
       last_is_meta = (XINT (last) >= 0
                      && EQ (Faref (this, last), meta_prefix_char));
 
-      /* if (nomenus && !ascii_sequence_p (this)) */
+      /* if (nomenus && !preferred_sequence_p (this)) */
       if (nomenus && XINT (last) >= 0
          && SYMBOLP (tem = Faref (this, make_number (0)))
          && !NILP (Fmemq (XCAR (parse_modifiers (tem)), Vmouse_events)))
@@ -2715,105 +2774,27 @@ where_is_internal (definition, keymaps, firstonly, noindirect, no_remap)
       data.this = this;
       data.last = last;
       data.last_is_meta = last_is_meta;
-      data.sequences = Qnil;
 
       if (CONSP (map))
        map_keymap (map, where_is_internal_1, Qnil, &data, 0);
-
-      sequences = data.sequences;
-
-      while (CONSP (sequences))
-       {
-         Lisp_Object sequence, remapped, function;
-         
-         sequence = XCAR (sequences);
-         sequences = XCDR (sequences);
-
-         /* If the current sequence is a command remapping with
-            format [remap COMMAND], find the key sequences
-            which run COMMAND, and use those sequences instead.  */
-         remapped = Qnil;
-         if (NILP (no_remap)
-             && VECTORP (sequence) && XVECTOR (sequence)->size == 2
-             && EQ (AREF (sequence, 0), Qremap)
-             && (function = AREF (sequence, 1), SYMBOLP (function)))
-           {
-             Lisp_Object remapped1;
-             
-             remapped1 = where_is_internal (function, keymaps, firstonly, noindirect, Qt);
-             if (CONSP (remapped1))
-               {
-                 /* Verify that this key binding actually maps to the
-                    remapped command (see below).  */
-                 if (!EQ (shadow_lookup (keymaps, XCAR (remapped1), Qnil), function))
-                   continue;
-                 sequence = XCAR (remapped1);
-                 remapped = XCDR (remapped1);
-                 goto record_sequence;
-               }
-           }
-
-         /* Verify that this key binding is not shadowed by another
-            binding for the same key, before we say it exists.
-
-            Mechanism: look for local definition of this key and if
-            it is defined and does not match what we found then
-            ignore this key.
-
-            Either nil or number as value from Flookup_key
-            means undefined.  */
-         if (!EQ (shadow_lookup (keymaps, sequence, Qnil), definition))
-           continue;
-
-       record_sequence:
-         /* Don't annoy user with strings from a menu such as
-            Select Paste.  Change them all to "(any string)",
-            so that there seems to be only one menu item
-            to report. */
-         if (! NILP (sequence))
-           {
-             Lisp_Object tem;
-             tem = Faref (sequence, make_number (XVECTOR (sequence)->size - 1));
-             if (STRINGP (tem))
-               Faset (sequence, make_number (XVECTOR (sequence)->size - 1),
-                      build_string ("(any string)"));
-           }
-
-         /* It is a true unshadowed match.  Record it, unless it's already
-            been seen (as could happen when inheriting keymaps).  */
-         if (NILP (Fmember (sequence, found)))
-           found = Fcons (sequence, found);
-
-         /* If firstonly is Qnon_ascii, then we can return the first
-            binding we find.  If firstonly is not Qnon_ascii but not
-            nil, then we should return the first ascii-only binding
-            we find.  */
-         if (EQ (firstonly, Qnon_ascii))
-           RETURN_UNGCPRO (sequence);
-         else if (!NILP (firstonly) && ascii_sequence_p (sequence))
-           RETURN_UNGCPRO (sequence);
-
-         if (CONSP (remapped))
-           {
-             sequence = XCAR (remapped);
-             remapped = XCDR (remapped);
-             goto record_sequence;
-           }
-       }
     }
 
-  UNGCPRO;
-
-  found = Fnreverse (found);
+  if (nomenus && !noindirect)
+    { /* Remember for which keymaps this cache was built.
+        We do it here (late) because we want to keep where_is_cache_keymaps
+        set to t while the cache isn't fully filled.  */
+      where_is_cache_keymaps = keymaps;
+      /* During cache-filling, data.sequences is not filled by
+        where_is_internal_1.  */
+      return Fgethash (definition, where_is_cache, Qnil);
+    }
+  else
+    return data.sequences;
+}
 
-  /* firstonly may have been t, but we may have gone all the way through
-     the keymaps without finding an all-ASCII key sequence.  So just
-     return the best we could find.  */
-  if (!NILP (firstonly))
-    return Fcar (found);
+static Lisp_Object Vwhere_is_preferred_modifier;
 
-  return found;
-}
+/* This function can GC if Flookup_key autoloads any keymaps.  */
 
 DEFUN ("where-is-internal", Fwhere_is_internal, Swhere_is_internal, 1, 5, 0,
        doc: /* Return list of keys that invoke DEFINITION.
@@ -2825,7 +2806,8 @@ If optional 3rd arg FIRSTONLY is non-nil, return the first key sequence found,
 rather than a list of all possible key sequences.
 If FIRSTONLY is the symbol `non-ascii', return the first binding found,
 no matter what it is.
-If FIRSTONLY has another non-nil value, prefer sequences of ASCII characters
+If FIRSTONLY has another non-nil value, prefer bindings
+that use the modifier key specified in `where-is-preferred-modifier'
 \(or their meta variants) and entirely reject menu bindings.
 
 If optional 4th arg NOINDIRECT is non-nil, don't follow indirections
@@ -2839,10 +2821,28 @@ remapped command in the returned list.  */)
      Lisp_Object definition, keymap;
      Lisp_Object firstonly, noindirect, no_remap;
 {
-  Lisp_Object sequences, keymaps;
+  /* The keymaps in which to search.  */
+  Lisp_Object keymaps;
+  /* Potentially relevant bindings in "shortest to longest" order.  */
+  Lisp_Object sequences = Qnil;
+    /* Actually relevant bindings.  */
+  Lisp_Object found = Qnil;
   /* 1 means ignore all menu bindings entirely.  */
   int nomenus = !NILP (firstonly) && !EQ (firstonly, Qnon_ascii);
-  Lisp_Object result;
+  struct gcpro gcpro1, gcpro2, gcpro3, gcpro4, gcpro5;
+  /* List of sequences found via remapping.  Keep them in a separate
+     variable, so as to push them later, since we prefer
+     non-remapped binding.  */
+  Lisp_Object remapped_sequences = Qnil;
+  /* Whether or not we're handling remapped sequences.  This is needed
+     because remapping is not done recursively by Fcommand_remapping: you
+     can't remap and remapped command.  */
+  int remapped = 0;
+  Lisp_Object tem;
+
+  /* Refresh the C version of the modifier preference.  */
+  where_is_preferred_modifier
+    = parse_solitary_modifier (Vwhere_is_preferred_modifier);
 
   /* Find the relevant keymaps.  */
   if (CONSP (keymap) && KEYMAPP (XCAR (keymap)))
@@ -2852,68 +2852,126 @@ remapped command in the returned list.  */)
   else
     keymaps = Fcurrent_active_maps (Qnil, Qnil);
 
-  /* Only use caching for the menubar (i.e. called with (def nil t nil).
-     We don't really need to check `keymap'.  */
-  if (nomenus && NILP (noindirect) && NILP (keymap))
+  GCPRO5 (definition, keymaps, found, sequences, remapped_sequences);
+
+  /* If this command is remapped, then it has no key bindings of its own.
+     FIXME: Actually, this is not quite right: if A is remapped to
+     `definition', then bindings to A will actually bind the key to
+     `definition' despite the remapping from `definition' to something else.
+     Another corner case is if `definition' is remapped to itself.  */
+  if (NILP (no_remap)
+      && SYMBOLP (definition)
+      && !NILP (Fcommand_remapping (definition, Qnil, keymaps)))
+    RETURN_UNGCPRO (Qnil);
+
+  if (SYMBOLP (definition)
+      && !NILP (firstonly)
+      && !NILP (tem = Fget (definition, QCadvertised_binding)))
     {
-      Lisp_Object *defns;
-      int i, j, n;
-      struct gcpro gcpro1, gcpro2, gcpro3, gcpro4, gcpro5;
+      /* We have a list of advertized bindings.  */
+      while (CONSP (tem))
+       if (EQ (shadow_lookup (keymaps, XCAR (tem), Qnil, 0), definition))
+         return XCAR (tem);
+       else
+         tem = XCDR (tem);
+      if (EQ (shadow_lookup (keymaps, tem, Qnil, 0), definition))
+       return tem;
+    }
 
-      /* Check heuristic-consistency of the cache.  */
-      if (NILP (Fequal (keymaps, where_is_cache_keymaps)))
-       where_is_cache = Qnil;
+  sequences = Freverse (where_is_internal (definition, keymaps,
+                                          !NILP (noindirect), nomenus));
 
-      if (NILP (where_is_cache))
-       {
-         /* We need to create the cache.  */
-         Lisp_Object args[2];
-         where_is_cache = Fmake_hash_table (0, args);
-         where_is_cache_keymaps = Qt;
+  while (CONSP (sequences)
+        /* If we're at the end of the `sequences' list and we haven't
+           considered remapped sequences yet, copy them over and
+           process them.  */
+        || (!remapped && (sequences = remapped_sequences,
+                          remapped = 1),
+            CONSP (sequences)))
+    {
+      Lisp_Object sequence, function;
 
-         /* Fill in the cache.  */
-         GCPRO5 (definition, keymaps, firstonly, noindirect, no_remap);
-         where_is_internal (definition, keymaps, firstonly, noindirect, no_remap);
-         UNGCPRO;
+      sequence = XCAR (sequences);
+      sequences = XCDR (sequences);
+
+      /* Verify that this key binding is not shadowed by another
+        binding for the same key, before we say it exists.
 
-         where_is_cache_keymaps = keymaps;
+        Mechanism: look for local definition of this key and if
+        it is defined and does not match what we found then
+        ignore this key.
+
+        Either nil or number as value from Flookup_key
+        means undefined.  */
+      if (NILP (Fequal (shadow_lookup (keymaps, sequence, Qnil, remapped),
+                       definition)))
+       continue;
+
+      /* If the current sequence is a command remapping with
+        format [remap COMMAND], find the key sequences
+        which run COMMAND, and use those sequences instead.  */
+      if (NILP (no_remap) && !remapped
+         && VECTORP (sequence) && ASIZE (sequence) == 2
+         && EQ (AREF (sequence, 0), Qremap)
+         && (function = AREF (sequence, 1), SYMBOLP (function)))
+       {
+         Lisp_Object seqs = where_is_internal (function, keymaps,
+                                               !NILP (noindirect), nomenus);
+         remapped_sequences = nconc2 (Freverse (seqs), remapped_sequences);
+         continue;
        }
 
-      /* We want to process definitions from the last to the first.
-        Instead of consing, copy definitions to a vector and step
-        over that vector.  */
-      sequences = Fgethash (definition, where_is_cache, Qnil);
-      n = XINT (Flength (sequences));
-      defns = (Lisp_Object *) alloca (n * sizeof *defns);
-      for (i = 0; CONSP (sequences); sequences = XCDR (sequences))
-       defns[i++] = XCAR (sequences);
-
-      /* Verify that the key bindings are not shadowed.  Note that
-        the following can GC.  */
-      GCPRO2 (definition, keymaps);
-      result = Qnil;
-      j = -1;
-      for (i = n - 1; i >= 0; --i)
-       if (EQ (shadow_lookup (keymaps, defns[i], Qnil), definition))
-         {
-           if (ascii_sequence_p (defns[i]))
-             break;
-           else if (j < 0)
-             j = i;
-         }
+      /* Don't annoy user with strings from a menu such as the
+        entries from the "Edit => Paste from Kill Menu".
+        Change them all to "(any string)", so that there
+        seems to be only one menu item to report.  */
+      if (! NILP (sequence))
+       {
+         Lisp_Object tem;
+         tem = Faref (sequence, make_number (ASIZE (sequence) - 1));
+         if (STRINGP (tem))
+           Faset (sequence, make_number (ASIZE (sequence) - 1),
+                  build_string ("(any string)"));
+       }
 
-      result = i >= 0 ? defns[i] : (j >= 0 ? defns[j] : Qnil);
-      UNGCPRO;
+      /* It is a true unshadowed match.  Record it, unless it's already
+        been seen (as could happen when inheriting keymaps).  */
+      if (NILP (Fmember (sequence, found)))
+       found = Fcons (sequence, found);
+
+      /* If firstonly is Qnon_ascii, then we can return the first
+        binding we find.  If firstonly is not Qnon_ascii but not
+        nil, then we should return the first ascii-only binding
+        we find.  */
+      if (EQ (firstonly, Qnon_ascii))
+       RETURN_UNGCPRO (sequence);
+      else if (!NILP (firstonly)
+              && 2 == preferred_sequence_p (sequence))
+       RETURN_UNGCPRO (sequence);
     }
+
+  UNGCPRO;
+
+  found = Fnreverse (found);
+
+  /* firstonly may have been t, but we may have gone all the way through
+     the keymaps without finding an all-ASCII key sequence.  So just
+     return the best we could find.  */
+  if (NILP (firstonly))
+    return found;
+  else if (where_is_preferred_modifier == 0)
+    return Fcar (found);
   else
-    {
-      /* Kill the cache so that where_is_internal_1 doesn't think
-        we're filling it up.  */
-      where_is_cache = Qnil;
-      result = where_is_internal (definition, keymaps, firstonly, noindirect, no_remap);
+    { /* Maybe we did not find a preferred_modifier binding, but we did find
+        some ASCII binding.  */
+      Lisp_Object bindings = found;
+      while (CONSP (bindings))
+       if (preferred_sequence_p (XCAR (bindings)))
+         return XCAR (bindings);
+       else
+         bindings = XCDR (bindings);
+      return Fcar (found);
     }
-
-  return result;
 }
 
 /* This function can GC because get_keyelt can.  */
@@ -2925,14 +2983,14 @@ where_is_internal_1 (key, binding, args, data)
 {
   struct where_is_internal_data *d = data; /* Cast! */
   Lisp_Object definition = d->definition;
-  Lisp_Object noindirect = d->noindirect;
+  int noindirect = d->noindirect;
   Lisp_Object this = d->this;
   Lisp_Object last = d->last;
   int last_is_meta = d->last_is_meta;
   Lisp_Object sequence;
 
   /* Search through indirections unless that's not wanted.  */
-  if (NILP (noindirect))
+  if (!noindirect)
     binding = get_keyelt (binding, 0);
 
   /* End this iteration if this element does not match
@@ -2951,7 +3009,11 @@ where_is_internal_1 (key, binding, args, data)
       Faset (sequence, last, make_number (XINT (key) | meta_modifier));
     }
   else
-    sequence = append_key (this, key);
+    {
+      if (CONSP (key))
+       key = Fcons (XCAR (key), XCDR (key));
+      sequence = append_key (this, key);
+    }
 
   if (!NILP (where_is_cache))
     {
@@ -3078,7 +3140,7 @@ You type        Translation\n\
          char *title, *p;
 
          if (!SYMBOLP (modes[i]))
-           abort();
+           abort ();
 
          p = title = (char *) alloca (42 + SCHARS (SYMBOL_NAME (modes[i])));
          *p++ = '\f';
@@ -3405,14 +3467,16 @@ describe_map (map, prefix, elt_describer, partial, shadow,
   kludge = Fmake_vector (make_number (1), Qnil);
   definition = Qnil;
 
+  GCPRO3 (prefix, definition, kludge);
+
+  map = call1 (Qkeymap_canonicalize, map);
+
   for (tail = map; CONSP (tail); tail = XCDR (tail))
     length_needed++;
 
   vect = ((struct describe_map_elt *)
          alloca (sizeof (struct describe_map_elt) * length_needed));
 
-  GCPRO3 (prefix, definition, kludge);
-
   for (tail = map; CONSP (tail); tail = XCDR (tail))
     {
       QUIT;
@@ -3453,7 +3517,7 @@ describe_map (map, prefix, elt_describer, partial, shadow,
          ASET (kludge, 0, event);
          if (!NILP (shadow))
            {
-             tem = shadow_lookup (shadow, kludge, Qt);
+             tem = shadow_lookup (shadow, kludge, Qt, 0);
              if (!NILP (tem))
                {
                  /* If both bindings are keymaps, this key is a prefix key,
@@ -3607,9 +3671,10 @@ DESCRIBER is the output function used; nil means use `princ'.  */)
    If the definition in effect in the whole map does not match
    the one in this vector, we ignore this one.
 
-   When describing a sub-char-table, INDICES is a list of
-   indices at higher levels in this char-table,
-   and CHAR_TABLE_DEPTH says how many levels down we have gone.
+   ARGS is simply passed as the second argument to ELT_DESCRIBER.
+
+   INDICES and CHAR_TABLE_DEPTH are ignored.  They will be removed in
+   the near future.
 
    KEYMAP_P is 1 if vector is known to be a keymap, so map ESC to M-.
 
@@ -3634,24 +3699,18 @@ describe_vector (vector, prefix, args, elt_describer,
   Lisp_Object definition;
   Lisp_Object tem2;
   Lisp_Object elt_prefix = Qnil;
-  register int i;
+  int i;
   Lisp_Object suppress;
   Lisp_Object kludge;
   int first = 1;
   struct gcpro gcpro1, gcpro2, gcpro3, gcpro4;
   /* Range of elements to be handled.  */
-  int from, to;
-  /* A flag to tell if a leaf in this level of char-table is not a
-     generic character (i.e. a complete multibyte character).  */
-  int complete_char;
-  int character;
+  int from, to, stop;
+  Lisp_Object character;
   int starting_i;
 
   suppress = Qnil;
 
-  if (indices == 0)
-    indices = (int *) alloca (3 * sizeof (int));
-
   definition = Qnil;
 
   if (!keymap_p)
@@ -3675,61 +3734,38 @@ describe_vector (vector, prefix, args, elt_describer,
   if (partial)
     suppress = intern ("suppress-keymap");
 
+  from = 0;
   if (CHAR_TABLE_P (vector))
-    {
-      if (char_table_depth == 0)
-       {
-         /* VECTOR is a top level char-table.  */
-         complete_char = 1;
-         from = 0;
-         to = CHAR_TABLE_ORDINARY_SLOTS;
-       }
-      else
-       {
-         /* VECTOR is a sub char-table.  */
-         if (char_table_depth >= 3)
-           /* A char-table is never that deep.  */
-           error ("Too deep char table");
-
-         complete_char
-           = (CHARSET_VALID_P (indices[0])
-              && ((CHARSET_DIMENSION (indices[0]) == 1
-                   && char_table_depth == 1)
-                  || char_table_depth == 2));
-
-         /* Meaningful elements are from 32th to 127th.  */
-         from = 32;
-         to = SUB_CHAR_TABLE_ORDINARY_SLOTS;
-       }
-    }
+    stop = MAX_5_BYTE_CHAR + 1, to = MAX_CHAR + 1;
   else
-    {
-      /* This does the right thing for ordinary vectors.  */
+    stop = to = XVECTOR (vector)->size;
 
-      complete_char = 1;
-      from = 0;
-      to = XVECTOR (vector)->size;
-    }
-
-  for (i = from; i < to; i++)
+  for (i = from; ; i++)
     {
       int this_shadowed = 0;
+      int range_beg, range_end;
+      Lisp_Object val;
+
       QUIT;
 
-      if (CHAR_TABLE_P (vector))
+      if (i == stop)
        {
-         if (char_table_depth == 0 && i >= CHAR_TABLE_SINGLE_BYTE_SLOTS)
-           complete_char = 0;
+         if (i == to)
+           break;
+         stop = to;
+       }
 
-         if (i >= CHAR_TABLE_SINGLE_BYTE_SLOTS
-             && !CHARSET_DEFINED_P (i - 128))
-           continue;
+      starting_i = i;
 
-         definition
-           = get_keyelt (XCHAR_TABLE (vector)->contents[i], 0);
+      if (CHAR_TABLE_P (vector))
+       {
+         range_beg = i;
+         i = stop - 1;
+         val = char_table_ref_and_range (vector, range_beg, &range_beg, &i);
        }
       else
-       definition = get_keyelt (AREF (vector, i), 0);
+       val = AREF (vector, i);
+      definition = get_keyelt (val, 0);
 
       if (NILP (definition)) continue;
 
@@ -3743,35 +3779,15 @@ describe_vector (vector, prefix, args, elt_describer,
          if (!NILP (tem)) continue;
        }
 
-      /* Set CHARACTER to the character this entry describes, if any.
-        Also update *INDICES.  */
-      if (CHAR_TABLE_P (vector))
-       {
-         indices[char_table_depth] = i;
-
-         if (char_table_depth == 0)
-           {
-             character = i;
-             indices[0] = i - 128;
-           }
-         else if (complete_char)
-           {
-             character = MAKE_CHAR (indices[0], indices[1], indices[2]);
-           }
-         else
-           character = 0;
-       }
-      else
-       character = i;
-
-      ASET (kludge, 0, make_number (character));
+      character = make_number (starting_i);
+      ASET (kludge, 0, character);
 
       /* If this binding is shadowed by some other map, ignore it.  */
-      if (!NILP (shadow) && complete_char)
+      if (!NILP (shadow))
        {
          Lisp_Object tem;
 
-         tem = shadow_lookup (shadow, kludge, Qt);
+         tem = shadow_lookup (shadow, kludge, Qt, 0);
 
          if (!NILP (tem))
            {
@@ -3784,7 +3800,7 @@ describe_vector (vector, prefix, args, elt_describer,
 
       /* Ignore this definition if it is shadowed by an earlier
         one in the same keymap.  */
-      if (!NILP (entire_map) && complete_char)
+      if (!NILP (entire_map))
        {
          Lisp_Object tem;
 
@@ -3796,97 +3812,38 @@ describe_vector (vector, prefix, args, elt_describer,
 
       if (first)
        {
-         if (char_table_depth == 0)
-           insert ("\n", 1);
+         insert ("\n", 1);
          first = 0;
        }
 
-      /* For a sub char-table, show the depth by indentation.
-        CHAR_TABLE_DEPTH can be greater than 0 only for a char-table.  */
-      if (char_table_depth > 0)
-       insert ("    ", char_table_depth * 2); /* depth is 1 or 2.  */
-
       /* Output the prefix that applies to every entry in this map.  */
       if (!NILP (elt_prefix))
        insert1 (elt_prefix);
 
-      /* Insert or describe the character this slot is for,
-        or a description of what it is for.  */
-      if (SUB_CHAR_TABLE_P (vector))
-       {
-         if (complete_char)
-           insert_char (character);
-         else
-           {
-             /* We need an octal representation for this block of
-                 characters.  */
-             char work[16];
-             sprintf (work, "(row %d)", i);
-             insert (work, strlen (work));
-           }
-       }
-      else if (CHAR_TABLE_P (vector))
-       {
-         if (complete_char)
-           insert1 (Fkey_description (kludge, prefix));
-         else
-           {
-             /* Print the information for this character set.  */
-             insert_string ("<");
-             tem2 = CHARSET_TABLE_INFO (i - 128, CHARSET_SHORT_NAME_IDX);
-             if (STRINGP (tem2))
-               insert_from_string (tem2, 0, 0, SCHARS (tem2),
-                                   SBYTES (tem2), 0);
-             else
-               insert ("?", 1);
-             insert (">", 1);
-           }
-       }
-      else
-       {
-         insert1 (Fkey_description (kludge, prefix));
-       }
-
-      /* If we find a sub char-table within a char-table,
-        scan it recursively; it defines the details for
-        a character set or a portion of a character set.  */
-      if (CHAR_TABLE_P (vector) && SUB_CHAR_TABLE_P (definition))
-       {
-         insert ("\n", 1);
-         describe_vector (definition, prefix, args, elt_describer,
-                          partial, shadow, entire_map,
-                          indices, char_table_depth + 1, keymap_p,
-                          mention_shadow);
-         continue;
-       }
-
-      starting_i = i;
+      insert1 (Fkey_description (kludge, prefix));
 
       /* Find all consecutive characters or rows that have the same
-         definition.  But, for elements of a top level char table, if
-         they are for charsets, we had better describe one by one even
-         if they have the same definition.  */
+         definition.  But, VECTOR is a char-table, we had better put a
+         boundary between normal characters (-#x3FFF7F) and 8-bit
+         characters (#x3FFF80-).  */
       if (CHAR_TABLE_P (vector))
        {
-         int limit = to;
-
-         if (char_table_depth == 0)
-           limit = CHAR_TABLE_SINGLE_BYTE_SLOTS;
-
-         while (i + 1 < limit
-                && (tem2 = get_keyelt (XCHAR_TABLE (vector)->contents[i + 1], 0),
-                    !NILP (tem2))
+         while (i + 1 < stop
+                && (range_beg = i + 1, range_end = stop - 1,
+                  val = char_table_ref_and_range (vector, range_beg,
+                                                  &range_beg, &range_end),
+                  tem2 = get_keyelt (val, 0),
+                  !NILP (tem2))
                 && !NILP (Fequal (tem2, definition)))
-           i++;
+           i = range_end;
        }
       else
-       while (i + 1 < to
+       while (i + 1 < stop
               && (tem2 = get_keyelt (AREF (vector, i + 1), 0),
                   !NILP (tem2))
               && !NILP (Fequal (tem2, definition)))
          i++;
 
-
       /* If we have a range of more than one character,
         print where the range reaches to.  */
 
@@ -3899,31 +3856,7 @@ describe_vector (vector, prefix, args, elt_describer,
          if (!NILP (elt_prefix))
            insert1 (elt_prefix);
 
-         if (CHAR_TABLE_P (vector))
-           {
-             if (char_table_depth == 0)
-               {
-                 insert1 (Fkey_description (kludge, prefix));
-               }
-             else if (complete_char)
-               {
-                 indices[char_table_depth] = i;
-                 character = MAKE_CHAR (indices[0], indices[1], indices[2]);
-                 insert_char (character);
-               }
-             else
-               {
-                 /* We need an octal representation for this block of
-                    characters.  */
-                 char work[16];
-                 sprintf (work, "(row %d)", i);
-                 insert (work, strlen (work));
-               }
-           }
-         else
-           {
-             insert1 (Fkey_description (kludge, prefix));
-           }
+         insert1 (Fkey_description (kludge, prefix));
        }
 
       /* Print a description of the definition of this character.
@@ -3939,11 +3872,11 @@ describe_vector (vector, prefix, args, elt_describer,
        }
     }
 
-  /* For (sub) char-table, print `defalt' slot at last.  */
-  if (CHAR_TABLE_P (vector) && !NILP (XCHAR_TABLE (vector)->defalt))
+  if (CHAR_TABLE_P (vector) && ! NILP (XCHAR_TABLE (vector)->defalt))
     {
-      insert ("    ", char_table_depth * 2);
-      insert_string ("<<default>>");
+      if (!NILP (elt_prefix))
+       insert1 (elt_prefix);
+      insert ("default", 7);
       (*elt_describer) (XCHAR_TABLE (vector)->defalt, args);
     }
 
@@ -3989,13 +3922,16 @@ Return list of symbols found.  */)
 void
 syms_of_keymap ()
 {
-  Qkeymap = intern ("keymap");
+  Qkeymap = intern_c_string ("keymap");
   staticpro (&Qkeymap);
   staticpro (&apropos_predicate);
   staticpro (&apropos_accumulate);
   apropos_predicate = Qnil;
   apropos_accumulate = Qnil;
 
+  Qkeymap_canonicalize = intern_c_string ("keymap-canonicalize");
+  staticpro (&Qkeymap_canonicalize);
+
   /* Now we are ready to set up this property, so we can
      create char tables.  */
   Fput (Qkeymap, Qchar_table_extra_slots, make_number (0));
@@ -4005,26 +3941,26 @@ syms_of_keymap ()
      pointed to by a C variable */
 
   global_map = Fmake_keymap (Qnil);
-  Fset (intern ("global-map"), global_map);
+  Fset (intern_c_string ("global-map"), global_map);
 
   current_global_map = global_map;
   staticpro (&global_map);
   staticpro (&current_global_map);
 
   meta_map = Fmake_keymap (Qnil);
-  Fset (intern ("esc-map"), meta_map);
-  Ffset (intern ("ESC-prefix"), meta_map);
+  Fset (intern_c_string ("esc-map"), meta_map);
+  Ffset (intern_c_string ("ESC-prefix"), meta_map);
 
   control_x_map = Fmake_keymap (Qnil);
-  Fset (intern ("ctl-x-map"), control_x_map);
-  Ffset (intern ("Control-X-prefix"), control_x_map);
+  Fset (intern_c_string ("ctl-x-map"), control_x_map);
+  Ffset (intern_c_string ("Control-X-prefix"), control_x_map);
 
   exclude_keys
-    = Fcons (Fcons (build_string ("DEL"), build_string ("\\d")),
-            Fcons (Fcons (build_string ("TAB"), build_string ("\\t")),
-                   Fcons (Fcons (build_string ("RET"), build_string ("\\r")),
-                          Fcons (Fcons (build_string ("ESC"), build_string ("\\e")),
-                                 Fcons (Fcons (build_string ("SPC"), build_string (" ")),
+    = pure_cons (pure_cons (make_pure_c_string ("DEL"), make_pure_c_string ("\\d")),
+                pure_cons (pure_cons (make_pure_c_string ("TAB"), make_pure_c_string ("\\t")),
+                   pure_cons (pure_cons (make_pure_c_string ("RET"), make_pure_c_string ("\\r")),
+                          pure_cons (pure_cons (make_pure_c_string ("ESC"), make_pure_c_string ("\\e")),
+                                 pure_cons (pure_cons (make_pure_c_string ("SPC"), make_pure_c_string (" ")),
                                         Qnil)))));
   staticpro (&exclude_keys);
 
@@ -4062,11 +3998,11 @@ don't alter it yourself.  */);
   Fset_keymap_parent (Vminibuffer_local_must_match_map,
                      Vminibuffer_local_completion_map);
 
-  DEFVAR_LISP ("minibuffer-local-must-match-filename-map",
-              &Vminibuffer_local_must_match_filename_map,
+  DEFVAR_LISP ("minibuffer-local-filename-must-match-map",
+              &Vminibuffer_local_filename_must_match_map,
               doc: /* Local keymap for minibuffer input with completion for filenames with exact match.  */);
-  Vminibuffer_local_must_match_filename_map = Fmake_sparse_keymap (Qnil);
-  Fset_keymap_parent (Vminibuffer_local_must_match_filename_map,
+  Vminibuffer_local_filename_must_match_map = Fmake_sparse_keymap (Qnil);
+  Fset_keymap_parent (Vminibuffer_local_filename_must_match_map,
                      Vminibuffer_local_must_match_map);
 
   DEFVAR_LISP ("minor-mode-map-alist", &Vminor_mode_map_alist,
@@ -4093,37 +4029,49 @@ the same way.  The "active" keymaps in each alist are used before
 `minor-mode-map-alist' and `minor-mode-overriding-map-alist'.  */);
   Vemulation_mode_map_alists = Qnil;
 
+  DEFVAR_LISP ("where-is-preferred-modifier", &Vwhere_is_preferred_modifier,
+              doc: /* Preferred modifier to use for `where-is'.
+When a single binding is requested, `where-is' will return one that
+uses this modifier if possible.  If nil, or if no such binding exists,
+bindings using keys without modifiers (or only with meta) will be
+preferred.  */);
+  Vwhere_is_preferred_modifier = Qnil;
+  where_is_preferred_modifier = 0;
+
   staticpro (&Vmouse_events);
-  Vmouse_events = Fcons (intern ("menu-bar"),
-                 Fcons (intern ("tool-bar"),
-                 Fcons (intern ("header-line"),
-                 Fcons (intern ("mode-line"),
-                 Fcons (intern ("mouse-1"),
-                 Fcons (intern ("mouse-2"),
-                 Fcons (intern ("mouse-3"),
-                 Fcons (intern ("mouse-4"),
-                 Fcons (intern ("mouse-5"),
-                        Qnil)))))))));
-
-
-  Qsingle_key_description = intern ("single-key-description");
+  Vmouse_events = pure_cons (intern_c_string ("menu-bar"),
+                 pure_cons (intern_c_string ("tool-bar"),
+                 pure_cons (intern_c_string ("header-line"),
+                 pure_cons (intern_c_string ("mode-line"),
+                 pure_cons (intern_c_string ("mouse-1"),
+                 pure_cons (intern_c_string ("mouse-2"),
+                 pure_cons (intern_c_string ("mouse-3"),
+                 pure_cons (intern_c_string ("mouse-4"),
+                 pure_cons (intern_c_string ("mouse-5"),
+                            Qnil)))))))));
+
+
+  Qsingle_key_description = intern_c_string ("single-key-description");
   staticpro (&Qsingle_key_description);
 
-  Qkey_description = intern ("key-description");
+  Qkey_description = intern_c_string ("key-description");
   staticpro (&Qkey_description);
 
-  Qkeymapp = intern ("keymapp");
+  Qkeymapp = intern_c_string ("keymapp");
   staticpro (&Qkeymapp);
 
-  Qnon_ascii = intern ("non-ascii");
+  Qnon_ascii = intern_c_string ("non-ascii");
   staticpro (&Qnon_ascii);
 
-  Qmenu_item = intern ("menu-item");
+  Qmenu_item = intern_c_string ("menu-item");
   staticpro (&Qmenu_item);
 
-  Qremap = intern ("remap");
+  Qremap = intern_c_string ("remap");
   staticpro (&Qremap);
 
+  QCadvertised_binding = intern_c_string (":advertised-binding");
+  staticpro (&QCadvertised_binding);
+
   command_remapping_vector = Fmake_vector (make_number (2), Qremap);
   staticpro (&command_remapping_vector);
 
@@ -4138,6 +4086,7 @@ the same way.  The "active" keymaps in each alist are used before
   defsubr (&Sset_keymap_parent);
   defsubr (&Smake_keymap);
   defsubr (&Smake_sparse_keymap);
+  defsubr (&Smap_keymap_internal);
   defsubr (&Smap_keymap);
   defsubr (&Scopy_keymap);
   defsubr (&Scommand_remapping);
@@ -4168,7 +4117,7 @@ void
 keys_of_keymap ()
 {
   initial_define_key (global_map, 033, "ESC-prefix");
-  initial_define_key (global_map, Ctl('X'), "Control-X-prefix");
+  initial_define_key (global_map, Ctl ('X'), "Control-X-prefix");
 }
 
 /* arch-tag: 6dd15c26-7cf1-41c4-b904-f42f7ddda463