Javascript 災(zāi)難性回溯

有些正則表達(dá)式看起來很簡單，但執(zhí)行起來耗時卻非常長，甚至?xí)?dǎo)致 JavaScript 引擎“掛起”。

大多數(shù)開發(fā)者遲早會遇到這樣的情況。典型的癥狀就是 —— 正則表達(dá)式有時可以正常工作，但對于某些字符串，它會消耗 100% 的 CPU 算力，出現(xiàn)“掛起”的現(xiàn)象。

在這種情況下，Web 瀏覽器會建議終止腳本并重新加載頁面。這顯然不是我們愿意看到的。

對于服務(wù)器端 JavaScript，這樣的正則表達(dá)式可能會掛起服務(wù)器進(jìn)程，這甚至更糟。所以我們絕對應(yīng)該研究研究它。

舉例

假設(shè)，我們現(xiàn)在有一個字符串，我們想檢查其中是否包含一些后面跟著可選空格 \s? 的單詞 \w+。

構(gòu)造此正則表達(dá)式最顯而易見的方式是一個單詞后跟著一個可選空格 \w+\s?，然后用 * 重復(fù)它。

寫成正則表達(dá)式即 ^(\w+\s?)*$，它指定 0 個及以上這樣的詞，從開頭 ^ 開始，并在行的結(jié)尾 $ 結(jié)束。

運行一下：

let regexp = /^(\w+\s?)*$/;

alert( regexp.test("A good string") ); // true
alert( regexp.test("Bad characters: $@#") ); // false

這似乎能正常工作。結(jié)果是正確的。但在特定的字符串上，它會消耗很多時間。它耗時太久以至于讓 CPU 會跑滿 100% 負(fù)載，導(dǎo)致 JavaScript 引擎“掛起”。

如果你運行下面這個例子，由于 JavaScript 會進(jìn)導(dǎo)致“掛起”，所以你可能什么結(jié)果都看不到。此時瀏覽器會停止對事件的響應(yīng)，UI 也會停止工作。一段時間之后，瀏覽器會建議重新加載頁面。所以請謹(jǐn)慎對待：

let regexp = /^(\w+\s?)*$/;
let str = "An input string that takes a long time or even makes this regexp hang!";

// 會耗費很長時間
alert( regexp.test(str) );

有一些正則表達(dá)式引擎可以很好地處理這樣的搜索，例如從 8.8 版本開始的 V8 引擎（因此 88 及以上版本的 Google Chrome 不會在這里掛起），而火狐（Firefox）瀏覽器確實會掛起。

簡化的例子

問題出在哪？為什么正則表達(dá)式會導(dǎo)致“掛起”？

為了理解它，我們來簡化一下例子：移除空格符 \s?，使其簡化為 ^(\w+)*$。

同時為了讓問題更明顯，再用 \d 替換掉 \w。生成的新正則表達(dá)式執(zhí)行時仍會導(dǎo)致掛起，例如：

let regexp = /^(\d+)*$/;

let str = "012345678901234567890123456789z";

// 會消耗很長時間（請小心?。?alert( regexp.test(str) );

所以正則表達(dá)式哪里出了問題？

首先，有人可能會注意到這個正則表達(dá)式的 (\d+)* 部分有點奇怪。量詞 * 看起來沒什么必要。如果我們要匹配一個數(shù)字，那可以使用 \d+。

實際上，正則表達(dá)式很死板。我們通過簡化前面的例子得到了一個簡化版的正則表達(dá)式。但慢的原因是一樣的。所以讓我們來理解一下它的執(zhí)行過程，然后問題的原因就會顯而易見了。

在 123456789z 這行（清楚起見，這里縮短了字符串，請注意末尾的非數(shù)字字符 z，這很重要）中搜索 ^(\d+)*$ 時到底發(fā)生了什么，為什么耗時這么久？

下面是正則表達(dá)式引擎的執(zhí)行過程：

1. 首先，正則表達(dá)式引擎嘗試查找括號中的內(nèi)容：數(shù)字 \d+。加號 + 默認(rèn)為貪婪模式，所以它消耗了所有數(shù)字：

   \d+.......
   (123456789)z

   消耗完所有數(shù)字后，認(rèn)為找到了 \d+（如 123456789）。

   然后它嘗試應(yīng)用星號量詞，但此時已經(jīng)沒有更多數(shù)字了，所以星號沒有給出任何信息。

   模式中接下來的 $ 匹配字符串的結(jié)束，但是我們例子的文字中有 z，所以匹配失?。?/p>

              X
   \d+........$
   (123456789)z

2. 由于沒有匹配結(jié)果，貪婪量詞 + 的重復(fù)匹配次數(shù)會減一，并回溯一個字符。

   現(xiàn)在 \d+ 會匹配除了最后一個數(shù)字之外的所有數(shù)字（12345678）：

   \d+.......
   (12345678)9z

3. 然后引擎嘗試從新位置 (9) 繼續(xù)搜索。

   星號 (\d+)* 可以成功應(yīng)用 —— 它匹配到了數(shù)字 9：

   \d+.......\d+
   (12345678)(9)z

   引擎再次去嘗試匹配 $，但又失敗了，因為它遇到了 z：

                X
   \d+.......\d+
   (12345678)(9)z

