GNU bug report logs - #20230
24.4.91; slow regexp

Message received at 20230 <at> debbugs.gnu.org:

Received: (at 20230) by debbugs.gnu.org; 26 Jun 2016 18:49:18 +0000
From debbugs-submit-bounces <at> debbugs.gnu.org Sun Jun 26 14:49:17 2016
Received: from localhost ([127.0.0.1]:57036 helo=debbugs.gnu.org)
	by debbugs.gnu.org with esmtp (Exim 4.84_2)
	(envelope-from <debbugs-submit-bounces <at> debbugs.gnu.org>)
	id 1bHF7N-0005Af-ND
	for submit <at> debbugs.gnu.org; Sun, 26 Jun 2016 14:49:17 -0400
Received: from mail-oi0-f66.google.com ([209.85.218.66]:32826)
 by debbugs.gnu.org with esmtp (Exim 4.84_2)
 (envelope-from <npostavs@HIDDEN>) id 1bHF7L-0005AM-Qt
 for 20230 <at> debbugs.gnu.org; Sun, 26 Jun 2016 14:49:16 -0400
Received: by mail-oi0-f66.google.com with SMTP id w141so27068775oia.0
 for <20230 <at> debbugs.gnu.org>; Sun, 26 Jun 2016 11:49:15 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113;
 h=mime-version:sender:from:date:message-id:subject:to:cc;
 bh=/5oVgw0VP0LR3W8nQrlx/QjN+tgrJQbhUlUiQEhvBzg=;
 b=iIdRTlJzwG3VjPTfNAAy0J8o1/OoKMegiy8xeMHm2klV9Dz/8iFQoYQQgJkakrO5AP
 +ypa8fulOQOy0ZxDzI4MCVFZYDWzvBfzsXpN8Uc69qZgYQqg6RUSU0Q4GqAk6FCcJGNr
 uB8ypLtf8jYa6qyGoAO3IindgiqiZGOkhQ18I+1SJv4K7nmB8hFQguGeHfc0mqfuufjH
 POQhSR9ABT+p6a6TTPabnmxqVod3+cJKwmHFS5NXTmQHaVEAzWegicWXSfMe78hJTKvL
 QO8wKdnztW8hm6VeNWbZ4TIR7cz4NqoPPflORa9vVfOITCberr91/am+WNBLE+BOe3Rp
 aiWA==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
 d=1e100.net; s=20130820;
 h=x-gm-message-state:mime-version:sender:from:date:message-id:subject
 :to:cc;
 bh=/5oVgw0VP0LR3W8nQrlx/QjN+tgrJQbhUlUiQEhvBzg=;
 b=J/f15cRSkXUWktx4F319x6CR9VORIK4JshWY8Iu/XFUQrNFXMakr1hBkPNWzikzRu/
 F62Tvdz3LwPuWaF3fT98M/05EreIlsqkhYZSj1hb/xb51F7Gd6JfCwfEouvfUgndF4Ai
 SiEIidPDNk60/Bh/GiW51u/h2wuqx/7wLSqOFR9sd6Svw84+SKU/k68+cDP35+wG+K0C
 9OhM/nWHuXTNjkhJ8k/8OzlOXf/tfl7zD/mfH+iIhhoGzLA9mEvGagj4nNbhR6SyxS0K
 kxCiMz7I6vdjiRGwTG7E+BGQ0R79wv2mdB6qVsQCQanMlL4XrrZunk5ldEBR5j9ML27b
 l9dA==
X-Gm-Message-State: ALyK8tJMYK5lJYOx0XML6gTANLH8HOJwCpoNP5t7KkKcW+mFojs5zUb9IAavacFTLlEQfS0V8LN2FUrdj56xUA==
X-Received: by 10.157.1.107 with SMTP id 98mr9229282otu.17.1466966950302; Sun,
 26 Jun 2016 11:49:10 -0700 (PDT)
MIME-Version: 1.0
Received: by 10.157.52.238 with HTTP; Sun, 26 Jun 2016 11:49:09 -0700 (PDT)
From: Noam Postavsky <npostavs@HIDDEN>
Date: Sun, 26 Jun 2016 14:49:09 -0400
X-Google-Sender-Auth: JOxBGUvidaPpIB7RPTb1IfKw1Ps
Message-ID: <CAM-tV-8-jLvPxhoxAayXhuX55-SeW5QYd0xHxHoHwLT-v11RJw@HIDDEN>
Subject: Bug #20230: 24.4.91; slow regexp
To: 20230 <at> debbugs.gnu.org
Content-Type: text/plain; charset=UTF-8
X-Spam-Score: -0.7 (/)
X-Debbugs-Envelope-To: 20230
Cc: Nicolas Richard <theonewiththeevillook@HIDDEN>
X-BeenThere: debbugs-submit <at> debbugs.gnu.org
X-Mailman-Version: 2.1.18
Precedence: list
List-Id: <debbugs-submit.debbugs.gnu.org>
List-Unsubscribe: <https://debbugs.gnu.org/cgi-bin/mailman/options/debbugs-submit>, 
 <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=unsubscribe>
