避免正则中的那些灾难性回溯 Catastrophic backtracking

今天某产品经理突然跑来跟我说线上有了个bug，上传了文件后浏览器卡死奔溃了内心一惊（这群产品狗是不是又瞎操作），最后经过一番侦察，定位到原来是下面这段代码导致的

    let input = `".........这里有50个字符以上。。。。。`
    function makeCellFromRowString(row) {
        row = row.replace(/,,/g,',-,').replace(/,,/g,',-,').replace(/^,/,'-,').replace(/,$/,',-');
        let p = /"([^"]*(?:(?:"")*[^"]*(?:"")*)*)"|([^,]+)/g; // (?:)的意思表示该分组不计入最后匹配结果的分组中
        let e = null;
        let cells = [];
        let temp = null;
        while ((e = p.exec(row)) != null) {
            temp = (e[2] || e[1]).replace(/""/g,'"');
            cells.push(temp);
        }
        return cells;
    }

当函数的入参是上面input的值的时候，程序就卡住了，这里就发生正则中很容易发生的 回溯灾难

我们现在考虑这样一个正则 /(x+x+)+y/ ,去匹配字符串 'xxxxxxxxxxy'

第一个x+会先匹配所有10个x,这个时候第二个x+会失败
此时第一个x+ 会发生回溯，去匹配 9个x ,这个时候第二个x 匹配x
分组1 此时匹配一次，开始判断是否有重复组，但没有x了于是匹配失败了
但是由于已经有一组满足了，于是开始匹配y,成功匹配上y,ok一切看上去很美好

但是灾难的事情发生了此时字符串变成了 'xxxxxxxxxx' ,y不见了

此时上面的第四步匹配y失败，于是开始回溯
由于第二个x+只匹配了一个x,所以不能回溯，但是第一个x+ 可以放弃一个x，此时第二个x+匹配xx，但还是匹配不到y
再次回溯，第二个x+现在有2个x，他可以放弃一个x，此时分组开始匹配第二组(x+x+),但是此时只有一个x，匹配失败
再次回溯，第一个x+减少到7个，第二个匹配3个，但是还是匹配 y 失败
再次回溯，第二个x减少到2个，匹配到第二组失败，然后到1个，此时第二组（x+x+）匹配成功（7，1）（1，1）
不过还是匹配 y 失败，然后第一个x+减少到6个，(6,4)->(6,2)(1,1)->(6,2)(2,1)->(6,2)(1,2) 10 .... 然后你会开始懵逼

点击这里你可以发现10个x一共判断了4085步才判断出正则匹配失败 11个x执行了8180步，12个x执行16371步，步骤几乎是指数式的复杂度 O(2^n)，这就是灾难性的回溯

上面这个例子最明智的修改方式无疑是修改成把正则修改成 /xx+y/ 消除嵌套的量词 + 另外一种做法是使用 Possessive Quantifier 就是 /(x+x+)++y/ 简单点说就是让正则引擎更加聪明快速的判断失败

大部分的灾难性回溯造成的原因是量词 + * 的嵌套使用造成的，所以谨慎使用

最简单避免灾难性回溯的方法就是，当嵌套重复性的操作符时候，确保对具体的同一段字符串只有一种匹配路径，如果一个内环重复了四次，外环重复了7次匹配的结果和内环重复6次，外环重复2次的结果一样，正则引擎会尝试回溯他们的组合

回到正题,将代码中的正则简化下就是下面这样，问题就出在嵌套了2层 *

/"[^"]([^"])*"/ 当要匹配的字符串是 "这里有100汉字 的话，由于最后无法匹配到 " , 这里就会有很多的组合了 (99)((1)) (98)((2)) (98)((1)(1)) (97)((1)(1)(1)) (97)((2)(1)) (97)((1)(2)) 。。。。。。。。。。就会不断的回溯

DarkFlame / blog