Re: performance/hang bug in regex.c

[Stefan Monnier]

> In a buffer containing the single line:
> aaba-----------------------------------------
> with point at the beginning of the line, executing this:
> M-:(re-search-forward "\\([^ab]+\\)+bb") RET
> sends emacs into a tizzy: 100% CPU is consumed and emacs appears hung;
> C-g unhangs it.  Shortening the line (reducing the number of dashes)
> changes behavior to a delay followed by the no-match error being
> triggered (correctly).  This repros reliably with 22.1.1 and with CVS
> HEAD as of 2008/08/10.  I do not have a fix or a workaround other than
> avoiding \\(...+\\)+ patterns.

Regexps can be implemented in mainly 2 ways: backtracking or not.
If you don't do backtracking, the above problem doesn't occur.
But many/most regexp implementations use a backtracking algorithm
because it's almost indispensable in order to handle backreferences.

Emacs provides backreferences and doesn't bother to provide 2 regexp
implementations (a backtracking one for regexps with backrefs and
a non-backtracking one for all the others), so you get pathological
behaviors for regexps such as the one above.  It's too bad, and I hope
we can fix it at some point, but don't hold your breath,


        Stefan