[[201253]]

1. 血案由來

近期我在為L(zhǎng)azada賣家中心做一個(gè)自助注冊(cè)的項(xiàng)目，其中的shop name校驗(yàn)規(guī)則較為復(fù)雜，要求：

1. 英文字母大小寫

2. 數(shù)字

3. 越南文

4. 一些特殊字符，如“&”，“-”，“_”等

看到這個(gè)要求的時(shí)候，自然而然地想到了正則表達(dá)式。于是就有了下面的表達(dá)式(寫的比較齪)：

^([A-Za-z0-9._()&'\- ]| 
[aAàÀảẢãÃáÁạẠăĂằẰẳẲẵẴắẮặẶâÂầẦẩẨẫẪấẤậẬbBcCdDđĐeEèÈẻẺẽẼéÉẹẸêÊềỀểỂễỄếẾệỆfFgGhHiIìÌỉỈĩĨíÍịỊjJkKlLmMnNoOòÒỏỎõÕóÓọỌôÔồỒổỔỗỖốỐộỘơƠờỜởỞỡỠớỚợỢpPqQrRsStTuUùÙủỦũŨúÚụỤưƯừỪửỬữỮứỨựỰvVwWxXyYỳỲỷỶỹỸýÝỵỴzZ])+$ 

在測(cè)試環(huán)境，這個(gè)表達(dá)式從功能上符合業(yè)務(wù)方的要求，就被發(fā)布到了馬來西亞的線上環(huán)境。結(jié)果上線之后，發(fā)現(xiàn)線上機(jī)器時(shí)有發(fā)生CPU飆到100%的情況，導(dǎo)致整個(gè)站點(diǎn)響應(yīng)異常緩慢。通過dump線程trace，才發(fā)現(xiàn)線程全部卡在了這個(gè)正則表達(dá)式的校驗(yàn)上：

一開始難以置信，一個(gè)正則表達(dá)式的匹配過程怎么可能引發(fā)CPU飚高呢?抱著懷疑的態(tài)度去查了資料才發(fā)現(xiàn)小小的正則表達(dá)式里面竟然大有文章，平時(shí)寫起來都是淺嘗輒止，只要能夠滿足功能需求，就認(rèn)為達(dá)到目的了，完全忽略了它可能帶來的性能隱患。

引發(fā)這次血案的就是所謂的正則“回溯陷阱(Catastrophic Backtracking)”。下面詳細(xì)介紹下這個(gè)問題，以避免重蹈覆轍。

2. 正則表達(dá)式引擎

說起回溯陷阱，要先從正則表達(dá)式的引擎說起。正則引擎主要可以分為基本不同的兩大類：一種是DFA(確定型有窮自動(dòng)機(jī))，另一種是NFA(不確定型有窮自動(dòng)機(jī))。簡(jiǎn)單來講，NFA 對(duì)應(yīng)的是正則表達(dá)式主導(dǎo)的匹配，而 DFA 對(duì)應(yīng)的是文本主導(dǎo)的匹配。

DFA從匹配文本入手，從左到右，每個(gè)字符不會(huì)匹配兩次，它的時(shí)間復(fù)雜度是多項(xiàng)式的，所以通常情況下，它的速度更快，但支持的特性很少，不支持捕獲組、各種引用等等;而NFA則是從正則表達(dá)式入手，不斷讀入字符，嘗試是否匹配當(dāng)前正則，不匹配則吐出字符重新嘗試，通常它的速度比較慢，最優(yōu)時(shí)間復(fù)雜度為多項(xiàng)式的，最差情況為指數(shù)級(jí)的。但NFA支持更多的特性，因而絕大多數(shù)編程場(chǎng)景下(包括java，js)，我們面對(duì)的是NFA。以下面的表達(dá)式和文本為例，

text = ‘after tonight’ 
regex = ‘to(nite|nighta|night)’ 

在NFA匹配時(shí)候，是根據(jù)正則表達(dá)式來匹配文本的，從t開始匹配a，失敗，繼續(xù)，直到文本里面的第一個(gè)t，接著比較o和e，失敗，正則回退到 t，繼續(xù)，直到文本里面的第二個(gè)t，然后 o和文本里面的o也匹配，繼續(xù)，正則表達(dá)式后面有三個(gè)可選條件，依次匹配，第一個(gè)失敗，接著二、三，直到匹配。

而在DFA匹配時(shí)候，采用的是用文本來匹配正則表達(dá)式的方式，從a開始匹配t，直到第一個(gè)t跟正則的t匹配，但e跟o匹配失敗，繼續(xù)，直到文本里面的第二個(gè) t 匹配正則的t，接著o與o匹配，n的時(shí)候發(fā)現(xiàn)正則里面有三個(gè)可選匹配，開始并行匹配，直到文本中的g使得第一個(gè)可選條件不匹配，繼續(xù)，直到最后匹配。

可以看到，DFA匹配過程中文本中的字符每一個(gè)只比較了一次，沒有吐出的操作，應(yīng)該是快于NFA的。另外，不管正則表達(dá)式怎么寫，對(duì)于DFA而言，文本的匹配過程是一致的，都是對(duì)文本的字符依次從左到右進(jìn)行匹配，所以，DFA在匹配過程中是跟正則表達(dá)式無關(guān)的，而 NFA 對(duì)于不同但效果相同的正則表達(dá)式，匹配過程是完全不同的。

3. 回溯

說完了引擎，我們?cè)賮砜纯吹降资裁词腔厮?。?duì)于下面這個(gè)表達(dá)式，相信大家很清楚它的意圖，

