PHP:意外的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);

产量

Elementi trovati: 
preg_match_all ERROR
Backtrack limit was exhausted!

此代码给出了PREG_BACKTRACK_LIMIT_ERROR错误...但回溯限制设置为100.000.000.

这是我第一次使用正则表达式,我真的不知道如何解决它.

非常感谢,Marco

Answer 1

另一个典型的灾难性回溯案例.今天一定是我的幸运日.

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

仅在大括号正确嵌套时才匹配.当然,它们不在你的字符串中.

现在的问题是你的正则表达式需要找出你可以用106 a秒构建的所有可能的字符串组合来解决这个问题,因为你有嵌套的量词((...)*)*).其中(纠正我,如果我错了)应该是在某处附近的106!里面说到

114628056373470835453434738414834942870388487424139673389282723476762012382449946252660360871841673476016298287096435143747350528228224302506311680000000000000000000000000

这很容易击败你的PREG_BACKTRACK_LIMIT.

如果你使用占有量词来确保你永远不会回溯到你已经匹配的非大括号,那么你应该没问题:

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