]> code.delx.au - gnu-emacs/blobdiff - src/keymap.c
*** empty log message ***
[gnu-emacs] / src / keymap.c
index 89271cf39714e8a2401128a30cf4e1f3e208796a..0c1a1146d15f5f97d8f396a04d78cde0c237f1ef 100644 (file)
@@ -1,5 +1,6 @@
 /* Manipulation of keymaps
-   Copyright (C) 1985, 86,87,88,93,94,95,98,99 Free Software Foundation, Inc.
+   Copyright (C) 1985, 86,87,88,93,94,95,98,99, 2000
+   Free Software Foundation, Inc.
 
 This file is part of GNU Emacs.
 
@@ -21,7 +22,6 @@ Boston, MA 02111-1307, USA.  */
 
 #include <config.h>
 #include <stdio.h>
-#undef NULL
 #include "lisp.h"
 #include "commands.h"
 #include "buffer.h"
@@ -99,10 +99,21 @@ extern Lisp_Object meta_prefix_char;
 
 extern Lisp_Object Voverriding_local_map;
 
-static Lisp_Object define_as_prefix ();
-static Lisp_Object describe_buffer_bindings ();
-static void describe_command (), describe_translation ();
-static void describe_map ();
+/* Hash table used to cache a reverse-map to speed up calls to where-is.  */
+static Lisp_Object where_is_cache;
+/* Which keymaps are reverse-stored in the cache.  */
+static Lisp_Object where_is_cache_keymaps;
+
+static Lisp_Object store_in_keymap P_ ((Lisp_Object, Lisp_Object, Lisp_Object));
+static void fix_submap_inheritance P_ ((Lisp_Object, Lisp_Object, Lisp_Object));
+
+static Lisp_Object define_as_prefix P_ ((Lisp_Object, Lisp_Object));
+static Lisp_Object describe_buffer_bindings P_ ((Lisp_Object));
+static void describe_command P_ ((Lisp_Object));
+static void describe_translation P_ ((Lisp_Object));
+static void describe_map P_ ((Lisp_Object, Lisp_Object,
+                             void (*) P_ ((Lisp_Object)),
+                             int, Lisp_Object, Lisp_Object*, int));
 \f
 /* Keymap object support - constructors and predicates.                        */
 
@@ -127,7 +138,7 @@ in case you use it as a menu with `x-popup-menu'.")
 }
 
 DEFUN ("make-sparse-keymap", Fmake_sparse_keymap, Smake_sparse_keymap, 0, 1, 0,
-  "Construct and return a new sparse-keymap list.\n\
+  "Construct and return a new sparse keymap.\n\
 Its car is `keymap' and its cdr is an alist of (CHAR . DEFINITION),\n\
 which binds the character CHAR to DEFINITION, or (SYMBOL . DEFINITION),\n\
 which binds the function key or mouse event SYMBOL to DEFINITION.\n\
@@ -167,23 +178,6 @@ initial_define_lispy_key (keymap, keyname, defname)
   store_in_keymap (keymap, intern (keyname), intern (defname));
 }
 
-/* Define character fromchar in map frommap as an alias for character
-   tochar in map tomap.  Subsequent redefinitions of the latter WILL
-   affect the former. */
-
-#if 0
-void
-synkey (frommap, fromchar, tomap, tochar)
-     struct Lisp_Vector *frommap, *tomap;
-     int fromchar, tochar;
-{
-  Lisp_Object v, c;
-  XSETVECTOR (v, tomap);
-  XSETFASTINT (c, tochar);
-  frommap->contents[fromchar] = Fcons (v, c);
-}
-#endif /* 0 */
-
 DEFUN ("keymapp", Fkeymapp, Skeymapp, 1, 1, 0,
   "Return t if OBJECT is a keymap.\n\
 \n\
@@ -195,7 +189,7 @@ is also allowed as an element.")
   (object)
      Lisp_Object object;
 {
-  return (NILP (get_keymap_1 (object, 0, 0)) ? Qnil : Qt);
+  return (KEYMAPP (object) ? Qt : Qnil);
 }
 
 /* Check that OBJECT is a keymap (after dereferencing through any
@@ -205,6 +199,9 @@ is also allowed as an element.")
    is an autoload form, do the autoload and try again.
    If AUTOLOAD is nonzero, callers must assume GC is possible.
 
+   If the map needs to be autoloaded, but AUTOLOAD is zero (and ERROR
+   is zero as well), return Qt.
+
    ERROR controls how we respond if OBJECT isn't a keymap.
    If ERROR is non-zero, signal an error; otherwise, just return Qnil.
 
@@ -212,10 +209,13 @@ is also allowed as an element.")
    Functions like Faccessible_keymaps which scan entire keymap trees
    shouldn't load every autoloaded keymap.  I'm not sure about this,
    but it seems to me that only read_key_sequence, Flookup_key, and
-   Fdefine_key should cause keymaps to be autoloaded.  */
+   Fdefine_key should cause keymaps to be autoloaded.
+
+   This function can GC when AUTOLOAD is non-zero, because it calls
+   do_autoload which can GC.  */
 
 Lisp_Object
-get_keymap_1 (object, error, autoload)
+get_keymap (object, error, autoload)
      Lisp_Object object;
      int error, autoload;
 {
@@ -226,50 +226,42 @@ get_keymap_1 (object, error, autoload)
     goto end;
   if (CONSP (object) && EQ (XCAR (object), Qkeymap))
     return object;
-  else
-    {
-      tem = indirect_function (object);
-      if (CONSP (tem) && EQ (XCAR (tem), Qkeymap))
-       return tem;
-    }
 
-  /* Should we do an autoload?  Autoload forms for keymaps have
-     Qkeymap as their fifth element.  */
-  if (autoload
-      && SYMBOLP (object)
-      && CONSP (tem)
-      && EQ (XCAR (tem), Qautoload))
+  tem = indirect_function (object);
+  if (CONSP (tem))
     {
-      Lisp_Object tail;
+      if (EQ (XCAR (tem), Qkeymap))
+       return tem;
 
-      tail = Fnth (make_number (4), tem);
-      if (EQ (tail, Qkeymap))
+      /* Should we do an autoload?  Autoload forms for keymaps have
+        Qkeymap as their fifth element.  */
+      if ((autoload || !error) && EQ (XCAR (tem), Qautoload))
        {
-         struct gcpro gcpro1, gcpro2;
-
-         GCPRO2 (tem, object);
-         do_autoload (tem, object);
-         UNGCPRO;
+         Lisp_Object tail;
 
-         goto autoload_retry;
+         tail = Fnth (make_number (4), tem);
+         if (EQ (tail, Qkeymap))
+           {
+             if (autoload)
+               {
+                 struct gcpro gcpro1, gcpro2;
+                 
+                 GCPRO2 (tem, object);
+                 do_autoload (tem, object);
+                 UNGCPRO;
+                 
+                 goto autoload_retry;
+               }
+             else
+               return Qt;
+           }
        }
     }
 
  end:
   if (error)
     wrong_type_argument (Qkeymapp, object);
-  else
-    return Qnil;
-}
-
-
-/* Follow any symbol chaining, and return the keymap denoted by OBJECT.
-   If OBJECT doesn't denote a keymap at all, signal an error.  */
-Lisp_Object
-get_keymap (object)
-     Lisp_Object object;
-{
-  return get_keymap_1 (object, 1, 0);
+  return Qnil;
 }
 \f
 /* Return the parent map of the keymap MAP, or nil if it has none.
@@ -282,18 +274,30 @@ DEFUN ("keymap-parent", Fkeymap_parent, Skeymap_parent, 1, 1, 0,
 {
   Lisp_Object list;
 
-  keymap = get_keymap_1 (keymap, 1, 1);
+  keymap = get_keymap (keymap, 1, 1);
 
   /* Skip past the initial element `keymap'.  */
   list = XCDR (keymap);
   for (; CONSP (list); list = XCDR (list))
     {
       /* See if there is another `keymap'.  */
-      if (EQ (Qkeymap, XCAR (list)))
+      if (KEYMAPP (list))
        return list;
     }
 
