bug#34823: 27.0.50; re-search-forward infloop

bug#34823: 27.0.50; re-search-forward infloop

[Vitalie Spinu]

Hi,

In the context of markdown-mode I am seeing a font-lock infloop with a
relatively simple regexp:

 1) emacs -Q
 2) open a buffer with the following line

   "$_\t$tmp\t$cat\t$donor\t$stage\t$pool\t$rep\t$time\t$comment"'

 3) at bol eval (re-search-forward "\\(\\w[^\n]*\\)+}")
    which infloops

I see it with emacs 25, 26 and 27.0.5.

  Vitalie

----

In GNU Emacs 27.0.50 (build 7, x86_64-pc-linux-gnu, GTK+ Version 3.22.30)
 of 2018-08-31 built on Galago
Repository revision: 244b6827257fb0ec9c14f19b9dd01a0e1bee1d75
Windowing system distributor 'The X.Org Foundation', version 11.0.11906000
System Description: Ubuntu 18.04.1 LTS

Recent messages:
For information about GNU Emacs and the GNU system, type C-h C-a.
(New file)
Mark set
Quit [2 times]
Mark activated [4 times]
ido-read-internal: Command attempted to use minibuffer while in minibuffer
Quit [3 times]
ido-read-internal: Command attempted to use minibuffer while in minibuffer
Quit [2 times]
ad-Advice-delete-char: Text is read-only [3 times]

Configured features:
XPM JPEG TIFF GIF PNG RSVG IMAGEMAGICK SOUND GPM DBUS GSETTINGS NOTIFY
ACL LIBSELINUX GNUTLS LIBXML2 FREETYPE M17N_FLT LIBOTF XFT ZLIB
TOOLKIT_SCROLL_BARS GTK3 X11 THREADS LCMS2

Important settings:
  value of $LC_MONETARY: nl_NL.UTF-8
  value of $LC_NUMERIC: nl_NL.UTF-8
  value of $LC_TIME: en_DK.UTF-8
  value of $LANG: en_GB.UTF-8
  locale-coding-system: utf-8-unix

Major mode: Fundamental

Minor modes in effect:
  smartparens-global-mode: t
  smartparens-mode: t
  TeX-PDF-mode: t
  helm-cider-mode: t
  global-eclim-mode: t
  display-time-mode: t
  helm-descbinds-mode: t
  openwith-mode: t
  pdf-occur-global-minor-mode: t
  global-edit-server-edit-mode: t
  global-company-mode: t
  company-mode: t
  ido-ubiquitous-mode: t
  save-place-mode: t
  shell-dirtrack-mode: t
  projectile-mode: t
  global-semantic-idle-completions-mode: t
  global-semantic-idle-summary-mode: t
  show-paren-mode: t
  savehist-mode: t
  global-auto-revert-mode: t
  beacon-mode: t
  override-global-mode: t
  global-subword-mode: t
  subword-mode: t
  ido-everywhere: t
  cl-old-struct-compat-mode: t
  tooltip-mode: t
  global-eldoc-mode: t
  electric-indent-mode: t
  mouse-wheel-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
  size-indication-mode: t
  column-number-mode: t
  line-number-mode: t
  transient-mark-mode: t

