* lisp/progmodes/js.el: Add notes in comments.
[bpt/emacs.git] / src / keymap.c
index 110447b..9f82175 100644 (file)
@@ -1,5 +1,5 @@
 /* Manipulation of keymaps
-   Copyright (C) 1985-1988, 1993-1995, 1998-2011 Free Software Foundation, Inc.
+   Copyright (C) 1985-1988, 1993-1995, 1998-2012 Free Software Foundation, Inc.
 
 This file is part of GNU Emacs.
 
@@ -16,6 +16,27 @@ GNU General Public License for more details.
 You should have received a copy of the GNU General Public License
 along with GNU Emacs.  If not, see <http://www.gnu.org/licenses/>.  */
 
+/* Old BUGS:
+   - [M-C-a] != [?\M-\C-a]
+   - [M-f2] != [?\e f2].
+   - (define-key map [menu-bar foo] <bla>) does not always place <bla>
+     at the head of the menu (if `foo' was already bound earlier and
+     then unbound, for example).
+   TODO:
+   - allow many more Meta -> ESC mappings (like Hyper -> C-e for Emacspeak)
+   - Think about the various defaulting that's currently hard-coded in
+     keyboard.c (uppercase->lowercase, char->charset, button-events, ...)
+     and make it more generic.  Maybe we should allow mappings of the
+     form (PREDICATE . BINDING) as generalization of the default binding,
+     tho probably a cleaner way to attack this is to allow functional
+     keymaps (i.e. keymaps that are implemented as functions that implement
+     a few different methods like `lookup', `map', ...).
+   - Make [a] equivalent to [?a].
+   BEWARE:
+   - map-keymap should work meaningfully even if entries are added/removed
+     to the keymap while iterating through it:
+       start - removed <= visited <= start + added
+ */
 
 #include <config.h>
 #include <stdio.h>
@@ -73,7 +94,6 @@ static Lisp_Object where_is_cache_keymaps;
 
 static Lisp_Object Flookup_key (Lisp_Object, Lisp_Object, Lisp_Object);
 static Lisp_Object store_in_keymap (Lisp_Object, Lisp_Object, Lisp_Object);
-static void fix_submap_inheritance (Lisp_Object, Lisp_Object, Lisp_Object);
 
 static Lisp_Object define_as_prefix (Lisp_Object, Lisp_Object);
 static void describe_command (Lisp_Object, Lisp_Object);
@@ -174,6 +194,12 @@ when reading a key-sequence to be looked-up in this keymap.  */)
       Lisp_Object tem = XCAR (map);
       if (STRINGP (tem))
        return tem;
+      else if (KEYMAPP (tem))
+       {
+         tem = Fkeymap_prompt (tem);
+         if (!NILP (tem))
+           return tem;
+       }
       map = XCDR (map);
     }
   return Qnil;
@@ -300,23 +326,16 @@ Return PARENT.  PARENT should be nil or another keymap.  */)
 {
   Lisp_Object list, prev;
   struct gcpro gcpro1, gcpro2;
-  int i;
 
-  /* Force a keymap flush for the next call to where-is.
-     Since this can be called from within where-is, we don't set where_is_cache
-     directly but only where_is_cache_keymaps, since where_is_cache shouldn't
-     be changed during where-is, while where_is_cache_keymaps is only used at
-     the very beginning of where-is and can thus be changed here without any
-     adverse effect.
-     This is a very minor correctness (rather than safety) issue.  */
-  where_is_cache_keymaps = Qt;
+  /* Flush any reverse-map cache.  */
+  where_is_cache = Qnil; where_is_cache_keymaps = Qt;
 
   GCPRO2 (keymap, parent);
   keymap = get_keymap (keymap, 1, 1);
 
   if (!NILP (parent))
     {
-      parent = get_keymap (parent, 1, 1);
+      parent = get_keymap (parent, 1, 0);
 
       /* Check for cycles.  */
       if (keymap_memberp (keymap, parent))
@@ -332,121 +351,35 @@ Return PARENT.  PARENT should be nil or another keymap.  */)
         If we came to the end, add the parent in PREV.  */
       if (!CONSP (list) || KEYMAPP (list))
        {
-         /* If we already have the right parent, return now
-            so that we avoid the loops below.  */
-         if (EQ (XCDR (prev), parent))
-           RETURN_UNGCPRO (parent);
-
          CHECK_IMPURE (prev);
          XSETCDR (prev, parent);
-         break;
+         RETURN_UNGCPRO (parent);
        }
       prev = list;
     }
