Re: Stack overflow in regexp matcher

[Denis Bueno]

On 3/30/07, Stefan Monnier <address@hidden> wrote:
> > With a recently compiled emacs, string-match on the following input
> > causes a stack overflow.
>
> Yup.  Emacs's regexp matcher uses backtracking, even for regexps which could
> be compiled into a DFA automaton.  So stack overflows are basically
> unavoidable in general and are hence not considered as bug in and of
> themselves (instead, the bug is generally in the regexp which needs to be
> optimized/adjusted to work around or minimize the stack overflow problem).
>
> I.e. if you tell us more, then maybe we can tell you how to avoid
> the problem.

I was having problem running checkstyle in JDE.

The regexp in question looks like: ".*some text.*". When used with
string-match, removing both ".*"s shouldn't affect the matching
semantically, right? If so, would it be wise to add a regexp
simplification step that, for example, could remove leading and
trailing ".*"s in regular expressions passed to string-match? I
realise now is not the time to talk about feature additions, but it
would certainly make my life simpler if any regular expression that
*can* be compiled to a DFA is.

(I also wonder where "regular expressions" that are more than regular
came from. Just because they are useful?)

-Denis