[[270927]]

正則表達(dá)式可能大部分人都用過，但是大家在使用的時候，有沒有想過正則表達(dá)式背后的原理，又或者當(dāng)我告訴你正則表達(dá)式可能存在性能問題導(dǎo)致線上掛掉，你會不會覺得特別吃驚？

我們先來看看7月初，因?yàn)橐粋€正則表達(dá)式，導(dǎo)致線上事故的例子。

https://blog.cloudflare.com/d...

簡單來說就是一個有性能問題的正則表達(dá)式，引起了災(zāi)難性回溯，導(dǎo)致cpu滿載。

性能問題的正則

先看看出問題的正則

引起性能問題的關(guān)鍵部分是 .*(?:.*=.*) ，這里我們先不管那個非捕獲組，將性能問題的正則看做 .*.*=.* 。

其中 . 表示匹配除了換行以外的任意字符（很多人把這里搞錯，容易出bug）， .* 表示貪婪匹配任意字符任意次。

什么是回溯

在使用貪婪匹配或者惰性匹配或者或匹配進(jìn)入到匹配路徑選擇的時候，遇到失敗的匹配路徑，嘗試走另外一個匹配路徑的這種行為，稱作回溯。

可以理解為走迷宮，一條路走到底，發(fā)現(xiàn)無路可走就回到上一個三岔口選擇另外的路。

回溯現(xiàn)象 

// 性能問題正則  
// 將下面代碼粘貼到瀏覽器控制臺運(yùn)行試試  
const regexp = `[A-Z]+\\d+(.*):(.*)+[A-Z]+\\d+`;  
const str = `A1:B$1,C$1:D$1,E$1:F$1,G$1:H$1`  
const reg = new RegExp(regexp);  
start = Date.now();  
const res = reg.test(str);  
end = Date.now();  
console.log('常規(guī)正則執(zhí)行耗時:' + (end - start)) 

現(xiàn)在來看看回溯究竟是怎么一回事

假設(shè)我們有一段正則 (.*)+\d ，這個時候輸入字符串為 abcd ，注意這個時候僅僅輸入了一個長度為4的字符串，我們來分析一下匹配回溯的過程：

上面展示了一個回溯的匹配過程，大概描述一下前三輪匹配。

注意 (.*)+ 這里可以先暫且看成多次執(zhí)行 .* 。 (.*){1,}

***次匹配，因?yàn)?.* 可以匹配任意個字符任意次，那么這里可以選擇匹配空、a、ab、abc、abcd，因?yàn)?* 的貪婪特性，所以 .* 直接匹配了 abcd 4個字符， + 因?yàn)楹竺鏇]有其他字符了，所以只看著 .* 吃掉 abcd 后就不匹配了，這里記錄 + 的值為1，然后 \d 沒有東西能夠匹配，所以匹配失敗，進(jìn)行***次回溯。

第二次匹配，因?yàn)檫M(jìn)行了回溯，所以回到上一個匹配路徑選擇的時候，上次 .* 匹配的是 abcd ，并且路不通，那么這次只能嘗試匹配 abc ，這個時候末尾還有一個 d ，那么可以理解為 .* ***次匹配了 abc ，然后因?yàn)?(.*)+ 的原因， .* 可以進(jìn)行第二次匹配，這里 .* 可以匹配 d ，這里記錄 + 的值為2，然后 \d 沒有東西能夠匹配，所以匹配失敗，進(jìn)行第二次回溯。

第三次匹配，因?yàn)檫M(jìn)行了回溯，所以回到上一個匹配路徑選擇的時候，上次***個 .* 匹配的是 abc ，第二個 .* 匹配的是 d ，并且路不通，所以這里第二次的 .* 不進(jìn)行匹配，這個時候末尾還有一個 d ， \d 和 d 匹配失敗，進(jìn)行第三次回溯。

如何減少或避免回溯

•  優(yōu)化正則表達(dá)式：時刻注意回溯造成的性能影響。
•  使用DFA正則引擎的正則表達(dá)式