4. 沒有匹配結(jié)果，所以引擎繼續(xù)回溯，減少重復(fù)匹配次數(shù)?；厮萃ǔＪ沁@樣工作的：最后一個貪婪量詞逐漸減少重復(fù)次數(shù)，直到達(dá)到最小值。然后前一個貪婪量詞再減少重復(fù)次數(shù)，以此類推。

   它會嘗試所有可能的排列組合，這里是它們的例子。

   第一個數(shù)字 \d+ 有 7 位數(shù)，后面跟著一個 2 位數(shù)的數(shù)字：

                X
   \d+......\d+
   (1234567)(89)z

   第一個數(shù)字有 7 位數(shù)，后面跟著兩個 1 位數(shù)：

                  X
   \d+......\d+\d+
   (1234567)(8)(9)z

   第一個數(shù)字有 6 位數(shù)，后面跟著一個 3 位數(shù)：

                X
   \d+.......\d+
   (123456)(789)z

   第一個數(shù)字有 6 位數(shù)，后面跟著兩個數(shù)字：

                  X
   \d+.....\d+ \d+
   (123456)(78)(9)z

   ……以此類推。

有很多種方式可以將數(shù)字序列 123456789 拆分為多個數(shù)字。準(zhǔn)確地說，有 2n-1 種，其中 n 是序列的長度。

• 對于 ?123456789?，?n=9?，也就是說有 511 種組合。
• 對于更長一點的 ?n=20? 的字符串，差不多有 100 萬種組合。
• 對于 ?n=30? —— 又增加了 1000 倍以上（1073741823 種組合）。

搜索需要這么長時間正是因為在一個一個地嘗試這么多種組合。

回到單詞和字符串

在我們第一個例子中，當(dāng)我們用 ^(\w+\s?)*$ 這種模式在字符串 An input that hangs! 中查找單詞時，就會發(fā)生類似的問題。

就是因為一個單詞 \w+ 可以被表示成很多種：

(input)
(inpu)(t)
(inp)(u)(t)
(in)(p)(ut)
...

以我們?nèi)说慕嵌葋砜矗茱@然它無法匹配成功，因為示例中的字符串以嘆號 ! 結(jié)尾，然而正則表達(dá)式期望在的是一個單詞 \w 末尾有或沒有空格 \s。但引擎理解不了這種狀況。

它嘗試了 (\w+\s?)* 的所有排列組合試圖去囊括整個字符串，包括帶空格 (\w+\s)* 的情形和不帶空格 (\w+)* 的情形（因為空格 \s? 是可選的）。由于各種排列組合的數(shù)量（我們已經(jīng)通過計算直觀感受過了）太多了，所以耗費了大量時間去查詢。

那怎么辦？

我們應(yīng)該改用懶惰模式嗎？

不幸的是，這沒用：如果我們用 \w+? 去替代 \w+，還是會掛起。排列組合的順序會變化，但是總數(shù)不變。

有些正則表達(dá)式引擎具有對棘手內(nèi)容的測試和自動化有限處理，可以避免遍歷所有排列組合來優(yōu)化速度，但大多數(shù)引擎沒有，而且也不是在所有情況下都有效果。

如何解決？

主要有 2 種解決方式。

第一種是減少可能的組合數(shù)量。

讓我們把正則表達(dá)式重寫為 ^(\w+\s)*\w*$ 以使空格變?yōu)榉强蛇x的 —— 我們將查找任意數(shù)量的單詞后跟空格 (\w+\s)*，然后跟著最后一個單詞 \w*（可選）。

這個正則表達(dá)式等同于之前那個（匹配內(nèi)容相同），并且運行起來也沒問題：

let regexp = /^(\w+\s)*\w*$/;
let str = "An input string that takes a long time or even makes this regex hang!";

alert( regexp.test(str) ); // false

為什么問題消失了？

因為現(xiàn)在空格是強制性的。

前面的正則表達(dá)式，如果我們省略空格，就會變成 (\w+)*，導(dǎo)致單個單詞中有很多 \w+ 組合 。

所以 input 可以匹配為 \w+ 的兩次重復(fù)，如下所示：

\w+  \w+
(inp)(ut)

新模式有所不同：(\w+\s)* 指定單詞的重復(fù)后面跟著一個空格！input 字符串不能匹配為 \w+\s 的兩次重復(fù)，因為空格是強制性的。

現(xiàn)在節(jié)省了嘗試大量（實際上是大多數(shù)）組合所需的時間。

防止回溯

有時候重寫正則表達(dá)式會比較麻煩。在上面的示例中，這很容易，但如何做到這一點并不總是很明顯。

此外，重寫的正則表達(dá)式通常更復(fù)雜，這并不好。在不做其他更改的情況下，正則表達(dá)式已經(jīng)夠復(fù)雜了。

幸運的是，還有另一種方式。我們可以禁止量詞的回溯。

