[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: performance/hang bug in regex.c
From: |
Stefan Monnier |
Subject: |
Re: performance/hang bug in regex.c |
Date: |
Tue, 02 Sep 2008 16:26:23 -0400 |
User-agent: |
Gnus/5.13 (Gnus v5.13) Emacs/23.0.60 (gnu/linux) |
> 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