bug#7227: re-search-forward goes infinite loop with dash inside []

[Andreas Schwab]

Jari Aalto <jari.aalto@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@linux-m68k.org
GPG Key fingerprint = 58CA 54C7 6D53 942B 1756  01D3 44D5 214B 8276 4ED5
"And now for something completely different."