GNU bug report logs - #7227
re-search-forward goes infinite loop with dash inside []

Previous Next

To add a comment to this bug, you must first unarchive it, by sending
a message to control AT debbugs.gnu.org, with unarchive 7227 in the body.
You can then email your comments to 7227 AT debbugs.gnu.org in the normal way.

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

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

From: Jari Aalto <jari.aalto <at> cante.net>
To: submit <at> debbugs.gnu.org
Subject: re-search-forward goes infinite loop with dash inside []
Date: Sat, 16 Oct 2010 12:16:01 +0300

Package: emacs
Version: 23.2+1-4
Severity: normal

Executing the following code causes Emacs to go into infinite loop.
Simply run it behind the last paren with C-x C-e

(re-search-forward "^\\([a-z0-9.-]+\\)+[ \t]+\\([0-9]+\\) +\\([a-z].*\\)")
                        ==========

If the dash is taken awy from the "[a-z0-9.-]", this code does not cause
infinite loop:

(re-search-forward "^\\([a-z0-9.]+\\)+[ \t]+\\([0-9]+\\) +\\([a-z].*\\)")

TEST ROWS FOR THE REGEXPS:

row-one 1234 rest of line

row2    1234 rest of line

TEST SETUP

emacs -Q --no-site-file
<copy the re-search-forward lisp statements into buffer>
<copy the test rows into buffer>
<Execute lisp statements>

-- System Information
Debian Release: squeeze/sid
  APT Prefers testing
  APT policy: (990, testing) (500, unstable) (1, experimental)
Architecture: amd64
Kernel: Linux picasso 2.6.32-5-amd64 #1 SMP Fri Sep 17 21:50:19 UTC 2010 x86_64 GNU/Linux
Locale: LANG=en_DK.UTF-8

-- Versions of packages `emacs depends on'.
Depends:
emacs23         23.2+1-4        GNU Emacs is the extensible self-documenting
emacs23-lucid   23.2+1-4        GNU Emacs is the extensible self-documenting
emacs23-nox     23.2+1-4        GNU Emacs is the extensible self-documenting

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

From: Andreas Schwab <schwab <at> linux-m68k.org>
To: Jari Aalto <jari.aalto <at> cante.net>
Cc: 7227 <at> debbugs.gnu.org
Subject: Re: bug#7227: re-search-forward goes infinite loop with dash inside []
Date: Sat, 16 Oct 2010 13:27:36 +0200

Jari Aalto <jari.aalto <at> cante.net> writes:

> Executing the following code causes Emacs to go into infinite loop.
> Simply run it behind the last paren with C-x C-e
>
> (re-search-forward "^\\([a-z0-9.-]+\\)+[ \t]+\\([0-9]+\\) +\\([a-z].*\\)")

Works fine here.

Note that nested repetitions like \([...]+\)+ are bad in any case.

Andreas.

-- 
Andreas Schwab, schwab <at> linux-m68k.org
GPG Key fingerprint = 58CA 54C7 6D53 942B 1756  01D3 44D5 214B 8276 4ED5
"And now for something completely different."

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

From: Andreas Röhler <andreas.roehler <at> easy-emacs.de>
To: bug-gnu-emacs <at> gnu.org
Subject: Re: bug#7227: re-search-forward goes infinite loop with dash inside []
Date: Sat, 16 Oct 2010 13:39:08 +0200

Am 16.10.2010 11:16, schrieb Jari Aalto:
> Package: emacs Version: 23.2+1-4 Severity: normal
>
> Executing the following code causes Emacs to go into infinite loop.
> Simply run it behind the last paren with C-x C-e
>
> (re-search-forward "^\\([a-z0-9.-]+\\)+[ \t]+\\([0-9]+\\)
> +\\([a-z].*\\)") ==========
>
> If the dash is taken awy from the "[a-z0-9.-]", this code does not
> cause infinite loop:
>
> (re-search-forward "^\\([a-z0-9.]+\\)+[ \t]+\\([0-9]+\\)
> +\\([a-z].*\\)")
>
> TEST ROWS FOR THE REGEXPS:
>
> row-one 1234 rest of line
>
> row2    1234 rest of line
>
> TEST SETUP
>
> emacs -Q --no-site-file <copy the re-search-forward lisp statements
> into buffer> <copy the test rows into buffer> <Execute lisp
> statements>
>
> -- System Information Debian Release: squeeze/sid APT Prefers
> testing APT policy: (990, testing) (500, unstable) (1, experimental)
> Architecture: amd64 Kernel: Linux picasso 2.6.32-5-amd64 #1 SMP Fri
> Sep 17 21:50:19 UTC 2010 x86_64 GNU/Linux Locale: LANG=en_DK.UTF-8
>
> -- Versions of packages `emacs depends on'. Depends: emacs23
> 23.2+1-4        GNU Emacs is the extensible self-documenting
> emacs23-lucid   23.2+1-4        GNU Emacs is the extensible
> self-documenting emacs23-nox     23.2+1-4        GNU Emacs is the
> extensible self-documenting
>
>
>
>

