GNU bug report logs - #20230
24.4.91; slow regexp

Previous Next

Package: emacs;

Reported by: Nicolas Richard <theonewiththeevillook <at> yahoo.fr>

Date: Mon, 30 Mar 2015 14:47:01 UTC

Severity: normal

Merged with 6640, 31817, 34823

Found in versions 23.2, 24.4.91, 27.0.50

To reply to this bug, email your comments to 20230 AT debbugs.gnu.org.

Toggle the display of automated, internal messages from the tracker.

View this report as an mbox folder, status mbox, maintainer mbox

Report forwarded to bug-gnu-emacs <at> gnu.org:
bug#20230; Package emacs. (Mon, 30 Mar 2015 14:47:01 GMT) Full text and rfc822 format available.
Acknowledgement sent to Nicolas Richard <theonewiththeevillook <at> yahoo.fr>:
New bug report received and forwarded. Copy sent to bug-gnu-emacs <at> gnu.org. (Mon, 30 Mar 2015 14:47:02 GMT) Full text and rfc822 format available.

Message #5 received at submit <at> debbugs.gnu.org (full text, mbox):

From: Nicolas Richard <theonewiththeevillook <at> yahoo.fr>
To: bug-gnu-emacs <at> gnu.org
Subject: 24.4.91; slow regexp
Date: Mon, 30 Mar 2015 16:46:45 +0200

Consider this snippet:

(with-temp-buffer
  (insert "**** foo\n")
  (insert ":PROPERTIES:\n")
  (dotimes (_ 7) (insert ":a:     \n"))
  (insert ":bar: foo\n\n:END:")
  (goto-char 10) ;; beginning of second line
  (looking-at "^[ 	]*:PROPERTIES:[ 	]*
\\(?:[ 	]*:\\S-+:\\(?: .*\\)?[ 	]*
\\)*[ 	]*:END:[ 	]*$"))

If that doesn't take several seconds, increasing the number 7 to 8, 9 or
more probably will. It does for me.

The regexp is one from org mode.

(It was suggested that a file this as a separate bug report in
http://debbugs.gnu.org/cgi/bugreport.cgi?bug=20191#28)

-- 
Nicolas
Information forwarded to bug-gnu-emacs <at> gnu.org:
bug#20230; Package emacs. (Sun, 26 Jun 2016 18:50:01 GMT) Full text and rfc822 format available.

Message #8 received at 20230 <at> debbugs.gnu.org (full text, mbox):

From: Noam Postavsky <npostavs <at> users.sourceforge.net>
To: 20230 <at> debbugs.gnu.org
Cc: Nicolas Richard <theonewiththeevillook <at> yahoo.fr>
Subject: Bug #20230: 24.4.91; slow regexp
Date: Sun, 26 Jun 2016 14:49:09 -0400

merge 6640 20230
quit

Same problem as http://debbugs.gnu.org/cgi/bugreport.cgi?bug=6640:
Emacs uses backtracking regexp engine, so when then you have a failing
regexp with repeated sub-parts that can match in many different ways,
you hit exponential behaviour. In this case

\\(?: .*\\)?[ ]*

can match a stretch of n spaces in n different ways, and since that
part is itself inside a * repetition, each those n ways has to be
tried on each line giving n^L runtime (where L is number of lines). A
faster regexp which should match the same is

  (looking-at "^[ \t]*:PROPERTIES:[ \t]*
\\(?:[ \t]*:\\S-+:[^\n]*
\\)*[ \t]*:END:[ \t]*$")
Merged 6640 20230. Request was from Noam Postavsky <npostavs <at> users.sourceforge.net> to control <at> debbugs.gnu.org. (Sun, 26 Jun 2016 18:50:02 GMT) Full text and rfc822 format available.
Merged 6640 20230 31817. Request was from Noam Postavsky <npostavs <at> gmail.com> to control <at> debbugs.gnu.org. (Sat, 16 Jun 2018 13:56:02 GMT) Full text and rfc822 format available.
Merged 6640 20230 31817 34823. Request was from Noam Postavsky <npostavs <at> gmail.com> to control <at> debbugs.gnu.org. (Tue, 02 Apr 2019 01:21:03 GMT) Full text and rfc822 format available.
This bug report was last modified 6 years and 73 days ago.

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.