Load-path shadows:
/home/vspinu/Dropbox/ELPA/math-symbol-lists-20170221.1353/math-symbol-lists hides ~/dev/math-symbol-lists/math-symbol-lists
/home/vspinu/Dropbox/ELPA/math-symbol-lists-20170221.1353/msl-build hides ~/dev/math-symbol-lists/msl-build
/home/vspinu/Dropbox/ELPA/key-combo-20150324.1439/key-combo hides ~/dev/key-combo/key-combo
/home/vspinu/Dropbox/ELPA/company-math-20171016.1514/company-math hides ~/VC/company-math/company-math
/home/vspinu/Dropbox/ELPA/smartparens-20181007.1501/smartparens hides ~/VC/smartparens/smartparens
/home/vspinu/Dropbox/ELPA/smartparens-20181007.1501/smartparens-html hides ~/VC/smartparens/smartparens-html
/home/vspinu/Dropbox/ELPA/smartparens-20181007.1501/smartparens-lua hides ~/VC/smartparens/smartparens-lua
/home/vspinu/Dropbox/ELPA/smartparens-20181007.1501/smartparens-scala hides ~/VC/smartparens/smartparens-scala
/home/vspinu/Dropbox/ELPA/smartparens-20181007.1501/smartparens-clojure hides ~/VC/smartparens/smartparens-clojure
/home/vspinu/Dropbox/ELPA/smartparens-20181007.1501/smartparens-config hides ~/VC/smartparens/smartparens-config
/home/vspinu/Dropbox/ELPA/smartparens-20181007.1501/smartparens-ruby hides ~/VC/smartparens/smartparens-ruby
/home/vspinu/Dropbox/ELPA/smartparens-20181007.1501/smartparens-rust hides ~/VC/smartparens/smartparens-rust
/home/vspinu/Dropbox/ELPA/smartparens-20181007.1501/smartparens-python hides ~/VC/smartparens/smartparens-python
/home/vspinu/Dropbox/ELPA/smartparens-20181007.1501/smartparens-racket hides ~/VC/smartparens/smartparens-racket
/home/vspinu/Dropbox/ELPA/smartparens-20181007.1501/smartparens-haskell hides ~/VC/smartparens/smartparens-haskell
/home/vspinu/Dropbox/ELPA/smartparens-20181007.1501/smartparens-latex hides ~/VC/smartparens/smartparens-latex
/home/vspinu/Dropbox/ELPA/smartparens-20181007.1501/smartparens-pkg hides ~/VC/smartparens/smartparens-pkg
/home/vspinu/Dropbox/ELPA/spinner-1.7.3/spinner hides ~/VC/spinner.el/spinner
/home/vspinu/Dropbox/ELPA/epl-20180205.2049/epl hides ~/VC/epl/epl
/home/vspinu/Dropbox/ELPA/dash-20180903.1042/dash hides ~/VC/dash.el/dash
/home/vspinu/Dropbox/ELPA/pkg-info-20150517.1143/pkg-info hides ~/VC/pkg-info.el/pkg-info
/home/vspinu/Dropbox/ELPA/projectile-20180824.2239/projectile hides ~/VC/projectile/projectile
/home/vspinu/Dropbox/ELPA/auto-complete-20170125.245/auto-complete-pkg hides ~/VC/auto-complete/auto-complete-pkg
/home/vspinu/Dropbox/ELPA/auto-complete-20170125.245/auto-complete-config hides ~/VC/auto-complete/auto-complete-config
/home/vspinu/Dropbox/ELPA/auto-complete-20170125.245/auto-complete hides ~/VC/auto-complete/auto-complete
/home/vspinu/Dropbox/ELPA/color-theme-solarized-20171024.1525/solarized-theme hides ~/VC/solarized-emacs/solarized-theme
/home/vspinu/Dropbox/ELPA/queue-0.2/queue hides ~/Dropbox/.emacs.d/queue
~/VC/markdown-mode/markdown-mode hides ~/Dropbox/.emacs.d/markdown-mode
/home/vspinu/Dropbox/ELPA/rebox2-20121113.2100/rebox2 hides ~/Dropbox/.emacs.d/rebox2
~/Dropbox/.emacs.d/allout-widgets hides /home/vspinu/bin/emacs/lisp/allout-widgets
~/Dropbox/.emacs.d/allout hides /home/vspinu/bin/emacs/lisp/allout
/home/vspinu/Dropbox/ELPA/less-css-mode-20161001.453/less-css-mode hides /home/vspinu/bin/emacs/lisp/textmodes/less-css-mode
~/Dropbox/.emacs.d/org-protocol hides /home/vspinu/bin/emacs/lisp/org/org-protocol
~/Dropbox/.emacs.d/tabulated-list hides /home/vspinu/bin/emacs/lisp/emacs-lisp/tabulated-list