-
-  /* Scan through for submaps, and set their parents too.  */
-
-  for (list = XCDR (keymap); CONSP (list); list = XCDR (list))
-    {
-      /* Stop the scan when we come to the parent.  */
-      if (EQ (XCAR (list), Qkeymap))
-       break;
-
-      /* If this element holds a prefix map, deal with it.  */
-      if (CONSP (XCAR (list))
-         && CONSP (XCDR (XCAR (list))))
-       fix_submap_inheritance (keymap, XCAR (XCAR (list)),
-                               XCDR (XCAR (list)));
-
-      if (VECTORP (XCAR (list)))
-       for (i = 0; i < XVECTOR_SIZE (XCAR (list)); i++)
-         if (CONSP (XVECTOR (XCAR (list))->contents[i]))
-           fix_submap_inheritance (keymap, make_number (i),
-                                   XVECTOR (XCAR (list))->contents[i]);
-
-      if (CHAR_TABLE_P (XCAR (list)))
-       {
-         map_char_table (fix_submap_inheritance, Qnil, XCAR (list), keymap);
-       }
-    }
-
-  RETURN_UNGCPRO (parent);
-}
-
-/* EVENT is defined in MAP as a prefix, and SUBMAP is its definition.
-   if EVENT is also a prefix in MAP's parent,
-   make sure that SUBMAP inherits that definition as its own parent.  */
-
-static void
-fix_submap_inheritance (Lisp_Object map, Lisp_Object event, Lisp_Object submap)
-{
-  Lisp_Object map_parent, parent_entry;
-
-  /* SUBMAP is a cons that we found as a key binding.
-     Discard the other things found in a menu key binding.  */
-
-  submap = get_keymap (get_keyelt (submap, 0), 0, 0);
-
-  /* If it isn't a keymap now, there's no work to do.  */
-  if (!CONSP (submap))
-    return;
-
-  map_parent = keymap_parent (map, 0);
-  if (!NILP (map_parent))
-    parent_entry =
-      get_keymap (access_keymap (map_parent, event, 0, 0, 0), 0, 0);
-  else
-    parent_entry = Qnil;
-
-  /* If MAP's parent has something other than a keymap,
-     our own submap shadows it completely.  */
-  if (!CONSP (parent_entry))
-    return;
-
-  if (! EQ (parent_entry, submap))
-    {
-      Lisp_Object submap_parent;
-      submap_parent = submap;
-      while (1)
-       {
-         Lisp_Object tem;
-
-         tem = keymap_parent (submap_parent, 0);
-
-         if (KEYMAPP (tem))
-           {
-             if (keymap_memberp (tem, parent_entry))
-               /* Fset_keymap_parent could create a cycle.  */
-               return;
-             submap_parent = tem;
-           }
-         else
-           break;
-       }
-      Fset_keymap_parent (submap_parent, parent_entry);
-    }
 }
 \f
+
 /* Look up IDX in MAP.  IDX may be any sort of event.
    Note that this does only one level of lookup; IDX must be a single
    event, not a sequence.
 
+   MAP must be a keymap or a list of keymaps.
+
    If T_OK is non-zero, bindings for Qt are treated as default
    bindings; any key left unmentioned by other tables and bindings is
    given the binding of Qt.
 
    If T_OK is zero, bindings for Qt are not treated specially.
 
-   If NOINHERIT, don't accept a subkeymap found in an inherited keymap.  */
+   If NOINHERIT, don't accept a subkeymap found in an inherited keymap.
 