Hi,

can't reproduce this with

GNU Emacs 23.1.1 (i586-suse-linux-gnu, GTK+ Version 2.20.1) of 2010-07-05

in scratch buffer I get an error immediatly:

Debugger entered--Lisp error: (search-failed "^\\([a-z0-9.-]+\\)+[
]+\\([0-9]+\\) +\\([a-z].*\\)")
  re-search-forward("^\\([a-z0-9.-]+\\)+[ 	]+\\([0-9]+\\) +\\([a-z].*\\)")
  eval((re-search-forward "^\\([a-z0-9.-]+\\)+[ 	]+\\([0-9]+\\)
+\\([a-z].*\\)"))
  eval-last-sexp-1(nil)
  eval-last-sexp(nil)
  call-interactively(eval-last-sexp nil nil)

Thanks for tiny-tools BTW.

Andreas

--
https://code.launchpad.net/~a-roehler/python-mode/python-mode-components
https://code.launchpad.net/s-x-emacs-werkstatt/

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

From: Jari Aalto <jari.aalto <at> cante.net>
To: 7227 <at> debbugs.gnu.org
Cc: Andreas Schwab <schwab <at> linux-m68k.org>
Subject: Re: bug#7227: re-search-forward goes infinite loop with dash inside []
Date: Sat, 16 Oct 2010 16:42:00 +0300

Andreas Schwab <schwab <at> linux-m68k.org> writes:

> Jari Aalto <jari.aalto <at> cante.net> writes:
>
>> Executing the following code causes Emacs to go into infinite loop.
>> Simply run it behind the last paren with C-x C-e
>>
>> (re-search-forward "^\\([a-z0-9.-]+\\)+[ \t]+\\([0-9]+\\) +\\([a-z].*\\)")
>
> Works fine here.

Hm. The test case needs adjustment:

;; (1) Run C-x C-e, works:

(re-search-forward "^\\([a-z0-9.-]+\\)+[ \t]+\\([0-9]+\\) +\\([a-z].*\\)")
row2    1234 rest of line

;; (2) but C-x C-e below causes a loop

(re-search-forward "^\\([a-z0-9.-]+\\)+[ \t]+\\([0-9]+\\) +\\([a-z].*\\)")
------------------------------------------------------------------------
row2    1234 rest of line

> Note that nested repetitions like \([...]+\)+ are bad in any case.

This was only a test. The anchor "^" should help, and I assume the first
'[a-z0-9.-]+' should be greedy, so it shouldn't take that long to
resolve.

Jari

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

From: Andreas Schwab <schwab <at> linux-m68k.org>
To: Jari Aalto <jari.aalto <at> cante.net>
Cc: 7227 <at> debbugs.gnu.org
Subject: Re: bug#7227: re-search-forward goes infinite loop with dash inside []
Date: Sat, 16 Oct 2010 15:54:17 +0200

Jari Aalto <jari.aalto <at> cante.net> writes:

> Hm. The test case needs adjustment:
>
> ;; (1) Run C-x C-e, works:
>
> (re-search-forward "^\\([a-z0-9.-]+\\)+[ \t]+\\([0-9]+\\) +\\([a-z].*\\)")
> row2    1234 rest of line
>
> ;; (2) but C-x C-e below causes a loop
>
> (re-search-forward "^\\([a-z0-9.-]+\\)+[ \t]+\\([0-9]+\\) +\\([a-z].*\\)")
> ------------------------------------------------------------------------
> row2    1234 rest of line
>
>> Note that nested repetitions like \([...]+\)+ are bad in any case.
>
> This was only a test. The anchor "^" should help, and I assume the first
> '[a-z0-9.-]+' should be greedy, so it shouldn't take that long to
> resolve.

Not in the non-matching case.  When the match against the dash line is
tried you get quadratic behaviour due to explosion of the search tree.

Andreas.

-- 
Andreas Schwab, schwab <at> linux-m68k.org
GPG Key fingerprint = 58CA 54C7 6D53 942B 1756  01D3 44D5 214B 8276 4ED5
"And now for something completely different."

Message #22 received at 7227-done <at> debbugs.gnu.org (full text, mbox):

From: Jari Aalto <jari.aalto <at> cante.net>
To: 7227-done <at> debbugs.gnu.org
Subject: Bug#7227 Close bts:gnu
Date: Fri, 22 Oct 2010 10:55:43 +0300

Reason for close:

Not a bug. In non-matching case, the regexp engine pumps up; thus "Loop
effect" feel.

Previous Next

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