寫在前面

正則表達式一直以來褒貶不一，大家有疑問的地方主要就是它的悲觀回溯問題，今天就來詳細討論一下這個問題。

前幾天有小夥伴來求救説頁面上有一個 input 框，隨着用户不斷輸入內容，頁面響應會越來越慢直到完全失去響應。

簡單溝通過後得知具體場景是這樣的：

input 框中允許用户輸入一連串逗號分隔的商品id 在用户輸入的過程中實時檢測用户輸入的內容是否符合規則，若不符合則給出提示信息 小夥伴的解決方案也很直接：

給 input 框綁定 keyup 事件。 在 keyup 事件回調函數中通過正則表達式判斷是否符合規則，決定是否展示提示信息。 經過反覆驗證得到如下規律：

用户在輸入商品 id 的過程中（連續輸入多個數字）不會卡頓 當用户輸入逗號時，出現卡頓。隨着輸入商品 id 的數量增加，卡頓越來越明顯，直至瀏覽器失去響應。 於是打開 Chrome 開發者工具，選擇 Performance (原 Timeline) 標籤頁。將整個過程記錄下來，得到如下時間線：

其中黃色寬條表示 JavaScript 主線程的執行情況。連續的黃條越長，表示單次 JavaScript 運行的時間越長。也就意味着 UI 失去響應的時間越長。這一點從截圖中的藍色框中也可以得到印證。藍色框中的紅色長條表示瀏覽器一幀（一次渲染）所需要的時間。

那麼到底是 JavaScript 中的哪些代碼佔中了這麼長 CPU 時間呢？我們在底部的選項卡中選中 Bottom-Up ，按 Total Time 降序排列。得到如下結果：

可以看出，72.% 的 CPU 時間用在了一條正則表達式上。你肯定想到了，這就是小夥伴用來檢查用户輸入是否合法的正則表達式。

完整的正則表達式是這樣的：

/^\s*((\d+(\,|，)\d+)*|(\d+))\s*$//^\s*((\d+(\,|，)\d+)*|(\d+))\s*$/

接着去 regex101 上測試一下，測試數據如下，由 10 個商品 ID 組成的字符串：

123456789,123456789,123456789,123456789,123456789,123456789,123456789,123456789,123456789,123456789 執行結果如下：

可以看到執行速度非常快，只用了不到 1ms。

接下來在測試數據結尾加一個逗號，以模擬不符合規則的情況：

正則表達式執行的時間暴增到 4.15s。

經過多次測試發現：每次正常匹配執行的時間都很短。每次不匹配時，執行的時間都很長，且隨着字符串長度的增加，時間成倍的增長。