-Lisp_Object
-access_keymap (Lisp_Object map, Lisp_Object idx, int t_ok, int noinherit, int autoload)
-{
-  Lisp_Object val;
-
-  /* Qunbound in VAL means we have found no binding yet.  */
-  val = Qunbound;
+   Returns Qunbound if no binding was found (and returns Qnil if a nil
+   binding was found).  */
 
+static Lisp_Object
+access_keymap_1 (Lisp_Object map, Lisp_Object idx, int t_ok, int noinherit, int autoload)
+{
   /* 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.  */
@@ -461,33 +394,33 @@ access_keymap (Lisp_Object map, Lisp_Object idx, int t_ok, int noinherit, int au
        with more than 24 bits of integer.  */
     XSETFASTINT (idx, XINT (idx) & (CHAR_META | (CHAR_META - 1)));
 
-  /* Handle the special meta -> esc mapping. */
-  if (INTEGERP (idx) && XUINT (idx) & meta_modifier)
+  /* Handle the special meta -> esc mapping.  */
+  if (INTEGERP (idx) && XFASTINT (idx) & meta_modifier)
     {
       /* See if there is a meta-map.  If there's none, there is
          no binding for IDX, unless a default binding exists in MAP.  */
       struct gcpro gcpro1;
-      Lisp_Object event_meta_map;
+      Lisp_Object event_meta_binding, event_meta_map;
       GCPRO1 (map);
       /* A strange value in which Meta is set would cause
         infinite recursion.  Protect against that.  */
       if (XINT (meta_prefix_char) & CHAR_META)
        meta_prefix_char = make_number (27);
-      event_meta_map = get_keymap (access_keymap (map, meta_prefix_char,
-                                                 t_ok, noinherit, autoload),
-                                  0, autoload);
+      event_meta_binding = access_keymap_1 (map, meta_prefix_char, t_ok,
+                                           noinherit, autoload);
+      event_meta_map = get_keymap (event_meta_binding, 0, autoload);
       UNGCPRO;
       if (CONSP (event_meta_map))
        {
          map = event_meta_map;
-         idx = make_number (XUINT (idx) & ~meta_modifier);
+         idx = make_number (XFASTINT (idx) & ~meta_modifier);
        }
       else if (t_ok)
        /* Set IDX to t, so that we only find a default binding.  */
        idx = Qt;
       else
-       /* We know there is no binding.  */
-       return Qnil;
+       /* An explicit nil binding, or no binding at all.  */
+       return NILP (event_meta_binding) ? Qnil : Qunbound;
     }
 
   /* t_binding is where we put a default binding that applies,
@@ -495,25 +428,52 @@ access_keymap (Lisp_Object map, Lisp_Object idx, int t_ok, int noinherit, int au
      for this key sequence.  */
   {
     Lisp_Object tail;
-    Lisp_Object t_binding = Qnil;
+    Lisp_Object t_binding = Qunbound;
+    Lisp_Object retval = Qunbound;
+    Lisp_Object retval_tail = Qnil;
     struct gcpro gcpro1, gcpro2, gcpro3, gcpro4;
 
-    GCPRO4 (map, tail, idx, t_binding);
+    GCPRO4 (tail, idx, t_binding, retval);
 
-    for (tail = XCDR (map);
+    for (tail = (CONSP (map) && EQ (Qkeymap, XCAR (map))) ? XCDR (map) : map;
         (CONSP (tail)
          || (tail = get_keymap (tail, 0, autoload), CONSP (tail)));
         tail = XCDR (tail))
       {
-       Lisp_Object binding;
+       /* Qunbound in VAL means we have found no binding.  */
+       Lisp_Object val = Qunbound;
+       Lisp_Object binding = XCAR (tail);
+       Lisp_Object submap = get_keymap (binding, 0, autoload);
 
-       binding = XCAR (tail);
-       if (SYMBOLP (binding))
+       if (EQ (binding, Qkeymap))
+         {
+           if (noinherit || NILP (retval))
+             /* If NOINHERIT, stop here, the rest is inherited.  */
+             break;
+           else if (!EQ (retval, Qunbound))
+             {
+               Lisp_Object parent_entry;
+               eassert (KEYMAPP (retval));
+               parent_entry
+                 = get_keymap (access_keymap_1 (tail, idx,
+                                                t_ok, 0, autoload),
+                               0, autoload);
+               if (KEYMAPP (parent_entry))
+                 {
+                   if (CONSP (retval_tail))
+                     XSETCDR (retval_tail, parent_entry);
+                   else
+                     {
+                       retval_tail = Fcons (retval, parent_entry);
+                       retval = Fcons (Qkeymap, retval_tail);
+                     }
+                 }
+               break;
+             }
+         }
+       else if (CONSP (submap))
          {
-           /* If NOINHERIT, stop finding prefix definitions
-              after we pass a second occurrence of the `keymap' symbol.  */
-           if (noinherit && EQ (binding, Qkeymap))
-             RETURN_UNGCPRO (Qnil);
+           val = access_keymap_1 (submap, idx, t_ok, noinherit, autoload);
          }
        else if (CONSP (binding))
          {
@@ -529,7 +489,7 @@ access_keymap (Lisp_Object map, Lisp_Object idx, int t_ok, int noinherit, int au
          }
        else if (VECTORP (binding))
          {
-           if (NATNUMP (idx) && XFASTINT (idx) < ASIZE (binding))
+           if (INTEGERP (idx) && XFASTINT (idx) < ASIZE (binding))
              val = AREF (binding, XFASTINT (idx));
          }
        else if (CHAR_TABLE_P (binding))
@@ -537,7 +497,7 @@ access_keymap (Lisp_Object map, Lisp_Object idx, int t_ok, int noinherit, int au
            /* Character codes with modifiers
               are not included in a char-table.
               All character codes without modifiers are included.  */
-           if (NATNUMP (idx) && (XFASTINT (idx) & CHAR_MODIFIER_MASK) == 0)
+           if (INTEGERP (idx) && (XFASTINT (idx) & CHAR_MODIFIER_MASK) == 0)
              {
                val = Faref (binding, idx);
                /* `nil' has a special meaning for char-tables, so
@@ -556,23 +516,47 @@ access_keymap (Lisp_Object map, Lisp_Object idx, int t_ok, int noinherit, int au
                 (i.e. it shadows any parent binding but not bindings in
                 keymaps of lower precedence).  */
              val = Qnil;
+
            val = get_keyelt (val, autoload);
-           if (KEYMAPP (val))
-             fix_submap_inheritance (map, idx, val);
-           RETURN_UNGCPRO (val);
+
+           if (!KEYMAPP (val))
+             {
+               if (NILP (retval) || EQ (retval, Qunbound))
+                 retval = val;
+               if (!NILP (val))
+                 break;  /* Shadows everything that follows.  */
+             }
+           else if (NILP (retval) || EQ (retval, Qunbound))
+             retval = val;
+           else if (CONSP (retval_tail))
+             {
+               XSETCDR (retval_tail, Fcons (val, Qnil));
+               retval_tail = XCDR (retval_tail);
+             }
+           else
+             {
+               retval_tail = Fcons (val, Qnil);
+               retval = Fcons (Qkeymap, Fcons (retval, retval_tail));
+             }
          }
        QUIT;
       }
     UNGCPRO;
-    return get_keyelt (t_binding, autoload);
+    return EQ (Qunbound, retval) ? get_keyelt (t_binding, autoload) : retval;
   }
 }
 
+Lisp_Object
+access_keymap (Lisp_Object map, Lisp_Object idx,
+              int t_ok, int noinherit, int autoload)
+{
+  Lisp_Object val = access_keymap_1 (map, idx, t_ok, noinherit, autoload);
+  return EQ (val, Qunbound) ? Qnil : val;
+}
+
 static void
 map_keymap_item (map_keymap_function_t fun, Lisp_Object args, Lisp_Object key, Lisp_Object val, void *data)
 {
-  /* We should maybe try to detect bindings shadowed by previous
-     ones and things like that.  */
   if (EQ (val, Qt))
     val = Qnil;
   (*fun) (key, val, args, data);
@@ -583,8 +567,8 @@ map_keymap_char_table_item (Lisp_Object args, Lisp_Object key, Lisp_Object val)
 {
   if (!NILP (val))
     {
-      map_keymap_function_t fun =
-       (map_keymap_function_t) XSAVE_VALUE (XCAR (args))->pointer;
+      map_keymap_function_t fun
+       (map_keymap_function_t) 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.  */
@@ -612,7 +596,9 @@ map_keymap_internal (Lisp_Object map,
     {
       Lisp_Object binding = XCAR (tail);
 
-      if (CONSP (binding))
+      if (KEYMAPP (binding))   /* An embedded parent.  */
+       break;
+      else if (CONSP (binding))
        map_keymap_item (fun, args, XCAR (binding), XCDR (binding), data);
       else if (VECTORP (binding))
        {
@@ -644,7 +630,7 @@ map_keymap_call (Lisp_Object key, Lisp_Object val, Lisp_Object fun, void *dummy)
   call2 (fun, key, val);
 }
 
-/* Same as map_keymap_internal, but doesn't traverses parent keymaps as well.
+/* Same as map_keymap_internal, but traverses parent keymaps as well.
    A non-zero AUTOLOAD indicates that autoloaded keymaps should be loaded.  */
 void
 map_keymap (Lisp_Object map, map_keymap_function_t fun, Lisp_Object args, void *data, int autoload)
@@ -654,8 +640,15 @@ map_keymap (Lisp_Object map, map_keymap_function_t fun, Lisp_Object args, void *
   map = get_keymap (map, 1, autoload);
   while (CONSP (map))
     {
-      map = map_keymap_internal (map, fun, args, data);
-      map = get_keymap (map, 0, autoload);
+      if (KEYMAPP (XCAR (map)))
+       {
+         map_keymap (XCAR (map), fun, args, data, autoload);
+         map = XCDR (map);
+       }
+      else
+       map = map_keymap_internal (map, fun, args, data);
+      if (!CONSP (map))
+       map = get_keymap (map, 0, autoload);
     }
   UNGCPRO;
 }
@@ -791,16 +784,10 @@ get_keyelt (Lisp_Object object, int autoload)
        }
 
       /* If the contents are (KEYMAP . ELEMENT), go indirect.  */
+      else if (KEYMAPP (XCAR (object)))
+       error ("Wow, indirect keymap entry!!");
       else
-       {
-         struct gcpro gcpro1;
-         Lisp_Object map;
-         GCPRO1 (object);
-         map = get_keymap (Fcar_safe (object), 0, autoload);
-         UNGCPRO;
-         return (!CONSP (map) ? object /* Invalid keymap */
-                 : access_keymap (map, Fcdr (object), 0, 0, autoload));
-       }
+       return object;
     }
 }
 
@@ -811,6 +798,9 @@ store_in_keymap (Lisp_Object keymap, register Lisp_Object idx, Lisp_Object def)
   where_is_cache = Qnil;
   where_is_cache_keymaps = Qt;
 
+  if (EQ (idx, Qkeymap))
+    error ("`keymap' is reserved for embedded parent maps");
+
   /* If we are preparing to dump, and DEF is a menu element
      with a menu item indicator, copy it to ensure it is not pure.  */
   if (CONSP (def) && PURE_P (def)
@@ -903,7 +893,16 @@ store_in_keymap (Lisp_Object keymap, register Lisp_Object idx, Lisp_Object def)
          }
        else if (CONSP (elt))
          {
-           if (EQ (idx, XCAR (elt)))
+           if (EQ (Qkeymap, XCAR (elt)))
+             { /* A sub keymap.  This might be due to a lookup that found
+                  two matching bindings (maybe because of a sub keymap).
+                  It almost never happens (since the second binding normally
+                  only happens in the inherited part of the keymap), but
+                  if it does, we want to update the sub-keymap since the
+                  main one might be temporary (built by access_keymap).  */
+               tail = insertion_point = elt;
+             }
+           else if (EQ (idx, XCAR (elt)))
              {
                CHECK_IMPURE (elt);
                XSETCDR (elt, def);
@@ -999,7 +998,7 @@ copy_keymap_item (Lisp_Object elt)
     }
   else
     {
-      /* It may be an old fomat menu item.
+      /* It may be an old format menu item.
         Skip the optional menu string.  */
       if (STRINGP (XCAR (tem)))
        {
@@ -1068,7 +1067,13 @@ is not copied.  */)
            ASET (elt, i, copy_keymap_item (AREF (elt, i)));
        }
       else if (CONSP (elt))
-       elt = Fcons (XCAR (elt), copy_keymap_item (XCDR (elt)));
+       {
+         if (EQ (XCAR (elt), Qkeymap))
+           /* This is a sub keymap.  */
+           elt = Fcopy_keymap (elt);
+         else
+           elt = Fcons (XCAR (elt), copy_keymap_item (XCDR (elt)));
+       }
       XSETCDR (tail, Fcons (elt, Qnil));
       tail = XCDR (tail);
       keymap = XCDR (keymap);
@@ -1200,13 +1205,20 @@ binding KEY to DEF is added at the front of KEYMAP.  */)
 
       keymap = get_keymap (cmd, 0, 1);
       if (!CONSP (keymap))
-       /* We must use Fkey_description rather than just passing key to
-          error; key might be a vector, not a string.  */
-       error ("Key sequence %s starts with non-prefix key %s",
-              SDATA (Fkey_description (key, Qnil)),
-              SDATA (Fkey_description (Fsubstring (key, make_number (0),
-                                                   make_number (idx)),
-                                       Qnil)));
+       {
+         const char *trailing_esc = ((EQ (c, meta_prefix_char) && metized)
+                                     ? (idx == 0 ? "ESC" : " ESC")
+                                     : "");
+
+         /* We must use Fkey_description rather than just passing key to
+            error; key might be a vector, not a string.  */
+         error ("Key sequence %s starts with non-prefix key %s%s",
+                SDATA (Fkey_description (key, Qnil)),
+                SDATA (Fkey_description (Fsubstring (key, make_number (0),
+                                                     make_number (idx)),
+                                         Qnil)),
+                trailing_esc);
+       }
     }
 }
 
@@ -1234,23 +1246,15 @@ remapping in all currently active keymaps.  */)
   ASET (command_remapping_vector, 1, command);
 
   if (NILP (keymaps))
-    return Fkey_binding (command_remapping_vector, Qnil, Qt, position);
+    command = Fkey_binding (command_remapping_vector, Qnil, Qt, position);
   else
-    {
-      Lisp_Object maps, binding;
-
-      for (maps = keymaps; CONSP (maps); maps = XCDR (maps))
-       {
-         binding = Flookup_key (XCAR (maps), command_remapping_vector, Qnil);
-         if (!NILP (binding) && !INTEGERP (binding))
-           return binding;
-       }
-      return Qnil;
-    }
+    command = Flookup_key (Fcons (Qkeymap, keymaps),
+                          command_remapping_vector, Qnil);
+  return INTEGERP (command) ? Qnil : command;
 }
 
 /* Value is number if KEY is too long; nil if valid but has no definition. */
-/* GC is possible in this function if it autoloads a keymap.  */
+/* GC is possible in this function.  */
 
 DEFUN ("lookup-key", Flookup_key, Slookup_key, 2, 3, 0,
        doc: /* In keymap KEYMAP, look up key sequence KEY.  Return the definition.
@@ -1325,10 +1329,6 @@ define_as_prefix (Lisp_Object keymap, Lisp_Object c)
   Lisp_Object cmd;
 
   cmd = Fmake_sparse_keymap (Qnil);
-  /* If this key is defined as a prefix in an inherited keymap,
-     make it a prefix in this map, and make its definition
-     inherit the other prefix definition.  */
-  cmd = nconc2 (cmd, access_keymap (keymap, c, 0, 0, 0));
   store_in_keymap (keymap, c, cmd);
 
   return cmd;
@@ -1357,7 +1357,7 @@ silly_event_symbol_error (Lisp_Object c)
   int modifiers;
 
   parsed = parse_modifiers (c);
-  modifiers = (int) XUINT (XCAR (XCDR (parsed)));
+  modifiers = XFASTINT (XCAR (XCDR (parsed)));
   base = XCAR (parsed);
   name = Fsymbol_name (base);
   /* This alist includes elements such as ("RET" . "\\r").  */
@@ -1399,7 +1399,7 @@ silly_event_symbol_error (Lisp_Object c)
    some systems, static gets macro-defined to be the empty string.
    Ickypoo.  */
 static Lisp_Object *cmm_modes = NULL, *cmm_maps = NULL;
-static int cmm_size = 0;
+static ptrdiff_t cmm_size = 0;
 
 /* Store a pointer to an array of the currently active minor modes in
    *modeptr, a pointer to an array of the keymaps of the currently
@@ -1419,10 +1419,10 @@ static int cmm_size = 0;
    loop.  Instead, we'll use realloc/malloc and silently truncate the
    list, let the key sequence be read, and hope some other piece of
    code signals the error.  */
-int
+ptrdiff_t
 current_minor_maps (Lisp_Object **modeptr, Lisp_Object **mapptr)
 {
-  int i = 0;
+  ptrdiff_t i = 0;
   int list_number = 0;
   Lisp_Object alist, assoc, var, val;
   Lisp_Object emulation_alists;
@@ -1465,9 +1465,16 @@ current_minor_maps (Lisp_Object **modeptr, Lisp_Object **mapptr)
 
            if (i >= cmm_size)
              {
-               int newsize, allocsize;
+               ptrdiff_t newsize, allocsize;
                Lisp_Object *newmodes, *newmaps;
 
+               /* Check for size calculation overflow.  Other code
+                  (e.g., read_key_sequence) adds 3 to the count
+                  later, so subtract 3 from the limit here.  */
+               if (min (PTRDIFF_MAX, SIZE_MAX) / (2 * sizeof *newmodes) - 3
+                   < cmm_size)
+                 break;
+
                newsize = cmm_size == 0 ? 30 : cmm_size * 2;
                allocsize = newsize * sizeof *newmodes;
 
@@ -1530,7 +1537,7 @@ like in the respective argument of `key-binding'. */)
 {
   int count = SPECPDL_INDEX ();
 
-  Lisp_Object keymaps;
+  Lisp_Object keymaps = Fcons (current_global_map, Qnil);
 
   /* 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
@@ -1560,12 +1567,11 @@ like in the respective argument of `key-binding'. */)
        }
     }
 
-  keymaps = Fcons (current_global_map, Qnil);
-
   if (!NILP (olp))
     {
       if (!NILP (KVAR (current_kboard, Voverriding_terminal_local_map)))
-       keymaps = Fcons (KVAR (current_kboard, Voverriding_terminal_local_map), keymaps);
+       keymaps = Fcons (KVAR (current_kboard, Voverriding_terminal_local_map),
+                        keymaps);
       /* The doc said that overriding-terminal-local-map should
         override overriding-local-map.  The code used them both,
         but it seems clearer to use just one.  rms, jan 2005.  */
@@ -1576,23 +1582,19 @@ like in the respective argument of `key-binding'. */)
     {
       Lisp_Object *maps;
       int nmaps, i;
-
-      Lisp_Object keymap, local_map;
-      EMACS_INT pt;
-
-      pt = INTEGERP (position) ? XINT (position)
+      EMACS_INT pt
+       = INTEGERP (position) ? XINT (position)
        : MARKERP (position) ? marker_position (position)
        : PT;
-
-      /* 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);
+      /* This usually returns the buffer's local map,
+        but that can be overridden by a `local-map' property.  */
+      Lisp_Object local_map = get_local_map (pt, current_buffer, Qlocal_map);
+      /* This returns nil unless there is a `keymap' property.  */
+      Lisp_Object keymap = get_local_map (pt, current_buffer, Qkeymap);
 
       if (CONSP (position))
        {
-         Lisp_Object string;
+         Lisp_Object string = POSN_STRING (position);
 
          /* For a mouse click, get the local text-property keymap
             of the place clicked on, rather than point.  */
@@ -1619,8 +1621,7 @@ like in the respective argument of `key-binding'. */)
             consider `local-map' and `keymap' properties of
             that string.  */
 
-         if (string = POSN_STRING (position),
-             (CONSP (string) && STRINGP (XCAR (string))))
+         if (CONSP (string) && STRINGP (XCAR (string)))
            {
              Lisp_Object pos, map;
 
@@ -1691,12 +1692,7 @@ specified buffer position instead of point are used.
   */)
   (Lisp_Object key, Lisp_Object accept_default, Lisp_Object no_remap, Lisp_Object position)
 {
-  Lisp_Object *maps, value;
-  int nmaps, i;
-  struct gcpro gcpro1, gcpro2;
-  int count = SPECPDL_INDEX ();
-
-  GCPRO2 (key, position);
+  Lisp_Object value;
 
   if (NILP (position) && VECTORP (key))
     {
@@ -1715,145 +1711,9 @@ specified buffer position instead of point are used.
        }
     }
 
-  /* Key sequences beginning with mouse clicks
-     are read using the keymaps of 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);
+  value = Flookup_key (Fcons (Qkeymap, Fcurrent_active_maps (Qt, position)),
+                      key, accept_default);
 
-      if (WINDOWP (window)
-         && BUFFERP (XWINDOW (window)->buffer)
-         && XBUFFER (XWINDOW (window)->buffer) != current_buffer)
-       {
-         /* Arrange to go back to the original buffer once we're done
-            processing the key sequence.  We don't use
-            save_excursion_{save,restore} here, in analogy to
-            `read-key-sequence' to avoid saving point.  Maybe this
-            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));
-       }
-    }
-
-  if (! NILP (KVAR (current_kboard, Voverriding_terminal_local_map)))
-    {
-      value = Flookup_key (KVAR (current_kboard, Voverriding_terminal_local_map),
-                          key, accept_default);
-      if (! NILP (value) && !INTEGERP (value))
-       goto done;
-    }
-  else if (! NILP (Voverriding_local_map))
-    {
-      value = Flookup_key (Voverriding_local_map, key, accept_default);
-      if (! NILP (value) && !INTEGERP (value))
-       goto done;
-    }
-  else
-    {
-      Lisp_Object keymap, local_map;
-      EMACS_INT pt;
-
-      pt = INTEGERP (position) ? XINT (position)
-       : MARKERP (position) ? marker_position (position)
-       : PT;
-
-      local_map = get_local_map (pt, current_buffer, Qlocal_map);
-      keymap = get_local_map (pt, current_buffer, Qkeymap);
-
-      if (CONSP (position))
-       {
-         Lisp_Object string;
-
-         /* 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;
-
-             pos = POSN_BUFFER_POSN (position);
-             if (INTEGERP (pos)
-                 && XINT (pos) >= BEG && XINT (pos) <= Z)
-               {
-                 local_map = get_local_map (XINT (pos),
-                                            current_buffer, Qlocal_map);
-
-                 keymap = get_local_map (XINT (pos),
-                                         current_buffer, Qkeymap);
-               }
-           }
-
-         /* If on a mode line string with a local keymap,
-            or for a click on a string, i.e. overlay string or a
-            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)
-                 && XINT (pos) >= 0
-                 && XINT (pos) < SCHARS (string))
-               {
-                 map = Fget_text_property (pos, Qlocal_map, string);
-                 if (!NILP (map))
-                   local_map = map;
-
-                 map = Fget_text_property (pos, Qkeymap, string);
-                 if (!NILP (map))
-                   keymap = map;
-               }
-           }
-
-       }
-
-      if (! NILP (keymap))
-       {
-         value = Flookup_key (keymap, key, accept_default);
-         if (! NILP (value) && !INTEGERP (value))
-           goto done;
-       }
-
-      nmaps = current_minor_maps (0, &maps);
-      /* Note that all these maps are GCPRO'd
-        in the places where we found them.  */
-
-      for (i = 0; i < nmaps; i++)
-       if (! NILP (maps[i]))
-         {
-           value = Flookup_key (maps[i], key, accept_default);
-           if (! NILP (value) && !INTEGERP (value))
-             goto done;
-         }
-
-      if (! NILP (local_map))
-       {
-         value = Flookup_key (local_map, key, accept_default);
-         if (! NILP (value) && !INTEGERP (value))
-           goto done;
-       }
-    }
-
-  value = Flookup_key (current_global_map, key, accept_default);
-
- done:
-  unbind_to (count, Qnil);
-
-  UNGCPRO;
   if (NILP (value) || INTEGERP (value))
     return Qnil;
 
@@ -2183,8 +2043,9 @@ static Lisp_Object Qsingle_key_description, Qkey_description;
 DEFUN ("key-description", Fkey_description, Skey_description, 1, 2, 0,
        doc: /* Return a pretty description of key-sequence KEYS.
 Optional arg PREFIX is the sequence of keys leading up to KEYS.
-Control characters turn into "C-foo" sequences, meta into "M-foo",
-spaces are put between sequence elements, etc.  */)
+For example, [?\C-x ?l] is converted into the string \"C-x l\".
+
+The `kbd' macro is an approximate inverse of this.  */)
   (Lisp_Object keys, Lisp_Object prefix)
 {
   int len = 0;
@@ -2226,7 +2087,7 @@ spaces are put between sequence elements, etc.  */)
   if (STRINGP (list))
     size = SCHARS (list);
   else if (VECTORP (list))
-    size = XVECTOR_SIZE (list);
+    size = ASIZE (list);
   else if (CONSP (list))
     size = XINT (Flength (list));
   else
@@ -2283,12 +2144,12 @@ spaces are put between sequence elements, etc.  */)
 
 
 char *
-push_key_description (register unsigned int c, register char *p, int force_multibyte)
+push_key_description (EMACS_INT ch, char *p, int force_multibyte)
 {
-  unsigned c2;
+  int c, c2;
 
   /* Clear all the meaningless bits above the meta bit.  */
-  c &= meta_modifier | ~ - meta_modifier;
+  c = ch & (meta_modifier | ~ - meta_modifier);
   c2 = c & ~(alt_modifier | ctrl_modifier | hyper_modifier
             | meta_modifier | shift_modifier | super_modifier);
 
@@ -2410,23 +2271,35 @@ around function keys and event symbols.  */)
   if (CONSP (key) && lucid_event_type_list_p (key))
     key = Fevent_convert_list (key);
 
+  if (CONSP (key) && INTEGERP (XCAR (key)) && INTEGERP (XCDR (key)))
+    /* An interval from a map-char-table.  */
+    return concat3 (Fsingle_key_description (XCAR (key), no_angles),
+                   build_string (".."),
+                   Fsingle_key_description (XCDR (key), no_angles));
+
   key = EVENT_HEAD (key);
 
-  if (INTEGERP (key))          /* Normal character */
+  if (INTEGERP (key))          /* Normal character */
     {
-      char tem[KEY_DESCRIPTION_SIZE];
+      char tem[KEY_DESCRIPTION_SIZE], *p;
 
-      *push_key_description (XUINT (key), tem, 1) = 0;
-      return build_string (tem);
+      p = push_key_description (XINT (key), tem, 1);
+      *p = 0;
+      return make_specified_string (tem, -1, p - tem, 1);
     }
-  else if (SYMBOLP (key))      /* Function key or event-symbol */
+  else if (SYMBOLP (key))      /* Function key or event-symbol */
     {
       if (NILP (no_angles))
        {
-         char *buffer
-           = (char *) alloca (SBYTES (SYMBOL_NAME (key)) + 5);
-         sprintf (buffer, "<%s>", SDATA (SYMBOL_NAME (key)));
-         return build_string (buffer);
+         char *buffer;
+         Lisp_Object result;
+         USE_SAFE_ALLOCA;
+         SAFE_ALLOCA (buffer, char *,
+                      sizeof "<>" + SBYTES (SYMBOL_NAME (key)));
+         esprintf (buffer, "<%s>", SDATA (SYMBOL_NAME (key)));
+         result = build_string (buffer);
+         SAFE_FREE ();
+         return result;
        }
       else
        return Fsymbol_name (key);
@@ -2515,7 +2388,7 @@ preferred_sequence_p (Lisp_Object seq)
        return 0;
       else
        {
-         int modifiers = XUINT (elt) & (CHAR_MODIFIER_MASK & ~CHAR_META);
+         int modifiers = XINT (elt) & (CHAR_MODIFIER_MASK & ~CHAR_META);
          if (modifiers == where_is_preferred_modifier)
            result = 2;
          else if (modifiers)
@@ -2680,7 +2553,8 @@ where_is_internal (Lisp_Object definition, Lisp_Object keymaps,
 DEFUN ("where-is-internal", Fwhere_is_internal, Swhere_is_internal, 1, 5, 0,
        doc: /* Return list of keys that invoke DEFINITION.
 If KEYMAP is a keymap, search only KEYMAP and the global keymap.
-If KEYMAP is nil, search all the currently active keymaps.
+If KEYMAP is nil, search all the currently active keymaps, except
+ for `overriding-local-map' (which is ignored).
 If KEYMAP is a list of keymaps, search only those keymaps.
 
 If optional 3rd arg FIRSTONLY is non-nil, return the first key sequence found,
@@ -2695,9 +2569,17 @@ If optional 4th arg NOINDIRECT is non-nil, don't follow indirections
 to other keymaps or slots.  This makes it possible to search for an
 indirect definition itself.
 
-If optional 5th arg NO-REMAP is non-nil, don't search for key sequences
-that invoke a command which is remapped to DEFINITION, but include the
-remapped command in the returned list.  */)
+The optional 5th arg NO-REMAP alters how command remapping is handled:
+
+- If another command OTHER-COMMAND is remapped to DEFINITION, normally
+  search for the bindings of OTHER-COMMAND and include them in the
+  returned list.  But if NO-REMAP is non-nil, include the vector
+  [remap OTHER-COMMAND] in the returned list instead, without
+  searching for those other bindings.
+
+- If DEFINITION is remapped to OTHER-COMMAND, normally return the
+  bindings for OTHER-COMMAND.  But if NO-REMAP is non-nil, return the
+  bindings for DEFINITION instead, ignoring its remapping.  */)
   (Lisp_Object definition, Lisp_Object keymap, Lisp_Object firstonly, Lisp_Object noindirect, Lisp_Object no_remap)
 {
   /* The keymaps in which to search.  */
@@ -2758,11 +2640,11 @@ remapped command in the returned list.  */)
       /* We have a list of advertised bindings.  */
       while (CONSP (tem))
        if (EQ (shadow_lookup (keymaps, XCAR (tem), Qnil, 0), definition))
-         return XCAR (tem);
+         RETURN_UNGCPRO (XCAR (tem));
        else
          tem = XCDR (tem);
       if (EQ (shadow_lookup (keymaps, tem, Qnil, 0), definition))
-       return tem;
+       RETURN_UNGCPRO (tem);
     }
 
   sequences = Freverse (where_is_internal (definition, keymaps,
@@ -3094,9 +2976,11 @@ You type        Translation\n\
    to look through.
 
    If MENTION_SHADOW is nonzero, then when something is shadowed by SHADOW,
-   don't omit it; instead, mention it but say it is shadowed.  */
+   don't omit it; instead, mention it but say it is shadowed.
 
-void
+   Return whether something was inserted or not.  */
+
+int
 describe_map_tree (Lisp_Object startmap, int partial, Lisp_Object shadow,
                   Lisp_Object prefix, const char *title, int nomenu, int transl,
                   int always_title, int mention_shadow)
@@ -3125,7 +3009,7 @@ key             binding\n\
 
          elt = XCAR (list);
          elt_prefix = Fcar (elt);
-         if (XVECTOR_SIZE (elt_prefix) >= 1)
+         if (ASIZE (elt_prefix) >= 1)
            {
              tem = Faref (elt_prefix, make_number (0));
              if (EQ (tem, Qmenu_bar))
@@ -3168,7 +3052,7 @@ key             binding\n\
          /* If the sequence by which we reach this keymap is zero-length,
             then the shadow map for this keymap is just SHADOW.  */
          if ((STRINGP (elt_prefix) && SCHARS (elt_prefix) == 0)
-             || (VECTORP (elt_prefix) && XVECTOR_SIZE (elt_prefix) == 0))
+             || (VECTORP (elt_prefix) && ASIZE (elt_prefix) == 0))
            ;
          /* If the sequence by which we reach this keymap actually has
             some elements, then the sequence's definition in SHADOW is
@@ -3206,10 +3090,8 @@ key             binding\n\
     skip: ;
     }
 
-  if (something)
-    insert_string ("\n");
-
   UNGCPRO;
+  return something;
 }
 
 static int previous_description_column;
@@ -3592,7 +3474,7 @@ describe_vector (Lisp_Object vector, Lisp_Object prefix, Lisp_Object args,
   if (CHAR_TABLE_P (vector))
     stop = MAX_5_BYTE_CHAR + 1, to = MAX_CHAR + 1;
   else
-    stop = to = XVECTOR_SIZE (vector);
+    stop = to = ASIZE (vector);
 
   for (i = from; ; i++)
     {
@@ -3774,15 +3656,13 @@ Return list of symbols found.  */)
 void
 syms_of_keymap (void)
 {
-  Qkeymap = intern_c_string ("keymap");
-  staticpro (&Qkeymap);
+  DEFSYM (Qkeymap, "keymap");
   staticpro (&apropos_predicate);
   staticpro (&apropos_accumulate);
   apropos_predicate = Qnil;
   apropos_accumulate = Qnil;
 
-  Qkeymap_canonicalize = intern_c_string ("keymap-canonicalize");
-  staticpro (&Qkeymap_canonicalize);
+  DEFSYM (Qkeymap_canonicalize, "keymap-canonicalize");
 
   /* Now we are ready to set up this property, so we can
      create char tables.  */
@@ -3831,31 +3711,6 @@ don't alter it yourself.  */);
   Vminibuffer_local_ns_map = Fmake_sparse_keymap (Qnil);
   Fset_keymap_parent (Vminibuffer_local_ns_map, Vminibuffer_local_map);
 
-  DEFVAR_LISP ("minibuffer-local-completion-map", Vminibuffer_local_completion_map,
-              doc: /* Local keymap for minibuffer input with completion.  */);
-  Vminibuffer_local_completion_map = Fmake_sparse_keymap (Qnil);
-  Fset_keymap_parent (Vminibuffer_local_completion_map, Vminibuffer_local_map);
-
-  DEFVAR_LISP ("minibuffer-local-filename-completion-map",
-              Vminibuffer_local_filename_completion_map,
-              doc: /* Local keymap for minibuffer input with completion for filenames.  */);
-  Vminibuffer_local_filename_completion_map = Fmake_sparse_keymap (Qnil);
-  Fset_keymap_parent (Vminibuffer_local_filename_completion_map,
-                     Vminibuffer_local_completion_map);
-
-
-  DEFVAR_LISP ("minibuffer-local-must-match-map", Vminibuffer_local_must_match_map,
-              doc: /* Local keymap for minibuffer input with completion, for exact match.  */);
-  Vminibuffer_local_must_match_map = Fmake_sparse_keymap (Qnil);
-  Fset_keymap_parent (Vminibuffer_local_must_match_map,
-                     Vminibuffer_local_completion_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_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,
               doc: /* Alist of keymaps to use for minor modes.
@@ -3882,11 +3737,11 @@ the same way.  The "active" keymaps in each alist are used before
   Vemulation_mode_map_alists = Qnil;
 
   DEFVAR_LISP ("where-is-preferred-modifier", Vwhere_is_preferred_modifier,
-              doc: /* Preferred modifier to use for `where-is'.
+              doc: /* Preferred modifier key 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.  */);
+uses this modifier key 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;
 
@@ -3902,27 +3757,13 @@ preferred.  */);
                  pure_cons (intern_c_string ("mouse-5"),
                             Qnil)))))))));
 