ab{1,3}c 

也就是說中間的b需要匹配1~3次。那么對(duì)于文本“abbbc”，按照第1部分NFA引擎的匹配規(guī)則，其實(shí)是沒有發(fā)生回溯的，在表達(dá)式中的a匹配完成之后，b恰好和文本中的3個(gè)b完整匹配，之后是c發(fā)生匹配，一氣呵成。如果我們把文本換成“abc”呢?無非就是少了一個(gè)字母b，卻發(fā)生了所謂的回溯。匹配過程如下圖所示(橙色為匹配，黃色為不匹配)，

1~2步應(yīng)該都好理解，但是為什么在第3步開始，雖然已經(jīng)文本中已經(jīng)有一個(gè)b匹配了b{1,3}，后面還會(huì)拉著字母c跟b{1,3}做比較呢?這個(gè)就是我們下面將要提到的正則的貪婪特性，也就是說b{1,3}會(huì)竭盡所能的匹配最多的字符。在這個(gè)地方我們先知道它一直要匹配到撞上南墻為止。 在這種情況下，第3步發(fā)生不匹配之后，整個(gè)匹配流程并沒有走完，而是像棧一樣，將字符c吐出來，然后去用正則表達(dá)式中的c去和文本中的c進(jìn)行匹配。這樣就發(fā)生了一次回溯。

4. 貪婪、懶惰與獨(dú)占

我們?cè)賮砜匆幌戮烤故裁词秦澙纺Ｊ健?/p>

下面的幾個(gè)特殊字符相信大家都知道它們的用法：

i. ?: 告訴引擎匹配前導(dǎo)字符0次或一次。事實(shí)上是表示前導(dǎo)字符是可選的。

ii. +: 告訴引擎匹配前導(dǎo)字符1次或多次。

iii. *: 告訴引擎匹配前導(dǎo)字符0次或多次。

iv. {min, max}: 告訴引擎匹配前導(dǎo)字符min次到max次。min和max都是非負(fù)整數(shù)。如果有逗號(hào)而max被省略了，則表示max沒有限制;如果逗號(hào)和max都被省略了，則表示重復(fù)min次。

默認(rèn)情況下，這個(gè)幾個(gè)特殊字符都是貪婪的，也就是說，它會(huì)根據(jù)前導(dǎo)字符去匹配盡可能多的內(nèi)容。這也就解釋了為什么在第3部分的例子中，第3步以后的事情會(huì)發(fā)生了。

在以上字符后加上一個(gè)問號(hào)(?)則可以開啟懶惰模式，在該模式下，正則引擎盡可能少的重復(fù)匹配字符，匹配成功之后它會(huì)繼續(xù)匹配剩余的字符串。在上例中，如果將正則換為

ab{1,3}?c 

則匹配過程變成了下面這樣(橙色為匹配，黃色為不匹配)，

由此可見，在非貪婪模式下，第2步正則中的b{1,3}?與文本b匹配之后，接著去用c與文本中的c進(jìn)行匹配，而未發(fā)生回溯。

如果在以上四種表達(dá)式后加上一個(gè)加號(hào)(+)，則會(huì)開啟獨(dú)占模式。同貪婪模式一樣，獨(dú)占模式一樣會(huì)匹配最長(zhǎng)。不過在獨(dú)占模式下，正則表達(dá)式盡可能長(zhǎng)地去匹配字符串，一旦匹配不成功就會(huì)結(jié)束匹配而不會(huì)回溯。我們以下面的表達(dá)式為例，

ab{1,3}+bc 

如果我們用文本"abbc"去匹配上面的表達(dá)式，匹配的過程如下圖所示(橙色為匹配，黃色為不匹配)，

可以發(fā)現(xiàn)，在第2和第3步，b{1,3}+會(huì)將文本中的2個(gè)字母b都匹配上，結(jié)果文本中只剩下一個(gè)字母c。那么在第4步時(shí)，正則中的b和文本中的c進(jìn)行匹配，當(dāng)無法匹配時(shí)，并不進(jìn)行回溯，這時(shí)候整個(gè)文本就無法和正則表達(dá)式發(fā)生匹配。如果將正則表達(dá)式中的加號(hào)(+)去掉，那么這個(gè)文本整體就是匹配的了。

把以上三種模式的表達(dá)式列出如下，

5. 總結(jié)

現(xiàn)在再回過頭看看文章開頭的那個(gè)很長(zhǎng)的正則表達(dá)式，其實(shí)簡(jiǎn)化之后，就是一個(gè)形如

^[允許字符集]+

的表達(dá)式。該字符集大小約為250，而+號(hào)表示至少出現(xiàn)一次。按照上面說到的NFA引擎貪婪模式，在用戶輸入一個(gè)過長(zhǎng)字符串進(jìn)行匹配時(shí)，一旦發(fā)生回溯，計(jì)算量將是巨大的。后來采用了獨(dú)占模式，CPU 100%的問題也得到了解決。

因此，在自己寫正則表達(dá)式的時(shí)候，一定不能大意，在實(shí)現(xiàn)功能的情況下，還要仔細(xì)考慮是否會(huì)帶來性能隱患。

【本文為51CTO專欄作者“阿里巴巴官方技術(shù)”原創(chuàng)稿件，轉(zhuǎn)載請(qǐng)聯(lián)系原作者】

戳這里，看該作者更多好文