災難性回溯

有些正規表示法看起來很簡單，但執行時間可能會非常長，甚至會讓 JavaScript 引擎「當機」。

大多數開發人員遲早都會遇到這種情況。典型的症狀是：正規表示法有時可以正常運作，但對於某些字串，它會「當機」，耗用 100% 的 CPU。

在這種情況下，網路瀏覽器會建議終止腳本並重新載入頁面。這肯定不是一件好事。

對於伺服器端 JavaScript，此類正則表示式可能會讓伺服器程序當機，這更糟。所以我們絕對應該仔細看看。

範例

假設我們有一個字串，我們想要檢查它是否包含字詞 \w+，每個字詞後面有一個空格 \s?（可選）。

建構正則表示式的明顯方法是取一個字詞，後面接一個空格 \w+\s?，然後用 * 重複。

這會讓我們得到正則表示式 ^(\w+\s?)*$，它指定零個或多個此類字詞，從開頭 ^ 開始，到結尾 $ 結束。

實際操作

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

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

正則表示式似乎有效。結果是正確的。儘管如此，在某些字串上，它需要花費大量時間。JavaScript 引擎會「當機」，CPU 使用率達到 100%。

如果您執行以下範例，您可能什麼都看不到，因為 JavaScript 會「當機」。網頁瀏覽器將停止對事件做出反應，使用者介面將停止運作（大多數瀏覽器只允許捲動）。過一段時間後，它會建議重新載入頁面。所以要小心

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

// will take a very long time
alert( regexp.test(str) );

公平地說，讓我們注意，有些正規表示式引擎可以有效地處理此類搜尋，例如從 8.8 版開始的 V8 引擎就可以做到這一點（因此 Google Chrome 88 在這裡不會當機），而 Firefox 瀏覽器會當機。

簡化的範例

問題出在哪裡？為什麼正規表示式會當機？

為了理解這一點，讓我們簡化範例：移除空格 \s?。然後它會變成 ^(\w+)*$。

為了讓事情更明顯，讓我們用 \d 替換 \w。產生的正規表示式仍然會當機，例如

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

let str = "012345678901234567890123456789z";

// will take a very long time (careful!)
alert( regexp.test(str) );

那麼正則表示式出了什麼問題？

首先，我們可能會注意到正則表示式 (\d+)* 有點奇怪。量詞 * 看起來很奇怪。如果我們想要一個數字，我們可以使用 \d+。

的確，正則表示式是人為的；我們是透過簡化前一個範例得到的。但它之所以慢的原因是一樣的。所以讓我們理解它，那麼前一個範例就會變得顯而易見。

在字串 123456789z（為清楚起見縮短了一點，請注意結尾有一個非數字字元 z，這很重要）中搜尋 ^(\d+)*$ 時發生了什麼事？為什麼需要這麼長的時間？

以下是正則表示式引擎執行的動作

1. 首先，正則表示式引擎會嘗試尋找括號中的內容：數字 \d+。預設情況下，加號 + 是貪婪的，因此它會使用所有數字

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

   在使用完所有數字後，\d+ 被視為已找到（例如 123456789）。

   然後套用星號量詞 (\d+)*。但是文字中沒有更多數字了，所以星號什麼都沒有給。

   樣式中的下一個字元是字串結尾 $。但在文字中，我們有 z，所以沒有匹配項

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

2. 由於沒有匹配項，貪婪量詞 + 會減少重複次數，回溯一個字元。

   現在 \d+ 會取用所有數字，除了最後一個（12345678）

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

3. 然後，引擎會嘗試從下一個位置（12345678 之後）繼續搜尋。

   星號 (\d+)* 可以套用，它會再提供一個 \d+ 的比對結果，數字 9

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

   引擎再次嘗試比對 $，但失敗了，因為它遇到 z

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

4. 沒有比對結果，因此引擎將繼續回溯，減少重複次數。回溯通常像這樣運作：最後一個貪婪量詞會減少重複次數，直到達到最小值。然後前一個貪婪量詞會減少，依此類推。

   所有可能的組合都會被嘗試。以下是範例。

   第一個數字 \d+ 有 7 個位數，然後是一個 2 位數的數字

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

   第一個數字有 7 個位數，然後是兩個 1 位數的數字

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

   第一個數字有 6 個位數，然後是一個 3 位數的數字

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

   第一個數字有 6 個位數，然後是 2 個數字

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

   …以此類推。

有許多方法可以將數字序列 123456789 分割成數字。精確來說，有 2n-1 種方法，其中 n 是序列的長度。

• 對於 123456789，我們有 n=9，因此有 511 種組合。
• 對於 n=20 的較長序列，大約有一百萬 (1048575) 種組合。
• 對於 n=30，多了一千倍 (1073741823 種組合)。

逐一嘗試這些組合，正是搜尋花費這麼長時間的原因。

回到字詞和字串

在我們的第一個範例中，當我們在字串 An input that hangs! 中使用模式 ^(\w+\s?)*$ 尋找字詞時，發生了類似的事情。

原因是字詞可以表示為一個 \w+ 或多個

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

對人類來說，很明顯沒有比對結果，因為字串以驚嘆號 ! 結尾，但正規表示式預期最後會有一個字元 \w 或一個空白 \s。但引擎不知道這一點。