List-Archive: <https://debbugs.gnu.org/cgi-bin/mailman/private/debbugs-submit/>
List-Post: <mailto:debbugs-submit <at> debbugs.gnu.org>
List-Help: <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=help>
List-Subscribe: <https://debbugs.gnu.org/cgi-bin/mailman/listinfo/debbugs-submit>, 
 <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=subscribe>
Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org
Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>
X-Spam-Score: -0.7 (/)

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

Message received at submit <at> debbugs.gnu.org:

Received: (at submit) by debbugs.gnu.org; 30 Mar 2015 14:46:06 +0000
From debbugs-submit-bounces <at> debbugs.gnu.org Mon Mar 30 10:46:06 2015
Received: from localhost ([127.0.0.1]:40583 helo=debbugs.gnu.org)
	by debbugs.gnu.org with esmtp (Exim 4.80)
	(envelope-from <debbugs-submit-bounces <at> debbugs.gnu.org>)
	id 1Ycax4-0001w2-67
	for submit <at> debbugs.gnu.org; Mon, 30 Mar 2015 10:46:06 -0400
Received: from eggs.gnu.org ([208.118.235.92]:35189)
 by debbugs.gnu.org with esmtp (Exim 4.80)
 (envelope-from <theonewiththeevillook@HIDDEN>) id 1Ycax1-0001vQ-PY
 for submit <at> debbugs.gnu.org; Mon, 30 Mar 2015 10:46:04 -0400
Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71)
 (envelope-from <theonewiththeevillook@HIDDEN>) id 1Ycawv-0004n5-9B
 for submit <at> debbugs.gnu.org; Mon, 30 Mar 2015 10:45:58 -0400
X-Spam-Checker-Version: SpamAssassin 3.3.2 (2011-06-06) on eggs.gnu.org
X-Spam-Level: 
X-Spam-Status: No, score=-0.5 required=5.0 tests=BAYES_05,FREEMAIL_FROM
 autolearn=disabled version=3.3.2
Received: from lists.gnu.org ([2001:4830:134:3::11]:58648)
 by eggs.gnu.org with esmtp (Exim 4.71)
 (envelope-from <theonewiththeevillook@HIDDEN>) id 1Ycawv-0004my-7B
 for submit <at> debbugs.gnu.org; Mon, 30 Mar 2015 10:45:57 -0400
Received: from eggs.gnu.org ([2001:4830:134:3::10]:36892)
 by lists.gnu.org with esmtp (Exim 4.71)
 (envelope-from <theonewiththeevillook@HIDDEN>) id 1Ycawu-0001P4-9D
 for bug-gnu-emacs@HIDDEN; Mon, 30 Mar 2015 10:45:57 -0400
Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71)
 (envelope-from <theonewiththeevillook@HIDDEN>) id 1Ycawq-0004m5-Et
 for bug-gnu-emacs@HIDDEN; Mon, 30 Mar 2015 10:45:56 -0400
Received: from mxin.ulb.ac.be ([164.15.128.112]:17636)
 by eggs.gnu.org with esmtp (Exim 4.71)
 (envelope-from <theonewiththeevillook@HIDDEN>) id 1Ycawq-0004lw-9P
 for bug-gnu-emacs@HIDDEN; Mon, 30 Mar 2015 10:45:52 -0400
X-IronPort-Anti-Spam-Filtered: true
X-IronPort-Anti-Spam-Result: As4SAP1gGVWkD4Xx/2dsb2JhbABcg1hcgkWvVAaTHod1AQEBAQEBfUEBAYRpJDQBBIh2ARQNog+RN5BdAYZNhg+CM4d8hBcFlE2GA4FWhSKNPSKBRQELAYIePDEBgkIBAQE
Received: from mathsrv4.ulb.ac.be (HELO localhost) ([164.15.133.241])
 by smtp.ulb.ac.be with ESMTP; 30 Mar 2015 16:45:37 +0200
From: Nicolas Richard <theonewiththeevillook@HIDDEN>
To: bug-gnu-emacs@HIDDEN
Subject: 24.4.91; slow regexp
Date: Mon, 30 Mar 2015 16:46:45 +0200
Message-ID: <87619iv8yy.fsf@HIDDEN>
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.4.91 (gnu/linux)
MIME-Version: 1.0
Content-Type: text/plain
X-detected-operating-system: by eggs.gnu.org: Genre and OS details not
 recognized.
X-detected-operating-system: by eggs.gnu.org: Error: Malformed IPv6 address
 (bad octet value).
X-Received-From: 2001:4830:134:3::11
X-Spam-Score: -5.0 (-----)
X-Debbugs-Envelope-To: submit
X-BeenThere: debbugs-submit <at> debbugs.gnu.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: <debbugs-submit.debbugs.gnu.org>
List-Unsubscribe: <https://debbugs.gnu.org/cgi-bin/mailman/options/debbugs-submit>, 
 <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=unsubscribe>
List-Archive: <https://debbugs.gnu.org/cgi-bin/mailman/private/debbugs-submit/>
List-Post: <mailto:debbugs-submit <at> debbugs.gnu.org>
List-Help: <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=help>
List-Subscribe: <https://debbugs.gnu.org/cgi-bin/mailman/listinfo/debbugs-submit>, 
 <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=subscribe>
Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org
Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>
X-Spam-Score: -5.0 (-----)

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