-  return Qnil;
+  return get_keymap (list, 0, 1);
+}
+
+
+/* Check whether MAP is one of MAPS parents.  */
+int
+keymap_memberp (map, maps)
+     Lisp_Object map, maps;
+{
+  if (NILP (map)) return 0;
+  while (KEYMAPP (maps) && !EQ (map, maps))
+    maps = Fkeymap_parent (maps);
+  return (EQ (map, maps));
 }
 
 /* Set the parent keymap of MAP to PARENT.  */
@@ -305,11 +309,29 @@ PARENT should be nil or another keymap.")
      Lisp_Object keymap, parent;
 {
   Lisp_Object list, prev;
+  struct gcpro gcpro1;
   int i;
 
-  keymap = get_keymap_1 (keymap, 1, 1);
+  /* 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;
+
+  keymap = get_keymap (keymap, 1, 1);
+  GCPRO1 (keymap);
+  
   if (!NILP (parent))
-    parent = get_keymap_1 (parent, 1, 1);
+    {
+      parent = get_keymap (parent, 1, 1);
+
+      /* Check for cycles.  */
+      if (keymap_memberp (keymap, parent))
+       error ("Cyclic keymap inheritance");
+    }
 
   /* Skip past the initial element `keymap'.  */
   prev = keymap;
@@ -318,12 +340,12 @@ PARENT should be nil or another keymap.")
       list = XCDR (prev);
       /* If there is a parent keymap here, replace it.
         If we came to the end, add the parent in PREV.  */
-      if (! CONSP (list) || EQ (Qkeymap, XCAR (list)))
+      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 parent;
+           RETURN_UNGCPRO (parent);
 
          XCDR (prev) = parent;
          break;
@@ -360,14 +382,14 @@ PARENT should be nil or another keymap.")
        }
     }
 
-  return parent;
+  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.  */
 
-void
+static void
 fix_submap_inheritance (map, event, submap)
      Lisp_Object map, event, submap;
 {
@@ -376,52 +398,23 @@ fix_submap_inheritance (map, event, submap)
   /* SUBMAP is a cons that we found as a key binding.
      Discard the other things found in a menu key binding.  */
 
-  if (CONSP (submap))
-    {
-      /* May be an old format menu item */
-      if (STRINGP (XCAR (submap)))
-       {
-         submap = XCDR (submap);
-         /* Also remove a menu help string, if any,
-            following the menu item name.  */
-         if (CONSP (submap) && STRINGP (XCAR (submap)))
-           submap = XCDR (submap);
-         /* Also remove the sublist that caches key equivalences, if any.  */
-         if (CONSP (submap)
-             && CONSP (XCAR (submap)))
-           {
-             Lisp_Object carcar;
-             carcar = XCAR (XCAR (submap));
-             if (NILP (carcar) || VECTORP (carcar))
-               submap = XCDR (submap);
-           }
-       }
-
-      /* Or a new format menu item */
-      else if (EQ (XCAR (submap), Qmenu_item)
-              && CONSP (XCDR (submap)))
-       {
-         submap = XCDR (XCDR (submap));
-         if (CONSP (submap))
-           submap = XCAR (submap);
-       }
-    }
+  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)
-      || ! EQ (XCAR (submap), Qkeymap))
+  if (!CONSP (submap))
     return;
 
   map_parent = Fkeymap_parent (map);
-  if (! NILP (map_parent))
-    parent_entry = access_keymap (map_parent, event, 0, 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, so use nil as SUBMAP's parent.  */
-  if (! (CONSP (parent_entry) && EQ (XCAR (parent_entry), Qkeymap)))
-    parent_entry = Qnil;
+     our own submap shadows it completely.  */
+  if (!CONSP (parent_entry))
+    return;
 
   if (! EQ (parent_entry, submap))
     {
@@ -430,12 +423,16 @@ fix_submap_inheritance (map, event, submap)
       while (1)
        {
          Lisp_Object tem;
+
          tem = Fkeymap_parent (submap_parent);
-         if (EQ (tem, parent_entry))
-           return;
-          if (CONSP (tem)
-             && EQ (XCAR (tem), Qkeymap))
-           submap_parent = tem;
+
+         if (KEYMAPP (tem))
+           {
+             if (keymap_memberp (tem, parent_entry))
+               /* Fset_keymap_parent could create a cycle.  */
+               return;
+             submap_parent = tem;
+           }
          else
            break;
        }
@@ -456,11 +453,12 @@ fix_submap_inheritance (map, event, submap)
    If NOINHERIT, don't accept a subkeymap found in an inherited keymap.  */
 
 Lisp_Object
-access_keymap (map, idx, t_ok, noinherit)
+access_keymap (map, idx, t_ok, noinherit, autoload)
      Lisp_Object map;
      Lisp_Object idx;
      int t_ok;
      int noinherit;
+     int autoload;
 {
   int noprefix = 0;
   Lisp_Object val;
@@ -479,12 +477,37 @@ access_keymap (map, idx, t_ok, noinherit)
        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)
+    {
+      /* See if there is a meta-map.  If there's none, there is
+         no binding for IDX, unless a default binding exists in MAP.  */
+      Lisp_Object meta_map =
+       get_keymap (access_keymap (map, meta_prefix_char,
+                                  t_ok, noinherit, autoload),
+                   0, autoload);
+      if (CONSP (meta_map))
+       {
+         map = meta_map;
+         idx = make_number (XUINT (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;
+    }
+
   {
     Lisp_Object tail;
     Lisp_Object t_binding;
 
     t_binding = Qnil;
-    for (tail = map; CONSP (tail); tail = XCDR (tail))
+    for (tail = XCDR (map);
+        (CONSP (tail)
+         || (tail = get_keymap (tail, 0, autoload), CONSP (tail)));
+        tail = XCDR (tail))
       {
        Lisp_Object binding;
 
@@ -493,7 +516,7 @@ access_keymap (map, idx, t_ok, noinherit)
          {
            /* If NOINHERIT, stop finding prefix definitions
               after we pass a second occurrence of the `keymap' symbol.  */
-           if (noinherit && EQ (binding, Qkeymap) && ! EQ (tail, map))
+           if (noinherit && EQ (binding, Qkeymap))
              noprefix = 1;
          }
        else if (CONSP (binding))
@@ -501,11 +524,11 @@ access_keymap (map, idx, t_ok, noinherit)
            if (EQ (XCAR (binding), idx))
              {
                val = XCDR (binding);
-               if (noprefix && CONSP (val) && EQ (XCAR (val), Qkeymap))
+               if (noprefix && KEYMAPP (val))
                  return Qnil;
                if (CONSP (val))
                  fix_submap_inheritance (map, idx, val);
-               return val;
+               return get_keyelt (val, autoload);
              }
            if (t_ok && EQ (XCAR (binding), Qt))
              t_binding = XCDR (binding);
@@ -515,11 +538,11 @@ access_keymap (map, idx, t_ok, noinherit)
            if (NATNUMP (idx) && XFASTINT (idx) < XVECTOR (binding)->size)
              {
                val = XVECTOR (binding)->contents[XFASTINT (idx)];
-               if (noprefix && CONSP (val) && EQ (XCAR (val), Qkeymap))
+               if (noprefix && KEYMAPP (val))
                  return Qnil;
                if (CONSP (val))
                  fix_submap_inheritance (map, idx, val);
-               return val;
+               return get_keyelt (val, autoload);
              }
          }
        else if (CHAR_TABLE_P (binding))
@@ -533,18 +556,18 @@ access_keymap (map, idx, t_ok, noinherit)
                         | CHAR_SHIFT | CHAR_CTL | CHAR_META)))
              {
                val = Faref (binding, idx);
-               if (noprefix && CONSP (val) && EQ (XCAR (val), Qkeymap))
+               if (noprefix && KEYMAPP (val))
                  return Qnil;
                if (CONSP (val))
                  fix_submap_inheritance (map, idx, val);
-               return val;
+               return get_keyelt (val, autoload);
              }
          }
 
        QUIT;
       }
 
-    return t_binding;
+    return get_keyelt (t_binding, autoload);
   }
 }
 
