Port accessible-keymaps

[brotzeit]

DEFUN ("accessible-keymaps", Faccessible_keymaps, Saccessible_keymaps,
       1, 2, 0,
       doc: /* Find all keymaps accessible via prefix characters from KEYMAP.
Returns a list of elements of the form (KEYS . MAP), where the sequence
KEYS starting from KEYMAP gets you to MAP.  These elements are ordered
so that the KEYS increase in length.  The first element is ([] . KEYMAP).
An optional argument PREFIX, if non-nil, should be a key sequence;
then the value includes only maps for prefixes that start with PREFIX.  */)
  (Lisp_Object keymap, Lisp_Object prefix)
{
  Lisp_Object maps, tail;
  EMACS_INT prefixlen = XFASTINT (Flength (prefix));

  if (!NILP (prefix))
    {
      /* If a prefix was specified, start with the keymap (if any) for
	 that prefix, so we don't waste time considering other prefixes.  */
      Lisp_Object tem;
      tem = Flookup_key (keymap, prefix, Qt);
      /* Flookup_key may give us nil, or a number,
	 if the prefix is not defined in this particular map.
	 It might even give us a list that isn't a keymap.  */
      tem = get_keymap (tem, 0, 0);
      /* If the keymap is autoloaded `tem' is not a cons-cell, but we still
	 want to return it.  */
      if (!NILP (tem))
	{
	  /* Convert PREFIX to a vector now, so that later on
	     we don't have to deal with the possibility of a string.  */
	  if (STRINGP (prefix))
	    {
	      int i, i_byte, c;
	      Lisp_Object copy;

	      copy = Fmake_vector (make_number (SCHARS (prefix)), Qnil);
	      for (i = 0, i_byte = 0; i < SCHARS (prefix);)
		{
		  int i_before = i;

		  FETCH_STRING_CHAR_ADVANCE (c, prefix, i, i_byte);
		  if (SINGLE_BYTE_CHAR_P (c) && (c & 0200))
		    c ^= 0200 | meta_modifier;
		  ASET (copy, i_before, make_number (c));
		}
	      prefix = copy;
	    }
	  maps = list1 (Fcons (prefix, tem));
	}
      else
	return Qnil;
    }
  else
    maps = list1 (Fcons (zero_vector, get_keymap (keymap, 1, 0)));

  /* For each map in the list maps,
     look at any other maps it points to,
     and stick them at the end if they are not already in the list.

     This is a breadth-first traversal, where tail is the queue of
     nodes, and maps accumulates a list of all nodes visited.  */

  for (tail = maps; CONSP (tail); tail = XCDR (tail))
    {
      struct accessible_keymaps_data data;
      register Lisp_Object thismap = Fcdr (XCAR (tail));
      Lisp_Object last;

      data.thisseq = Fcar (XCAR (tail));
      data.maps = maps;
      data.tail = tail;
      last = make_number (XINT (Flength (data.thisseq)) - 1);
      /* Does the current sequence end in the meta-prefix-char?  */
      data.is_metized = (XINT (last) >= 0
		    /* Don't metize the last char of PREFIX.  */
		    && XINT (last) >= prefixlen
		    && EQ (Faref (data.thisseq, last), meta_prefix_char));

      /* Since we can't run lisp code, we can't scan autoloaded maps.  */
      if (CONSP (thismap))
	map_keymap (thismap, accessible_keymaps_1, Qnil, &data, 0);
    }
  return maps;
}