Re: Stack overflow in regexp matcher

[Stefan Monnier <monnier@iro.umontreal.ca>]

> The following fails with "Stack overflow in regexp matcher" in emacs 23
> and 24:

> (string-match
>  "^\\[.+\\]$"
>  (concat
>   "["
>   (mapconcat (lambda (i) "x") (number-sequence 1 33500) "")
>   "]"))

> This surprised me; I assumed that the ^ and $ anchors, and the simple
> ".+" requirement in the middle would result in a simple, efficient
> regexp.

The problem is that Emacs's regexp engine is not very clever.

Basically, each time . succeeds we first recurse, trying to match the
rest against ".*\\]$", and if that fails then we try to match
"\\]$" instead.  The fact that at each step we have this "fork" of two
different possible ways to match, means that at each step we have to
push something on the stack, so the longer the string against which we
match, the deeper the stack we need.

You can fix it by using a regexp that does not need this backtracking.
E.g. "^\\[[^]\n]+\\]$".  If you do that, then Emacs's regexp engine will
notice that when [^]\n] matches, then "\\]$" can't match, so there's no
point pushing something on the stack to try the second path when the
first fails.  I.e. it will do the whole match with a constant amount of
stack space.

This relates also to the recent discussion with Ilya in the thread
titled "will we ever have zero width assertions in regexps?".


        Stefan