@@ -578,15 +601,30 @@ get_keyelt (object, autoload)
 
       /* If the keymap contents looks like (menu-item name . DEFN)
         or (menu-item name DEFN ...) then use DEFN.
-        This is a new format menu item.
-      */
+        This is a new format menu item.  */
       else if (EQ (XCAR (object), Qmenu_item))
        {
          if (CONSP (XCDR (object)))
            {
+             Lisp_Object tem;
+
              object = XCDR (XCDR (object));
+             tem = object;
              if (CONSP (object))
                object = XCAR (object);
+
+             /* If there's a `:filter FILTER', apply FILTER to the
+                menu-item's definition to get the real definition to
+                use.  */
+             for (; CONSP (tem) && CONSP (XCDR (tem)); tem = XCDR (tem))
+               if (EQ (XCAR (tem), QCfilter) && autoload)
+                 {
+                   Lisp_Object filter;
+                   filter = XCAR (XCDR (tem));
+                   filter = list2 (filter, list2 (Qquote, object));
+                   object = menu_item_eval_property (filter);
+                   break;
+                 }
            }
          else
            /* Invalid keymap */
@@ -616,36 +654,24 @@ get_keyelt (object, autoload)
       /* If the contents are (KEYMAP . ELEMENT), go indirect.  */
       else
        {
-         register Lisp_Object map;
-         map = get_keymap_1 (Fcar_safe (object), 0, autoload);
-         if (NILP (map))
-           /* Invalid keymap */
-           return object;
-         else
-           {
-             Lisp_Object key;
-             key = Fcdr (object);
-             if (INTEGERP (key) && (XINT (key) & meta_modifier))
-               {
-                 object = access_keymap (map, meta_prefix_char, 0, 0);
-                 map = get_keymap_1 (object, 0, autoload);
-                 object = access_keymap (map, make_number (XINT (key)
-                                                           & ~meta_modifier),
-                                         0, 0);
-               }
-             else
-               object = access_keymap (map, key, 0, 0);
-           }
+         Lisp_Object map;
+         map = get_keymap (Fcar_safe (object), 0, autoload);
+         return (!CONSP (map) ? object /* Invalid keymap */
+                 : access_keymap (map, Fcdr (object), 0, 0, autoload));
        }
     }
 }
 
-Lisp_Object
+static Lisp_Object
 store_in_keymap (keymap, idx, def)
      Lisp_Object keymap;
      register Lisp_Object idx;
      register Lisp_Object def;
 {
+  /* Flush any reverse-map cache.  */
+  where_is_cache = Qnil;
+  where_is_cache_keymaps = Qt;
+
   /* 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)
@@ -689,9 +715,9 @@ store_in_keymap (keymap, idx, def)
        elt = XCAR (tail);
        if (VECTORP (elt))
          {
-           if (NATNUMP (idx) && XFASTINT (idx) < XVECTOR (elt)->size)
+           if (NATNUMP (idx) && XFASTINT (idx) < ASIZE (elt))
              {
-               XVECTOR (elt)->contents[XFASTINT (idx)] = def;
+               ASET (elt, XFASTINT (idx), def);
                return def;
              }
            insertion_point = tail;
@@ -719,15 +745,12 @@ store_in_keymap (keymap, idx, def)
                return def;
              }
          }
-       else if (SYMBOLP (elt))
-         {
-           /* If we find a 'keymap' symbol in the spine of KEYMAP,
-               then we must have found the start of a second keymap
-               being used as the tail of KEYMAP, and a binding for IDX
-               should be inserted before it.  */
-           if (EQ (elt, Qkeymap))
-             goto keymap_end;
-         }
+       else if (EQ (elt, Qkeymap))
+         /* If we find a 'keymap' symbol in the spine of KEYMAP,
+            then we must have found the start of a second keymap
+            being used as the tail of KEYMAP, and a binding for IDX
+            should be inserted before it.  */
+         goto keymap_end;
 
        QUIT;
       }
@@ -738,7 +761,7 @@ store_in_keymap (keymap, idx, def)
     XCDR (insertion_point)
       = Fcons (Fcons (idx, def), XCDR (insertion_point));
   }
-         
+  
   return def;
 }
 
@@ -746,7 +769,7 @@ void
 copy_keymap_1 (chartable, idx, elt)
      Lisp_Object chartable, idx, elt;
 {
-  if (!SYMBOLP (elt) && ! NILP (Fkeymapp (elt)))
+  if (CONSP (elt) && EQ (XCAR (elt), Qkeymap))
     Faset (chartable, idx, Fcopy_keymap (elt));
 }
 
@@ -762,7 +785,7 @@ is not copied.")
 {
   register Lisp_Object copy, tail;
 
-  copy = Fcopy_alist (get_keymap (keymap));
+  copy = Fcopy_alist (get_keymap (keymap, 1, 0));
 
   for (tail = copy; CONSP (tail); tail = XCDR (tail))
     {
@@ -785,11 +808,9 @@ is not copied.")
          elt = Fcopy_sequence (elt);
          XCAR (tail) = elt;
 
-         for (i = 0; i < XVECTOR (elt)->size; i++)
-           if (!SYMBOLP (XVECTOR (elt)->contents[i])
-               && ! NILP (Fkeymapp (XVECTOR (elt)->contents[i])))
-             XVECTOR (elt)->contents[i]
-               = Fcopy_keymap (XVECTOR (elt)->contents[i]);
+         for (i = 0; i < ASIZE (elt); i++)
+           if (CONSP (AREF (elt, i)) && EQ (XCAR (AREF (elt, i)), Qkeymap))
+             ASET (elt, i, Fcopy_keymap (AREF (elt, i)));
        }
       else if (CONSP (elt) && CONSP (XCDR (elt)))
        {
@@ -820,7 +841,7 @@ is not copied.")
                    = Fcons (XCAR (tem), XCDR (tem));
                  elt = XCDR (elt);
                  tem = XCAR (elt);
-                 if (!(SYMBOLP (tem) || NILP (Fkeymapp (tem))))
+                 if (CONSP (tem) && EQ (XCAR (tem), Qkeymap))
                    XCAR (elt) = Fcopy_keymap (tem);
                  tem = XCDR (elt);
                  if (CONSP (tem) && CONSP (XCAR (tem)))
@@ -857,8 +878,8 @@ is not copied.")
                    XCDR (elt) = XCDR (tem);
                }
              if (CONSP (elt)
-                 && ! SYMBOLP (XCDR (elt))
-                 && ! NILP (Fkeymapp (XCDR (elt))))
+                 && CONSP (XCDR (elt))
+                 && EQ (XCAR (XCDR (elt)), Qkeymap))
                XCDR (elt) = Fcopy_keymap (XCDR (elt));
            }
 
@@ -905,7 +926,7 @@ the front of KEYMAP.")
   int length;
   struct gcpro gcpro1, gcpro2, gcpro3;
 
-  keymap = get_keymap_1 (keymap, 1, 1);
+  keymap = get_keymap (keymap, 1, 1);
 
   if (!VECTORP (key) && !STRINGP (key))
     key = wrong_type_argument (Qarrayp, key);
@@ -954,14 +975,14 @@ the front of KEYMAP.")
       if (idx == length)
        RETURN_UNGCPRO (store_in_keymap (keymap, c, def));
 
-      cmd = get_keyelt (access_keymap (keymap, c, 0, 1), 1);
+      cmd = access_keymap (keymap, c, 0, 1, 1);
 
       /* If this key is undefined, make it a prefix.  */
       if (NILP (cmd))
        cmd = define_as_prefix (keymap, c);
 
