[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: performance/hang bug in regex.c
From: |
Richard M. Stallman |
Subject: |
Re: performance/hang bug in regex.c |
Date: |
Tue, 02 Sep 2008 22:41:28 -0400 |
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,
This comes up often enough that maybe it should be explained in one
of the manuals.