GNU bug report logs - #6640
23.2; Why is this regexp search taking so long? (and will it end?)

Previous Next

Full log

Message #13 received at control <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]*$")

Previous Next

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