A Deep Dive into PCRE's Max Backtrack/Recursion Limits中文EN

Today, Tank asked about this regex:

/<script>.*?<\/script>/is

When the string to be matched is longer than 100014, it will not produce the correct result:

$reg = "/<script>.*?<\/script>/is";
$str = "<script>********</script>"; //length greater than 100014
$ret = preg_replace($reg, "", $str); //returns NULL

Does a regex impose a length limit on the string it matches?
No, of course not. Here is the reason: the PCRE extension in PHP offers two settings.

1. pcre.backtrack_limit //max backtrack count
2. pcre.recursion_limit //max nesting depth

The default backtrack_limit is 100000 (a hundred thousand).
This problem is tied to the backtrack_limit setting. To understand why it happens, the key is knowing what "backtracking" is.
This regex uses non-greedy mode. Put simply, non-greedy matching prefers not to match when matching is optional. It records the alternative state and hands matching control to the regex's next character, and when the match after that fails, it backtracks and tries to match.
An example:

Source string: aaab
Regex:         .*?b

At the start of matching, ".*?" takes control first. Because it is non-greedy, it prefers not to match and hands control to the next pattern character, "b". "b" fails to match at position 1 of the source string (an "a"), so it backtracks and hands control back to ".*?". This time ".*?" matches one character, "a", and hands control to "b" again. This repeats until a match is found. In that process, 3 backtracks happened in total.
Now let us look at the example from the start of this post. The default backtrack_limit is 100000, and the source string begins with , leaving 99997 characters.
Also, because of the logic inside the match function itself, the example at the start of this post bumps the backtrack count up by 3 (if you are curious, see the match function logic in pcrelib/pcre_exec.c), so right before matching "", the backtrack count in PCRE is exactly 100000, and the match succeeds and exits normally.
Add just one more character, though, and the backtrack count goes above 100000, so the match fails and exits.
Since PHP 5.2, there is:

int preg_last_error ( void )
Returns the error code of the last PCRE regex execution.

We should check this function's return value often. A non-zero value means the previous regex call errored, and specifically for the example in this post, the error returned is (PREG_BACKTRACK_LIMIT_ERROR)
Lastly, one more note: non-greedy mode causes too much backtracking, which inevitably brings performance problems. Rewriting the regex appropriately avoids this. For example, change the regex from the start of this post to:

/<script>[^<]*<\/script>/is

and there will not be nearly so much backtracking.
The recursion_limit caps the maximum regex nesting depth. Set it too high and you may exhaust the stack space and blow it. The default of 100000 seems a bit too large...
Take a string of length 10000 and this seemingly "simple" one-liner regex:

//recursion_limit defaults to 100000
$reg = /(.+?)+/is;
$str = str_pad("laruence", 10000, "a"); //length is 10000
$ret = preg_repalce($reg, "", $str);

It will dump core, because the nesting is too deep and the stack blows.
You can work around this temporarily by changing the stack size. Set the stack space to 20M and the code above runs fine, but that is certainly not the perfect solution. The root fix is still to optimize the regex.
Finally: A regex is easy to write, but hard to use well.. Especially when processing large volumes of text, a carelessly designed regex easily leads to deep nesting, and for performance's sake, if string handling can do the job, use string handling instead.