Subject: bug#48812: 28.0.50; describe-bindings stucks and gets high CPU load

From: Naofumi Yasufuku <[email-masked]>
Date: Fri, 4 Jun 2021 00:06:55 +0900

This describe-bindings stuck is caused by millions of shadow_lookup() calls
in src/keymap.c describe_vector().

------------------------------------------------------------------------
$ ./src/emacs
describe_vector] shadow_lookup loop START: definition=self-insert-command shadowed_by=nil starting_i=128 i=4194175
describe_vector] shadow_lookup loop END:   definition=self-insert-command shadowed_by=nil starting_i=128 i=4194175
describe_vector] shadow_lookup loop START: definition=self-insert-command shadowed_by=nil starting_i=4194176 i=4194303
describe_vector] shadow_lookup loop END:   definition=self-insert-command shadowed_by=nil starting_i=4194176 i=4194303
describe_vector] shadow_lookup loop START: definition=digit-argument shadowed_by=nil starting_i=48 i=57
describe_vector] shadow_lookup loop END:   definition=digit-argument shadowed_by=nil starting_i=48 i=57
$ 
------------------------------------------------------------------------
diff --git a/src/keymap.c b/src/keymap.c
index fb8eceaec1..0efa78ce9b 100644
--- a/src/keymap.c
+++ b/src/keymap.c
@@ -3065,6 +3065,11 @@ describe_vector (Lisp_Object vector, Lisp_Object prefix, Lisp_Object args,
       if (CHAR_TABLE_P (vector) && i != starting_i)
 	{
 	  Lisp_Object key = make_nil_vector (1);
+	  fprintf (stderr, "%s] shadow_lookup loop START: definition=%s shadowed_by=%s starting_i=%d i=%d\n",
+		   __func__,
+		   SDATA (SYMBOL_NAME (definition)),
+		   SDATA (SYMBOL_NAME (shadowed_by)),
+		   starting_i, i);
 	  for (int j = starting_i + 1; j <= i; j++)
 	    {
 	      ASET (key, 0, make_fixnum (j));
@@ -3072,6 +3077,11 @@ describe_vector (Lisp_Object vector, Lisp_Object prefix, Lisp_Object args,
 	      if (NILP (Fequal (tem, shadowed_by)))
 		i = j - 1;
 	    }
+	  fprintf (stderr, "%s] shadow_lookup loop END:   definition=%s shadowed_by=%s starting_i=%d i=%d\n",
+		   __func__,
+		   SDATA (SYMBOL_NAME (definition)),
+		   SDATA (SYMBOL_NAME (shadowed_by)),
+		   starting_i, i);
 	}
 
       /* If we have a range of more than one character,
------------------------------------------------------------------------

This shadow_lookup() loop was introduced by the following commit:

------------------------------------------------------------------------
commit a6490343366f2b2331a91dcb693effb3a9dd78f5
Author: Stefan Kangas <[email-masked]>
Date:   Fri Nov 13 15:28:29 2020 +0100

    Don't show key ranges if shadowed by different commands

    * src/keymap.c (describe_vector): Make sure found consecutive keys
    are either not shadowed or, if they are, that they are shadowed by
    the same command.  (Bug#9293)
    * test/src/keymap-tests.el
    (help--describe-vector/bug-9293-one-shadowed-in-range): New test.

------------------------------------------------------------------------

In GNU Emacs 28.0.50 (build 3, aarch64-unknown-linux-gnu, GTK+ Version 3.24.25, cairo version 1.16.0)
 of 2021-06-03 built on phoebe
Repository revision: 089e0c4c55dcf72f9cf2f6f04b8a52fc7355499c
Repository branch: master
Windowing system distributor 'The X.Org Foundation', version 11.0.12101001
System Description: Ubuntu 21.04

Configured features:
CAIRO DBUS FREETYPE GIF GLIB GMP GNUTLS GPM GSETTINGS HARFBUZZ JPEG JSON
LCMS2 LIBSELINUX LIBSYSTEMD LIBXML2 MODULES NOTIFY INOTIFY PDUMPER PNG
RSVG SECCOMP SOUND THREADS TIFF TOOLKIT_SCROLL_BARS X11 XDBE XIM XPM
GTK3 ZLIB

Important settings:
  value of $LANG: en_US.UTF-8
  value of $XMODIFIERS: @im=ibus
  locale-coding-system: utf-8-unix

Major mode: C/*l

Minor modes in effect:
  bug-reference-prog-mode: t
  tooltip-mode: t
  global-eldoc-mode: t
  electric-indent-mode: t
  mouse-wheel-mode: t
  tool-bar-mode: t
  menu-bar-mode: t
  file-name-shadow-mode: t
  global-font-lock-mode: t
  font-lock-mode: t
  blink-cursor-mode: t
  auto-composition-mode: t
  auto-encryption-mode: t
  auto-compression-mode: t
  line-number-mode: t
  transient-mark-mode: t
  abbrev-mode: t

Load-path shadows:
None found.

Features:
(shadow sort mail-extr emacsbug message rmc puny rfc822 mml mml-sec epa
derived epg epg-config gnus-util rmail rmail-loaddefs auth-source cl-seq
eieio eieio-core cl-macs eieio-loaddefs password-cache json map
text-property-search mm-decode mm-bodies mm-encode mail-parse rfc2231
mailabbrev gmm-utils mailheader sendmail rfc2047 rfc2045 ietf-drums
mm-util mail-prsvr mail-utils vc-git diff-mode easy-mmode vc
vc-dispatcher bug-reference cc-mode cc-fonts cc-guess cc-menus cc-cmds
cc-styles cc-align cc-engine cc-vars cc-defs misearch multi-isearch
dired-aux dired dired-loaddefs time-date subr-x cl-extra seq byte-opt gv
bytecomp byte-compile cconv kmacro two-column help-mode cl-loaddefs
cl-lib iso-transl tooltip eldoc electric uniquify ediff-hook vc-hooks
lisp-float-type mwheel term/x-win x-win term/common-win x-dnd tool-bar
dnd fontset image regexp-opt fringe tabulated-list replace newcomment
text-mode elisp-mode lisp-mode prog-mode register page tab-bar menu-bar
rfn-eshadow isearch easymenu timer select scroll-bar mouse jit-lock
font-lock syntax font-core term/tty-colors frame minibuffer cl-generic
cham georgian utf-8-lang misc-lang vietnamese tibetan thai tai-viet lao
korean japanese eucjp-ms cp51932 hebrew greek romanian slovak czech
european ethiopic indian cyrillic chinese composite charscript charprop
case-table epa-hook jka-cmpr-hook help simple abbrev obarray
cl-preloaded nadvice button loaddefs faces cus-face macroexp files
window text-properties overlay sha1 md5 base64 format env code-pages
mule custom widget hashtable-print-readable backquote threads dbusbind
inotify lcms2 dynamic-setting system-font-setting font-render-setting
cairo move-toolbar gtk x-toolkit x multi-tty make-network-process emacs)

Memory information:
((conses 16 118009 7881)
 (symbols 48 9308 1)
 (strings 32 27924 2053)
 (string-bytes 1 1038142)
 (vectors 16 18491)
 (vector-slots 8 227657 9510)
 (floats 8 31 163)
 (intervals 56 10630 0)
 (buffers 992 14))