問題的根源在于正則表達(dá)式引擎嘗試了許多對人類看來顯然是錯誤的組合。

例如，正則表達(dá)式 (\d+)*$ 中 + 對于我們?nèi)祟悂碚f很明顯不應(yīng)去回溯。就算我們用兩個單獨的 \d+\d+ 去替換一個 \d+，也根本沒變化：

\d+........
(123456789)!

\d+...\d+....
(1234)(56789)!

在原先的那個例子 ^(\w+\s?)*$ 中，我們可能希望在 \w+ 中禁止回溯。即：\w+ 應(yīng)該匹配一個完整的單詞，并且具有最大可能的長度。無需降低 \w+ 的重復(fù)次數(shù)或?qū)⑵洳鸱譃閮蓚€單詞 \w+\w+ 等等。

為此，現(xiàn)代正則表達(dá)式引擎支持占有型量詞（Possessive Quantifiers）。如果我們在常規(guī)量詞之后添加 +，則常規(guī)量詞就變成了占有型量詞。也就是說，我們可以使用 \d++ 替代 \d+ 來阻止 + 回溯。

占有型量詞實際上比“常規(guī)”量詞更簡單。它們只是盡可能多地匹配，沒有任何回溯。沒有回溯的搜索過程更簡單。

還有所謂的“原子捕獲組” —— 一種禁用括號內(nèi)回溯的方法。

……但壞消息是，JavaScript 并不支持它。

我們可以通過使用“前瞻變換（lookahead transform）”來模擬它們。

用前瞻視角解決問題

所以，我們來到了真正的高階主題。我們希望量詞，例如 + 不要回溯，因為有時回溯沒有意義。

在不回溯的情況下盡可能多地重復(fù) \w 的模式可以寫為：(?=(\w+))\1。當(dāng)然，我們可以采用另一種模式來代替 \w。

這可能看起來很奇怪，但它實際上是一個非常簡單的轉(zhuǎn)換。

讓我們解讀一下：

• 前瞻斷言 ??=? 從當(dāng)前位置開始，向前查找最長的單詞 ?\w+?。
• 引擎不會去記住帶有 ??=...? 的括號中的內(nèi)容。所以將 ?\w+? 放入括號中，這樣引擎就會記住這些內(nèi)容了。
• ……然后用 ?\1? 來引用括號中的內(nèi)容。

也就是說：我們先進(jìn)行前瞻查找 —— 如果有符合 \w+ 的單詞，我們就可將其匹配為 \1。

為什么？因為前瞻斷言查找到一個單詞 \w+，將其作為一個整體，然后將其捕獲為 \1。所以我們最終實現(xiàn)了一種占有型加號 + 量詞。它只捕獲整個單詞 \w+，而不會只捕獲一部分。

例如，在單詞 JavaScript 中不僅可以匹配 Java，而且可以忽略 Script，以匹配模式的其余部分。

下面是 2 個模式的對比：

alert( "JavaScript".match(/\w+Script/)); // JavaScript
alert( "JavaScript".match(/(?=(\w+))\1Script/)); // null

1. 第一個變體 \w+ 首先捕獲整個 JavaScript 單詞，然而接下來 + 會一個字符一個字符地進(jìn)行回溯，試圖匹配整個模式的其余部分，直到 \w+ 匹配到了 Java 時，它最終才匹配成功。
2. 第二個變體 (?=(\w+)) 前瞻查找并匹配整個單詞 JavaScript，然后把整個單詞作為一個整體包含進(jìn) \1 中，所以在它后面就無法查找到 Script 了。

當(dāng)我們需要禁止 + 進(jìn)行回溯，只需要把 (?=(\w+))\1 中的 \w 替換成更復(fù)雜的正則表達(dá)式就能實現(xiàn)了。

請注意：

這些文章中有更多關(guān)于占有型量詞和前瞻斷言之間關(guān)系的內(nèi)容：正則表達(dá)式：使用前瞻斷言模擬原子分組（和占有型量詞） 和 模擬原子組。

現(xiàn)在讓我們用前瞻斷言重寫第一個例子中的正則表達(dá)式來防止回溯吧：

let regexp = /^((?=(\w+))\2\s?)*$/;

alert( regexp.test("A good string") ); // true

let str = "An input string that takes a long time or even makes this regex hang!";

alert( regexp.test(str) ); // false，有效且執(zhí)行的很快！

這里我們用 \2 而不是 \1，因為這里有額外的外部括號。為了防止數(shù)字弄混了，我們可以給括號命名，例如 (?<word>\w+)。

// 括號被命名為 ?<word>，使用 \k<word> 進(jìn)行引用
let regexp = /^((?=(?<word>\w+))\k<word>\s?)*$/;

let str = "An input string that takes a long time or even makes this regex hang!";

alert( regexp.test(str) ); // false

alert( regexp.test("A correct string") ); // true

本文所描述的問題稱作“災(zāi)難性回溯（Catastrophic Backtracking）”，又譯作“回溯陷阱”。

我們介紹了兩種解決方式：

• 重寫正則表達(dá)式，以盡可能降低可能的組合數(shù)量。
• 防止回溯。