-      keymap = get_keymap_1 (cmd, 0, 1);
-      if (NILP (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 uses invalid prefix characters",
@@ -995,13 +1016,11 @@ recognize the default bindings, just as `read-key-sequence' does.")
   register int idx;
   register Lisp_Object cmd;
   register Lisp_Object c;
-  int metized = 0;
   int length;
   int t_ok = ! NILP (accept_default);
-  int meta_bit;
   struct gcpro gcpro1;
 
-  keymap = get_keymap_1 (keymap, 1, 1);
+  keymap = get_keymap (keymap, 1, 1);
 
   if (!VECTORP (key) && !STRINGP (key))
     key = wrong_type_argument (Qarrayp, key);
@@ -1010,43 +1029,26 @@ recognize the default bindings, just as `read-key-sequence' does.")
   if (length == 0)
     return keymap;
 
-  if (VECTORP (key))
-    meta_bit = meta_modifier;
-  else
-    meta_bit = 0x80;
-
   GCPRO1 (key);
 
   idx = 0;
   while (1)
     {
-      c = Faref (key, make_number (idx));
+      c = Faref (key, make_number (idx++));
 
       if (CONSP (c) && lucid_event_type_list_p (c))
        c = Fevent_convert_list (c);
 
-      if (INTEGERP (c)
-         && (XINT (c) & meta_bit)
-         && !metized)
-       {
-         c = meta_prefix_char;
-         metized = 1;
-       }
-      else
-       {
-         if (INTEGERP (c))
-           XSETINT (c, XINT (c) & ~meta_bit);
-
-         metized = 0;
-         idx++;
-       }
+      /* Turn the 8th bit of string chars into a meta modifier.  */
+      if (XINT (c) & 0x80 && STRINGP (key))
+       XSETINT (c, (XINT (c) | meta_modifier) & ~0x80);
 
-      cmd = get_keyelt (access_keymap (keymap, c, t_ok, 0), 1);
+      cmd = access_keymap (keymap, c, t_ok, 0, 1);
       if (idx == length)
        RETURN_UNGCPRO (cmd);
 
-      keymap = get_keymap_1 (cmd, 0, 1);
-      if (NILP (keymap))
+      keymap = get_keymap (cmd, 0, 1);
+      if (!CONSP (keymap))
        RETURN_UNGCPRO (make_number (idx));
 
       QUIT;
@@ -1061,44 +1063,13 @@ static Lisp_Object
 define_as_prefix (keymap, c)
      Lisp_Object keymap, c;
 {
-  Lisp_Object inherit, cmd;
+  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.  */
-  inherit = access_keymap (keymap, c, 0, 0);
-#if 0
-  /* This code is needed to do the right thing in the following case:
-     keymap A inherits from B,
-     you define KEY as a prefix in A,
-     then later you define KEY as a prefix in B.
-     We want the old prefix definition in A to inherit from that in B.
-     It is hard to do that retroactively, so this code
-     creates the prefix in B right away.
-
-     But it turns out that this code causes problems immediately
-     when the prefix in A is defined: it causes B to define KEY
-     as a prefix with no subcommands.
-
-     So I took out this code.  */
-  if (NILP (inherit))
-    {
-      /* If there's an inherited keymap
-        and it doesn't define this key,
-        make it define this key.  */
-      Lisp_Object tail;
-
-      for (tail = Fcdr (keymap); CONSP (tail); tail = XCDR (tail))
-       if (EQ (XCAR (tail), Qkeymap))
-         break;
-
-      if (!NILP (tail))
-       inherit = define_as_prefix (tail, c);
-    }
-#endif
-
-  cmd = nconc2 (cmd, inherit);
+  cmd = nconc2 (cmd, access_keymap (keymap, c, 0, 0, 0));
   store_in_keymap (keymap, c, cmd);
 
   return cmd;
@@ -1187,16 +1158,18 @@ current_minor_maps (modeptr, mapptr)
            {
              Lisp_Object *newmodes, *newmaps;
 
+             /* Use malloc/realloc here.  See the comment above
+                this function.  */
              if (cmm_maps)
                {
                  BLOCK_INPUT;
                  cmm_size *= 2;
                  newmodes
                    = (Lisp_Object *) realloc (cmm_modes,
-                                              cmm_size * sizeof (Lisp_Object));
+                                               cmm_size * sizeof *newmodes);
                  newmaps
                    = (Lisp_Object *) realloc (cmm_maps,
-                                              cmm_size * sizeof (Lisp_Object));
+                                               cmm_size * sizeof *newmaps);
                  UNBLOCK_INPUT;
                }
              else
@@ -1204,18 +1177,18 @@ current_minor_maps (modeptr, mapptr)
                  BLOCK_INPUT;
                  cmm_size = 30;
                  newmodes
-                   = (Lisp_Object *) malloc (cmm_size * sizeof (Lisp_Object));
+                   = (Lisp_Object *) malloc (cmm_size * sizeof *newmodes);
                  newmaps
-                   = (Lisp_Object *) malloc (cmm_size * sizeof (Lisp_Object));
+                   = (Lisp_Object *) malloc (cmm_size * sizeof *newmaps);
                  UNBLOCK_INPUT;
                }
 
-             if (newmaps && newmodes)
-               {
-                 cmm_modes = newmodes;
-                 cmm_maps = newmaps;
-               }
-             else
+             if (newmodes)
+               cmm_modes = newmodes;
+             if (newmaps)
+               cmm_maps = newmaps;
+             
+             if (newmodes == NULL || newmaps == NULL)
                break;
            }
 
@@ -1379,11 +1352,11 @@ bindings; see the description of `lookup-key' for more details about this.")
   GCPRO2 (key, binding);
 
   for (i = j = 0; i < nmaps; i++)
-    if (! NILP (maps[i])
-       && ! NILP (binding = Flookup_key (maps[i], key, accept_default))
+    if (!NILP (maps[i])
+       && !NILP (binding = Flookup_key (maps[i], key, accept_default))
        && !INTEGERP (binding))
       {
-       if (! NILP (get_keymap (binding)))
+       if (KEYMAPP (binding))
          maps[j++] = Fcons (modes[i], binding);
        else if (j == 0)
          RETURN_UNGCPRO (Fcons (Fcons (modes[i], binding), Qnil));
@@ -1419,7 +1392,7 @@ DEFUN ("use-global-map", Fuse_global_map, Suse_global_map, 1, 1, 0,
   (keymap)
      Lisp_Object keymap;
 {
-  keymap = get_keymap (keymap);
+  keymap = get_keymap (keymap, 1, 1);
   current_global_map = keymap;
 
   return Qnil;
@@ -1432,7 +1405,7 @@ If KEYMAP is nil, that means no local keymap.")
      Lisp_Object keymap;
 {
   if (!NILP (keymap))
-    keymap = get_keymap (keymap);
+    keymap = get_keymap (keymap, 1, 1);
 
   current_buffer->keymap = keymap;
 
@@ -1497,8 +1470,8 @@ then the value includes only maps for prefixes that start with PREFIX.")
       /* Flookup_key may give us nil, or a number,
         if the prefix is not defined in this particular map.
         It might even give us a list that isn't a keymap.  */
-      tem = get_keymap_1 (tem, 0, 0);
-      if (!NILP (tem))
+      tem = get_keymap (tem, 0, 0);
+      if (CONSP (tem))
        {
          /* Convert PREFIX to a vector now, so that later on
             we don't have to deal with the possibility of a string.  */
@@ -1515,7 +1488,7 @@ then the value includes only maps for prefixes that start with PREFIX.")
                  FETCH_STRING_CHAR_ADVANCE (c, prefix, i, i_byte);
                  if (SINGLE_BYTE_CHAR_P (c) && (c & 0200))
                    c ^= 0200 | meta_modifier;
-                 XVECTOR (copy)->contents[i_before] = make_number (c);
+                 ASET (copy, i_before, make_number (c));
                }
              prefix = copy;
            }
@@ -1526,7 +1499,7 @@ then the value includes only maps for prefixes that start with PREFIX.")
     }
   else
     maps = Fcons (Fcons (Fmake_vector (make_number (0), Qnil),
-                        get_keymap (keymap)),
+                        get_keymap (keymap, 1, 0)),
                  Qnil);
 
   /* For each map in the list maps,
@@ -1572,17 +1545,17 @@ then the value includes only maps for prefixes that start with PREFIX.")
              register int i;
 
              /* Vector keymap.  Scan all the elements.  */
-             for (i = 0; i < XVECTOR (elt)->size; i++)
+             for (i = 0; i < ASIZE (elt); i++)
                {
                  register Lisp_Object tem;
                  register Lisp_Object cmd;
 
-                 cmd = get_keyelt (XVECTOR (elt)->contents[i], 0);
+                 cmd = get_keyelt (AREF (elt, i), 0);
                  if (NILP (cmd)) continue;
-                 tem = Fkeymapp (cmd);
-                 if (!NILP (tem))
+                 tem = get_keymap (cmd, 0, 0);
+                 if (CONSP (tem))
                    {
-                     cmd = get_keymap (cmd);
+                     cmd = tem;
                      /* Ignore keymaps that are already added to maps.  */
                      tem = Frassq (cmd, maps);
                      if (NILP (tem))
@@ -1620,11 +1593,11 @@ then the value includes only maps for prefixes that start with PREFIX.")
 
              cmd = get_keyelt (XCDR (elt), 0);
              /* Ignore definitions that aren't keymaps themselves.  */
-             tem = Fkeymapp (cmd);
-             if (!NILP (tem))
+             tem = get_keymap (cmd, 0, 0);
+             if (CONSP (tem))
                {
                  /* Ignore keymaps that have been seen already.  */
-                 cmd = get_keymap (cmd);
+                 cmd = tem;
                  tem = Frassq (cmd, maps);
                  if (NILP (tem))
                    {
@@ -1640,7 +1613,7 @@ then the value includes only maps for prefixes that start with PREFIX.")
 
                          element = thisseq;
                          tem = Fvconcat (1, &element);
-                         XSETFASTINT (XVECTOR (tem)->contents[XINT (last)],
+                         XSETFASTINT (AREF (tem, XINT (last)),
                                       XINT (elt) | meta_modifier);
 
                          /* This new sequence is the same length as
@@ -1704,10 +1677,10 @@ accessible_keymaps_char_table (args, index, cmd)
   tail = XCAR (XCDR (args));
   thisseq = XCDR (XCDR (args));
 
-  tem = Fkeymapp (cmd);
-  if (!NILP (tem))
+  tem = get_keymap (cmd, 0, 0);
+  if (CONSP (tem))
     {
-      cmd = get_keymap (cmd);
+      cmd = tem;
       /* Ignore keymaps that are already added to maps.  */
       tem = Frassq (cmd, maps);
       if (NILP (tem))
@@ -1729,10 +1702,10 @@ spaces are put between sequence elements, etc.")
   (keys)
      Lisp_Object keys;
 {
-  int len;
+  int len = 0;
   int i, i_byte;
   Lisp_Object sep;
-  Lisp_Object *args;
+  Lisp_Object *args = NULL;
 
   if (STRINGP (keys))
     {
@@ -1746,7 +1719,7 @@ spaces are put between sequence elements, etc.")
          FETCH_STRING_CHAR_ADVANCE (c, keys, i, i_byte);
          if (SINGLE_BYTE_CHAR_P (c) && (c & 0200))
            c ^= 0200 | meta_modifier;
-         XSETFASTINT (XVECTOR (vector)->contents[i_before], c);
+         XSETFASTINT (AREF (vector, i_before), c);
        }
       keys = vector;
     }
@@ -1764,7 +1737,7 @@ spaces are put between sequence elements, etc.")
 
       for (i = 0; i < len; i++)
        {
-         args[i * 2] = Fsingle_key_description (XVECTOR (keys)->contents[i]);
+         args[i * 2] = Fsingle_key_description (AREF (keys, i), Qnil);
          args[i * 2 + 1] = sep;
        }
     }
@@ -1781,7 +1754,7 @@ spaces are put between sequence elements, etc.")
 
       for (i = 0; i < len; i++)
        {
-         args[i * 2] = Fsingle_key_description (XCAR (keys));
+         args[i * 2] = Fsingle_key_description (XCAR (keys), Qnil);
          args[i * 2 + 1] = sep;
          keys = XCDR (keys);
        }
@@ -1789,6 +1762,8 @@ spaces are put between sequence elements, etc.")
   else
     keys = wrong_type_argument (Qarrayp, keys);
 
+  if (len == 0)
+    return build_string ("");
   return Fconcat (len * 2 - 1, args);
 }
 
@@ -1797,8 +1772,12 @@ push_key_description (c, p)
      register unsigned int c;
      register char *p;
 {
+  unsigned c2;
+  
   /* 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);
 
   if (c & alt_modifier)
     {
@@ -1806,11 +1785,12 @@ push_key_description (c, p)
       *p++ = '-';
       c -= alt_modifier;
     }
-  if (c & ctrl_modifier)
+  if ((c & ctrl_modifier) != 0
+      || (c2 < ' ' && c2 != 27 && c2 != '\t' && c2 != Ctl ('M')))
     {
       *p++ = 'C';
       *p++ = '-';
-      c -= ctrl_modifier;
+      c &= ~ctrl_modifier;
     }
   if (c & hyper_modifier)
     {
@@ -1858,8 +1838,7 @@ push_key_description (c, p)
        }
       else
        {
-         *p++ = 'C';
-         *p++ = '-';
+         /* `C-' already added above.  */
          if (c > 0 && c <= Ctl ('Z'))
            *p++ = c + 0140;
          else
@@ -1884,9 +1863,6 @@ push_key_description (c, p)
     *p++ = c;
   else
     {
-      if (! NILP (current_buffer->enable_multibyte_characters))
-       c = unibyte_char_to_multibyte (c);
-
       if (NILP (current_buffer->enable_multibyte_characters)
          || SINGLE_BYTE_CHAR_P (c)
          || ! char_valid_p (c, 0))
@@ -1911,11 +1887,14 @@ push_key_description (c, p)
 
 /* This function cannot GC.  */
 
-DEFUN ("single-key-description", Fsingle_key_description, Ssingle_key_description, 1, 1, 0,
+DEFUN ("single-key-description", Fsingle_key_description,
+       Ssingle_key_description, 1, 2, 0,
   "Return a pretty description of command character KEY.\n\
-Control characters turn into C-whatever, etc.")
-  (key)
-     Lisp_Object key;
+Control characters turn into C-whatever, etc.\n\
+Optional argument NO-ANGLES non-nil means don't put angle brackets\n\
+around function keys and event symbols.")
+  (key, no_angles)
+     Lisp_Object key, no_angles;
 {
   if (CONSP (key) && lucid_event_type_list_p (key))
     key = Fevent_convert_list (key);
@@ -1953,14 +1932,21 @@ Control characters turn into C-whatever, etc.")
     }
   else if (SYMBOLP (key))      /* Function key or event-symbol */
     {
-      char *buffer = (char *) alloca (STRING_BYTES (XSYMBOL (key)->name) + 5);
-      sprintf (buffer, "<%s>", XSYMBOL (key)->name->data);
-      return build_string (buffer);
+      if (NILP (no_angles))
+       {
+         char *buffer
+           = (char *) alloca (STRING_BYTES (XSYMBOL (key)->name) + 5);
+         sprintf (buffer, "<%s>", XSYMBOL (key)->name->data);
+         return build_string (buffer);
+       }
+      else
+       return Fsymbol_name (key);
     }
   else if (STRINGP (key))      /* Buffer names in the menubar.  */
     return Fcopy_sequence (key);
   else
     error ("KEY must be an integer, cons, symbol, or string");
+  return Qnil;
 }
 
 char *
@@ -2046,76 +2032,47 @@ ascii_sequence_p (seq)
 static Lisp_Object where_is_internal_1 ();
 static void where_is_internal_2 ();
 
+/* 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.  */
+
+static Lisp_Object
+shadow_lookup (shadow, key, flag)
+     Lisp_Object shadow, key, flag;
+{
+  Lisp_Object tail, value;
+
+  for (tail = shadow; CONSP (tail); tail = XCDR (tail))
+    {
+      value = Flookup_key (XCAR (tail), key, flag);
+      if (!NILP (value) && !NATNUMP (value))
+       return value;
+    }
+  return Qnil;
+}
+
 /* This function can GC if Flookup_key autoloads any keymaps.  */
 
-DEFUN ("where-is-internal", Fwhere_is_internal, Swhere_is_internal, 1, 4, 0,
-  "Return list of keys that invoke DEFINITION.\n\
-If KEYMAP is non-nil, search only KEYMAP and the global keymap.\n\
-If KEYMAP is nil, search all the currently active keymaps.\n\
-\n\
-If optional 3rd arg FIRSTONLY is non-nil, return the first key sequence found,\n\
-rather than a list of all possible key sequences.\n\
-If FIRSTONLY is the symbol `non-ascii', return the first binding found,\n\
-no matter what it is.\n\
-If FIRSTONLY has another non-nil value, prefer sequences of ASCII characters,\n\
-and entirely reject menu bindings.\n\
-\n\
-If optional 4th arg NOINDIRECT is non-nil, don't follow indirections\n\
-to other keymaps or slots.  This makes it possible to search for an\n\
-indirect definition itself.")
-  (definition, keymap, firstonly, noindirect)
-     Lisp_Object definition, keymap;
+static Lisp_Object
+where_is_internal (definition, keymaps, firstonly, noindirect)
+     Lisp_Object definition, keymaps;
      Lisp_Object firstonly, noindirect;
 {
-  Lisp_Object maps;
+  Lisp_Object maps = Qnil;
   Lisp_Object found, sequences;
-  Lisp_Object keymap1;
-  int keymap_specified = !NILP (keymap);
   struct gcpro gcpro1, gcpro2, gcpro3, gcpro4, gcpro5;
   /* 1 means ignore all menu bindings entirely.  */
   int nomenus = !NILP (firstonly) && !EQ (firstonly, Qnon_ascii);
 
-  /* Find keymaps accessible from `keymap' or the current
-     context.  But don't muck with the value of `keymap',
-     because `where_is_internal_1' uses it to check for
-     shadowed bindings. */
-  keymap1 = keymap;
-  if (! keymap_specified)
-    keymap1 = get_local_map (PT, current_buffer, keymap);
-    
-  if (!NILP (keymap1))
-    maps = nconc2 (Faccessible_keymaps (get_keymap (keymap1), Qnil),
-                  Faccessible_keymaps (get_keymap (current_global_map),
-                                       Qnil));
-  else
+  found = keymaps;
+  while (CONSP (found))
     {
-      keymap1 = keymap;
-      if (! keymap_specified)
-       keymap1 = get_local_map (PT, current_buffer, local_map);
-    
-      if (!NILP (keymap1))
-       maps = nconc2 (Faccessible_keymaps (get_keymap (keymap1), Qnil),
-                      Faccessible_keymaps (get_keymap (current_global_map),
-                                           Qnil));
-      else
-       maps = Faccessible_keymaps (get_keymap (current_global_map), Qnil);
-    }
-
-  /* Put the minor mode keymaps on the front.  */
-  if (! keymap_specified)
-    {
-      Lisp_Object minors;
-      minors = Fnreverse (Fcurrent_minor_mode_maps ());
-      while (!NILP (minors))
-       {
-         maps = nconc2 (Faccessible_keymaps (get_keymap (XCAR (minors)),
-                                             Qnil),
-                        maps);
-         minors = XCDR (minors);
-       }
+      maps =
+       nconc2 (maps,
+               Faccessible_keymaps (get_keymap (XCAR (found), 1, 0), Qnil));
+      found = XCDR (found);
     }
-
-  GCPRO5 (definition, keymap, maps, found, sequences);
+  GCPRO5 (definition, keymaps, maps, found, sequences);
   found = Qnil;
   sequences = Qnil;
 
@@ -2136,6 +2093,12 @@ indirect definition itself.")
       last_is_meta = (XINT (last) >= 0
                      && EQ (Faref (this, last), meta_prefix_char));
 
+      if (nomenus && !ascii_sequence_p (this))
+       /* If no menu entries should be returned, skip over the
+          keymaps bound to `menu-bar' and `tool-bar' and other
+          non-ascii prefixes.  */
+       continue;
+      
       QUIT;
 
       while (CONSP (map))
@@ -2165,10 +2128,10 @@ indirect definition itself.")
              /* In a vector, look at each element.  */
              for (i = 0; i < XVECTOR (elt)->size; i++)
                {
-                 binding = XVECTOR (elt)->contents[i];
+                 binding = AREF (elt, i);
                  XSETFASTINT (key, i);
                  sequence = where_is_internal_1 (binding, key, definition,
-                                                 noindirect, keymap, this,
+                                                 noindirect, this,
                                                  last, nomenus, last_is_meta);
                  if (!NILP (sequence))
                    sequences = Fcons (sequence, sequences);
@@ -2180,14 +2143,13 @@ indirect definition itself.")
              Lisp_Object args;
 
              args = Fcons (Fcons (Fcons (definition, noindirect),
-                                  Fcons (keymap, Qnil)),
+                                  Qnil), /* Result accumulator.  */
                            Fcons (Fcons (this, last),
                                   Fcons (make_number (nomenus),
                                          make_number (last_is_meta))));
-
              map_char_table (where_is_internal_2, Qnil, elt, args,
                              0, indices);
-             sequences = XCDR (XCDR (XCAR (args)));
+             sequences = XCDR (XCAR (args));
            }
          else if (CONSP (elt))
            {
@@ -2197,7 +2159,7 @@ indirect definition itself.")
              binding = XCDR (elt);
 
              sequence = where_is_internal_1 (binding, key, definition,
-                                             noindirect, keymap, this,
+                                             noindirect, this,
                                              last, nomenus, last_is_meta);
              if (!NILP (sequence))
                sequences = Fcons (sequence, sequences);
@@ -2210,6 +2172,18 @@ indirect definition itself.")
 
              sequence = XCAR (sequences);
 
+             /* 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;
+
              /* 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)))
@@ -2240,90 +2214,151 @@ indirect definition itself.")
   return found;
 }
 
+DEFUN ("where-is-internal", Fwhere_is_internal, Swhere_is_internal, 1, 4, 0,
+  "Return list of keys that invoke DEFINITION.\n\
+If KEYMAP is non-nil, search only KEYMAP and the global keymap.\n\
+If KEYMAP is nil, search all the currently active keymaps.\n\
+If KEYMAP is a list of keymaps, search only those keymaps.\n\
+\n\
+If optional 3rd arg FIRSTONLY is non-nil, return the first key sequence found,\n\
+rather than a list of all possible key sequences.\n\
+If FIRSTONLY is the symbol `non-ascii', return the first binding found,\n\
+no matter what it is.\n\
+If FIRSTONLY has another non-nil value, prefer sequences of ASCII characters,\n\
+and entirely reject menu bindings.\n\
+\n\
+If optional 4th arg NOINDIRECT is non-nil, don't follow indirections\n\
+to other keymaps or slots.  This makes it possible to search for an\n\
+indirect definition itself.")
+  (definition, xkeymap, firstonly, noindirect)
+     Lisp_Object definition, xkeymap;
+     Lisp_Object firstonly, noindirect;
+{
+  Lisp_Object sequences, keymaps;
+  struct gcpro gcpro1, gcpro2, gcpro3, gcpro4;
+  /* 1 means ignore all menu bindings entirely.  */
+  int nomenus = !NILP (firstonly) && !EQ (firstonly, Qnon_ascii);
+
+  /* Find the relevant keymaps.  */
+  if (CONSP (xkeymap) && KEYMAPP (XCAR (xkeymap)))
+    keymaps = xkeymap;
+  else if (! NILP (xkeymap))
+    keymaps = Fcons (xkeymap, Fcons (current_global_map, Qnil));
+  else
+    keymaps =
+      Fdelq (Qnil,
+            nconc2 (Fcurrent_minor_mode_maps (),
+                    Fcons (get_local_map (PT, current_buffer, keymap),
+                           Fcons (get_local_map (PT, current_buffer, local_map),
+                                  Fcons (current_global_map, Qnil)))));
+
+  /* Only use caching for the menubar (i.e. called with (def nil t nil).
+     We don't really need to check `xkeymap'.  */
+  if (nomenus && NILP (noindirect) && NILP (xkeymap))
+    {
+      /* 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;
+         
+         /* Fill in the cache.  */
+         GCPRO4 (definition, keymaps, firstonly, noindirect);
+         where_is_internal (definition, keymaps, firstonly, noindirect);
+         UNGCPRO;
+
+         where_is_cache_keymaps = keymaps;
+       }
+
+      sequences = Fgethash (definition, where_is_cache, Qnil);
+      /* Verify that the key bindings are not shadowed.  */
+      /* key-binding can GC. */
+      GCPRO3 (definition, sequences, keymaps);
+      for (sequences = Fnreverse (sequences);
+          CONSP (sequences);
+          sequences = XCDR (sequences))
+       if (EQ (shadow_lookup (keymaps, XCAR (sequences), Qnil), definition)
+           && ascii_sequence_p (XCAR (sequences)))
+         RETURN_UNGCPRO (XCAR (sequences));
+      RETURN_UNGCPRO (Qnil);
+    }
+  else
+    {
+      /* Kill the cache so that where_is_internal_1 doesn't think
+        we're filling it up.  */
+      where_is_cache = Qnil;
+      return where_is_internal (definition, keymaps, firstonly, noindirect);
+    }
+}
+
 /* This is the function that Fwhere_is_internal calls using map_char_table.
    ARGS has the form
    (((DEFINITION . NOINDIRECT) . (KEYMAP . RESULT))
     .
     ((THIS . LAST) . (NOMENUS . LAST_IS_META)))
    Since map_char_table doesn't really use the return value from this function,
-   we the result append to RESULT, the slot in ARGS.  */
+   we the result append to RESULT, the slot in ARGS.
+
+   This function can GC because it calls where_is_internal_1 which can
+   GC.  */
 
 static void
 where_is_internal_2 (args, key, binding)
      Lisp_Object args, key, binding;
 {
-  Lisp_Object definition, noindirect, keymap, this, last;
+  Lisp_Object definition, noindirect, this, last;
   Lisp_Object result, sequence;
   int nomenus, last_is_meta;
+  struct gcpro gcpro1, gcpro2, gcpro3;
 
-  result = XCDR (XCDR (XCAR (args)));
+  GCPRO3 (args, key, binding);
+  result = XCDR (XCAR (args));
   definition = XCAR (XCAR (XCAR (args)));
   noindirect = XCDR (XCAR (XCAR (args)));
-  keymap = XCAR (XCDR (XCAR (args)));
   this = XCAR (XCAR (XCDR (args)));
   last = XCDR (XCAR (XCDR (args)));
   nomenus = XFASTINT (XCAR (XCDR (XCDR (args))));
   last_is_meta = XFASTINT (XCDR (XCDR (XCDR (args))));
 
-  sequence = where_is_internal_1 (binding, key, definition, noindirect, keymap,
+  sequence = where_is_internal_1 (binding, key, definition, noindirect,
                                  this, last, nomenus, last_is_meta);
 
   if (!NILP (sequence))
-    XCDR (XCDR (XCAR (args)))
-      = Fcons (sequence, result);
+    XCDR (XCAR (args)) = Fcons (sequence, result);
+
+  UNGCPRO;
 }
 
+
+/* This function cannot GC.  */
+
 static Lisp_Object
-where_is_internal_1 (binding, key, definition, noindirect, keymap, this, last,
+where_is_internal_1 (binding, key, definition, noindirect, this, last,
                     nomenus, last_is_meta)
-     Lisp_Object binding, key, definition, noindirect, keymap, this, last;
+     Lisp_Object binding, key, definition, noindirect, this, last;
      int nomenus, last_is_meta;
 {
   Lisp_Object sequence;
-  int keymap_specified = !NILP (keymap);
 
   /* Search through indirections unless that's not wanted.  */
   if (NILP (noindirect))
-    {
-      if (nomenus)
-       {
-         while (1)
-           {
-             Lisp_Object map, tem;
-             /* If the contents are (KEYMAP . ELEMENT), go indirect.  */
-             map = get_keymap_1 (Fcar_safe (definition), 0, 0);
-             tem = Fkeymapp (map);
-             if (!NILP (tem))
-               definition = access_keymap (map, Fcdr (definition), 0, 0);
-             else
-               break;
-           }
-         /* If the contents are (menu-item ...) or (STRING ...), reject.  */
-         if (CONSP (definition)
-             && (EQ (XCAR (definition),Qmenu_item)
-                 || STRINGP (XCAR (definition))))
-           return Qnil;
-       }
-      else
-       binding = get_keyelt (binding, 0);
-    }
+    binding = get_keyelt (binding, 0);
 
   /* End this iteration if this element does not match
      the target.  */
 
-  if (CONSP (definition))
-    {
-      Lisp_Object tem;
-      tem = Fequal (binding, definition);
-      if (NILP (tem))
-       return Qnil;
-    }
-  else
-    if (!EQ (binding, definition))
-      return Qnil;
+  if (!(!NILP (where_is_cache) /* everything "matches" during cache-fill.  */
+       || EQ (binding, definition)
+       || (CONSP (definition) && !NILP (Fequal (binding, definition)))))
+    /* Doesn't match.  */
+    return Qnil;
 
-  /* We have found a match.
-     Construct the key sequence where we found it.  */
+  /* We have found a match.  Construct the key sequence where we found it.  */
   if (INTEGERP (key) && last_is_meta)
     {
       sequence = Fcopy_sequence (this);
@@ -2332,40 +2367,14 @@ where_is_internal_1 (binding, key, definition, noindirect, keymap, this, last,
   else
     sequence = append_key (this, key);
 
-  /* 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 (keymap_specified)
+  if (!NILP (where_is_cache))
     {
-      binding = Flookup_key (keymap, sequence, Qnil);
-      if (!NILP (binding) && !INTEGERP (binding))
-       {
-         if (CONSP (definition))
-           {
-             Lisp_Object tem;
-             tem = Fequal (binding, definition);
-             if (NILP (tem))
-               return Qnil;
-           }
-         else
-           if (!EQ (binding, definition))
-             return Qnil;
-       }
+      Lisp_Object sequences = Fgethash (binding, where_is_cache, Qnil);
+      Fputhash (binding, Fcons (sequence, sequences), where_is_cache);
+      return Qnil;
     }
   else
-    {
-      binding = Fkey_binding (sequence, Qnil);
-      if (!EQ (binding, definition))
-       return Qnil;
-    }
-
-  return sequence;
+    return sequence;
 }
 \f
 /* describe-bindings - summarizing all the bindings in a set of keymaps.  */
@@ -2479,7 +2488,9 @@ You type        Translation\n\
        if (!SYMBOLP (modes[i]))
          abort();
 
-       p = title = (char *) alloca (40 + XSYMBOL (modes[i])->name->size);
+       p = title = (char *) alloca (42 + XSYMBOL (modes[i])->name->size);
+       *p++ = '\f';
+       *p++ = '\n';
        *p++ = '`';
        bcopy (XSYMBOL (modes[i])->name->data, p,
               XSYMBOL (modes[i])->name->size);
@@ -2505,17 +2516,17 @@ You type        Translation\n\
   if (!NILP (start1))
     {
       describe_map_tree (start1, 1, shadow, prefix,
-                        "Major Mode Bindings", nomenu, 0, 0);
+                        "\f\nMajor Mode Bindings", nomenu, 0, 0);
       shadow = Fcons (start1, shadow);
     }
 
   describe_map_tree (current_global_map, 1, shadow, prefix,
-                    "Global Bindings", nomenu, 0, 1);
+                    "\f\nGlobal Bindings", nomenu, 0, 1);
 
   /* Print the function-key-map translations under this prefix.  */
   if (!NILP (Vfunction_key_map))
     describe_map_tree (Vfunction_key_map, 0, Qnil, prefix,
-                      "Function key map translations", nomenu, 1, 0);
+                      "\f\nFunction key map translations", nomenu, 1, 0);
 
   call0 (intern ("help-mode"));
   Fset_buffer (descbuf);
@@ -2632,7 +2643,7 @@ key             binding\n\
          /* If shmap is not nil and not a keymap,
             it completely shadows this map, so don't
             describe this map at all.  */
-         if (!NILP (shmap) && NILP (Fkeymapp (shmap)))
+         if (!NILP (shmap) && !KEYMAPP (shmap))
            goto skip;
 
          if (!NILP (shmap))
@@ -2694,14 +2705,10 @@ describe_command (definition)
     }
   else if (STRINGP (definition) || VECTORP (definition))
     insert_string ("Keyboard Macro\n");
+  else if (KEYMAPP (definition))
+    insert_string ("Prefix Command\n");
   else
-    {
-      tem1 = Fkeymapp (definition);
-      if (!NILP (tem1))
-       insert_string ("Prefix Command\n");
-      else
-       insert_string ("??\n");
-    }
+    insert_string ("??\n");
 }
 
 static void
@@ -2723,32 +2730,10 @@ describe_translation (definition)
       insert1 (Fkey_description (definition));
       insert_string ("\n");
     }
