src/keymap.c

   1 /* Manipulation of keymaps
   2    Copyright (C) 1985, 86,87,88,93,94,95,98,99, 2000, 2001
   3    Free Software Foundation, Inc.
   4
   5 This file is part of GNU Emacs.
   6
   7 GNU Emacs is free software; you can redistribute it and/or modify
   8 it under the terms of the GNU General Public License as published by
   9 the Free Software Foundation; either version 2, or (at your option)
  10 any later version.
  11
  12 GNU Emacs is distributed in the hope that it will be useful,
  13 but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 GNU General Public License for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GNU Emacs; see the file COPYING.  If not, write to
  19 the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  20 Boston, MA 02111-1307, USA.  */
  21
  22
  23 #include <config.h>
  24 #include <stdio.h>
  25 #include "lisp.h"
  26 #include "commands.h"
  27 #include "buffer.h"
  28 #include "charset.h"
  29 #include "keyboard.h"
  30 #include "termhooks.h"
  31 #include "blockinput.h"
  32 #include "puresize.h"
  33 #include "intervals.h"
  34
  35 #define min(a, b) ((a) < (b) ? (a) : (b))
  36
  37 /* The number of elements in keymap vectors.  */
  38 #define DENSE_TABLE_SIZE (0200)
  39
  40 /* Actually allocate storage for these variables */
  41
  42 Lisp_Object current_global_map; /* Current global keymap */
  43
  44 Lisp_Object global_map;         /* default global key bindings */
  45
  46 Lisp_Object meta_map;           /* The keymap used for globally bound
  47                                    ESC-prefixed default commands */
  48
  49 Lisp_Object control_x_map;      /* The keymap used for globally bound
  50                                    C-x-prefixed default commands */
  51
  52 /* was MinibufLocalMap */
  53 Lisp_Object Vminibuffer_local_map;
  54                                 /* The keymap used by the minibuf for local
  55                                    bindings when spaces are allowed in the
  56                                    minibuf */
  57
  58 /* was MinibufLocalNSMap */
  59 Lisp_Object Vminibuffer_local_ns_map;
  60                                 /* The keymap used by the minibuf for local
  61                                    bindings when spaces are not encouraged
  62                                    in the minibuf */
  63
  64 /* keymap used for minibuffers when doing completion */
  65 /* was MinibufLocalCompletionMap */
  66 Lisp_Object Vminibuffer_local_completion_map;
  67
  68 /* keymap used for minibuffers when doing completion and require a match */
  69 /* was MinibufLocalMustMatchMap */
  70 Lisp_Object Vminibuffer_local_must_match_map;
  71
  72 /* Alist of minor mode variables and keymaps.  */
  73 Lisp_Object Vminor_mode_map_alist;
  74
  75 /* Alist of major-mode-specific overrides for
  76    minor mode variables and keymaps.  */
  77 Lisp_Object Vminor_mode_overriding_map_alist;
  78
  79 /* Keymap mapping ASCII function key sequences onto their preferred forms.
  80    Initialized by the terminal-specific lisp files.  See DEFVAR for more
  81    documentation.  */
  82 Lisp_Object Vfunction_key_map;
  83
  84 /* Keymap mapping ASCII function key sequences onto their preferred forms.  */
  85 Lisp_Object Vkey_translation_map;
  86
  87 /* A list of all commands given new bindings since a certain time
  88    when nil was stored here.
  89    This is used to speed up recomputation of menu key equivalents
  90    when Emacs starts up.   t means don't record anything here.  */
  91 Lisp_Object Vdefine_key_rebound_commands;
  92
  93 Lisp_Object Qkeymapp, Qkeymap, Qnon_ascii, Qmenu_item;
  94
  95 /* A char with the CHAR_META bit set in a vector or the 0200 bit set
  96    in a string key sequence is equivalent to prefixing with this
  97    character.  */
  98 extern Lisp_Object meta_prefix_char;
  99
 100 extern Lisp_Object Voverriding_local_map;
 101
 102 /* Hash table used to cache a reverse-map to speed up calls to where-is.  */
 103 static Lisp_Object where_is_cache;
 104 /* Which keymaps are reverse-stored in the cache.  */
 105 static Lisp_Object where_is_cache_keymaps;
 106
 107 static Lisp_Object store_in_keymap P_ ((Lisp_Object, Lisp_Object, Lisp_Object));
 108 static void fix_submap_inheritance P_ ((Lisp_Object, Lisp_Object, Lisp_Object));
 109
 110 static Lisp_Object define_as_prefix P_ ((Lisp_Object, Lisp_Object));
 111 static Lisp_Object describe_buffer_bindings P_ ((Lisp_Object));
 112 static void describe_command P_ ((Lisp_Object));
 113 static void describe_translation P_ ((Lisp_Object));
 114 static void describe_map P_ ((Lisp_Object, Lisp_Object,
 115                               void (*) P_ ((Lisp_Object)),
 116                               int, Lisp_Object, Lisp_Object*, int));
 117 \f
 118 /* Keymap object support - constructors and predicates.                 */
 119
 120 DEFUN ("make-keymap", Fmake_keymap, Smake_keymap, 0, 1, 0,
 121   "Construct and return a new keymap, of the form (keymap CHARTABLE . ALIST).\n\
 122 CHARTABLE is a char-table that holds the bindings for the ASCII\n\
 123 characters.  ALIST is an assoc-list which holds bindings for function keys,\n\
 124 mouse events, and any other things that appear in the input stream.\n\
 125 All entries in it are initially nil, meaning \"command undefined\".\n\n\
 126 The optional arg STRING supplies a menu name for the keymap\n\
 127 in case you use it as a menu with `x-popup-menu'.")
 128   (string)
 129      Lisp_Object string;
 130 {
 131   Lisp_Object tail;
 132   if (!NILP (string))
 133     tail = Fcons (string, Qnil);
 134   else
 135     tail = Qnil;
 136   return Fcons (Qkeymap,
 137                 Fcons (Fmake_char_table (Qkeymap, Qnil), tail));
 138 }
 139
 140 DEFUN ("make-sparse-keymap", Fmake_sparse_keymap, Smake_sparse_keymap, 0, 1, 0,
 141   "Construct and return a new sparse keymap.\n\
 142 Its car is `keymap' and its cdr is an alist of (CHAR . DEFINITION),\n\
 143 which binds the character CHAR to DEFINITION, or (SYMBOL . DEFINITION),\n\
 144 which binds the function key or mouse event SYMBOL to DEFINITION.\n\
 145 Initially the alist is nil.\n\n\
 146 The optional arg STRING supplies a menu name for the keymap\n\
 147 in case you use it as a menu with `x-popup-menu'.")
 148   (string)
 149      Lisp_Object string;
 150 {
 151   if (!NILP (string))
 152     return Fcons (Qkeymap, Fcons (string, Qnil));
 153   return Fcons (Qkeymap, Qnil);
 154 }
 155
 156 /* This function is used for installing the standard key bindings
 157    at initialization time.
 158
 159    For example:
 160
 161    initial_define_key (control_x_map, Ctl('X'), "exchange-point-and-mark");  */
 162
 163 void
 164 initial_define_key (keymap, key, defname)
 165      Lisp_Object keymap;
 166      int key;
 167      char *defname;
 168 {
 169   store_in_keymap (keymap, make_number (key), intern (defname));
 170 }
 171
 172 void
 173 initial_define_lispy_key (keymap, keyname, defname)
 174      Lisp_Object keymap;
 175      char *keyname;
 176      char *defname;
 177 {
 178   store_in_keymap (keymap, intern (keyname), intern (defname));
 179 }
 180
 181 DEFUN ("keymapp", Fkeymapp, Skeymapp, 1, 1, 0,
 182   "Return t if OBJECT is a keymap.\n\
 183 \n\
 184 A keymap is a list (keymap . ALIST),\n\
 185 or a symbol whose function definition is itself a keymap.\n\
 186 ALIST elements look like (CHAR . DEFN) or (SYMBOL . DEFN);\n\
 187 a vector of densely packed bindings for small character codes\n\
 188 is also allowed as an element.")
 189   (object)
 190      Lisp_Object object;
 191 {
 192   return (KEYMAPP (object) ? Qt : Qnil);
 193 }
 194
 195 /* Check that OBJECT is a keymap (after dereferencing through any
 196    symbols).  If it is, return it.
 197
 198    If AUTOLOAD is non-zero and OBJECT is a symbol whose function value
 199    is an autoload form, do the autoload and try again.
 200    If AUTOLOAD is nonzero, callers must assume GC is possible.
 201
 202    If the map needs to be autoloaded, but AUTOLOAD is zero (and ERROR
 203    is zero as well), return Qt.
 204
 205    ERROR controls how we respond if OBJECT isn't a keymap.
 206    If ERROR is non-zero, signal an error; otherwise, just return Qnil.
 207
 208    Note that most of the time, we don't want to pursue autoloads.
 209    Functions like Faccessible_keymaps which scan entire keymap trees
 210    shouldn't load every autoloaded keymap.  I'm not sure about this,
 211    but it seems to me that only read_key_sequence, Flookup_key, and
 212    Fdefine_key should cause keymaps to be autoloaded.
 213
 214    This function can GC when AUTOLOAD is non-zero, because it calls
 215    do_autoload which can GC.  */
 216
 217 Lisp_Object
 218 get_keymap (object, error, autoload)
 219      Lisp_Object object;
 220      int error, autoload;
 221 {
 222   Lisp_Object tem;
 223
 224  autoload_retry:
 225   if (NILP (object))
 226     goto end;
 227   if (CONSP (object) && EQ (XCAR (object), Qkeymap))
 228     return object;
 229
 230   tem = indirect_function (object);
 231   if (CONSP (tem))
 232     {
 233       if (EQ (XCAR (tem), Qkeymap))
 234         return tem;
 235
 236       /* Should we do an autoload?  Autoload forms for keymaps have
 237          Qkeymap as their fifth element.  */
 238       if ((autoload || !error) && EQ (XCAR (tem), Qautoload))
 239         {
 240           Lisp_Object tail;
 241
 242           tail = Fnth (make_number (4), tem);
 243           if (EQ (tail, Qkeymap))
 244             {
 245               if (autoload)
 246                 {
 247                   struct gcpro gcpro1, gcpro2;
 248
 249                   GCPRO2 (tem, object);
 250                   do_autoload (tem, object);
 251                   UNGCPRO;
 252
 253                   goto autoload_retry;
 254                 }
 255               else
 256                 return Qt;
 257             }
 258         }
 259     }
 260
 261  end:
 262   if (error)
 263     wrong_type_argument (Qkeymapp, object);
 264   return Qnil;
 265 }
 266 \f
 267 /* Return the parent map of the keymap MAP, or nil if it has none.
 268    We assume that MAP is a valid keymap.  */
 269
 270 DEFUN ("keymap-parent", Fkeymap_parent, Skeymap_parent, 1, 1, 0,
 271   "Return the parent keymap of KEYMAP.")
 272   (keymap)
 273      Lisp_Object keymap;
 274 {
 275   Lisp_Object list;
 276
 277   keymap = get_keymap (keymap, 1, 1);
 278
 279   /* Skip past the initial element `keymap'.  */
 280   list = XCDR (keymap);
 281   for (; CONSP (list); list = XCDR (list))
 282     {
 283       /* See if there is another `keymap'.  */
 284       if (KEYMAPP (list))
 285         return list;
 286     }
 287
 288   return get_keymap (list, 0, 1);
 289 }
 290
 291
 292 /* Check whether MAP is one of MAPS parents.  */
 293 int
 294 keymap_memberp (map, maps)
 295      Lisp_Object map, maps;
 296 {
 297   if (NILP (map)) return 0;
 298   while (KEYMAPP (maps) && !EQ (map, maps))
 299     maps = Fkeymap_parent (maps);
 300   return (EQ (map, maps));
 301 }
 302
 303 /* Set the parent keymap of MAP to PARENT.  */
 304
 305 DEFUN ("set-keymap-parent", Fset_keymap_parent, Sset_keymap_parent, 2, 2, 0,
 306   "Modify KEYMAP to set its parent map to PARENT.\n\
 307 PARENT should be nil or another keymap.")
 308   (keymap, parent)
 309      Lisp_Object keymap, parent;
 310 {
 311   Lisp_Object list, prev;
 312   struct gcpro gcpro1;
 313   int i;
 314
 315   /* Force a keymap flush for the next call to where-is.
 316      Since this can be called from within where-is, we don't set where_is_cache
 317      directly but only where_is_cache_keymaps, since where_is_cache shouldn't
 318      be changed during where-is, while where_is_cache_keymaps is only used at
 319      the very beginning of where-is and can thus be changed here without any
 320      adverse effect.
 321      This is a very minor correctness (rather than safety) issue.  */
 322   where_is_cache_keymaps = Qt;
 323
 324   keymap = get_keymap (keymap, 1, 1);
 325   GCPRO1 (keymap);
 326
 327   if (!NILP (parent))
 328     {
 329       parent = get_keymap (parent, 1, 1);
 330
 331       /* Check for cycles.  */
 332       if (keymap_memberp (keymap, parent))
 333         error ("Cyclic keymap inheritance");
 334     }
 335
 336   /* Skip past the initial element `keymap'.  */
 337   prev = keymap;
 338   while (1)
 339     {
 340       list = XCDR (prev);
 341       /* If there is a parent keymap here, replace it.
 342          If we came to the end, add the parent in PREV.  */
 343       if (! CONSP (list) || KEYMAPP (list))
 344         {
 345           /* If we already have the right parent, return now
 346              so that we avoid the loops below.  */
 347           if (EQ (XCDR (prev), parent))
 348             RETURN_UNGCPRO (parent);
 349
 350           XCDR (prev) = parent;
 351           break;
 352         }
 353       prev = list;
 354     }
 355
 356   /* Scan through for submaps, and set their parents too.  */
 357
 358   for (list = XCDR (keymap); CONSP (list); list = XCDR (list))
 359     {
 360       /* Stop the scan when we come to the parent.  */
 361       if (EQ (XCAR (list), Qkeymap))
 362         break;
 363
 364       /* If this element holds a prefix map, deal with it.  */
 365       if (CONSP (XCAR (list))
 366           && CONSP (XCDR (XCAR (list))))
 367         fix_submap_inheritance (keymap, XCAR (XCAR (list)),
 368                                 XCDR (XCAR (list)));
 369
 370       if (VECTORP (XCAR (list)))
 371         for (i = 0; i < XVECTOR (XCAR (list))->size; i++)
 372           if (CONSP (XVECTOR (XCAR (list))->contents[i]))
 373             fix_submap_inheritance (keymap, make_number (i),
 374                                     XVECTOR (XCAR (list))->contents[i]);
 375
 376       if (CHAR_TABLE_P (XCAR (list)))
 377         {
 378           Lisp_Object indices[3];
 379
 380           map_char_table (fix_submap_inheritance, Qnil, XCAR (list),
 381                           keymap, 0, indices);
 382         }
 383     }
 384
 385   RETURN_UNGCPRO (parent);
 386 }
 387
 388 /* EVENT is defined in MAP as a prefix, and SUBMAP is its definition.
 389    if EVENT is also a prefix in MAP's parent,
 390    make sure that SUBMAP inherits that definition as its own parent.  */
 391
 392 static void
 393 fix_submap_inheritance (map, event, submap)
 394      Lisp_Object map, event, submap;
 395 {
 396   Lisp_Object map_parent, parent_entry;
 397
 398   /* SUBMAP is a cons that we found as a key binding.
 399      Discard the other things found in a menu key binding.  */
 400
 401   submap = get_keymap (get_keyelt (submap, 0), 0, 0);
 402
 403   /* If it isn't a keymap now, there's no work to do.  */
 404   if (!CONSP (submap))
 405     return;
 406
 407   map_parent = Fkeymap_parent (map);
 408   if (!NILP (map_parent))
 409     parent_entry =
 410       get_keymap (access_keymap (map_parent, event, 0, 0, 0), 0, 0);
 411   else
 412     parent_entry = Qnil;
 413
 414   /* If MAP's parent has something other than a keymap,
 415      our own submap shadows it completely.  */
 416   if (!CONSP (parent_entry))
 417     return;
 418
 419   if (! EQ (parent_entry, submap))
 420     {
 421       Lisp_Object submap_parent;
 422       submap_parent = submap;
 423       while (1)
 424         {
 425           Lisp_Object tem;
 426
 427           tem = Fkeymap_parent (submap_parent);
 428
 429           if (KEYMAPP (tem))
 430             {
 431               if (keymap_memberp (tem, parent_entry))
 432                 /* Fset_keymap_parent could create a cycle.  */
 433                 return;
 434               submap_parent = tem;
 435             }
 436           else
 437             break;
 438         }
 439       Fset_keymap_parent (submap_parent, parent_entry);
 440     }
 441 }
 442 \f
 443 /* Look up IDX in MAP.  IDX may be any sort of event.
 444    Note that this does only one level of lookup; IDX must be a single
 445    event, not a sequence.
 446
 447    If T_OK is non-zero, bindings for Qt are treated as default
 448    bindings; any key left unmentioned by other tables and bindings is
 449    given the binding of Qt.
 450
 451    If T_OK is zero, bindings for Qt are not treated specially.
 452
 453    If NOINHERIT, don't accept a subkeymap found in an inherited keymap.  */
 454
 455 Lisp_Object
 456 access_keymap (map, idx, t_ok, noinherit, autoload)
 457      Lisp_Object map;
 458      Lisp_Object idx;
 459      int t_ok;
 460      int noinherit;
 461      int autoload;
 462 {
 463   int noprefix = 0;
 464   Lisp_Object val;
 465
 466   /* If idx is a list (some sort of mouse click, perhaps?),
 467      the index we want to use is the car of the list, which
 468      ought to be a symbol.  */
 469   idx = EVENT_HEAD (idx);
 470
 471   /* If idx is a symbol, it might have modifiers, which need to
 472      be put in the canonical order.  */
 473   if (SYMBOLP (idx))
 474     idx = reorder_modifiers (idx);
 475   else if (INTEGERP (idx))
 476     /* Clobber the high bits that can be present on a machine
 477        with more than 24 bits of integer.  */
 478     XSETFASTINT (idx, XINT (idx) & (CHAR_META | (CHAR_META - 1)));
 479
 480   /* Handle the special meta -> esc mapping. */
 481   if (INTEGERP (idx) && XUINT (idx) & meta_modifier)
 482     {
 483       /* See if there is a meta-map.  If there's none, there is
 484          no binding for IDX, unless a default binding exists in MAP.  */
 485       Lisp_Object meta_map =
 486         get_keymap (access_keymap (map, meta_prefix_char,
 487                                    t_ok, noinherit, autoload),
 488                     0, autoload);
 489       if (CONSP (meta_map))
 490         {
 491           map = meta_map;
 492           idx = make_number (XUINT (idx) & ~meta_modifier);
 493         }
 494       else if (t_ok)
 495         /* Set IDX to t, so that we only find a default binding.  */
 496         idx = Qt;
 497       else
 498         /* We know there is no binding.  */
 499         return Qnil;
 500     }
 501
 502   {
 503     Lisp_Object tail;
 504     Lisp_Object t_binding;
 505
 506     t_binding = Qnil;
 507     for (tail = XCDR (map);
 508          (CONSP (tail)
 509           || (tail = get_keymap (tail, 0, autoload), CONSP (tail)));
 510          tail = XCDR (tail))
 511       {
 512         Lisp_Object binding;
 513
 514         binding = XCAR (tail);
 515         if (SYMBOLP (binding))
 516           {
 517             /* If NOINHERIT, stop finding prefix definitions
 518                after we pass a second occurrence of the `keymap' symbol.  */
 519             if (noinherit && EQ (binding, Qkeymap))
 520               noprefix = 1;
 521           }
 522         else if (CONSP (binding))
 523           {
 524             if (EQ (XCAR (binding), idx))
 525               {
 526                 val = XCDR (binding);
 527                 if (noprefix && KEYMAPP (val))
 528                   return Qnil;
 529                 if (CONSP (val))
 530                   fix_submap_inheritance (map, idx, val);
 531                 return get_keyelt (val, autoload);
 532               }
 533             if (t_ok && EQ (XCAR (binding), Qt))
 534               t_binding = XCDR (binding);
 535           }
 536         else if (VECTORP (binding))
 537           {
 538             if (NATNUMP (idx) && XFASTINT (idx) < XVECTOR (binding)->size)
 539               {
 540                 val = XVECTOR (binding)->contents[XFASTINT (idx)];
 541                 if (noprefix && KEYMAPP (val))
 542                   return Qnil;
 543                 if (CONSP (val))
 544                   fix_submap_inheritance (map, idx, val);
 545                 return get_keyelt (val, autoload);
 546               }
 547           }
 548         else if (CHAR_TABLE_P (binding))
 549           {
 550             /* Character codes with modifiers
 551                are not included in a char-table.
 552                All character codes without modifiers are included.  */
 553             if (NATNUMP (idx)
 554                 && ! (XFASTINT (idx)
 555                       & (CHAR_ALT | CHAR_SUPER | CHAR_HYPER
 556                          | CHAR_SHIFT | CHAR_CTL | CHAR_META)))
 557               {
 558                 val = Faref (binding, idx);
 559                 if (noprefix && KEYMAPP (val))
 560                   return Qnil;
 561                 if (CONSP (val))
 562                   fix_submap_inheritance (map, idx, val);
 563                 return get_keyelt (val, autoload);
 564               }
 565           }
 566
 567         QUIT;
 568       }
 569
 570     return get_keyelt (t_binding, autoload);
 571   }
 572 }
 573
 574 /* Given OBJECT which was found in a slot in a keymap,
 575    trace indirect definitions to get the actual definition of that slot.
 576    An indirect definition is a list of the form
 577    (KEYMAP . INDEX), where KEYMAP is a keymap or a symbol defined as one
 578    and INDEX is the object to look up in KEYMAP to yield the definition.
 579
 580    Also if OBJECT has a menu string as the first element,
 581    remove that.  Also remove a menu help string as second element.
 582
 583    If AUTOLOAD is nonzero, load autoloadable keymaps
 584    that are referred to with indirection.  */
 585
 586 Lisp_Object
 587 get_keyelt (object, autoload)
 588      register Lisp_Object object;
 589      int autoload;
 590 {
 591   while (1)
 592     {
 593       if (!(CONSP (object)))
 594         /* This is really the value.  */
 595         return object;
 596
 597       /* If the keymap contents looks like (keymap ...) or (lambda ...)
 598          then use itself. */
 599       else if (EQ (XCAR (object), Qkeymap) || EQ (XCAR (object), Qlambda))
 600         return object;
 601
 602       /* If the keymap contents looks like (menu-item name . DEFN)
 603          or (menu-item name DEFN ...) then use DEFN.
 604          This is a new format menu item.  */
 605       else if (EQ (XCAR (object), Qmenu_item))
 606         {
 607           if (CONSP (XCDR (object)))
 608             {
 609               Lisp_Object tem;
 610
 611               object = XCDR (XCDR (object));
 612               tem = object;
 613               if (CONSP (object))
 614                 object = XCAR (object);
 615
 616               /* If there's a `:filter FILTER', apply FILTER to the
 617                  menu-item's definition to get the real definition to
 618                  use.  */
 619               for (; CONSP (tem) && CONSP (XCDR (tem)); tem = XCDR (tem))
 620                 if (EQ (XCAR (tem), QCfilter) && autoload)
 621                   {
 622                     Lisp_Object filter;
 623                     filter = XCAR (XCDR (tem));
 624                     filter = list2 (filter, list2 (Qquote, object));
 625                     object = menu_item_eval_property (filter);
 626                     break;
 627                   }
 628             }
 629           else
 630             /* Invalid keymap */
 631             return object;
 632         }
 633
 634       /* If the keymap contents looks like (STRING . DEFN), use DEFN.
 635          Keymap alist elements like (CHAR MENUSTRING . DEFN)
 636          will be used by HierarKey menus.  */
 637       else if (STRINGP (XCAR (object)))
 638         {
 639           object = XCDR (object);
 640           /* Also remove a menu help string, if any,
 641              following the menu item name.  */
 642           if (CONSP (object) && STRINGP (XCAR (object)))
 643             object = XCDR (object);
 644           /* Also remove the sublist that caches key equivalences, if any.  */
 645           if (CONSP (object) && CONSP (XCAR (object)))
 646             {
 647               Lisp_Object carcar;
 648               carcar = XCAR (XCAR (object));
 649               if (NILP (carcar) || VECTORP (carcar))
 650                 object = XCDR (object);
 651             }
 652         }
 653
 654       /* If the contents are (KEYMAP . ELEMENT), go indirect.  */
 655       else
 656         {
 657           Lisp_Object map;
 658           map = get_keymap (Fcar_safe (object), 0, autoload);
 659           return (!CONSP (map) ? object /* Invalid keymap */
 660                   : access_keymap (map, Fcdr (object), 0, 0, autoload));
 661         }
 662     }
 663 }
 664
 665 static Lisp_Object
 666 store_in_keymap (keymap, idx, def)
 667      Lisp_Object keymap;
 668      register Lisp_Object idx;
 669      register Lisp_Object def;
 670 {
 671   /* Flush any reverse-map cache.  */
 672   where_is_cache = Qnil;
 673   where_is_cache_keymaps = Qt;
 674
 675   /* If we are preparing to dump, and DEF is a menu element
 676      with a menu item indicator, copy it to ensure it is not pure.  */
 677   if (CONSP (def) && PURE_P (def)
 678       && (EQ (XCAR (def), Qmenu_item) || STRINGP (XCAR (def))))
 679     def = Fcons (XCAR (def), XCDR (def));
 680
 681   if (!CONSP (keymap) || ! EQ (XCAR (keymap), Qkeymap))
 682     error ("attempt to define a key in a non-keymap");
 683
 684   /* If idx is a list (some sort of mouse click, perhaps?),
 685      the index we want to use is the car of the list, which
 686      ought to be a symbol.  */
 687   idx = EVENT_HEAD (idx);
 688
 689   /* If idx is a symbol, it might have modifiers, which need to
 690      be put in the canonical order.  */
 691   if (SYMBOLP (idx))
 692     idx = reorder_modifiers (idx);
 693   else if (INTEGERP (idx))
 694     /* Clobber the high bits that can be present on a machine
 695        with more than 24 bits of integer.  */
 696     XSETFASTINT (idx, XINT (idx) & (CHAR_META | (CHAR_META - 1)));
 697
 698   /* Scan the keymap for a binding of idx.  */
 699   {
 700     Lisp_Object tail;
 701
 702     /* The cons after which we should insert new bindings.  If the
 703        keymap has a table element, we record its position here, so new
 704        bindings will go after it; this way, the table will stay
 705        towards the front of the alist and character lookups in dense
 706        keymaps will remain fast.  Otherwise, this just points at the
 707        front of the keymap.  */
 708     Lisp_Object insertion_point;
 709
 710     insertion_point = keymap;
 711     for (tail = XCDR (keymap); CONSP (tail); tail = XCDR (tail))
 712       {
 713         Lisp_Object elt;
 714
 715         elt = XCAR (tail);
 716         if (VECTORP (elt))
 717           {
 718             if (NATNUMP (idx) && XFASTINT (idx) < ASIZE (elt))
 719               {
 720                 ASET (elt, XFASTINT (idx), def);
 721                 return def;
 722               }
 723             insertion_point = tail;
 724           }
 725         else if (CHAR_TABLE_P (elt))
 726           {
 727             /* Character codes with modifiers
 728                are not included in a char-table.
 729                All character codes without modifiers are included.  */
 730             if (NATNUMP (idx)
 731                 && ! (XFASTINT (idx)
 732                       & (CHAR_ALT | CHAR_SUPER | CHAR_HYPER
 733                          | CHAR_SHIFT | CHAR_CTL | CHAR_META)))
 734               {
 735                 Faset (elt, idx, def);
 736                 return def;
 737               }
 738             insertion_point = tail;
 739           }
 740         else if (CONSP (elt))
 741           {
 742             if (EQ (idx, XCAR (elt)))
 743               {
 744                 XCDR (elt) = def;
 745                 return def;
 746               }
 747           }
 748         else if (EQ (elt, Qkeymap))
 749           /* If we find a 'keymap' symbol in the spine of KEYMAP,
 750              then we must have found the start of a second keymap
 751              being used as the tail of KEYMAP, and a binding for IDX
 752              should be inserted before it.  */
 753           goto keymap_end;
 754
 755         QUIT;
 756       }
 757
 758   keymap_end:
 759     /* We have scanned the entire keymap, and not found a binding for
 760        IDX.  Let's add one.  */
 761     XCDR (insertion_point)
 762       = Fcons (Fcons (idx, def), XCDR (insertion_point));
 763   }
 764
 765   return def;
 766 }
 767
 768 void
 769 copy_keymap_1 (chartable, idx, elt)
 770      Lisp_Object chartable, idx, elt;
 771 {
 772   if (CONSP (elt) && EQ (XCAR (elt), Qkeymap))
 773     Faset (chartable, idx, Fcopy_keymap (elt));
 774 }
 775
 776 DEFUN ("copy-keymap", Fcopy_keymap, Scopy_keymap, 1, 1, 0,
 777   "Return a copy of the keymap KEYMAP.\n\
 778 The copy starts out with the same definitions of KEYMAP,\n\
 779 but changing either the copy or KEYMAP does not affect the other.\n\
 780 Any key definitions that are subkeymaps are recursively copied.\n\
 781 However, a key definition which is a symbol whose definition is a keymap\n\
 782 is not copied.")
 783   (keymap)
 784      Lisp_Object keymap;
 785 {
 786   register Lisp_Object copy, tail;
 787
 788   copy = Fcopy_alist (get_keymap (keymap, 1, 0));
 789
 790   for (tail = copy; CONSP (tail); tail = XCDR (tail))
 791     {
 792       Lisp_Object elt;
 793
 794       elt = XCAR (tail);
 795       if (CHAR_TABLE_P (elt))
 796         {
 797           Lisp_Object indices[3];
 798
 799           elt = Fcopy_sequence (elt);
 800           XCAR (tail) = elt;
 801
 802           map_char_table (copy_keymap_1, Qnil, elt, elt, 0, indices);
 803         }
 804       else if (VECTORP (elt))
 805         {
 806           int i;
 807
 808           elt = Fcopy_sequence (elt);
 809           XCAR (tail) = elt;
 810
 811           for (i = 0; i < ASIZE (elt); i++)
 812             if (CONSP (AREF (elt, i)) && EQ (XCAR (AREF (elt, i)), Qkeymap))
 813               ASET (elt, i, Fcopy_keymap (AREF (elt, i)));
 814         }
 815       else if (CONSP (elt) && CONSP (XCDR (elt)))
 816         {
 817           Lisp_Object tem;
 818           tem = XCDR (elt);
 819
 820           /* Is this a new format menu item.  */
 821           if (EQ (XCAR (tem),Qmenu_item))
 822             {
 823               /* Copy cell with menu-item marker.  */
 824               XCDR (elt)
 825                 = Fcons (XCAR (tem), XCDR (tem));
 826               elt = XCDR (elt);
 827               tem = XCDR (elt);
 828               if (CONSP (tem))
 829                 {
 830                   /* Copy cell with menu-item name.  */
 831                   XCDR (elt)
 832                     = Fcons (XCAR (tem), XCDR (tem));
 833                   elt = XCDR (elt);
 834                   tem = XCDR (elt);
 835                 };
 836               if (CONSP (tem))
 837                 {
 838                   /* Copy cell with binding and if the binding is a keymap,
 839                      copy that.  */
 840                   XCDR (elt)
 841                     = Fcons (XCAR (tem), XCDR (tem));
 842                   elt = XCDR (elt);
 843                   tem = XCAR (elt);
 844                   if (CONSP (tem) && EQ (XCAR (tem), Qkeymap))
 845                     XCAR (elt) = Fcopy_keymap (tem);
 846                   tem = XCDR (elt);
 847                   if (CONSP (tem) && CONSP (XCAR (tem)))
 848                     /* Delete cache for key equivalences.  */
 849                     XCDR (elt) = XCDR (tem);
 850                 }
 851             }
 852           else
 853             {
 854               /* It may be an old fomat menu item.
 855                  Skip the optional menu string.
 856               */
 857               if (STRINGP (XCAR (tem)))
 858                 {
 859                   /* Copy the cell, since copy-alist didn't go this deep.  */
 860                   XCDR (elt)
 861                     = Fcons (XCAR (tem), XCDR (tem));
 862                   elt = XCDR (elt);
 863                   tem = XCDR (elt);
 864                   /* Also skip the optional menu help string.  */
 865                   if (CONSP (tem) && STRINGP (XCAR (tem)))
 866                     {
 867                       XCDR (elt)
 868                         = Fcons (XCAR (tem), XCDR (tem));
 869                       elt = XCDR (elt);
 870                       tem = XCDR (elt);
 871                     }
 872                   /* There may also be a list that caches key equivalences.
 873                      Just delete it for the new keymap.  */
 874                   if (CONSP (tem)
 875                       && CONSP (XCAR (tem))
 876                       && (NILP (XCAR (XCAR (tem)))
 877                           || VECTORP (XCAR (XCAR (tem)))))
 878                     XCDR (elt) = XCDR (tem);
 879                 }
 880               if (CONSP (elt)
 881                   && CONSP (XCDR (elt))
 882                   && EQ (XCAR (XCDR (elt)), Qkeymap))
 883                 XCDR (elt) = Fcopy_keymap (XCDR (elt));
 884             }
 885
 886         }
 887     }
 888
 889   return copy;
 890 }
 891 \f
 892 /* Simple Keymap mutators and accessors.                                */
 893
 894 /* GC is possible in this function if it autoloads a keymap.  */
 895
 896 DEFUN ("define-key", Fdefine_key, Sdefine_key, 3, 3, 0,
 897   "Args KEYMAP, KEY, DEF.  Define key sequence KEY, in KEYMAP, as DEF.\n\
 898 KEYMAP is a keymap.  KEY is a string or a vector of symbols and characters\n\
 899 meaning a sequence of keystrokes and events.\n\
 900 Non-ASCII characters with codes above 127 (such as ISO Latin-1)\n\
 901 can be included if you use a vector.\n\
 902 DEF is anything that can be a key's definition:\n\
 903  nil (means key is undefined in this keymap),\n\
 904  a command (a Lisp function suitable for interactive calling)\n\
 905  a string (treated as a keyboard macro),\n\
 906  a keymap (to define a prefix key),\n\
 907  a symbol.  When the key is looked up, the symbol will stand for its\n\
 908     function definition, which should at that time be one of the above,\n\
 909     or another symbol whose function definition is used, etc.\n\
 910  a cons (STRING . DEFN), meaning that DEFN is the definition\n\
 911     (DEFN should be a valid definition in its own right),\n\
 912  or a cons (KEYMAP . CHAR), meaning use definition of CHAR in map KEYMAP.\n\
 913 \n\
 914 If KEYMAP is a sparse keymap, the pair binding KEY to DEF is added at\n\
 915 the front of KEYMAP.")
 916   (keymap, key, def)
 917      Lisp_Object keymap;
 918      Lisp_Object key;
 919      Lisp_Object def;
 920 {
 921   register int idx;
 922   register Lisp_Object c;
 923   register Lisp_Object cmd;
 924   int metized = 0;
 925   int meta_bit;
 926   int length;
 927   struct gcpro gcpro1, gcpro2, gcpro3;
 928
 929   keymap = get_keymap (keymap, 1, 1);
 930
 931   if (!VECTORP (key) && !STRINGP (key))
 932     key = wrong_type_argument (Qarrayp, key);
 933
 934   length = XFASTINT (Flength (key));
 935   if (length == 0)
 936     return Qnil;
 937
 938   if (SYMBOLP (def) && !EQ (Vdefine_key_rebound_commands, Qt))
 939     Vdefine_key_rebound_commands = Fcons (def, Vdefine_key_rebound_commands);
 940
 941   GCPRO3 (keymap, key, def);
 942
 943   if (VECTORP (key))
 944     meta_bit = meta_modifier;
 945   else
 946     meta_bit = 0x80;
 947
 948   idx = 0;
 949   while (1)
 950     {
 951       c = Faref (key, make_number (idx));
 952
 953       if (CONSP (c) && lucid_event_type_list_p (c))
 954         c = Fevent_convert_list (c);
 955
 956       if (INTEGERP (c)
 957           && (XINT (c) & meta_bit)
 958           && !metized)
 959         {
 960           c = meta_prefix_char;
 961           metized = 1;
 962         }
 963       else
 964         {
 965           if (INTEGERP (c))
 966             XSETINT (c, XINT (c) & ~meta_bit);
 967
 968           metized = 0;
 969           idx++;
 970         }
 971
 972       if (! INTEGERP (c) && ! SYMBOLP (c) && ! CONSP (c))
 973         error ("Key sequence contains invalid events");
 974
 975       if (idx == length)
 976         RETURN_UNGCPRO (store_in_keymap (keymap, c, def));
 977
 978       cmd = access_keymap (keymap, c, 0, 1, 1);
 979
 980       /* If this key is undefined, make it a prefix.  */
 981       if (NILP (cmd))
 982         cmd = define_as_prefix (keymap, c);
 983
 984       keymap = get_keymap (cmd, 0, 1);
 985       if (!CONSP (keymap))
 986         /* We must use Fkey_description rather than just passing key to
 987            error; key might be a vector, not a string.  */
 988         error ("Key sequence %s uses invalid prefix characters",
 989                XSTRING (Fkey_description (key))->data);
 990     }
 991 }
 992
 993 /* Value is number if KEY is too long; NIL if valid but has no definition. */
 994 /* GC is possible in this function if it autoloads a keymap.  */
 995
 996 DEFUN ("lookup-key", Flookup_key, Slookup_key, 2, 3, 0,
 997   "In keymap KEYMAP, look up key sequence KEY.  Return the definition.\n\
 998 nil means undefined.  See doc of `define-key' for kinds of definitions.\n\
 999 \n\
1000 A number as value means KEY is \"too long\";\n\
1001 that is, characters or symbols in it except for the last one\n\
1002 fail to be a valid sequence of prefix characters in KEYMAP.\n\
1003 The number is how many characters at the front of KEY\n\
1004 it takes to reach a non-prefix command.\n\
1005 \n\
1006 Normally, `lookup-key' ignores bindings for t, which act as default\n\
1007 bindings, used when nothing else in the keymap applies; this makes it\n\
1008 usable as a general function for probing keymaps.  However, if the\n\
1009 third optional argument ACCEPT-DEFAULT is non-nil, `lookup-key' will\n\
1010 recognize the default bindings, just as `read-key-sequence' does.")
1011   (keymap, key, accept_default)
1012      register Lisp_Object keymap;
1013      Lisp_Object key;
1014      Lisp_Object accept_default;
1015 {
1016   register int idx;
1017   register Lisp_Object cmd;
1018   register Lisp_Object c;
1019   int length;
1020   int t_ok = ! NILP (accept_default);
1021   struct gcpro gcpro1;
1022
1023   keymap = get_keymap (keymap, 1, 1);
1024
1025   if (!VECTORP (key) && !STRINGP (key))
1026     key = wrong_type_argument (Qarrayp, key);
1027
1028   length = XFASTINT (Flength (key));
1029   if (length == 0)
1030     return keymap;
1031
1032   GCPRO1 (key);
1033
1034   idx = 0;
1035   while (1)
1036     {
1037       c = Faref (key, make_number (idx++));
1038
1039       if (CONSP (c) && lucid_event_type_list_p (c))
1040         c = Fevent_convert_list (c);
1041
1042       /* Turn the 8th bit of string chars into a meta modifier.  */
1043       if (XINT (c) & 0x80 && STRINGP (key))
1044         XSETINT (c, (XINT (c) | meta_modifier) & ~0x80);
1045
1046       cmd = access_keymap (keymap, c, t_ok, 0, 1);
1047       if (idx == length)
1048         RETURN_UNGCPRO (cmd);
1049
1050       keymap = get_keymap (cmd, 0, 1);
1051       if (!CONSP (keymap))
1052         RETURN_UNGCPRO (make_number (idx));
1053
1054       QUIT;
1055     }
1056 }
1057
1058 /* Make KEYMAP define event C as a keymap (i.e., as a prefix).
1059    Assume that currently it does not define C at all.
1060    Return the keymap.  */
1061
1062 static Lisp_Object
1063 define_as_prefix (keymap, c)
1064      Lisp_Object keymap, c;
1065 {
1066   Lisp_Object cmd;
1067
1068   cmd = Fmake_sparse_keymap (Qnil);
1069   /* If this key is defined as a prefix in an inherited keymap,
1070      make it a prefix in this map, and make its definition
1071      inherit the other prefix definition.  */
1072   cmd = nconc2 (cmd, access_keymap (keymap, c, 0, 0, 0));
1073   store_in_keymap (keymap, c, cmd);
1074
1075   return cmd;
1076 }
1077
1078 /* Append a key to the end of a key sequence.  We always make a vector.  */
1079
1080 Lisp_Object
1081 append_key (key_sequence, key)
1082      Lisp_Object key_sequence, key;
1083 {
1084   Lisp_Object args[2];
1085
1086   args[0] = key_sequence;
1087
1088   args[1] = Fcons (key, Qnil);
1089   return Fvconcat (2, args);
1090 }
1091
1092 \f
1093 /* Global, local, and minor mode keymap stuff.                          */
1094
1095 /* We can't put these variables inside current_minor_maps, since under
1096    some systems, static gets macro-defined to be the empty string.
1097    Ickypoo.  */
1098 static Lisp_Object *cmm_modes, *cmm_maps;
1099 static int cmm_size;
1100
1101 /* Error handler used in current_minor_maps.  */
1102 static Lisp_Object
1103 current_minor_maps_error ()
1104 {
1105   return Qnil;
1106 }
1107
1108 /* Store a pointer to an array of the keymaps of the currently active
1109    minor modes in *buf, and return the number of maps it contains.
1110
1111    This function always returns a pointer to the same buffer, and may
1112    free or reallocate it, so if you want to keep it for a long time or
1113    hand it out to lisp code, copy it.  This procedure will be called
1114    for every key sequence read, so the nice lispy approach (return a
1115    new assoclist, list, what have you) for each invocation would
1116    result in a lot of consing over time.
1117
1118    If we used xrealloc/xmalloc and ran out of memory, they would throw
1119    back to the command loop, which would try to read a key sequence,
1120    which would call this function again, resulting in an infinite
1121    loop.  Instead, we'll use realloc/malloc and silently truncate the
1122    list, let the key sequence be read, and hope some other piece of
1123    code signals the error.  */
1124 int
1125 current_minor_maps (modeptr, mapptr)
1126      Lisp_Object **modeptr, **mapptr;
1127 {
1128   int i = 0;
1129   int list_number = 0;
1130   Lisp_Object alist, assoc, var, val;
1131   Lisp_Object lists[2];
1132
1133   lists[0] = Vminor_mode_overriding_map_alist;
1134   lists[1] = Vminor_mode_map_alist;
1135
1136   for (list_number = 0; list_number < 2; list_number++)
1137     for (alist = lists[list_number];
1138          CONSP (alist);
1139          alist = XCDR (alist))
1140       if ((assoc = XCAR (alist), CONSP (assoc))
1141           && (var = XCAR (assoc), SYMBOLP (var))
1142           && (val = find_symbol_value (var), ! EQ (val, Qunbound))
1143           && ! NILP (val))
1144         {
1145           Lisp_Object temp;
1146
1147           /* If a variable has an entry in Vminor_mode_overriding_map_alist,
1148              and also an entry in Vminor_mode_map_alist,
1149              ignore the latter.  */
1150           if (list_number == 1)
1151             {
1152               val = assq_no_quit (var, lists[0]);
1153               if (!NILP (val))
1154                 break;
1155             }
1156
1157           if (i >= cmm_size)
1158             {
1159               Lisp_Object *newmodes, *newmaps;
1160
1161               /* Use malloc/realloc here.  See the comment above
1162                  this function.  */
1163               if (cmm_maps)
1164                 {
1165                   BLOCK_INPUT;
1166                   cmm_size *= 2;
1167                   newmodes
1168                     = (Lisp_Object *) realloc (cmm_modes,
1169                                                 cmm_size * sizeof *newmodes);
1170                   newmaps
1171                     = (Lisp_Object *) realloc (cmm_maps,
1172                                                 cmm_size * sizeof *newmaps);
1173                   UNBLOCK_INPUT;
1174                 }
1175               else
1176                 {
1177                   BLOCK_INPUT;
1178                   cmm_size = 30;
1179                   newmodes
1180                     = (Lisp_Object *) malloc (cmm_size * sizeof *newmodes);
1181                   newmaps
1182                     = (Lisp_Object *) malloc (cmm_size * sizeof *newmaps);
1183                   UNBLOCK_INPUT;
1184                 }
1185
1186               if (newmodes)
1187                 cmm_modes = newmodes;
1188               if (newmaps)
1189                 cmm_maps = newmaps;
1190
1191               if (newmodes == NULL || newmaps == NULL)
1192                 break;
1193             }
1194
1195           /* Get the keymap definition--or nil if it is not defined.  */
1196           temp = internal_condition_case_1 (Findirect_function,
1197                                             XCDR (assoc),
1198                                             Qerror, current_minor_maps_error);
1199           if (!NILP (temp))
1200             {
1201               cmm_modes[i] = var;
1202               cmm_maps [i] = temp;
1203               i++;
1204             }
1205         }
1206
1207   if (modeptr) *modeptr = cmm_modes;
1208   if (mapptr)  *mapptr  = cmm_maps;
1209   return i;
1210 }
1211
1212 /* GC is possible in this function if it autoloads a keymap.  */
1213
1214 DEFUN ("key-binding", Fkey_binding, Skey_binding, 1, 2, 0,
1215   "Return the binding for command KEY in current keymaps.\n\
1216 KEY is a string or vector, a sequence of keystrokes.\n\
1217 The binding is probably a symbol with a function definition.\n\
1218 \n\
1219 Normally, `key-binding' ignores bindings for t, which act as default\n\
1220 bindings, used when nothing else in the keymap applies; this makes it\n\
1221 usable as a general function for probing keymaps.  However, if the\n\
1222 optional second argument ACCEPT-DEFAULT is non-nil, `key-binding' does\n\
1223 recognize the default bindings, just as `read-key-sequence' does.")
1224   (key, accept_default)
1225      Lisp_Object key, accept_default;
1226 {
1227   Lisp_Object *maps, value;
1228   int nmaps, i;
1229   struct gcpro gcpro1;
1230
1231   GCPRO1 (key);
1232
1233   if (!NILP (current_kboard->Voverriding_terminal_local_map))
1234     {
1235       value = Flookup_key (current_kboard->Voverriding_terminal_local_map,
1236                            key, accept_default);
1237       if (! NILP (value) && !INTEGERP (value))
1238         RETURN_UNGCPRO (value);
1239     }
1240   else if (!NILP (Voverriding_local_map))
1241     {
1242       value = Flookup_key (Voverriding_local_map, key, accept_default);
1243       if (! NILP (value) && !INTEGERP (value))
1244         RETURN_UNGCPRO (value);
1245     }
1246   else
1247     {
1248       Lisp_Object local;
1249
1250       nmaps = current_minor_maps (0, &maps);
1251       /* Note that all these maps are GCPRO'd
1252          in the places where we found them.  */
1253
1254       for (i = 0; i < nmaps; i++)
1255         if (! NILP (maps[i]))
1256           {
1257             value = Flookup_key (maps[i], key, accept_default);
1258             if (! NILP (value) && !INTEGERP (value))
1259               RETURN_UNGCPRO (value);
1260           }
1261
1262       local = get_local_map (PT, current_buffer, Qkeymap);
1263       if (! NILP (local))
1264         {
1265           value = Flookup_key (local, key, accept_default);
1266           if (! NILP (value) && !INTEGERP (value))
1267             RETURN_UNGCPRO (value);
1268         }
1269
1270       local = get_local_map (PT, current_buffer, Qlocal_map);
1271
1272       if (! NILP (local))
1273         {
1274           value = Flookup_key (local, key, accept_default);
1275           if (! NILP (value) && !INTEGERP (value))
1276             RETURN_UNGCPRO (value);
1277         }
1278     }
1279
1280   value = Flookup_key (current_global_map, key, accept_default);
1281   UNGCPRO;
1282   if (! NILP (value) && !INTEGERP (value))
1283     return value;
1284
1285   return Qnil;
1286 }
1287
1288 /* GC is possible in this function if it autoloads a keymap.  */
1289
1290 DEFUN ("local-key-binding", Flocal_key_binding, Slocal_key_binding, 1, 2, 0,
1291   "Return the binding for command KEYS in current local keymap only.\n\
1292 KEYS is a string, a sequence of keystrokes.\n\
1293 The binding is probably a symbol with a function definition.\n\
1294 \n\
1295 If optional argument ACCEPT-DEFAULT is non-nil, recognize default\n\
1296 bindings; see the description of `lookup-key' for more details about this.")
1297   (keys, accept_default)
1298      Lisp_Object keys, accept_default;
1299 {
1300   register Lisp_Object map;
1301   map = current_buffer->keymap;
1302   if (NILP (map))
1303     return Qnil;
1304   return Flookup_key (map, keys, accept_default);
1305 }
1306
1307 /* GC is possible in this function if it autoloads a keymap.  */
1308
1309 DEFUN ("global-key-binding", Fglobal_key_binding, Sglobal_key_binding, 1, 2, 0,
1310   "Return the binding for command KEYS in current global keymap only.\n\
1311 KEYS is a string, a sequence of keystrokes.\n\
1312 The binding is probably a symbol with a function definition.\n\
1313 This function's return values are the same as those of lookup-key\n\
1314 \(which see).\n\
1315 \n\
1316 If optional argument ACCEPT-DEFAULT is non-nil, recognize default\n\
1317 bindings; see the description of `lookup-key' for more details about this.")
1318   (keys, accept_default)
1319      Lisp_Object keys, accept_default;
1320 {
1321   return Flookup_key (current_global_map, keys, accept_default);
1322 }
1323
1324 /* GC is possible in this function if it autoloads a keymap.  */
1325
1326 DEFUN ("minor-mode-key-binding", Fminor_mode_key_binding, Sminor_mode_key_binding, 1, 2, 0,
1327   "Find the visible minor mode bindings of KEY.\n\
1328 Return an alist of pairs (MODENAME . BINDING), where MODENAME is the\n\
1329 the symbol which names the minor mode binding KEY, and BINDING is\n\
1330 KEY's definition in that mode.  In particular, if KEY has no\n\
1331 minor-mode bindings, return nil.  If the first binding is a\n\
1332 non-prefix, all subsequent bindings will be omitted, since they would\n\
1333 be ignored.  Similarly, the list doesn't include non-prefix bindings\n\
1334 that come after prefix bindings.\n\
1335 \n\
1336 If optional argument ACCEPT-DEFAULT is non-nil, recognize default\n\
1337 bindings; see the description of `lookup-key' for more details about this.")
1338   (key, accept_default)
1339      Lisp_Object key, accept_default;
1340 {
1341   Lisp_Object *modes, *maps;
1342   int nmaps;
1343   Lisp_Object binding;
1344   int i, j;
1345   struct gcpro gcpro1, gcpro2;
1346
1347   nmaps = current_minor_maps (&modes, &maps);
1348   /* Note that all these maps are GCPRO'd
1349      in the places where we found them.  */
1350
1351   binding = Qnil;
1352   GCPRO2 (key, binding);
1353
1354   for (i = j = 0; i < nmaps; i++)
1355     if (!NILP (maps[i])
1356         && !NILP (binding = Flookup_key (maps[i], key, accept_default))
1357         && !INTEGERP (binding))
1358       {
1359         if (KEYMAPP (binding))
1360           maps[j++] = Fcons (modes[i], binding);
1361         else if (j == 0)
1362           RETURN_UNGCPRO (Fcons (Fcons (modes[i], binding), Qnil));
1363       }
1364
1365   UNGCPRO;
1366   return Flist (j, maps);
1367 }
1368
1369 DEFUN ("define-prefix-command", Fdefine_prefix_command, Sdefine_prefix_command, 1, 3, 0,
1370   "Define COMMAND as a prefix command.  COMMAND should be a symbol.\n\
1371 A new sparse keymap is stored as COMMAND's function definition and its value.\n\
1372 If a second optional argument MAPVAR is given, the map is stored as\n\
1373 its value instead of as COMMAND's value; but COMMAND is still defined\n\
1374 as a function.\n\
1375 The third optional argument NAME, if given, supplies a menu name\n\
1376 string for the map.  This is required to use the keymap as a menu.")
1377   (command, mapvar, name)
1378      Lisp_Object command, mapvar, name;
1379 {
1380   Lisp_Object map;
1381   map = Fmake_sparse_keymap (name);
1382   Ffset (command, map);
1383   if (!NILP (mapvar))
1384     Fset (mapvar, map);
1385   else
1386     Fset (command, map);
1387   return command;
1388 }
1389
1390 DEFUN ("use-global-map", Fuse_global_map, Suse_global_map, 1, 1, 0,
1391   "Select KEYMAP as the global keymap.")
1392   (keymap)
1393      Lisp_Object keymap;
1394 {
1395   keymap = get_keymap (keymap, 1, 1);
1396   current_global_map = keymap;
1397
1398   return Qnil;
1399 }
1400
1401 DEFUN ("use-local-map", Fuse_local_map, Suse_local_map, 1, 1, 0,
1402   "Select KEYMAP as the local keymap.\n\
1403 If KEYMAP is nil, that means no local keymap.")
1404   (keymap)
1405      Lisp_Object keymap;
1406 {
1407   if (!NILP (keymap))
1408     keymap = get_keymap (keymap, 1, 1);
1409
1410   current_buffer->keymap = keymap;
1411
1412   return Qnil;
1413 }
1414
1415 DEFUN ("current-local-map", Fcurrent_local_map, Scurrent_local_map, 0, 0, 0,
1416   "Return current buffer's local keymap, or nil if it has none.")
1417   ()
1418 {
1419   return current_buffer->keymap;
1420 }
1421
1422 DEFUN ("current-global-map", Fcurrent_global_map, Scurrent_global_map, 0, 0, 0,
1423   "Return the current global keymap.")
1424   ()
1425 {
1426   return current_global_map;
1427 }
1428
1429 DEFUN ("current-minor-mode-maps", Fcurrent_minor_mode_maps, Scurrent_minor_mode_maps, 0, 0, 0,
1430   "Return a list of keymaps for the minor modes of the current buffer.")
1431   ()
1432 {
1433   Lisp_Object *maps;
1434   int nmaps = current_minor_maps (0, &maps);
1435
1436   return Flist (nmaps, maps);
1437 }
1438 \f
1439 /* Help functions for describing and documenting keymaps.               */
1440
1441 static void accessible_keymaps_char_table P_ ((Lisp_Object, Lisp_Object, Lisp_Object));
1442
1443 /* This function cannot GC.  */
1444
1445 DEFUN ("accessible-keymaps", Faccessible_keymaps, Saccessible_keymaps,
1446   1, 2, 0,
1447   "Find all keymaps accessible via prefix characters from KEYMAP.\n\
1448 Returns a list of elements of the form (KEYS . MAP), where the sequence\n\
1449 KEYS starting from KEYMAP gets you to MAP.  These elements are ordered\n\
1450 so that the KEYS increase in length.  The first element is ([] . KEYMAP).\n\
1451 An optional argument PREFIX, if non-nil, should be a key sequence;\n\
1452 then the value includes only maps for prefixes that start with PREFIX.")
1453   (keymap, prefix)
1454      Lisp_Object keymap, prefix;
1455 {
1456   Lisp_Object maps, good_maps, tail;
1457   int prefixlen = 0;
1458
1459   /* no need for gcpro because we don't autoload any keymaps.  */
1460
1461   if (!NILP (prefix))
1462     prefixlen = XINT (Flength (prefix));
1463
1464   if (!NILP (prefix))
1465     {
1466       /* If a prefix was specified, start with the keymap (if any) for
1467          that prefix, so we don't waste time considering other prefixes.  */
1468       Lisp_Object tem;
1469       tem = Flookup_key (keymap, prefix, Qt);
1470       /* Flookup_key may give us nil, or a number,
1471          if the prefix is not defined in this particular map.
1472          It might even give us a list that isn't a keymap.  */
1473       tem = get_keymap (tem, 0, 0);
1474       if (CONSP (tem))
1475         {
1476           /* Convert PREFIX to a vector now, so that later on
1477              we don't have to deal with the possibility of a string.  */
1478           if (STRINGP (prefix))
1479             {
1480               int i, i_byte, c;
1481               Lisp_Object copy;
1482
1483               copy = Fmake_vector (make_number (XSTRING (prefix)->size), Qnil);
1484               for (i = 0, i_byte = 0; i < XSTRING (prefix)->size;)
1485                 {
1486                   int i_before = i;
1487
1488                   FETCH_STRING_CHAR_ADVANCE (c, prefix, i, i_byte);
1489                   if (SINGLE_BYTE_CHAR_P (c) && (c & 0200))
1490                     c ^= 0200 | meta_modifier;
1491                   ASET (copy, i_before, make_number (c));
1492                 }
1493               prefix = copy;
1494             }
1495           maps = Fcons (Fcons (prefix, tem), Qnil);
1496         }
1497       else
1498         return Qnil;
1499     }
1500   else
1501     maps = Fcons (Fcons (Fmake_vector (make_number (0), Qnil),
1502                          get_keymap (keymap, 1, 0)),
1503                   Qnil);
1504
1505   /* For each map in the list maps,
1506      look at any other maps it points to,
1507      and stick them at the end if they are not already in the list.
1508
1509      This is a breadth-first traversal, where tail is the queue of
1510      nodes, and maps accumulates a list of all nodes visited.  */
1511
1512   for (tail = maps; CONSP (tail); tail = XCDR (tail))
1513     {
1514       register Lisp_Object thisseq, thismap;
1515       Lisp_Object last;
1516       /* Does the current sequence end in the meta-prefix-char?  */
1517       int is_metized;
1518
1519       thisseq = Fcar (Fcar (tail));
1520       thismap = Fcdr (Fcar (tail));
1521       last = make_number (XINT (Flength (thisseq)) - 1);
1522       is_metized = (XINT (last) >= 0
1523                     /* Don't metize the last char of PREFIX.  */
1524                     && XINT (last) >= prefixlen
1525                     && EQ (Faref (thisseq, last), meta_prefix_char));
1526
1527       for (; CONSP (thismap); thismap = XCDR (thismap))
1528         {
1529           Lisp_Object elt;
1530
1531           elt = XCAR (thismap);
1532
1533           QUIT;
1534
1535           if (CHAR_TABLE_P (elt))
1536             {
1537               Lisp_Object indices[3];
1538
1539               map_char_table (accessible_keymaps_char_table, Qnil,
1540                               elt, Fcons (Fcons (maps, make_number (is_metized)),
1541                                           Fcons (tail, thisseq)),
1542                               0, indices);
1543             }
1544           else if (VECTORP (elt))
1545             {
1546               register int i;
1547
1548               /* Vector keymap.  Scan all the elements.  */
1549               for (i = 0; i < ASIZE (elt); i++)
1550                 {
1551                   register Lisp_Object tem;
1552                   register Lisp_Object cmd;
1553
1554                   cmd = get_keyelt (AREF (elt, i), 0);
1555                   if (NILP (cmd)) continue;
1556                   tem = get_keymap (cmd, 0, 0);
1557                   if (CONSP (tem))
1558                     {
1559                       cmd = tem;
1560                       /* Ignore keymaps that are already added to maps.  */
1561                       tem = Frassq (cmd, maps);
1562                       if (NILP (tem))
1563                         {
1564                           /* If the last key in thisseq is meta-prefix-char,
1565                              turn it into a meta-ized keystroke.  We know
1566                              that the event we're about to append is an
1567                              ascii keystroke since we're processing a
1568                              keymap table.  */
1569                           if (is_metized)
1570                             {
1571                               int meta_bit = meta_modifier;
1572                               tem = Fcopy_sequence (thisseq);
1573
1574                               Faset (tem, last, make_number (i | meta_bit));
1575
1576                               /* This new sequence is the same length as
1577                                  thisseq, so stick it in the list right
1578                                  after this one.  */
1579                               XCDR (tail)
1580                                 = Fcons (Fcons (tem, cmd), XCDR (tail));
1581                             }
1582                           else
1583                             {
1584                               tem = append_key (thisseq, make_number (i));
1585                               nconc2 (tail, Fcons (Fcons (tem, cmd), Qnil));
1586                             }
1587                         }
1588                     }
1589                 }
1590             }
1591           else if (CONSP (elt))
1592             {
1593               register Lisp_Object cmd, tem;
1594
1595               cmd = get_keyelt (XCDR (elt), 0);
1596               /* Ignore definitions that aren't keymaps themselves.  */
1597               tem = get_keymap (cmd, 0, 0);
1598               if (CONSP (tem))
1599                 {
1600                   /* Ignore keymaps that have been seen already.  */
1601                   cmd = tem;
1602                   tem = Frassq (cmd, maps);
1603                   if (NILP (tem))
1604                     {
1605                       /* Let elt be the event defined by this map entry.  */
1606                       elt = XCAR (elt);
1607
1608                       /* If the last key in thisseq is meta-prefix-char, and
1609                          this entry is a binding for an ascii keystroke,
1610                          turn it into a meta-ized keystroke.  */
1611                       if (is_metized && INTEGERP (elt))
1612                         {
1613                           Lisp_Object element;
1614
1615                           element = thisseq;
1616                           tem = Fvconcat (1, &element);
1617                           XSETFASTINT (AREF (tem, XINT (last)),
1618                                        XINT (elt) | meta_modifier);
1619
1620                           /* This new sequence is the same length as
1621                              thisseq, so stick it in the list right
1622                              after this one.  */
1623                           XCDR (tail)
1624                             = Fcons (Fcons (tem, cmd), XCDR (tail));
1625                         }
1626                       else
1627                         nconc2 (tail,
1628                                 Fcons (Fcons (append_key (thisseq, elt), cmd),
1629                                        Qnil));
1630                     }
1631                 }
1632             }
1633         }
1634     }
1635
1636   if (NILP (prefix))
1637     return maps;
1638
1639   /* Now find just the maps whose access prefixes start with PREFIX.  */
1640
1641   good_maps = Qnil;
1642   for (; CONSP (maps); maps = XCDR (maps))
1643     {
1644       Lisp_Object elt, thisseq;
1645       elt = XCAR (maps);
1646       thisseq = XCAR (elt);
1647       /* The access prefix must be at least as long as PREFIX,
1648          and the first elements must match those of PREFIX.  */
1649       if (XINT (Flength (thisseq)) >= prefixlen)
1650         {
1651           int i;
1652           for (i = 0; i < prefixlen; i++)
1653             {
1654               Lisp_Object i1;
1655               XSETFASTINT (i1, i);
1656               if (!EQ (Faref (thisseq, i1), Faref (prefix, i1)))
1657                 break;
1658             }
1659           if (i == prefixlen)
1660             good_maps = Fcons (elt, good_maps);
1661         }
1662     }
1663
1664   return Fnreverse (good_maps);
1665 }
1666
1667 static void
1668 accessible_keymaps_char_table (args, index, cmd)
1669      Lisp_Object args, index, cmd;
1670 {
1671   Lisp_Object tem;
1672   Lisp_Object maps, tail, thisseq;
1673   int is_metized;
1674
1675   cmd = get_keyelt (cmd, 0);
1676   if (NILP (cmd))
1677     return;
1678
1679   maps = XCAR (XCAR (args));
1680   is_metized = XINT (XCDR (XCAR (args)));
1681   tail = XCAR (XCDR (args));
1682   thisseq = XCDR (XCDR (args));
1683
1684   tem = get_keymap (cmd, 0, 0);
1685   if (CONSP (tem))
1686     {
1687       cmd = tem;
1688       /* Ignore keymaps that are already added to maps.  */
1689       tem = Frassq (cmd, maps);
1690       if (NILP (tem))
1691         {
1692           /* If the last key in thisseq is meta-prefix-char,
1693              turn it into a meta-ized keystroke.  We know
1694              that the event we're about to append is an
1695              ascii keystroke since we're processing a
1696              keymap table.  */
1697           if (is_metized)
1698             {
1699               int meta_bit = meta_modifier;
1700               Lisp_Object last = make_number (XINT (Flength (thisseq)) - 1);
1701               tem = Fcopy_sequence (thisseq);
1702
1703               Faset (tem, last, make_number (XINT (index) | meta_bit));
1704
1705               /* This new sequence is the same length as
1706                  thisseq, so stick it in the list right
1707                  after this one.  */
1708               XCDR (tail)
1709                 = Fcons (Fcons (tem, cmd), XCDR (tail));
1710             }
1711           else
1712             {
1713               tem = append_key (thisseq, index);
1714               nconc2 (tail, Fcons (Fcons (tem, cmd), Qnil));
1715             }
1716         }
1717     }
1718 }
1719 \f
1720 Lisp_Object Qsingle_key_description, Qkey_description;
1721
1722 /* This function cannot GC.  */
1723
1724 DEFUN ("key-description", Fkey_description, Skey_description, 1, 1, 0,
1725   "Return a pretty description of key-sequence KEYS.\n\
1726 Control characters turn into \"C-foo\" sequences, meta into \"M-foo\"\n\
1727 spaces are put between sequence elements, etc.")
1728   (keys)
1729      Lisp_Object keys;
1730 {
1731   int len = 0;
1732   int i, i_byte;
1733   Lisp_Object sep;
1734   Lisp_Object *args = NULL;
1735
1736   if (STRINGP (keys))
1737     {
1738       Lisp_Object vector;
1739       vector = Fmake_vector (Flength (keys), Qnil);
1740       for (i = 0, i_byte = 0; i < XSTRING (keys)->size; )
1741         {
1742           int c;
1743           int i_before = i;
1744
1745           FETCH_STRING_CHAR_ADVANCE (c, keys, i, i_byte);
1746           if (SINGLE_BYTE_CHAR_P (c) && (c & 0200))
1747             c ^= 0200 | meta_modifier;
1748           XSETFASTINT (AREF (vector, i_before), c);
1749         }
1750       keys = vector;
1751     }
1752
1753   if (VECTORP (keys))
1754     {
1755       /* In effect, this computes
1756          (mapconcat 'single-key-description keys " ")
1757          but we shouldn't use mapconcat because it can do GC.  */
1758
1759       len = XVECTOR (keys)->size;
1760       sep = build_string (" ");
1761       /* This has one extra element at the end that we don't pass to Fconcat.  */
1762       args = (Lisp_Object *) alloca (len * 2 * sizeof (Lisp_Object));
1763
1764       for (i = 0; i < len; i++)
1765         {
1766           args[i * 2] = Fsingle_key_description (AREF (keys, i), Qnil);
1767           args[i * 2 + 1] = sep;
1768         }
1769     }
1770   else if (CONSP (keys))
1771     {
1772       /* In effect, this computes
1773          (mapconcat 'single-key-description keys " ")
1774          but we shouldn't use mapconcat because it can do GC.  */
1775
1776       len = XFASTINT (Flength (keys));
1777       sep = build_string (" ");
1778       /* This has one extra element at the end that we don't pass to Fconcat.  */
1779       args = (Lisp_Object *) alloca (len * 2 * sizeof (Lisp_Object));
1780
1781       for (i = 0; i < len; i++)
1782         {
1783           args[i * 2] = Fsingle_key_description (XCAR (keys), Qnil);
1784           args[i * 2 + 1] = sep;
1785           keys = XCDR (keys);
1786         }
1787     }
1788   else
1789     keys = wrong_type_argument (Qarrayp, keys);
1790
1791   if (len == 0)
1792     return build_string ("");
1793   return Fconcat (len * 2 - 1, args);
1794 }
1795
1796 char *
1797 push_key_description (c, p, force_multibyte)
1798      register unsigned int c;
1799      register char *p;
1800      int force_multibyte;
1801 {
1802   unsigned c2;
1803
1804   /* Clear all the meaningless bits above the meta bit.  */
1805   c &= meta_modifier | ~ - meta_modifier;
1806   c2 = c & ~(alt_modifier | ctrl_modifier | hyper_modifier
1807              | meta_modifier | shift_modifier | super_modifier);
1808
1809   if (c & alt_modifier)
1810     {
1811       *p++ = 'A';
1812       *p++ = '-';
1813       c -= alt_modifier;
1814     }
1815   if ((c & ctrl_modifier) != 0
1816       || (c2 < ' ' && c2 != 27 && c2 != '\t' && c2 != Ctl ('M')))
1817     {
1818       *p++ = 'C';
1819       *p++ = '-';
1820       c &= ~ctrl_modifier;
1821     }
1822   if (c & hyper_modifier)
1823     {
1824       *p++ = 'H';
1825       *p++ = '-';
1826       c -= hyper_modifier;
1827     }
1828   if (c & meta_modifier)
1829     {
1830       *p++ = 'M';
1831       *p++ = '-';
1832       c -= meta_modifier;
1833     }
1834   if (c & shift_modifier)
1835     {
1836       *p++ = 'S';
1837       *p++ = '-';
1838       c -= shift_modifier;
1839     }
1840   if (c & super_modifier)
1841     {
1842       *p++ = 's';
1843       *p++ = '-';
1844       c -= super_modifier;
1845     }
1846   if (c < 040)
1847     {
1848       if (c == 033)
1849         {
1850           *p++ = 'E';
1851           *p++ = 'S';
1852           *p++ = 'C';
1853         }
1854       else if (c == '\t')
1855         {
1856           *p++ = 'T';
1857           *p++ = 'A';
1858           *p++ = 'B';
1859         }
1860       else if (c == Ctl ('M'))
1861         {
1862           *p++ = 'R';
1863           *p++ = 'E';
1864           *p++ = 'T';
1865         }
1866       else
1867         {
1868           /* `C-' already added above.  */
1869           if (c > 0 && c <= Ctl ('Z'))
1870             *p++ = c + 0140;
1871           else
1872             *p++ = c + 0100;
1873         }
1874     }
1875   else if (c == 0177)
1876     {
1877       *p++ = 'D';
1878       *p++ = 'E';
1879       *p++ = 'L';
1880     }
1881   else if (c == ' ')
1882    {
1883       *p++ = 'S';
1884       *p++ = 'P';
1885       *p++ = 'C';
1886     }
1887   else if (c < 128
1888            || (NILP (current_buffer->enable_multibyte_characters)
1889                && SINGLE_BYTE_CHAR_P (c)
1890                && !force_multibyte))
1891     {
1892       *p++ = c;
1893     }
1894   else
1895     {
1896       int valid_p = SINGLE_BYTE_CHAR_P (c) || char_valid_p (c, 0);
1897
1898       if (force_multibyte && valid_p)
1899         {
1900           if (SINGLE_BYTE_CHAR_P (c))
1901             c = unibyte_char_to_multibyte (c);
1902           p += CHAR_STRING (c, p);
1903         }
1904       else if (NILP (current_buffer->enable_multibyte_characters)
1905                || valid_p)
1906         {
1907           int bit_offset;
1908           *p++ = '\\';
1909           /* The biggest character code uses 19 bits.  */
1910           for (bit_offset = 18; bit_offset >= 0; bit_offset -= 3)
1911             {
1912               if (c >= (1 << bit_offset))
1913                 *p++ = ((c & (7 << bit_offset)) >> bit_offset) + '0';
1914             }
1915         }
1916       else
1917         p += CHAR_STRING (c, p);
1918     }
1919
1920   return p;
1921 }
1922
1923 /* This function cannot GC.  */
1924
1925 DEFUN ("single-key-description", Fsingle_key_description,
1926        Ssingle_key_description, 1, 2, 0,
1927   "Return a pretty description of command character KEY.\n\
1928 Control characters turn into C-whatever, etc.\n\
1929 Optional argument NO-ANGLES non-nil means don't put angle brackets\n\
1930 around function keys and event symbols.")
1931   (key, no_angles)
1932      Lisp_Object key, no_angles;
1933 {
1934   if (CONSP (key) && lucid_event_type_list_p (key))
1935     key = Fevent_convert_list (key);
1936
1937   key = EVENT_HEAD (key);
1938
1939   if (INTEGERP (key))           /* Normal character */
1940     {
1941       unsigned int charset, c1, c2;
1942       int without_bits = XINT (key) & ~((-1) << CHARACTERBITS);
1943
1944       if (SINGLE_BYTE_CHAR_P (without_bits))
1945         charset = 0;
1946       else
1947         SPLIT_CHAR (without_bits, charset, c1, c2);
1948
1949       if (charset
1950           && CHARSET_DEFINED_P (charset)
1951           && ((c1 >= 0 && c1 < 32)
1952               || (c2 >= 0 && c2 < 32)))
1953         {
1954           /* Handle a generic character.  */
1955           Lisp_Object name;
1956           name = CHARSET_TABLE_INFO (charset, CHARSET_LONG_NAME_IDX);
1957           CHECK_STRING (name, 0);
1958           return concat2 (build_string ("Character set "), name);
1959         }
1960       else
1961         {
1962           char tem[KEY_DESCRIPTION_SIZE];
1963           int len;
1964
1965           *push_key_description (XUINT (key), tem, 1) = 0;
1966           len = strlen (tem);
1967           return make_multibyte_string (tem,
1968                                         multibyte_chars_in_text (tem, len),
1969                                         len);
1970         }
1971     }
1972   else if (SYMBOLP (key))       /* Function key or event-symbol */
1973     {
1974       if (NILP (no_angles))
1975         {
1976           char *buffer
1977             = (char *) alloca (STRING_BYTES (XSYMBOL (key)->name) + 5);
1978           sprintf (buffer, "<%s>", XSYMBOL (key)->name->data);
1979           return build_string (buffer);
1980         }
1981       else
1982         return Fsymbol_name (key);
1983     }
1984   else if (STRINGP (key))       /* Buffer names in the menubar.  */
1985     return Fcopy_sequence (key);
1986   else
1987     error ("KEY must be an integer, cons, symbol, or string");
1988   return Qnil;
1989 }
1990
1991 char *
1992 push_text_char_description (c, p)
1993      register unsigned int c;
1994      register char *p;
1995 {
1996   if (c >= 0200)
1997     {
1998       *p++ = 'M';
1999       *p++ = '-';
2000       c -= 0200;
2001     }
2002   if (c < 040)
2003     {
2004       *p++ = '^';
2005       *p++ = c + 64;            /* 'A' - 1 */
2006     }
2007   else if (c == 0177)
2008     {
2009       *p++ = '^';
2010       *p++ = '?';
2011     }
2012   else
2013     *p++ = c;
2014   return p;
2015 }
2016
2017 /* This function cannot GC.  */
2018
2019 DEFUN ("text-char-description", Ftext_char_description, Stext_char_description, 1, 1, 0,
2020   "Return a pretty description of file-character CHARACTER.\n\
2021 Control characters turn into \"^char\", etc.")
2022   (character)
2023      Lisp_Object character;
2024 {
2025   /* Currently MAX_MULTIBYTE_LENGTH is 4 (< 6).  */
2026   unsigned char str[6];
2027   int c;
2028
2029   CHECK_NUMBER (character, 0);
2030
2031   c = XINT (character);
2032   if (!SINGLE_BYTE_CHAR_P (c))
2033     {
2034       int len = CHAR_STRING (c, str);
2035
2036       return make_multibyte_string (str, 1, len);
2037     }
2038
2039   *push_text_char_description (c & 0377, str) = 0;
2040
2041   return build_string (str);
2042 }
2043
2044 /* Return non-zero if SEQ contains only ASCII characters, perhaps with
2045    a meta bit.  */
2046 static int
2047 ascii_sequence_p (seq)
2048      Lisp_Object seq;
2049 {
2050   int i;
2051   int len = XINT (Flength (seq));
2052
2053   for (i = 0; i < len; i++)
2054     {
2055       Lisp_Object ii, elt;
2056
2057       XSETFASTINT (ii, i);
2058       elt = Faref (seq, ii);
2059
2060       if (!INTEGERP (elt)
2061           || (XUINT (elt) & ~CHAR_META) >= 0x80)
2062         return 0;
2063     }
2064
2065   return 1;
2066 }
2067
2068 \f
2069 /* where-is - finding a command in a set of keymaps.                    */
2070
2071 static Lisp_Object where_is_internal_1 ();
2072 static void where_is_internal_2 ();
2073
2074 /* Like Flookup_key, but uses a list of keymaps SHADOW instead of a single map.
2075    Returns the first non-nil binding found in any of those maps.  */
2076
2077 static Lisp_Object
2078 shadow_lookup (shadow, key, flag)
2079      Lisp_Object shadow, key, flag;
2080 {
2081   Lisp_Object tail, value;
2082
2083   for (tail = shadow; CONSP (tail); tail = XCDR (tail))
2084     {
2085       value = Flookup_key (XCAR (tail), key, flag);
2086       if (!NILP (value) && !NATNUMP (value))
2087         return value;
2088     }
2089   return Qnil;
2090 }
2091
2092 /* This function can GC if Flookup_key autoloads any keymaps.  */
2093
2094 static Lisp_Object
2095 where_is_internal (definition, keymaps, firstonly, noindirect)
2096      Lisp_Object definition, keymaps;
2097      Lisp_Object firstonly, noindirect;
2098 {
2099   Lisp_Object maps = Qnil;
2100   Lisp_Object found, sequences;
2101   struct gcpro gcpro1, gcpro2, gcpro3, gcpro4, gcpro5;
2102   /* 1 means ignore all menu bindings entirely.  */
2103   int nomenus = !NILP (firstonly) && !EQ (firstonly, Qnon_ascii);
2104
2105   found = keymaps;
2106   while (CONSP (found))
2107     {
2108       maps =
2109         nconc2 (maps,
2110                 Faccessible_keymaps (get_keymap (XCAR (found), 1, 0), Qnil));
2111       found = XCDR (found);
2112     }
2113
2114   GCPRO5 (definition, keymaps, maps, found, sequences);
2115   found = Qnil;
2116   sequences = Qnil;
2117
2118   for (; !NILP (maps); maps = Fcdr (maps))
2119     {
2120       /* Key sequence to reach map, and the map that it reaches */
2121       register Lisp_Object this, map;
2122
2123       /* In order to fold [META-PREFIX-CHAR CHAR] sequences into
2124          [M-CHAR] sequences, check if last character of the sequence
2125          is the meta-prefix char.  */
2126       Lisp_Object last;
2127       int last_is_meta;
2128
2129       this = Fcar (Fcar (maps));
2130       map  = Fcdr (Fcar (maps));
2131       last = make_number (XINT (Flength (this)) - 1);
2132       last_is_meta = (XINT (last) >= 0
2133                       && EQ (Faref (this, last), meta_prefix_char));
2134
2135       /* if (nomenus && !ascii_sequence_p (this)) */
2136       if (nomenus && XINT (last) >= 0
2137           && !INTEGERP (Faref (this, make_number (0))))
2138         /* If no menu entries should be returned, skip over the
2139            keymaps bound to `menu-bar' and `tool-bar' and other
2140            non-ascii prefixes like `C-down-mouse-2'.  */
2141         continue;
2142
2143       QUIT;
2144
2145       while (CONSP (map))
2146         {
2147           /* Because the code we want to run on each binding is rather
2148              large, we don't want to have two separate loop bodies for
2149              sparse keymap bindings and tables; we want to iterate one
2150              loop body over both keymap and vector bindings.
2151
2152              For this reason, if Fcar (map) is a vector, we don't
2153              advance map to the next element until i indicates that we
2154              have finished off the vector.  */
2155           Lisp_Object elt, key, binding;
2156           elt = XCAR (map);
2157           map = XCDR (map);
2158
2159           sequences = Qnil;
2160
2161           QUIT;
2162
2163           /* Set key and binding to the current key and binding, and
2164              advance map and i to the next binding.  */
2165           if (VECTORP (elt))
2166             {
2167               Lisp_Object sequence;
2168               int i;
2169               /* In a vector, look at each element.  */
2170               for (i = 0; i < XVECTOR (elt)->size; i++)
2171                 {
2172                   binding = AREF (elt, i);
2173                   XSETFASTINT (key, i);
2174                   sequence = where_is_internal_1 (binding, key, definition,
2175                                                   noindirect, this,
2176                                                   last, nomenus, last_is_meta);
2177                   if (!NILP (sequence))
2178                     sequences = Fcons (sequence, sequences);
2179                 }
2180             }
2181           else if (CHAR_TABLE_P (elt))
2182             {
2183               Lisp_Object indices[3];
2184               Lisp_Object args;
2185
2186               args = Fcons (Fcons (Fcons (definition, noindirect),
2187                                    Qnil), /* Result accumulator.  */
2188                             Fcons (Fcons (this, last),
2189                                    Fcons (make_number (nomenus),
2190                                           make_number (last_is_meta))));
2191               map_char_table (where_is_internal_2, Qnil, elt, args,
2192                               0, indices);
2193               sequences = XCDR (XCAR (args));
2194             }
2195           else if (CONSP (elt))
2196             {
2197               Lisp_Object sequence;
2198
2199               key = XCAR (elt);
2200               binding = XCDR (elt);
2201
2202               sequence = where_is_internal_1 (binding, key, definition,
2203                                               noindirect, this,
2204                                               last, nomenus, last_is_meta);
2205               if (!NILP (sequence))
2206                 sequences = Fcons (sequence, sequences);
2207             }
2208
2209
2210           for (; ! NILP (sequences); sequences = XCDR (sequences))
2211             {
2212               Lisp_Object sequence;
2213
2214               sequence = XCAR (sequences);
2215
2216               /* Verify that this key binding is not shadowed by another
2217                  binding for the same key, before we say it exists.
2218
2219                  Mechanism: look for local definition of this key and if
2220                  it is defined and does not match what we found then
2221                  ignore this key.
2222
2223                  Either nil or number as value from Flookup_key
2224                  means undefined.  */
2225               if (!EQ (shadow_lookup (keymaps, sequence, Qnil), definition))
2226                 continue;
2227
2228               /* It is a true unshadowed match.  Record it, unless it's already
2229                  been seen (as could happen when inheriting keymaps).  */
2230               if (NILP (Fmember (sequence, found)))
2231                 found = Fcons (sequence, found);
2232
2233               /* If firstonly is Qnon_ascii, then we can return the first
2234                  binding we find.  If firstonly is not Qnon_ascii but not
2235                  nil, then we should return the first ascii-only binding
2236                  we find.  */
2237               if (EQ (firstonly, Qnon_ascii))
2238                 RETURN_UNGCPRO (sequence);
2239               else if (! NILP (firstonly) && ascii_sequence_p (sequence))
2240                 RETURN_UNGCPRO (sequence);
2241             }
2242         }
2243     }
2244
2245   UNGCPRO;
2246
2247   found = Fnreverse (found);
2248
2249   /* firstonly may have been t, but we may have gone all the way through
2250      the keymaps without finding an all-ASCII key sequence.  So just
2251      return the best we could find.  */
2252   if (! NILP (firstonly))
2253     return Fcar (found);
2254
2255   return found;
2256 }
2257
2258 DEFUN ("where-is-internal", Fwhere_is_internal, Swhere_is_internal, 1, 4, 0,
2259   "Return list of keys that invoke DEFINITION.\n\
2260 If KEYMAP is non-nil, search only KEYMAP and the global keymap.\n\
2261 If KEYMAP is nil, search all the currently active keymaps.\n\
2262 If KEYMAP is a list of keymaps, search only those keymaps.\n\
2263 \n\
2264 If optional 3rd arg FIRSTONLY is non-nil, return the first key sequence found,\n\
2265 rather than a list of all possible key sequences.\n\
2266 If FIRSTONLY is the symbol `non-ascii', return the first binding found,\n\
2267 no matter what it is.\n\
2268 If FIRSTONLY has another non-nil value, prefer sequences of ASCII characters,\n\
2269 and entirely reject menu bindings.\n\
2270 \n\
2271 If optional 4th arg NOINDIRECT is non-nil, don't follow indirections\n\
2272 to other keymaps or slots.  This makes it possible to search for an\n\
2273 indirect definition itself.")
2274   (definition, keymap, firstonly, noindirect)
2275      Lisp_Object definition, keymap;
2276      Lisp_Object firstonly, noindirect;
2277 {
2278   Lisp_Object sequences, keymaps;
2279   /* 1 means ignore all menu bindings entirely.  */
2280   int nomenus = !NILP (firstonly) && !EQ (firstonly, Qnon_ascii);
2281   Lisp_Object result;
2282
2283   /* Find the relevant keymaps.  */
2284   if (CONSP (keymap) && KEYMAPP (XCAR (keymap)))
2285     keymaps = keymap;
2286   else if (! NILP (keymap))
2287     keymaps = Fcons (keymap, Fcons (current_global_map, Qnil));
2288   else
2289     keymaps =
2290       Fdelq (Qnil,
2291              nconc2 (Fcurrent_minor_mode_maps (),
2292                      Fcons (get_local_map (PT, current_buffer, Qkeymap),
2293                             Fcons (get_local_map (PT, current_buffer,
2294                                                   Qlocal_map),
2295                                    Fcons (current_global_map, Qnil)))));
2296
2297   /* Only use caching for the menubar (i.e. called with (def nil t nil).
2298      We don't really need to check `keymap'.  */
2299   if (nomenus && NILP (noindirect) && NILP (keymap))
2300     {
2301       Lisp_Object *defns;
2302       int i, j, n;
2303       struct gcpro gcpro1, gcpro2, gcpro3, gcpro4;
2304
2305       /* Check heuristic-consistency of the cache.  */
2306       if (NILP (Fequal (keymaps, where_is_cache_keymaps)))
2307         where_is_cache = Qnil;
2308
2309       if (NILP (where_is_cache))
2310         {
2311           /* We need to create the cache.  */
2312           Lisp_Object args[2];
2313           where_is_cache = Fmake_hash_table (0, args);
2314           where_is_cache_keymaps = Qt;
2315
2316           /* Fill in the cache.  */
2317           GCPRO4 (definition, keymaps, firstonly, noindirect);
2318           where_is_internal (definition, keymaps, firstonly, noindirect);
2319           UNGCPRO;
2320
2321           where_is_cache_keymaps = keymaps;
2322         }
2323
2324       /* We want to process definitions from the last to the first.
2325          Instead of consing, copy definitions to a vector and step
2326          over that vector.  */
2327       sequences = Fgethash (definition, where_is_cache, Qnil);
2328       n = XINT (Flength (sequences));
2329       defns = (Lisp_Object *) alloca (n * sizeof *defns);
2330       for (i = 0; CONSP (sequences); sequences = XCDR (sequences))
2331         defns[i++] = XCAR (sequences);
2332
2333       /* Verify that the key bindings are not shadowed.  Note that
2334          the following can GC.  */
2335       GCPRO2 (definition, keymaps);
2336       result = Qnil;
2337       j = -1;
2338       for (i = n - 1; i >= 0; --i)
2339         if (EQ (shadow_lookup (keymaps, defns[i], Qnil), definition))
2340           {
2341             if (ascii_sequence_p (defns[i]))
2342               break;
2343             else if (j < 0)
2344               j = i;
2345           }
2346
2347       result = i >= 0 ? defns[i] : (j >= 0 ? defns[j] : Qnil);
2348       UNGCPRO;
2349     }
2350   else
2351     {
2352       /* Kill the cache so that where_is_internal_1 doesn't think
2353          we're filling it up.  */
2354       where_is_cache = Qnil;
2355       result = where_is_internal (definition, keymaps, firstonly, noindirect);
2356     }
2357
2358   return result;
2359 }
2360
2361 /* This is the function that Fwhere_is_internal calls using map_char_table.
2362    ARGS has the form
2363    (((DEFINITION . NOINDIRECT) . (KEYMAP . RESULT))
2364     .
2365     ((THIS . LAST) . (NOMENUS . LAST_IS_META)))
2366    Since map_char_table doesn't really use the return value from this function,
2367    we the result append to RESULT, the slot in ARGS.
2368
2369    This function can GC because it calls where_is_internal_1 which can
2370    GC.  */
2371
2372 static void
2373 where_is_internal_2 (args, key, binding)
2374      Lisp_Object args, key, binding;
2375 {
2376   Lisp_Object definition, noindirect, this, last;
2377   Lisp_Object result, sequence;
2378   int nomenus, last_is_meta;
2379   struct gcpro gcpro1, gcpro2, gcpro3;
2380
2381   GCPRO3 (args, key, binding);
2382   result = XCDR (XCAR (args));
2383   definition = XCAR (XCAR (XCAR (args)));
2384   noindirect = XCDR (XCAR (XCAR (args)));
2385   this = XCAR (XCAR (XCDR (args)));
2386   last = XCDR (XCAR (XCDR (args)));
2387   nomenus = XFASTINT (XCAR (XCDR (XCDR (args))));
2388   last_is_meta = XFASTINT (XCDR (XCDR (XCDR (args))));
2389
2390   sequence = where_is_internal_1 (binding, key, definition, noindirect,
2391                                   this, last, nomenus, last_is_meta);
2392
2393   if (!NILP (sequence))
2394     XCDR (XCAR (args)) = Fcons (sequence, result);
2395
2396   UNGCPRO;
2397 }
2398
2399
2400 /* This function cannot GC.  */
2401
2402 static Lisp_Object
2403 where_is_internal_1 (binding, key, definition, noindirect, this, last,
2404                      nomenus, last_is_meta)
2405      Lisp_Object binding, key, definition, noindirect, this, last;
2406      int nomenus, last_is_meta;
2407 {
2408   Lisp_Object sequence;
2409
2410   /* Search through indirections unless that's not wanted.  */
2411   if (NILP (noindirect))
2412     binding = get_keyelt (binding, 0);
2413
2414   /* End this iteration if this element does not match
2415      the target.  */
2416
2417   if (!(!NILP (where_is_cache)  /* everything "matches" during cache-fill.  */
2418         || EQ (binding, definition)
2419         || (CONSP (definition) && !NILP (Fequal (binding, definition)))))
2420     /* Doesn't match.  */
2421     return Qnil;
2422
2423   /* We have found a match.  Construct the key sequence where we found it.  */
2424   if (INTEGERP (key) && last_is_meta)
2425     {
2426       sequence = Fcopy_sequence (this);
2427       Faset (sequence, last, make_number (XINT (key) | meta_modifier));
2428     }
2429   else
2430     sequence = append_key (this, key);
2431
2432   if (!NILP (where_is_cache))
2433     {
2434       Lisp_Object sequences = Fgethash (binding, where_is_cache, Qnil);
2435       Fputhash (binding, Fcons (sequence, sequences), where_is_cache);
2436       return Qnil;
2437     }
2438   else
2439     return sequence;
2440 }
2441 \f
2442 /* describe-bindings - summarizing all the bindings in a set of keymaps.  */
2443
2444 DEFUN ("describe-bindings-internal", Fdescribe_bindings_internal, Sdescribe_bindings_internal, 0, 2, "",
2445   "Show a list of all defined keys, and their definitions.\n\
2446 We put that list in a buffer, and display the buffer.\n\
2447 \n\
2448 The optional argument MENUS, if non-nil, says to mention menu bindings.\n\
2449 \(Ordinarily these are omitted from the output.)\n\
2450 The optional argument PREFIX, if non-nil, should be a key sequence;\n\
2451 then we display only bindings that start with that prefix.")
2452   (menus, prefix)
2453      Lisp_Object menus, prefix;
2454 {
2455   register Lisp_Object thisbuf;
2456   XSETBUFFER (thisbuf, current_buffer);
2457   internal_with_output_to_temp_buffer ("*Help*",
2458                                        describe_buffer_bindings,
2459                                        list3 (thisbuf, prefix, menus));
2460   return Qnil;
2461 }
2462
2463 /* ARG is (BUFFER PREFIX MENU-FLAG).  */
2464
2465 static Lisp_Object
2466 describe_buffer_bindings (arg)
2467      Lisp_Object arg;
2468 {
2469   Lisp_Object descbuf, prefix, shadow;
2470   int nomenu;
2471   register Lisp_Object start1;
2472   struct gcpro gcpro1;
2473
2474   char *alternate_heading
2475     = "\
2476 Keyboard translations:\n\n\
2477 You type        Translation\n\
2478 --------        -----------\n";
2479
2480   descbuf = XCAR (arg);
2481   arg = XCDR (arg);
2482   prefix = XCAR (arg);
2483   arg = XCDR (arg);
2484   nomenu = NILP (XCAR (arg));
2485
2486   shadow = Qnil;
2487   GCPRO1 (shadow);
2488
2489   Fset_buffer (Vstandard_output);
2490
2491   /* Report on alternates for keys.  */
2492   if (STRINGP (Vkeyboard_translate_table) && !NILP (prefix))
2493     {
2494       int c;
2495       unsigned char *translate = XSTRING (Vkeyboard_translate_table)->data;
2496       int translate_len = XSTRING (Vkeyboard_translate_table)->size;
2497
2498       for (c = 0; c < translate_len; c++)
2499         if (translate[c] != c)
2500           {
2501             char buf[KEY_DESCRIPTION_SIZE];
2502             char *bufend;
2503
2504             if (alternate_heading)
2505               {
2506                 insert_string (alternate_heading);
2507                 alternate_heading = 0;
2508               }
2509
2510             bufend = push_key_description (translate[c], buf, 1);
2511             insert (buf, bufend - buf);
2512             Findent_to (make_number (16), make_number (1));
2513             bufend = push_key_description (c, buf, 1);
2514             insert (buf, bufend - buf);
2515
2516             insert ("\n", 1);
2517           }
2518
2519       insert ("\n", 1);
2520     }
2521
2522   if (!NILP (Vkey_translation_map))
2523     describe_map_tree (Vkey_translation_map, 0, Qnil, prefix,
2524                        "Key translations", nomenu, 1, 0);
2525
2526   {
2527     int i, nmaps;
2528     Lisp_Object *modes, *maps;
2529
2530     /* Temporarily switch to descbuf, so that we can get that buffer's
2531        minor modes correctly.  */
2532     Fset_buffer (descbuf);
2533
2534     if (!NILP (current_kboard->Voverriding_terminal_local_map)
2535         || !NILP (Voverriding_local_map))
2536       nmaps = 0;
2537     else
2538       nmaps = current_minor_maps (&modes, &maps);
2539     Fset_buffer (Vstandard_output);
2540
2541     /* Print the minor mode maps.  */
2542     for (i = 0; i < nmaps; i++)
2543       {
2544         /* The title for a minor mode keymap
2545            is constructed at run time.
2546            We let describe_map_tree do the actual insertion
2547            because it takes care of other features when doing so.  */
2548         char *title, *p;
2549
2550         if (!SYMBOLP (modes[i]))
2551           abort();
2552
2553         p = title = (char *) alloca (42 + XSYMBOL (modes[i])->name->size);
2554         *p++ = '\f';
2555         *p++ = '\n';
2556         *p++ = '`';
2557         bcopy (XSYMBOL (modes[i])->name->data, p,
2558                XSYMBOL (modes[i])->name->size);
2559         p += XSYMBOL (modes[i])->name->size;
2560         *p++ = '\'';
2561         bcopy (" Minor Mode Bindings", p, sizeof (" Minor Mode Bindings") - 1);
2562         p += sizeof (" Minor Mode Bindings") - 1;
2563         *p = 0;
2564
2565         describe_map_tree (maps[i], 1, shadow, prefix, title, nomenu, 0, 0);
2566         shadow = Fcons (maps[i], shadow);
2567       }
2568   }
2569
2570   /* Print the (major mode) local map.  */
2571   if (!NILP (current_kboard->Voverriding_terminal_local_map))
2572     start1 = current_kboard->Voverriding_terminal_local_map;
2573   else if (!NILP (Voverriding_local_map))
2574     start1 = Voverriding_local_map;
2575   else
2576     start1 = XBUFFER (descbuf)->keymap;
2577
2578   if (!NILP (start1))
2579     {
2580       describe_map_tree (start1, 1, shadow, prefix,
2581                          "\f\nMajor Mode Bindings", nomenu, 0, 0);
2582       shadow = Fcons (start1, shadow);
2583     }
2584
2585   describe_map_tree (current_global_map, 1, shadow, prefix,
2586                      "\f\nGlobal Bindings", nomenu, 0, 1);
2587
2588   /* Print the function-key-map translations under this prefix.  */
2589   if (!NILP (Vfunction_key_map))
2590     describe_map_tree (Vfunction_key_map, 0, Qnil, prefix,
2591                        "\f\nFunction key map translations", nomenu, 1, 0);
2592
2593   call0 (intern ("help-mode"));
2594   Fset_buffer (descbuf);
2595   UNGCPRO;
2596   return Qnil;
2597 }
2598
2599 /* Insert a description of the key bindings in STARTMAP,
2600     followed by those of all maps reachable through STARTMAP.
2601    If PARTIAL is nonzero, omit certain "uninteresting" commands
2602     (such as `undefined').
2603    If SHADOW is non-nil, it is a list of maps;
2604     don't mention keys which would be shadowed by any of them.
2605    PREFIX, if non-nil, says mention only keys that start with PREFIX.
2606    TITLE, if not 0, is a string to insert at the beginning.
2607    TITLE should not end with a colon or a newline; we supply that.
2608    If NOMENU is not 0, then omit menu-bar commands.
2609
2610    If TRANSL is nonzero, the definitions are actually key translations
2611    so print strings and vectors differently.
2612
2613    If ALWAYS_TITLE is nonzero, print the title even if there are no maps
2614    to look through.  */
2615
2616 void
2617 describe_map_tree (startmap, partial, shadow, prefix, title, nomenu, transl,
2618                    always_title)
2619      Lisp_Object startmap, shadow, prefix;
2620      int partial;
2621      char *title;
2622      int nomenu;
2623      int transl;
2624      int always_title;
2625 {
2626   Lisp_Object maps, orig_maps, seen, sub_shadows;
2627   struct gcpro gcpro1, gcpro2, gcpro3;
2628   int something = 0;
2629   char *key_heading
2630     = "\
2631 key             binding\n\
2632 ---             -------\n";
2633
2634   orig_maps = maps = Faccessible_keymaps (startmap, prefix);
2635   seen = Qnil;
2636   sub_shadows = Qnil;
2637   GCPRO3 (maps, seen, sub_shadows);
2638
2639   if (nomenu)
2640     {
2641       Lisp_Object list;
2642
2643       /* Delete from MAPS each element that is for the menu bar.  */
2644       for (list = maps; !NILP (list); list = XCDR (list))
2645         {
2646           Lisp_Object elt, prefix, tem;
2647
2648           elt = Fcar (list);
2649           prefix = Fcar (elt);
2650           if (XVECTOR (prefix)->size >= 1)
2651             {
2652               tem = Faref (prefix, make_number (0));
2653               if (EQ (tem, Qmenu_bar))
2654                 maps = Fdelq (elt, maps);
2655             }
2656         }
2657     }
2658
2659   if (!NILP (maps) || always_title)
2660     {
2661       if (title)
2662         {
2663           insert_string (title);
2664           if (!NILP (prefix))
2665             {
2666               insert_string (" Starting With ");
2667               insert1 (Fkey_description (prefix));
2668             }
2669           insert_string (":\n");
2670         }
2671       insert_string (key_heading);
2672       something = 1;
2673     }
2674
2675   for (; !NILP (maps); maps = Fcdr (maps))
2676     {
2677       register Lisp_Object elt, prefix, tail;
2678
2679       elt = Fcar (maps);
2680       prefix = Fcar (elt);
2681
2682       sub_shadows = Qnil;
2683
2684       for (tail = shadow; CONSP (tail); tail = XCDR (tail))
2685         {
2686           Lisp_Object shmap;
2687
2688           shmap = XCAR (tail);
2689
2690           /* If the sequence by which we reach this keymap is zero-length,
2691              then the shadow map for this keymap is just SHADOW.  */
2692           if ((STRINGP (prefix) && XSTRING (prefix)->size == 0)
2693               || (VECTORP (prefix) && XVECTOR (prefix)->size == 0))
2694             ;
2695           /* If the sequence by which we reach this keymap actually has
2696              some elements, then the sequence's definition in SHADOW is
2697              what we should use.  */
2698           else
2699             {
2700               shmap = Flookup_key (shmap, Fcar (elt), Qt);
2701               if (INTEGERP (shmap))
2702                 shmap = Qnil;
2703             }
2704
2705           /* If shmap is not nil and not a keymap,
2706              it completely shadows this map, so don't
2707              describe this map at all.  */
2708           if (!NILP (shmap) && !KEYMAPP (shmap))
2709             goto skip;
2710
2711           if (!NILP (shmap))
2712             sub_shadows = Fcons (shmap, sub_shadows);
2713         }
2714
2715       /* Maps we have already listed in this loop shadow this map.  */
2716       for (tail = orig_maps; ! EQ (tail, maps); tail = XCDR (tail))
2717         {
2718           Lisp_Object tem;
2719           tem = Fequal (Fcar (XCAR (tail)), prefix);
2720           if (! NILP (tem))
2721             sub_shadows = Fcons (XCDR (XCAR (tail)), sub_shadows);
2722         }
2723
2724       describe_map (Fcdr (elt), prefix,
2725                     transl ? describe_translation : describe_command,
2726                     partial, sub_shadows, &seen, nomenu);
2727
2728     skip: ;
2729     }
2730
2731   if (something)
2732     insert_string ("\n");
2733
2734   UNGCPRO;
2735 }
2736
2737 static int previous_description_column;
2738
2739 static void
2740 describe_command (definition)
2741      Lisp_Object definition;
2742 {
2743   register Lisp_Object tem1;
2744   int column = current_column ();
2745   int description_column;
2746
2747   /* If column 16 is no good, go to col 32;
2748      but don't push beyond that--go to next line instead.  */
2749   if (column > 30)
2750     {
2751       insert_char ('\n');
2752       description_column = 32;
2753     }
2754   else if (column > 14 || (column > 10 && previous_description_column == 32))
2755     description_column = 32;
2756   else
2757     description_column = 16;
2758
2759   Findent_to (make_number (description_column), make_number (1));
2760   previous_description_column = description_column;
2761
2762   if (SYMBOLP (definition))
2763     {
2764       XSETSTRING (tem1, XSYMBOL (definition)->name);
2765       insert1 (tem1);
2766       insert_string ("\n");
2767     }
2768   else if (STRINGP (definition) || VECTORP (definition))
2769     insert_string ("Keyboard Macro\n");
2770   else if (KEYMAPP (definition))
2771     insert_string ("Prefix Command\n");
2772   else
2773     insert_string ("??\n");
2774 }
2775
2776 static void
2777 describe_translation (definition)
2778      Lisp_Object definition;
2779 {
2780   register Lisp_Object tem1;
2781
2782   Findent_to (make_number (16), make_number (1));
2783
2784   if (SYMBOLP (definition))
2785     {
2786       XSETSTRING (tem1, XSYMBOL (definition)->name);
2787       insert1 (tem1);
2788       insert_string ("\n");
2789     }
2790   else if (STRINGP (definition) || VECTORP (definition))
2791     {
2792       insert1 (Fkey_description (definition));
2793       insert_string ("\n");
2794     }
2795   else if (KEYMAPP (definition))
2796     insert_string ("Prefix Command\n");
2797   else
2798     insert_string ("??\n");
2799 }
2800
2801 /* Describe the contents of map MAP, assuming that this map itself is
2802    reached by the sequence of prefix keys KEYS (a string or vector).
2803    PARTIAL, SHADOW, NOMENU are as in `describe_map_tree' above.  */
2804
2805 static void
2806 describe_map (map, keys, elt_describer, partial, shadow, seen, nomenu)
2807      register Lisp_Object map;
2808      Lisp_Object keys;
2809      void (*elt_describer) P_ ((Lisp_Object));
2810      int partial;
2811      Lisp_Object shadow;
2812      Lisp_Object *seen;
2813      int nomenu;
2814 {
2815   Lisp_Object elt_prefix;
2816   Lisp_Object tail, definition, event;
2817   Lisp_Object tem;
2818   Lisp_Object suppress;
2819   Lisp_Object kludge;
2820   int first = 1;
2821   struct gcpro gcpro1, gcpro2, gcpro3;
2822
2823   suppress = Qnil;
2824
2825   if (!NILP (keys) && XFASTINT (Flength (keys)) > 0)
2826     {
2827       /* Call Fkey_description first, to avoid GC bug for the other string.  */
2828       tem = Fkey_description (keys);
2829       elt_prefix = concat2 (tem, build_string (" "));
2830     }
2831   else
2832     elt_prefix = Qnil;
2833
2834   if (partial)
2835     suppress = intern ("suppress-keymap");
2836
2837   /* This vector gets used to present single keys to Flookup_key.  Since
2838      that is done once per keymap element, we don't want to cons up a
2839      fresh vector every time.  */
2840   kludge = Fmake_vector (make_number (1), Qnil);
2841   definition = Qnil;
2842
2843   GCPRO3 (elt_prefix, definition, kludge);
2844
2845   for (tail = map; CONSP (tail); tail = XCDR (tail))
2846     {
2847       QUIT;
2848
2849       if (VECTORP (XCAR (tail))
2850           || CHAR_TABLE_P (XCAR (tail)))
2851         describe_vector (XCAR (tail),
2852                          elt_prefix, elt_describer, partial, shadow, map,
2853                          (int *)0, 0);
2854       else if (CONSP (XCAR (tail)))
2855         {
2856           event = XCAR (XCAR (tail));
2857
2858           /* Ignore bindings whose "keys" are not really valid events.
2859              (We get these in the frames and buffers menu.)  */
2860           if (! (SYMBOLP (event) || INTEGERP (event)))
2861             continue;
2862
2863           if (nomenu && EQ (event, Qmenu_bar))
2864             continue;
2865
2866           definition = get_keyelt (XCDR (XCAR (tail)), 0);
2867
2868           /* Don't show undefined commands or suppressed commands.  */
2869           if (NILP (definition)) continue;
2870           if (SYMBOLP (definition) && partial)
2871             {
2872               tem = Fget (definition, suppress);
2873               if (!NILP (tem))
2874                 continue;
2875             }
2876
2877           /* Don't show a command that isn't really visible
2878              because a local definition of the same key shadows it.  */
2879
2880           ASET (kludge, 0, event);
2881           if (!NILP (shadow))
2882             {
2883               tem = shadow_lookup (shadow, kludge, Qt);
2884               if (!NILP (tem)) continue;
2885             }
2886
2887           tem = Flookup_key (map, kludge, Qt);
2888           if (! EQ (tem, definition)) continue;
2889
2890           if (first)
2891             {
2892               previous_description_column = 0;
2893               insert ("\n", 1);
2894               first = 0;
2895             }
2896
2897           if (!NILP (elt_prefix))
2898             insert1 (elt_prefix);
2899
2900           /* THIS gets the string to describe the character EVENT.  */
2901           insert1 (Fsingle_key_description (event, Qnil));
2902
2903           /* Print a description of the definition of this character.
2904              elt_describer will take care of spacing out far enough
2905              for alignment purposes.  */
2906           (*elt_describer) (definition);
2907         }
2908       else if (EQ (XCAR (tail), Qkeymap))
2909         {
2910           /* The same keymap might be in the structure twice, if we're
2911              using an inherited keymap.  So skip anything we've already
2912              encountered.  */
2913           tem = Fassq (tail, *seen);
2914           if (CONSP (tem) && !NILP (Fequal (XCAR (tem), keys)))
2915             break;
2916           *seen = Fcons (Fcons (tail, keys), *seen);
2917         }
2918     }
2919
2920   UNGCPRO;
2921 }
2922
2923 static void
2924 describe_vector_princ (elt)
2925      Lisp_Object elt;
2926 {
2927   Findent_to (make_number (16), make_number (1));
2928   Fprinc (elt, Qnil);
2929   Fterpri (Qnil);
2930 }
2931
2932 DEFUN ("describe-vector", Fdescribe_vector, Sdescribe_vector, 1, 1, 0,
2933   "Insert a description of contents of VECTOR.\n\
2934 This is text showing the elements of vector matched against indices.")
2935   (vector)
2936      Lisp_Object vector;
2937 {
2938   int count = specpdl_ptr - specpdl;
2939
2940   specbind (Qstandard_output, Fcurrent_buffer ());
2941   CHECK_VECTOR_OR_CHAR_TABLE (vector, 0);
2942   describe_vector (vector, Qnil, describe_vector_princ, 0,
2943                    Qnil, Qnil, (int *)0, 0);
2944
2945   return unbind_to (count, Qnil);
2946 }
2947
2948 /* Insert in the current buffer a description of the contents of VECTOR.
2949    We call ELT_DESCRIBER to insert the description of one value found
2950    in VECTOR.
2951
2952    ELT_PREFIX describes what "comes before" the keys or indices defined
2953    by this vector.  This is a human-readable string whose size
2954    is not necessarily related to the situation.
2955
2956    If the vector is in a keymap, ELT_PREFIX is a prefix key which
2957    leads to this keymap.
2958
2959    If the vector is a chartable, ELT_PREFIX is the vector
2960    of bytes that lead to the character set or portion of a character
2961    set described by this chartable.
2962
2963    If PARTIAL is nonzero, it means do not mention suppressed commands
2964    (that assumes the vector is in a keymap).
2965
2966    SHADOW is a list of keymaps that shadow this map.
2967    If it is non-nil, then we look up the key in those maps
2968    and we don't mention it now if it is defined by any of them.
2969
2970    ENTIRE_MAP is the keymap in which this vector appears.
2971    If the definition in effect in the whole map does not match
2972    the one in this vector, we ignore this one.
2973
2974    When describing a sub-char-table, INDICES is a list of
2975    indices at higher levels in this char-table,
2976    and CHAR_TABLE_DEPTH says how many levels down we have gone.  */
2977
2978 void
2979 describe_vector (vector, elt_prefix, elt_describer,
2980                  partial, shadow, entire_map,
2981                  indices, char_table_depth)
2982      register Lisp_Object vector;
2983      Lisp_Object elt_prefix;
2984      void (*elt_describer) P_ ((Lisp_Object));
2985      int partial;
2986      Lisp_Object shadow;
2987      Lisp_Object entire_map;
2988      int *indices;
2989      int char_table_depth;
2990 {
2991   Lisp_Object definition;
2992   Lisp_Object tem2;
2993   register int i;
2994   Lisp_Object suppress;
2995   Lisp_Object kludge;
2996   int first = 1;
2997   struct gcpro gcpro1, gcpro2, gcpro3;
2998   /* Range of elements to be handled.  */
2999   int from, to;
3000   /* A flag to tell if a leaf in this level of char-table is not a
3001      generic character (i.e. a complete multibyte character).  */
3002   int complete_char;
3003   int character;
3004   int starting_i;
3005
3006   suppress = Qnil;
3007
3008   if (indices == 0)
3009     indices = (int *) alloca (3 * sizeof (int));
3010
3011   definition = Qnil;
3012
3013   /* This vector gets used to present single keys to Flookup_key.  Since
3014      that is done once per vector element, we don't want to cons up a
3015      fresh vector every time.  */
3016   kludge = Fmake_vector (make_number (1), Qnil);
3017   GCPRO3 (elt_prefix, definition, kludge);
3018
3019   if (partial)
3020     suppress = intern ("suppress-keymap");
3021
3022   if (CHAR_TABLE_P (vector))
3023     {
3024       if (char_table_depth == 0)
3025         {
3026           /* VECTOR is a top level char-table.  */
3027           complete_char = 1;
3028           from = 0;
3029           to = CHAR_TABLE_ORDINARY_SLOTS;
3030         }
3031       else
3032         {
3033           /* VECTOR is a sub char-table.  */
3034           if (char_table_depth >= 3)
3035             /* A char-table is never that deep.  */
3036             error ("Too deep char table");
3037
3038           complete_char
3039             = (CHARSET_VALID_P (indices[0])
3040                && ((CHARSET_DIMENSION (indices[0]) == 1
3041                     && char_table_depth == 1)
3042                    || char_table_depth == 2));
3043
3044           /* Meaningful elements are from 32th to 127th.  */
3045           from = 32;
3046           to = SUB_CHAR_TABLE_ORDINARY_SLOTS;
3047         }
3048     }
3049   else
3050     {
3051       /* This does the right thing for ordinary vectors.  */
3052
3053       complete_char = 1;
3054       from = 0;
3055       to = XVECTOR (vector)->size;
3056     }
3057
3058   for (i = from; i < to; i++)
3059     {
3060       QUIT;
3061
3062       if (CHAR_TABLE_P (vector))
3063         {
3064           if (char_table_depth == 0 && i >= CHAR_TABLE_SINGLE_BYTE_SLOTS)
3065             complete_char = 0;
3066
3067           if (i >= CHAR_TABLE_SINGLE_BYTE_SLOTS
3068               && !CHARSET_DEFINED_P (i - 128))
3069             continue;
3070
3071           definition
3072             = get_keyelt (XCHAR_TABLE (vector)->contents[i], 0);
3073         }
3074       else
3075         definition = get_keyelt (AREF (vector, i), 0);
3076
3077       if (NILP (definition)) continue;
3078
3079       /* Don't mention suppressed commands.  */
3080       if (SYMBOLP (definition) && partial)
3081         {
3082           Lisp_Object tem;
3083
3084           tem = Fget (definition, suppress);
3085
3086           if (!NILP (tem)) continue;
3087         }
3088
3089       /* Set CHARACTER to the character this entry describes, if any.
3090          Also update *INDICES.  */
3091       if (CHAR_TABLE_P (vector))
3092         {
3093           indices[char_table_depth] = i;
3094
3095           if (char_table_depth == 0)
3096             {
3097               character = i;
3098               indices[0] = i - 128;
3099             }
3100           else if (complete_char)
3101             {
3102               character = MAKE_CHAR (indices[0], indices[1], indices[2]);
3103             }
3104           else
3105             character = 0;
3106         }
3107       else
3108         character = i;
3109
3110       /* If this binding is shadowed by some other map, ignore it.  */
3111       if (!NILP (shadow) && complete_char)
3112         {
3113           Lisp_Object tem;
3114
3115           ASET (kludge, 0, make_number (character));
3116           tem = shadow_lookup (shadow, kludge, Qt);
3117
3118           if (!NILP (tem)) continue;
3119         }
3120
3121       /* Ignore this definition if it is shadowed by an earlier
3122          one in the same keymap.  */
3123       if (!NILP (entire_map) && complete_char)
3124         {
3125           Lisp_Object tem;
3126
3127           ASET (kludge, 0, make_number (character));
3128           tem = Flookup_key (entire_map, kludge, Qt);
3129
3130           if (! EQ (tem, definition))
3131             continue;
3132         }
3133
3134       if (first)
3135         {
3136           if (char_table_depth == 0)
3137             insert ("\n", 1);
3138           first = 0;
3139         }
3140
3141       /* For a sub char-table, show the depth by indentation.
3142          CHAR_TABLE_DEPTH can be greater than 0 only for a char-table.  */
3143       if (char_table_depth > 0)
3144         insert ("    ", char_table_depth * 2); /* depth is 1 or 2.  */
3145
3146       /* Output the prefix that applies to every entry in this map.  */
3147       if (!NILP (elt_prefix))
3148         insert1 (elt_prefix);
3149
3150       /* Insert or describe the character this slot is for,
3151          or a description of what it is for.  */
3152       if (SUB_CHAR_TABLE_P (vector))
3153         {
3154           if (complete_char)
3155             insert_char (character);
3156           else
3157             {
3158               /* We need an octal representation for this block of
3159                  characters.  */
3160               char work[16];
3161               sprintf (work, "(row %d)", i);
3162               insert (work, strlen (work));
3163             }
3164         }
3165       else if (CHAR_TABLE_P (vector))
3166         {
3167           if (complete_char)
3168             insert1 (Fsingle_key_description (make_number (character), Qnil));
3169           else
3170             {
3171               /* Print the information for this character set.  */
3172               insert_string ("<");
3173               tem2 = CHARSET_TABLE_INFO (i - 128, CHARSET_SHORT_NAME_IDX);
3174               if (STRINGP (tem2))
3175                 insert_from_string (tem2, 0, 0, XSTRING (tem2)->size,
3176                                     STRING_BYTES (XSTRING (tem2)), 0);
3177               else
3178                 insert ("?", 1);
3179               insert (">", 1);
3180             }
3181         }
3182       else
3183         {
3184           insert1 (Fsingle_key_description (make_number (character), Qnil));
3185         }
3186
3187       /* If we find a sub char-table within a char-table,
3188          scan it recursively; it defines the details for
3189          a character set or a portion of a character set.  */
3190       if (CHAR_TABLE_P (vector) && SUB_CHAR_TABLE_P (definition))
3191         {
3192           insert ("\n", 1);
3193           describe_vector (definition, elt_prefix, elt_describer,
3194                            partial, shadow, entire_map,
3195                            indices, char_table_depth + 1);
3196           continue;
3197         }
3198
3199       starting_i = i;
3200
3201       /* Find all consecutive characters or rows that have the same
3202          definition.  But, for elements of a top level char table, if
3203          they are for charsets, we had better describe one by one even
3204          if they have the same definition.  */
3205       if (CHAR_TABLE_P (vector))
3206         {
3207           int limit = to;
3208
3209           if (char_table_depth == 0)
3210             limit = CHAR_TABLE_SINGLE_BYTE_SLOTS;
3211
3212           while (i + 1 < limit
3213                  && (tem2 = get_keyelt (XCHAR_TABLE (vector)->contents[i + 1], 0),
3214                      !NILP (tem2))
3215                  && !NILP (Fequal (tem2, definition)))
3216             i++;
3217         }
3218       else
3219         while (i + 1 < to
3220                && (tem2 = get_keyelt (AREF (vector, i + 1), 0),
3221                    !NILP (tem2))
3222                && !NILP (Fequal (tem2, definition)))
3223           i++;
3224
3225
3226       /* If we have a range of more than one character,
3227          print where the range reaches to.  */
3228
3229       if (i != starting_i)
3230         {
3231           insert (" .. ", 4);
3232
3233           if (!NILP (elt_prefix))
3234             insert1 (elt_prefix);
3235
3236           if (CHAR_TABLE_P (vector))
3237             {
3238               if (char_table_depth == 0)
3239                 {
3240                   insert1 (Fsingle_key_description (make_number (i), Qnil));
3241                 }
3242               else if (complete_char)
3243                 {
3244                   indices[char_table_depth] = i;
3245                   character = MAKE_CHAR (indices[0], indices[1], indices[2]);
3246                   insert_char (character);
3247                 }
3248               else
3249                 {
3250                   /* We need an octal representation for this block of
3251                      characters.  */
3252                   char work[16];
3253                   sprintf (work, "(row %d)", i);
3254                   insert (work, strlen (work));
3255                 }
3256             }
3257           else
3258             {
3259               insert1 (Fsingle_key_description (make_number (i), Qnil));
3260             }
3261         }
3262
3263       /* Print a description of the definition of this character.
3264          elt_describer will take care of spacing out far enough
3265          for alignment purposes.  */
3266       (*elt_describer) (definition);
3267     }
3268
3269   /* For (sub) char-table, print `defalt' slot at last.  */
3270   if (CHAR_TABLE_P (vector) && !NILP (XCHAR_TABLE (vector)->defalt))
3271     {
3272       insert ("    ", char_table_depth * 2);
3273       insert_string ("<<default>>");
3274       (*elt_describer) (XCHAR_TABLE (vector)->defalt);
3275     }
3276
3277   UNGCPRO;
3278 }
3279 \f
3280 /* Apropos - finding all symbols whose names match a regexp.            */
3281 Lisp_Object apropos_predicate;
3282 Lisp_Object apropos_accumulate;
3283
3284 static void
3285 apropos_accum (symbol, string)
3286      Lisp_Object symbol, string;
3287 {
3288   register Lisp_Object tem;
3289
3290   tem = Fstring_match (string, Fsymbol_name (symbol), Qnil);
3291   if (!NILP (tem) && !NILP (apropos_predicate))
3292     tem = call1 (apropos_predicate, symbol);
3293   if (!NILP (tem))
3294     apropos_accumulate = Fcons (symbol, apropos_accumulate);
3295 }
3296
3297 DEFUN ("apropos-internal", Fapropos_internal, Sapropos_internal, 1, 2, 0,
3298   "Show all symbols whose names contain match for REGEXP.\n\
3299 If optional 2nd arg PREDICATE is non-nil, (funcall PREDICATE SYMBOL) is done\n\
3300 for each symbol and a symbol is mentioned only if that returns non-nil.\n\
3301 Return list of symbols found.")
3302   (regexp, predicate)
3303      Lisp_Object regexp, predicate;
3304 {
3305   struct gcpro gcpro1, gcpro2;
3306   CHECK_STRING (regexp, 0);
3307   apropos_predicate = predicate;
3308   GCPRO2 (apropos_predicate, apropos_accumulate);
3309   apropos_accumulate = Qnil;
3310   map_obarray (Vobarray, apropos_accum, regexp);
3311   apropos_accumulate = Fsort (apropos_accumulate, Qstring_lessp);
3312   UNGCPRO;
3313   return apropos_accumulate;
3314 }
3315 \f
3316 void
3317 syms_of_keymap ()
3318 {
3319   Qkeymap = intern ("keymap");
3320   staticpro (&Qkeymap);
3321
3322   /* Now we are ready to set up this property, so we can
3323      create char tables.  */
3324   Fput (Qkeymap, Qchar_table_extra_slots, make_number (0));
3325
3326   /* Initialize the keymaps standardly used.
3327      Each one is the value of a Lisp variable, and is also
3328      pointed to by a C variable */
3329
3330   global_map = Fmake_keymap (Qnil);
3331   Fset (intern ("global-map"), global_map);
3332
3333   current_global_map = global_map;
3334   staticpro (&global_map);
3335   staticpro (&current_global_map);
3336
3337   meta_map = Fmake_keymap (Qnil);
3338   Fset (intern ("esc-map"), meta_map);
3339   Ffset (intern ("ESC-prefix"), meta_map);
3340
3341   control_x_map = Fmake_keymap (Qnil);
3342   Fset (intern ("ctl-x-map"), control_x_map);
3343   Ffset (intern ("Control-X-prefix"), control_x_map);
3344
3345   DEFVAR_LISP ("define-key-rebound-commands", &Vdefine_key_rebound_commands,
3346     "List of commands given new key bindings recently.\n\
3347 This is used for internal purposes during Emacs startup;\n\
3348 don't alter it yourself.");
3349   Vdefine_key_rebound_commands = Qt;
3350
3351   DEFVAR_LISP ("minibuffer-local-map", &Vminibuffer_local_map,
3352     "Default keymap to use when reading from the minibuffer.");
3353   Vminibuffer_local_map = Fmake_sparse_keymap (Qnil);
3354
3355   DEFVAR_LISP ("minibuffer-local-ns-map", &Vminibuffer_local_ns_map,
3356     "Local keymap for the minibuffer when spaces are not allowed.");
3357   Vminibuffer_local_ns_map = Fmake_sparse_keymap (Qnil);
3358
3359   DEFVAR_LISP ("minibuffer-local-completion-map", &Vminibuffer_local_completion_map,
3360     "Local keymap for minibuffer input with completion.");
3361   Vminibuffer_local_completion_map = Fmake_sparse_keymap (Qnil);
3362
3363   DEFVAR_LISP ("minibuffer-local-must-match-map", &Vminibuffer_local_must_match_map,
3364     "Local keymap for minibuffer input with completion, for exact match.");
3365   Vminibuffer_local_must_match_map = Fmake_sparse_keymap (Qnil);
3366
3367   DEFVAR_LISP ("minor-mode-map-alist", &Vminor_mode_map_alist,
3368     "Alist of keymaps to use for minor modes.\n\
3369 Each element looks like (VARIABLE . KEYMAP); KEYMAP is used to read\n\
3370 key sequences and look up bindings iff VARIABLE's value is non-nil.\n\
3371 If two active keymaps bind the same key, the keymap appearing earlier\n\
3372 in the list takes precedence.");
3373   Vminor_mode_map_alist = Qnil;
3374
3375   DEFVAR_LISP ("minor-mode-overriding-map-alist", &Vminor_mode_overriding_map_alist,
3376     "Alist of keymaps to use for minor modes, in current major mode.\n\
3377 This variable is a alist just like `minor-mode-map-alist', and it is\n\
3378 used the same way (and before `minor-mode-map-alist'); however,\n\
3379 it is provided for major modes to bind locally.");
3380   Vminor_mode_overriding_map_alist = Qnil;
3381
3382   DEFVAR_LISP ("function-key-map", &Vfunction_key_map,
3383   "Keymap mapping ASCII function key sequences onto their preferred forms.\n\
3384 This allows Emacs to recognize function keys sent from ASCII\n\
3385 terminals at any point in a key sequence.\n\
3386 \n\
3387 The `read-key-sequence' function replaces any subsequence bound by\n\
3388 `function-key-map' with its binding.  More precisely, when the active\n\
3389 keymaps have no binding for the current key sequence but\n\
3390 `function-key-map' binds a suffix of the sequence to a vector or string,\n\
3391 `read-key-sequence' replaces the matching suffix with its binding, and\n\
3392 continues with the new sequence.\n\
3393 \n\
3394 The events that come from bindings in `function-key-map' are not\n\
3395 themselves looked up in `function-key-map'.\n\
3396 \n\
3397 For example, suppose `function-key-map' binds `ESC O P' to [f1].\n\
3398 Typing `ESC O P' to `read-key-sequence' would return [f1].  Typing\n\
3399 `C-x ESC O P' would return [?\\C-x f1].  If [f1] were a prefix\n\
3400 key, typing `ESC O P x' would return [f1 x].");
3401   Vfunction_key_map = Fmake_sparse_keymap (Qnil);
3402
3403   DEFVAR_LISP ("key-translation-map", &Vkey_translation_map,
3404     "Keymap of key translations that can override keymaps.\n\
3405 This keymap works like `function-key-map', but comes after that,\n\
3406 and applies even for keys that have ordinary bindings.");
3407   Vkey_translation_map = Qnil;
3408
3409   Qsingle_key_description = intern ("single-key-description");
3410   staticpro (&Qsingle_key_description);
3411
3412   Qkey_description = intern ("key-description");
3413   staticpro (&Qkey_description);
3414
3415   Qkeymapp = intern ("keymapp");
3416   staticpro (&Qkeymapp);
3417
3418   Qnon_ascii = intern ("non-ascii");
3419   staticpro (&Qnon_ascii);
3420
3421   Qmenu_item = intern ("menu-item");
3422   staticpro (&Qmenu_item);
3423
3424   where_is_cache_keymaps = Qt;
3425   where_is_cache = Qnil;
3426   staticpro (&where_is_cache);
3427   staticpro (&where_is_cache_keymaps);
3428
3429   defsubr (&Skeymapp);
3430   defsubr (&Skeymap_parent);
3431   defsubr (&Sset_keymap_parent);
3432   defsubr (&Smake_keymap);
3433   defsubr (&Smake_sparse_keymap);
3434   defsubr (&Scopy_keymap);
3435   defsubr (&Skey_binding);
3436   defsubr (&Slocal_key_binding);
3437   defsubr (&Sglobal_key_binding);
3438   defsubr (&Sminor_mode_key_binding);
3439   defsubr (&Sdefine_key);
3440   defsubr (&Slookup_key);
3441   defsubr (&Sdefine_prefix_command);
3442   defsubr (&Suse_global_map);
3443   defsubr (&Suse_local_map);
3444   defsubr (&Scurrent_local_map);
3445   defsubr (&Scurrent_global_map);
3446   defsubr (&Scurrent_minor_mode_maps);
3447   defsubr (&Saccessible_keymaps);
3448   defsubr (&Skey_description);
3449   defsubr (&Sdescribe_vector);
3450   defsubr (&Ssingle_key_description);
3451   defsubr (&Stext_char_description);
3452   defsubr (&Swhere_is_internal);
3453   defsubr (&Sdescribe_bindings_internal);
3454   defsubr (&Sapropos_internal);
3455 }
3456
3457 void
3458 keys_of_keymap ()
3459 {
3460   initial_define_key (global_map, 033, "ESC-prefix");
3461   initial_define_key (global_map, Ctl('X'), "Control-X-prefix");
3462 }