什么是DFA正則引擎

傳統(tǒng)正則引擎分為NFA（非確定性有限狀態(tài)自動機(jī)），和DFA（確定性有限狀態(tài)自動機(jī)）。

DFA

對于給定的任意一個狀態(tài)和輸入字符，DFA只會轉(zhuǎn)移到一個確定的狀態(tài)。并且DFA不允許出現(xiàn)沒有輸入字符的狀態(tài)轉(zhuǎn)移。

比如狀態(tài)0，在輸入字符A的時候，終點(diǎn)只有1個，只能到狀態(tài)1。

NFA

對于任意一個狀態(tài)和輸入字符，NFA所能轉(zhuǎn)移的狀態(tài)是一個非空集合。

比如狀態(tài)0，在輸入字符A的時候，終點(diǎn)可以是多個，即能到狀態(tài)1，也能到狀態(tài)0。

DFA和NFA的正則引擎的區(qū)別

那么講了這么多之后，DFA和NFA正則引擎究竟有什么區(qū)別呢？或者說DFA和NFA是如何實(shí)現(xiàn)正則引擎的呢？

DFA

正則里面的DFA引擎實(shí)際上就是把正則表達(dá)式轉(zhuǎn)換成一個圖的鄰接表，然后通過跳表的形式判斷一個字符串是否匹配該正則。 

// 大概模擬一下  
function machine(input) {  
    if (typeof input !== 'string') {  
        console.log('輸入有誤');  
        return;  
    }  
    // 比如正則：/abc/ 轉(zhuǎn)換成DFA之后  
    // 這里我們定義了4種狀態(tài)，分別是0,1,2,3，初始狀態(tài)為0  
    const reg = {  
        0: {  
            a: 1,  
        },  
        1: {  
            b: 3,  
        },  
        2: {  
            isEnd: true,  
        },  
        3: {  
            c: 2,  
        },  
    };  
    let status = 0;  
    for (let i = 0; i < input.length; i++) {  
        const inputinputChar = input[i];  
        status = reg[status][inputChar];  
        if (typeof status === 'undefined') {  
            console.log('匹配失敗');  
            return false;  
        }  
    }  
    const end = reg[status];  
    if (end && end.isEnd === true) {  
        console.log('匹配成功');  
        return true;  
    } else {  
        console.log('匹配失敗');  
        return false;  
    }  
}  
const input = 'abc';  
machine(input); 

優(yōu)點(diǎn)：不管正則表達(dá)式寫的再爛，匹配速度都很快

缺點(diǎn)：高級功能比如捕獲組和斷言都不支持

NFA

正則里面NFA引擎實(shí)際上就是在語法解析的時候，構(gòu)造出的一個有向圖。然后通過深搜的方式，去一條路徑一條路徑的遞歸嘗試。

優(yōu)點(diǎn)：功能強(qiáng)大，可以拿到匹配的上下文信息，支持各種斷言捕獲組環(huán)視之類的功能

缺點(diǎn)：對開發(fā)正則功底要求較高，需要注意回溯造成的性能問題

總結(jié)

現(xiàn)在回到問題的開頭，我們再來看看為什么他的正則會有性能問題

1.  首先他的正則使用的NFA的正則引擎（大部分語言的正則引擎都是NFA的，js也是，所以要注意性能問題產(chǎn)生的影響）
2.  他寫出了有性能問題的正則表達(dá)式，容易造成災(zāi)難性回溯。

如果要避免此類的問題，要么提高開發(fā)對正則的性能問題的意識，要么改用DFA的正則引擎（速度快，功能弱，沒有補(bǔ)貨組斷言等功能）。

注意事項(xiàng)

在平常寫正則的時候，少寫模糊匹配，越精確越好，模糊匹配、貪婪匹配、惰性匹配都會帶來回溯問題，選一個影響盡可能小的方式就好。寫正則的時候有一個性能問題的概念在腦子里就行。