regex - PHP: unexpected PREG_BACKTRACK_LIMIT_ERROR

Question

function recursiveSplit($string, $layer) {
    $err = preg_match_all("/{(([^{}]*|(?R))*)}/",$string,$matches);
    echo "Elementi trovati: $err<br>";
    if($err == FALSE) echo "preg_match_all ERROR<br>";

    // iterate thru matches and continue recursive split
    if (count($matches) > 1) {
        for ($i = 0; $i < count($matches[1]); $i++) {
            if (is_string($matches[1][$i])) {
                if (strlen($matches[1][$i]) > 0) {
                    echo "<pre>Layer ".$layer.":   ".$matches[1][$i]."</pre><br />";
                    recursiveSplit($matches[1][$i], $layer + 1);
                }
            }
        }
    }
}

$buffer = "{aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa{aaaaaaaaaaaaaaaaaa{aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa}";
recursiveSplit($buffer, 0);

output

Elementi trovati: 
preg_match_all ERROR
Backtrack limit was exhausted!

this code gives me a PREG_BACKTRACK_LIMIT_ERROR error... but the backtrack limit is set to 100.000.000.

This is my first time with regex, and I really do not know how to solve it.

Thank you very much, Marco

Answer 1

Another classic case of catastrophic backtracking. Must be my lucky day today.

/{(([^{}]*|(?R))*)}/

only matches if the braces are nested correctly. Which they aren't, of course, in your string.

Now the problem is that your regex needs to figure out all possible string combinations you can build with 106 as to figure that out because you have nested quantifiers ((...)*)*). Which (correct me if I'm wrong) should be somewhere in the vicinity of 106! which comes to

114628056373470835453434738414834942870388487424139673389282723476762012382449946252660360871841673476016298287096435143747350528228224302506311680000000000000000000000000

which easily beats your PREG_BACKTRACK_LIMIT.

If you use possessive quantifiers to make sure that you'll never backtrack into the non-braces you've already matched, then you should be OK:

/{(([^{}]*+|(?R))*)}/