bug#41155: 26.3; regexp 99% locks up emacs

bug#41155: 26.3; regexp 99% locks up emacs

[jan via Bug reports for GNU Emacs, the Swiss army knife of text editors]

Hi all,
was trying to use highlight-regexp, locked up emacs. Turns out it's not
entirely locked up.
To reproduce:

Start emacs with -Q

Switch to *scratch* buffer. Type (below the existing text that comes
with *scratch*)

hello
world

Do highlight-regexp:

M-s h r  \(.+\)\{,50\}\1\{,50\}\1  RET

It seemingly locks.  Process goes to 100% of one core and stays there.
C-g will not (apparently) stop it

Note that if you completely clear the scratch buffer beforehand it
seems to be OK.

I originally put it down to the regexp being clearly pathalogical but I
don't believe it's that, at least not the whole story. Left long enough
some highlighting will happen (maybe not with this particular text but
I've seen it happen), so it seems to have succeeded, but it still
appears locked up (100% cpu, unresponsive to keyboard).  C-g in fact
does do something; move the cursor as normal and it will appear stuck
(cursor doesn't move), however type C-g repeatedly and the cursor will
start to move.  Process will stay at 100% though. At no point will C-g
restore it to normal behaviour.

Tried the same on ubuntu (except did not start it -Q), same result.

Can reproduce?

cheers

jan


In GNU Emacs 26.3 (build 1, x86_64-w64-mingw32)
 of 2019-08-29 built on CIRROCUMULUS
Repository revision: 96dd0196c28bc36779584e47fffcca433c9309cd
Windowing system distributor 'Microsoft Corp.', version 6.1.7601
Recent messages:
Loading desktop...done
Warning: desktop file appears to be in use by PID 3000.
Using it may cause conflicts.  Use it anyway? (y or n) n
Desktop file in use; not loaded.
For information about GNU Emacs and the GNU system, type C-h C-a.
Making completion list... [2 times]

Configured using:
 'configure --without-dbus --host=x86_64-w64-mingw32
 --without-compress-install 'CFLAGS=-O2 -static -g3''

Configured features:
XPM JPEG TIFF GIF PNG RSVG SOUND NOTIFY ACL GNUTLS LIBXML2 ZLIB
TOOLKIT_SCROLL_BARS THREADS LCMS2

Important settings:
  value of $LANG: ENG
  locale-coding-system: cp1252

Major mode: Lisp Interaction

Minor modes in effect:
  desktop-save-mode: t
  tooltip-mode: t
  global-eldoc-mode: t
  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
  auto-composition-mode: t
  auto-encryption-mode: t
  auto-compression-mode: t
  line-number-mode: t
  transient-mark-mode: t

Load-path shadows:
None found.

Features:
(shadow sort mail-extr emacsbug message rmc puny dired dired-loaddefs
rfc822 mml mml-sec epa derived 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 elec-pair helm-gtags subr-x pulse which-func imenu helm-files
helm-buffers helm-occur helm-tags helm-locate helm-grep helm-regexp
format-spec helm-utils helm-help helm-types helm easy-mmode helm-source
eieio-compat helm-multi-match helm-lib async edmacro kmacro desktop
frameset cus-start cus-load finder-inf info package easymenu epg-config
url-handlers url-parse auth-source cl-seq eieio eieio-core cl-macs
eieio-loaddefs password-cache 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 dos-w32
ls-lisp disp-table term/w32-win w32-win w32-vars term/common-win
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 w32notify w32
lcms2 multi-tty make-network-process emacs)

Memory information:
((conses 16 156269 6137)
 (symbols 48 25959 1)
 (miscs 40 37 100)
 (strings 32 48072 1094)
 (string-bytes 1 1466455)
 (vectors 16 22867)
 (vector-slots 8 590863 3372)
 (floats 8 86 31)
 (intervals 56 248 18)
 (buffers 992 12))

bug#41155: 26.3; regexp 99% locks up emacs

[Paul Eggert]

> I originally put it down to the regexp being clearly pathalogical

Yes, that's pretty much it. Emacs uses a backtracking matcher and its worst case
performance is exponential. You can even use the matcher to solve Diophantine
integer equations ... verrrryy slowly; see:

http://blog.stevenlevithan.com/archives/algebra-with-regexes

So, don't do that. (Or if you *do* want to do that, fix the matcher - but good
luck with that....)

bug#41155: 26.3; regexp 99% locks up emacs

[jan via Bug reports for GNU Emacs, the Swiss army knife of text editors]

I'm not sure that's the whole issue though

1. C-g does not break out.   If emacs simply hands off to a
C-language-based regex engine and waits for it to return then that
*may* be inevitable but I don't know.

2. I've done a bit of experimenting just now and something doesn't add
up, I'll try to reproduce that tomorrow, draw some conclusions and
post here.

Thanks for the feedback. And the equation solver weirdness, which I'll
read in detail later!

thanks

jan

On 12/05/2020, Paul Eggert <eggert@cs.ucla.edu> wrote:
>> I originally put it down to the regexp being clearly pathalogical
>
> Yes, that's pretty much it. Emacs uses a backtracking matcher and its worst
> case
> performance is exponential. You can even use the matcher to solve
> Diophantine
> integer equations ... verrrryy slowly; see:
>
> http://blog.stevenlevithan.com/archives/algebra-with-regexes
>
> So, don't do that. (Or if you *do* want to do that, fix the matcher - but
> good
> luck with that....)
>

bug#41155: 26.3; regexp 99% locks up emacs

[jan via Bug reports for GNU Emacs, the Swiss army knife of text editors]

I've had more of a play, I see what you're saying and it makes sense.

It locks up because it's a pathological, but C-g *will* interrupt it.
My mistake was thinking it would cancel the highlight-regexp, but of
course it doesn't, emacs handles a few keyboard events then goes right
back to its inefficient scanning.

So I get a self-inflicted denial of service. That may be a problem but
it isn't the one I originally reported.

I'm not sure the regexp is in fact working correctly but I'll leave it for now.

Would someone consider this closing this issue please?

thanks

jan

On 12/05/2020, jan <rtm443x@googlemail.com> wrote:
> I'm not sure that's the whole issue though
>
> 1. C-g does not break out.   If emacs simply hands off to a
> C-language-based regex engine and waits for it to return then that
> *may* be inevitable but I don't know.
>
> 2. I've done a bit of experimenting just now and something doesn't add
> up, I'll try to reproduce that tomorrow, draw some conclusions and
> post here.
>
> Thanks for the feedback. And the equation solver weirdness, which I'll
> read in detail later!
>
> thanks
>
> jan
>
> On 12/05/2020, Paul Eggert <eggert@cs.ucla.edu> wrote:
>>> I originally put it down to the regexp being clearly pathalogical
>>
>> Yes, that's pretty much it. Emacs uses a backtracking matcher and its
>> worst
>> case
>> performance is exponential. You can even use the matcher to solve
>> Diophantine
>> integer equations ... verrrryy slowly; see:
>>
>> http://blog.stevenlevithan.com/archives/algebra-with-regexes
>>
>> So, don't do that. (Or if you *do* want to do that, fix the matcher - but
>> good
>> luck with that....)
>>
>

bug#41155: 26.3; regexp 99% locks up emacs

[Paul Eggert]

On 5/13/20 2:11 AM, jan wrote:

> Would someone consider this closing this issue please?

Sure, done. Thanks for following up.