Subject: bug#20230: Bug #20230: 24.4.91; slow regexp

From: Noam Postavsky <[email-masked]>
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]*$")