+  else if (KEYMAPP (definition))
+    insert_string ("Prefix Command\n");
   else
-    {
-      tem1 = Fkeymapp (definition);
-      if (!NILP (tem1))
-       insert_string ("Prefix Command\n");
-      else
-       insert_string ("??\n");
-    }
-}
-
-/* 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.  */
-
-static Lisp_Object
-shadow_lookup (shadow, key, flag)
-     Lisp_Object shadow, key, flag;
-{
-  Lisp_Object tail, value;
-
-  for (tail = shadow; CONSP (tail); tail = XCDR (tail))
-    {
-      value = Flookup_key (XCAR (tail), key, flag);
-      if (!NILP (value))
-       return value;
-    }
-  return Qnil;
+    insert_string ("??\n");
 }
 
 /* Describe the contents of map MAP, assuming that this map itself is
@@ -2773,6 +2758,8 @@ describe_map (map, keys, elt_describer, partial, shadow, seen, nomenu)
   int first = 1;
   struct gcpro gcpro1, gcpro2, gcpro3;
 
+  suppress = Qnil;
+
   if (!NILP (keys) && XFASTINT (Flength (keys)) > 0)
     {
       /* Call Fkey_description first, to avoid GC bug for the other string.  */
@@ -2828,7 +2815,7 @@ describe_map (map, keys, elt_describer, partial, shadow, seen, nomenu)
          /* Don't show a command that isn't really visible
             because a local definition of the same key shadows it.  */
 