-
-  Qsingle_key_description = intern_c_string ("single-key-description");
-  staticpro (&Qsingle_key_description);
-
-  Qkey_description = intern_c_string ("key-description");
-  staticpro (&Qkey_description);
-
-  Qkeymapp = intern_c_string ("keymapp");
-  staticpro (&Qkeymapp);
-
-  Qnon_ascii = intern_c_string ("non-ascii");
-  staticpro (&Qnon_ascii);
-
-  Qmenu_item = intern_c_string ("menu-item");
-  staticpro (&Qmenu_item);
-
-  Qremap = intern_c_string ("remap");
-  staticpro (&Qremap);
-
-  QCadvertised_binding = intern_c_string (":advertised-binding");
-  staticpro (&QCadvertised_binding);
+  DEFSYM (Qsingle_key_description, "single-key-description");
+  DEFSYM (Qkey_description, "key-description");
+  DEFSYM (Qkeymapp, "keymapp");
+  DEFSYM (Qnon_ascii, "non-ascii");
+  DEFSYM (Qmenu_item, "menu-item");
+  DEFSYM (Qremap, "remap");
+  DEFSYM (QCadvertised_binding, ":advertised-binding");
 
   command_remapping_vector = Fmake_vector (make_number (2), Qremap);
   staticpro (&command_remapping_vector);