bug#20230: 24.4.91; slow regexp

bug#20230: 24.4.91; slow regexp

[Nicolas Richard]

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

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

[Noam Postavsky]

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]*$")