它嘗試正規表示式 (\w+\s?)* 可以「消耗」字串的所有組合，包括有空白 (\w+\s)* 和沒有空白 (\w+)* 的變體（因為空白 \s? 是可選的）。由於有許多這樣的組合（我們在數字中看過），因此搜尋花費了很長的時間。

該怎麼辦？

我們應該開啟懶惰模式嗎？

很遺憾，這沒有幫助：如果我們將 \w+ 替換為 \w+?，正規表示式仍然會當機。組合的順序會改變，但總數不會改變。

有些正規表示式引擎有棘手的測試和有限自動化，可以避免進行所有組合或讓它快得多，但大多數引擎沒有，而且它並不總是能提供幫助。

如何修復？

有兩種主要方法可以修復問題。

第一個是降低可能的組合數量。

我們透過將正規表示式改寫為 ^(\w+\s)*\w*$ 來讓空白變成非選項 – 我們將尋找任何數量，後面接著空白 (\w+\s)* 的字詞，然後（選擇性地）一個最後的字詞 \w*。

這個正規表示式等同於前一個（比對相同），而且運作良好。

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

為什麼問題消失了？

那是因為現在空白是強制性的。

前一個正規表示式，如果我們省略空白，會變成 (\w+)*，導致在單一字詞中出現許多 \w+ 的組合。

因此 input 可以比對成 \w+ 的兩個重複，如下所示

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

新的樣式不同：(\w+\s)* 指定字詞的重複，後面接著空白！input 字串無法比對成 \w+\s 的兩個重複，因為空白是強制性的。

現在省下了嘗試許多（實際上是大部分）組合所需的時間。

防止回溯

不過，重新寫正規表示式並不總是方便。在上面的範例中很容易，但要如何執行並不總是顯而易見。

此外，重新寫的正規表示式通常更複雜，這並不好。正規表示式已經夠複雜，不需要額外的努力。

幸運的是，有一個替代方法。我們可以禁止量詞的回溯。

問題的根源在於正規表示式引擎嘗試許多對人類來說顯然錯誤的組合。

例如，在正規表示式 (\d+)*$ 中，對人類來說很明顯，+ 不應該回溯。如果我們將一個 \d+ 替換成兩個分開的 \d+\d+，什麼都不會改變。

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

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

而在原始範例 ^(\w+\s?)*$ 中，我們可能想要禁止 \w+ 中的回溯。也就是說：\w+ 應該比對整個字詞，而且長度要儘可能長。沒有必要降低 \w+ 中的重複計數，或將其拆分成兩個字詞 \w+\w+ 等等。

現代的正規表示式引擎支援佔有量詞。如果在正規量詞後加上 +，正規量詞就會變成佔有量詞。也就是說，我們使用 \d++ 取代 \d+ 來阻止 + 回溯。

佔有量詞實際上比「正規」量詞更簡單。它們只會盡可能地匹配，而不會回溯。沒有回溯的搜尋程序更簡單。

還有一種所謂的「原子捕獲群組」，這是一種在括號內停用回溯的方法。

…但壞消息是，JavaScript 不幸地不支援它們。

不過，我們可以使用「前瞻轉換」來模擬它們。

前瞻來救援！

因此，我們已經進入真正的進階主題。我們希望量詞，例如 + 不要回溯，因為有時候回溯沒有意義。

在不回溯的情況下，取用 \w 的重複次數最多的模式為：(?=(\w+))\1。當然，我們可以使用 \w 以外的其他模式。

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

讓我們解碼它

• 前瞻 ?= 從目前位置向前尋找最長的字詞 \w+。
• 引擎不會記住 ?=... 中括號的內容，所以將 \w+ 包在括號中。然後引擎會記住它們的內容
• …並允許我們在模式中將它們參照為 \1。

也就是說：我們向前看，如果有一個字詞 \w+，則將它匹配為 \1。

為什麼？那是因為前瞻將字詞 \w+ 作為一個整體找到，並且我們使用 \1 將它擷取到模式中。因此，我們基本上實作了一個佔有加號 + 量詞。它只擷取整個字詞 \w+，而不是它的部分。

例如，在字詞 JavaScript 中，它可能不僅匹配 Java，而且會略過 Script 來匹配模式的其餘部分。

以下是兩個模式的比較

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

1. 在第一個變體中，\w+ 首先捕獲整個字詞 JavaScript，但接著 + 會逐字回溯，嘗試比對模式的其餘部分，直到最後成功（當 \w+ 比對到 Java）。
2. 在第二個變體中，(?=(\w+)) 向前查看並找到字詞 JavaScript，該字詞透過 \1 整個包含在模式中，因此在字詞之後找不到 Script。

當我們需要禁止 + 之後回溯時，我們可以將更複雜的正規表示式放入 (?=(\w+))\1 中，而不是 \w。

讓我們使用向前查看重寫第一個範例以防止回溯

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, works and fast!

這裡使用 \2 而不是 \1，因為有額外的外層括號。為了避免弄亂數字，我們可以為括號命名，例如 (?<word>\w+)。

// parentheses are named ?<word>, referenced as \k<word>
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

本文中描述的問題稱為「災難性回溯」。

我們介紹了兩種解決方法

• 重寫正規表示式以降低可能的組合數。
• 防止回溯。