Features:
(shadow sort mail-extr emacsbug message rmc puny rfc822 mml mml-sec epa
epg gnus-util rmail rmail-loaddefs mm-decode mm-bodies mm-encode
mail-parse rfc2231 mailabbrev gmm-utils mailheader sendmail rfc2047
rfc2045 ietf-drums mm-util mail-prsvr mail-utils smex aggressive-indent
rainbow-delimiters bug-reference pig-snippets yasnippet-snippets
yasnippet elec-pair server hc-zenburn-theme eldoc-eval zotelo vlf
vlf-base vlf-tune my-smartparens-config smartparens-config
smartparens-ruby smartparens-org smartparens-markdown smartparens-text
smartparens-latex smartparens-html smartparens-ess smartparens-clojure
smartparens polymode-test-utils ert ewoc debug polymode-debug trace
poly-erb poly-rst rst poly-org poly-slim slim-mode ruby-mode poly-R
poly-markdown poly-noweb polymode poly-lock polymode-base polymode-weave
polymode-export polymode-compat polymode-methods polymode-core
polymode-classes eieio-custom eieio-base markdown-mode ess-site
ess-toolbar ess-mouse mouseme ess-jags-d ess-bugs-l essd-els
ess-stata-mode ess-stata-lang make-regexp ess-sas-d ess-sas-l ess-sas-a
ess-julia julia-mode latex latex-flymake tex-ispell tex-style
reftex-cite reftex reftex-loaddefs reftex-vars tex dbus crm ess-r-mode
ess-r-flymake flymake-proc flymake ess-r-xref ess-r-package
ess-r-completion ess-roxy ess-r-syntax ess-rd hideshow ess-sp6-d
ess-trns ess-s-lang ess-help ess-mode ess-inf ess-tracebug ess ess-utils
ess-custom cider-ns cider-find helm-cider helm-cider-spec
helm-cider-repl helm-cider-cheatsheet helm-cider-util cider-cheatsheet
cider-decompile javap-mode cider-apropos apropos cider-macroexpansion
cider-selector cider-scratch cider cider-debug cider-browse-ns
cider-inspector cider-mode cider-completion cider-profile cider-eval
cider-repl-history pulse cider-repl cider-resolve cider-test
cider-overlays cider-stacktrace cider-doc cider-browse-spec org-table
cider-grimoire cider-popup cider-eldoc cider-client cider-common
cider-util color cider-connection sesman-browser sesman vc vc-dispatcher
nrepl-client queue nrepl-dict cider-compat spinner clojure-mode derived
lisp-mnt align company-emacs-eclim eclim-completion eclimd eclim
eclim-debug gud eclim-java-run eclim-problems popup eclim-maven
eclim-ant eclim-java dash eclim-project sh-script smie executable
ob-latex ob-R time appt diary-lib diary-loaddefs org-clock org-agenda
org-element avl-tree generator org org-macro org-footnote org-pcomplete
org-list org-faces org-entities noutline outline org-version
ob-emacs-lisp ob ob-tangle org-src ob-ref ob-lob ob-table ob-keys ob-exp
ob-comint ob-core ob-eval org-compat org-macs org-loaddefs cal-menu
calendar cal-loaddefs iimage helm-dash helm-descbinds helm-net
browse-url xml url url-proxy url-privacy url-expand url-methods
url-history url-cookie url-domsuf url-util mailcap sgml-mode dom
openwith pdf-occur tablist tablist-filter semantic/wisent/comp
semantic/wisent semantic/wisent/wisent dired dired-loaddefs pdf-isearch
let-alist pdf-misc pdf-tools pdf-view bookmark pp jka-compr pdf-cache
pdf-info tq pdf-util image-mode edit-server company-math company-oddmuse
company-keywords company-etags etags xref project company-gtags
company-dabbrev-code company-dabbrev company-files company-capf
company-cmake company-xcode company-clang company-semantic company-eclim
company-template company-bbdb company math-symbol-lists
ido-completing-read+ memoize s cus-edit minibuf-eldef saveplace
helm-projectile helm-files helm-tags helm-buffers helm-grep wgrep-helm
wgrep helm-regexp helm-locate helm-types helm-imenu helm-utils helm-help
helm helm-source eieio-compat helm-multi-match helm-lib async tramp-sh
docker-tramp tramp-cache tramp trampver tramp-compat tramp-loaddefs
ucs-normalize shell pcomplete parse-time format-spec projectile subr-x
grep ffap thingatpt langtool pcase compile comint ansi-color ring
flyspell ispell smart-mode-line-dark-theme smart-mode-line rich-minority
menu-bar+ cl-extra help-mode recentf tree-widget wid-edit ibuf-ext
ibuffer ibuffer-loaddefs semantic/idle semantic/format ezimage
semantic/tag-ls semantic/find semantic/ctxt semantic/util-modes
semantic/util semantic semantic/tag semantic/lex semantic/fw mode-local
find-func cedet paren savehist autorevert filenotify beacon cus-start
cus-load diminish use-package use-package-ensure use-package-delight
use-package-diminish use-package-bind-key bind-key use-package-core
tex-site clojurescript-mode-autoloads csv-mode-autoloads esk-autoloads
idle-highlight-mode-autoloads rx logito-autoloads memory-usage-autoloads
advice rainbow-mode-autoloads rebox2-autoloads sml-mode-autoloads
windresize-autoloads info warnings key-combo easy-mmode cl desktop
frameset filesets cap-words superword subword delsel ido imenu-anywhere
imenu iflipb edmacro kmacro finder-inf package easymenu epg-config
url-handlers url-parse auth-source cl-seq eieio eieio-core cl-macs
eieio-loaddefs password-cache json map url-vars seq byte-opt gv bytecomp
byte-compile cconv cl-loaddefs cl-lib time-date mule-util 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 menu-bar rfn-eshadow isearch timer select
scroll-bar mouse jit-lock font-lock syntax facemenu font-core
term/tty-colors frame 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 minibuffer cl-preloaded nadvice loaddefs
button faces cus-face macroexp files 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 move-toolbar gtk x-toolkit x
multi-tty make-network-process emacs)

Memory information:
((conses 16 972819 26432)
 (symbols 48 68247 1)
 (miscs 40 129 226)
 (strings 32 246201 16927)
 (string-bytes 1 6790923)
 (vectors 16 92395)
 (vector-slots 8 1708820 15212)
 (floats 8 481 583)
 (intervals 56 4552 46)
 (buffers 992 16))

bug#34823: 27.0.50; re-search-forward infloop

[Mattias Engdegård]

It is not actually an infinite loop; it just takes a very long time.

Your case is, more or less, essentially

(search-string "\\(?:a*\\)*b" "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa")

Try trimming the string, and you will see that the match does terminate (and fail); it is just super-linear in the length of the text.
This is a shortcoming of the general type of regexp engine used by Emacs.

To work around your problem, you should make the regexp less prone to backtracking. Try asking on the list help-gnu-emacs@gnu.org for advice. Describe what text you wish to match as precisely as possible.