-         XVECTOR (kludge)->contents[0] = event;
+         ASET (kludge, 0, event);
          if (!NILP (shadow))
            {
              tem = shadow_lookup (shadow, kludge, Qt);
@@ -2849,7 +2836,7 @@ describe_map (map, keys, elt_describer, partial, shadow, seen, nomenu)
            insert1 (elt_prefix);
 
          /* THIS gets the string to describe the character EVENT.  */
-         insert1 (Fsingle_key_description (event));
+         insert1 (Fsingle_key_description (event, Qnil));
 
          /* Print a description of the definition of this character.
             elt_describer will take care of spacing out far enough
@@ -2954,6 +2941,8 @@ describe_vector (vector, elt_prefix, elt_describer,
   int character;
   int starting_i;
 
+  suppress = Qnil;
+
   if (indices == 0)
     indices = (int *) alloca (3 * sizeof (int));
 
@@ -3021,7 +3010,7 @@ describe_vector (vector, elt_prefix, elt_describer,
            = get_keyelt (XCHAR_TABLE (vector)->contents[i], 0);
        }
       else
-       definition = get_keyelt (XVECTOR (vector)->contents[i], 0);
+       definition = get_keyelt (AREF (vector, i), 0);
 
       if (NILP (definition)) continue;      
 
@@ -3061,7 +3050,7 @@ describe_vector (vector, elt_prefix, elt_describer,
        {
          Lisp_Object tem;
          
-         XVECTOR (kludge)->contents[0] = make_number (character);
+         ASET (kludge, 0, make_number (character));
          tem = shadow_lookup (shadow, kludge, Qt);
 
          if (!NILP (tem)) continue;
@@ -3073,7 +3062,7 @@ describe_vector (vector, elt_prefix, elt_describer,
        {
          Lisp_Object tem;
 
-         XVECTOR (kludge)->contents[0] = make_number (character);
+         ASET (kludge, 0, make_number (character));
          tem = Flookup_key (entire_map, kludge, Qt);
 
          if (! EQ (tem, definition))
@@ -3114,7 +3103,7 @@ describe_vector (vector, elt_prefix, elt_describer,
       else if (CHAR_TABLE_P (vector))
        {
          if (complete_char)
-           insert1 (Fsingle_key_description (make_number (character)));
+           insert1 (Fsingle_key_description (make_number (character), Qnil));
          else
            {
              /* Print the information for this character set.  */
@@ -3130,7 +3119,7 @@ describe_vector (vector, elt_prefix, elt_describer,
        }
       else
        {
-         insert1 (Fsingle_key_description (make_number (character)));
+         insert1 (Fsingle_key_description (make_number (character), Qnil));
        }
 
       /* If we find a sub char-table within a char-table,
@@ -3166,7 +3155,7 @@ describe_vector (vector, elt_prefix, elt_describer,
        }
       else
        while (i + 1 < to
-              && (tem2 = get_keyelt (XVECTOR (vector)->contents[i + 1], 0),
+              && (tem2 = get_keyelt (AREF (vector, i + 1), 0),
                   !NILP (tem2))
               && !NILP (Fequal (tem2, definition)))
          i++;
@@ -3186,7 +3175,7 @@ describe_vector (vector, elt_prefix, elt_describer,
            {
              if (char_table_depth == 0)
                {
-                 insert1 (Fsingle_key_description (make_number (i)));
+                 insert1 (Fsingle_key_description (make_number (i), Qnil));
                }
              else if (complete_char)
                {
@@ -3205,7 +3194,7 @@ describe_vector (vector, elt_prefix, elt_describer,
            }
          else
            {
-             insert1 (Fsingle_key_description (make_number (i)));
+             insert1 (Fsingle_key_description (make_number (i), Qnil));
            }
        }
 
@@ -3370,6 +3359,11 @@ and applies even for keys that have ordinary bindings.");
   Qmenu_item = intern ("menu-item");
   staticpro (&Qmenu_item);
 
+  where_is_cache_keymaps = Qt;
+  where_is_cache = Qnil;
+  staticpro (&where_is_cache);
+  staticpro (&where_is_cache_keymaps);
+
   defsubr (&Skeymapp);
   defsubr (&Skeymap_parent);
   defsubr (&Sset_keymap_parent);