[[270927]]

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

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

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

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

性能問(wèn)題的正則

先看看出問(wèn)題的正則

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

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

什么是回溯

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

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

回溯現(xiàn)象 

// 性能問(wèn)題正則  
// 將下面代碼粘貼到瀏覽器控制臺(tái)運(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í)行耗時(shí):' + (end - start)) 

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

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

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

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

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

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

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

如何減少或避免回溯

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

什么是DFA正則引擎

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

DFA

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

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

NFA

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

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

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

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

DFA

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

// 大概模擬一下  
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)：高級(jí)功能比如捕獲組和斷言都不支持

NFA

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

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

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

總結(jié)

現(xiàn)在回到問(wèn)題的開(kāi)頭，我們?cè)賮?lái)看看為什么他的正則會(huì)有性能問(wèn)題

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

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

注意事項(xiàng)

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