如何讓這個正則表達式不會導致「災難性回溯」？

Question

我試圖用一個URL匹配的正則表達式，我從http://daringfireball.net/2010/07/improved_regex_for_matching_urls

(?xi) 
\b 
(      # Capture 1: entire matched URL 
    (?: 
    https?://    # http or https protocol 
    |      # or 
    www\d{0,3}[.]   # "www.", "www1.", "www2." … "www999." 
    |       # or 
    [a-z0-9.\-]+[.][a-z]{2,4}/ # looks like domain name followed by a slash 
) 
    (?:      # One or more: 
    [^\s()<>]+     # Run of non-space, non-()<> 
    |       # or 
    \(([^\s()<>]+|(\([^\s()<>]+\)))*\) # balanced parens, up to 2 levels 
)+ 
    (?:      # End with: 
    \(([^\s()<>]+|(\([^\s()<>]+\)))*\) # balanced parens, up to 2 levels 
    |        # or 
    [^\s`!()\[\]{};:'".,<>?«»「」‘’]  # not a space or one of these punct chars 
) 
) 

了基於答案another question，似乎有導致此正則表達式來backtrack catastrophically箱子。例如：

var re = /\b((?:https?:\/\/|www\d{0,3}[.]|[a-z0-9.\-]+[.][a-z]{2,4}\/)(?:[^\s()<>]+|\(([^\s()<>]+|(\([^\s()<>]+\)))*\))+(?:\(([^\s()<>]+|(\([^\s()<>]+\)))*\)|[^\s`!()\[\]{};:'".,<>?«»「」‘’]))/i; 
re.test("http://google.com/?q=(AAAAAAAAAAAAAAAAAAAAAAAAAAAAA)") 

...可能需要很長的時間來執行（例如，在Chrome）

在我看來，問題在於這部分代碼：

(?:      # One or more: 
    [^\s()<>]+     # Run of non-space, non-()<> 
    |       # or 
    \(([^\s()<>]+|(\([^\s()<>]+\)))*\) # balanced parens, up to 2 levels 
)+ 

...這似乎是大致相當於(.+|\((.+|(\(.+\)))*\))+，它看起來像它包含(.+)+

有沒有變化我可以作出這樣會避免？

Answer 1

將其更改爲以下應防止災難性回溯：

(?xi) 
\b 
(      # Capture 1: entire matched URL 
    (?: 
    https?://    # http or https protocol 
    |      # or 
    www\d{0,3}[.]   # "www.", "www1.", "www2." … "www999." 
    |       # or 
    [a-z0-9.\-]+[.][a-z]{2,4}/ # looks like domain name followed by a slash 
) 
    (?:      # One or more: 
    [^\s()<>]+     # Run of non-space, non-()<> 
    |       # or 
    \(([^\s()<>]|(\([^\s()<>]+\)))*\) # balanced parens, up to 2 levels 
)+ 
    (?:      # End with: 
    \(([^\s()<>]|(\([^\s()<>]+\)))*\) # balanced parens, up to 2 levels 
    |        # or 
    [^\s`!()\[\]{};:'".,<>?«»「」‘’]  # not a space or one of these punct chars 
) 
) 

這是由在每一個「平衡的括號」正則表達式的部分的第一[^\s()<>]後刪除+的唯一變化。

這裏是一個行版本測試與JS：

var re = /\b((?:https?:\/\/|www\d{0,3}[.]|[a-z0-9.\-]+[.][a-z]{2,4}\/)(?:[^\s()<>]+|\(([^\s()<>]|(\([^\s()<>]+\)))*\))+(?:\(([^\s()<>]|(\([^\s()<>]+\)))*\)|[^\s`!()\[\]{};:'".,<>?«»「」‘’]))/i; 
re.test("http://google.com/?q=(AAAAAAAAAAAAAAAAAAAAAAAAAAAAA") 

原正則表達式的問題部分是平衡的括號部分，以簡化爲什麼回溯發生時，我要徹底的解釋除去它的嵌套的括號部分，因爲它不是與此有關：

\(([^\s()<>]+|(\([^\s()<>]+\)))*\) # original 
\(([^\s()<>]+)*\)      # expanded below 

\(    # literal '(' 
(    # start group, repeat zero or more times 
    [^\s()<>]+  # one or more non-special characters 
)*    # end group 
\)    # literal ')' 

考慮一下用字符串'(AAAAA'這裏發生，字面(將匹配然後該組將消耗，並且)將無法​​匹配。在這一點上，該組將放棄一個A，保留AAAA，並嘗試在此時繼續比賽。因爲該組後面有一個*，該組可以匹配多次，所以現在您將有([^\s()<>]+)*匹配AAAA，然後在第二次通過時匹配A。當這失敗時，另一個A將被原始捕獲放棄並被第二次捕獲消耗。

這將繼續長期而導致以下嘗試匹配，其中每個逗號分隔的組表示該組匹配不同的時間，以及有多少字符實例匹配：

AAAAA 
AAAA, A 
AAA, AA 
AAA, A, A 
AA, AAA 
AA, AA, A 
AA, A, AA 
AA, A, A, A 
.... 

我可能計算錯了，但我確定它確定在正確表達式不匹配之前共計16步。隨着您繼續在字符串中添加其他字符，計算出來的步數將呈指數級增長。

通過刪除+並將其更改爲\(([^\s()<>])*\)，您將避免此回溯情況。

添加交替回來檢查嵌套圓括號不會導致任何問題。

請注意，您可能需要添加某種錨字符串的結束，因爲目前"http://google.com/?q=(AAAAAAAAAAAAAAAAAAAAAAAAAAAAA"將匹配到之前的(，所以re.test(...)將返回true因爲http://google.com/?q=匹配。