接下來讓我們認真的觀察一下這個正則表達式： /^\s*((\d+(,|，)\d+)*|(\d+))\s*$/ 去掉匹配首尾的空白字符，其核心結構只有兩部分 ((\d+(\,|，)\d+)* 與 (\d+)。前者用於匹配多個商品 ID 的情況，後者匹配只有一個商品 ID 的情況。

前者的基本模式是這樣的 商品ID,商品ID，然後把該模式重複多次。仔細觀察後很快我就發現了第一個問題，假設用户輸入的內容是 商品ID,商品ID,商品ID 。你會發現它符合輸入規則，但是不與該正則表達式匹配。因為第一次匹配後剩餘的字符串部分 ,商品ID 無法與基本模式形成匹配。

真的是這樣嗎？

測試發現，依然可以匹配。但匹配的內容和我們預期的並不一致。

最後一次匹配的內容是，9,123456789。不難想象第一次的匹配結果就是 123456789,12345678。

這裏可以看出小夥伴編寫的正則有兩個問題：

1. 邏輯錯誤。通過測試結果可以看出無法匹配出正確的商品 ID。如果商品 ID 運行只有 1 位數字，則匹配失敗。
2. 性能差。

在瞭解需求後，我給小夥伴提供了一種正則寫法： ^\s*(\d+(,|，))*\d+\s*$ 經過測試，這種寫法在保證邏輯無誤的前提下還保證了執行效率(在有數百個商品 ID 的情況下依然可以在幾毫秒內執行完畢)。

講到這裏，你可能會有兩個問題：

1. 為何第一種寫法的正則表達式匹配結果和我們預想的不一致。
2. 為何兩種寫法的性能差別如此之大。

要回答這個問題，還要從正則表達式中 * 符號的執行邏輯説起。

回溯

上面將了這麼多，主要是想説明正則表達式的回溯情況，如果大家還不瞭解，沒有關係，接下來通過一個簡單的例子講解一下。

大家都知道 * 表示匹配前面的子表達式 0 次或多次（且儘可能多的匹配）。但這個邏輯具體是如何執行的呢？讓我們通過幾個小例子來看一下。

示例1

假設有正則表達式 /^(a*)b$/ 和字符串 aaaaab。如果用該正則匹配這個字符串會得到什麼呢？

答案很簡單。兩者匹配，且捕獲組捕獲到字符串 aaaaa。

示例2

這次讓我們把正則改寫成 /^(a*)ab$/。再次和字符串 aaaaab 匹配。結果如何呢？

兩者依然匹配，但捕獲組捕獲到字符串 aaaa。因為捕獲組後續的表達式佔用了 1 個 a 字符。但是你有沒有考慮過這個看似簡單結果是經過何種過程得到的呢？

讓我們一步一步來看：

1. 匹配開始 (a*) 捕獲儘可能多的字符 a。
2. (a*) 一直捕獲，直到遇到字符 b。這時 (a*) 已經捕獲了 aaaaa。
3. 正則表達式繼續執行 (a*) 之後的 ab 匹配。但此時由於字符串僅剩一個 b 字符。導致無法完成匹配。
4. (a*) 從已捕獲的字符串中“吐”出一個字符 a。這時捕獲結果為 aaaa，剩餘字符串為 ab。
5. 重新執行正則中 ab的匹配。發現正好與剩餘字符串匹配。整個匹配過程結束。返回捕獲結果 aaaa。

從第3，4步可以看到，暫時的無法匹配並不會立即導致整體匹配失敗。而是會從捕獲組中“吐出”字符以嘗試。這個“吐出”的過程就叫回溯。

回溯並不僅執行一次，而是會一直回溯到另一個極端。對於 * 符號而言，就是匹配 0 次的情況。

示例3

這次我們把正則改為 /^(a*)aaaab$/。字符串依然為 aaaaab。根據前邊的介紹很容易直到。此次要回溯 4 次才可以完成匹配。具體執行過程不再贅述。

示例4

這次我們的正則改為 /^(a*)b$/。但是把要匹配的字符串改為 aaaaa。去掉了結尾的字符 b。

讓我們看看此時的執行流程：

1. (a*) 首先匹配了所有 aaaaa。
2. 嘗試匹配 b。但是匹配失敗。
3. 回溯 1 個字符。此時剩餘字符串為 a。依然無法匹配字符 b。
4. 回溯一直進行。直到匹配 0 次的情況。此時剩餘字符串為 aaaaa。依然無法匹配 b。
5. 所有的可能性均已嘗試過，依然無法匹配。最終導致整體匹配失敗。

可以看到，雖然我們可以一眼看出二者無法匹配。但正則表達式在執行時還要“傻傻的”逐一回溯所有可能性，才能確定最終結果。這個“傻傻的”回溯過程就叫悲觀回溯。

雖然這個過程看起來有點傻，但是不是感覺也沒什麼大問題？為何會有性能問題呢？讓我們回到最初的那個正則表達式。

示例5

這次正則表達式回到 ^\s*((\d+(,|，)\d+)*|(\d+))\s*$。字符串為123456789,123456789,123456789, 執行的結果依然為不匹配。這點毫無疑問。但問題是，執行的過程中，進行了多少次回溯呢？

讓我們統計一下：

1. 首輪執行過後的捕獲結果是 123456789,12345678，9,123456789。但這時剩餘字符串僅剩 , 一個字符。於是開始悲觀回溯。

2. 首先看第一個匹配不變的情況下，第二個匹配組回溯的情況。

   a. 回退 1 個字符。剩餘字符串為 9,。不匹配。共回溯 1 次。
   b. 回退 2 個字符。剩餘字符串為 89,。不匹配。但是 89 又進行一次回溯。共回溯 2 次。
   c. 以此類推。最多回退 8 個字符。此時剩餘字符串為 23456789,。共可以回溯 8 次。
   d. 累計回溯 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 = 36 次。

3. 接着，第一個捕獲組回溯 1 個字符。捕獲結果變為 123456789,1234567，89,123456789。此時又將循環一遍 2 中的所有邏輯。累計回溯 36 + 1次。

4. 以此類推，全部回溯完成，需要回溯 324 次。

假設我們增加一個商品 ID，字符串變為 123456789,123456789,123456789,123456789,。此時的回溯次數增加到 2628 次。

以此類推可得。

商品 ID 個數 | 回溯次數 | | -------- | --------- | | 3 | 324 | | 4 | 2628 | | 5 | 21060 | | 6 | 168516 | | 7 | 1348164 | | 8 | 10785348 | | 9 | 86282820 | | 10 | 690262596

可見問題在於，隨着商品 ID 個數的增長，回溯次數會成指數級增長。最終導致 JavaScript 主進程忙於進行計算，使頁面失去響應。

但是我當時給出的解決方案：

^\s*(\d+(,|，))*\d+\s*$

也使用了 * 符號，按説也會進行悲觀回溯。為何沒有性能問題呢？

答案在於，對於同一字符串是否有多種可行的匹配模式。也就是説對於某個固定的字符串，你的正則表達式是否有“唯一解”。

舉例對於我給出的正則，對於字符串 123456789,123456789,123456789 只可能有 1 種匹配結果。那就是 123456789,，123456789, 和 123456789。因此，在回溯時只需進行一次線性的回溯即可（24 次）。而不會像前面分析的第一種正則一樣，有多種“可能”的匹配方式。

解決方案

在瞭解了悲觀回溯為何會導致性能問題後，就可以考慮如何解決這個問題。要解決這個問題，大概有以下幾個思路：

方案一：禁止回溯

這個思路很直接，既然回溯可能有性能問題，那我們是否可以禁止正則表達式進行回溯呢。

答案是：可以。

有兩種語法可以防止回溯：

• 有限量詞（Possessive Quantifiers）
• 原子分組（Atomic Grouping）

關於這兩種語法，感興趣的同學可以自行 Google。在此不詳細解釋。因為這兩種語法在 JavaScript 中均不被支持。

方案二：避免導致性能問題的回溯

這個思路也比較容易想到。其實經過思考不難想到。兩種模式的正則表達式很可能會導致有性能問題的回溯。

• 前後重複的模式。 例如 /x*x*/。雖然這個例子看起來很“弱智”，但是當規則變複雜時，每一個 x 又可能是由多個子表達式組成的。當這些子表達式存在邏輯上的交集時，就可能會出現性能問題。
• 嵌套的量詞。例如 /(x*)*/。包括文中提到的第一個正則也屬於這種模式。

當我們在編寫正則表達式時寫出了這種模式的時候，大家就要謹慎起來。考慮一下是否有潛在的性能問題，是否有更好的寫法了。

方案三：不使用正則表達式

其實像文中舉的這個例子，甚至都沒必要使用正則表達式。直接寫一個 JavaScript 函數，按逗號切分字符串，逐個字符判斷即可。而且可以保證代碼的性能是線性的。

參考

[1]正則表達式的悲觀回溯
[2]正則表達式回溯漏洞
[3]正則表達式中的悲觀回溯