Wie kann ich diesen regulären Ausdruck nicht in "katastrophalen Backtracking" führen?

Question

Ich versuche, eine URL passende regulären Ausdruck zu verwenden, die ich von http://daringfireball.net/2010/07/improved_regex_for_matching_urls bekam

(?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 
) 
) 

Basierend auf den Antworten auf another question, scheint es, dass es Fälle gibt, die diese Regex backtrack catastrophically verursachen. Zum Beispiel:

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)") 

... kann eine wirklich lange Zeit in Anspruch nehmen auszuführen (zB in Chrome)

Es scheint mir, dass das Problem in diesem Teil des Codes liegt:

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

... das scheint (.+|\((.+|(\(.+\)))*\))+ etwa gleich zu sein, was aussieht wie es (.+)+ enthält

gibt es eine Änderung, die ich, dass das wird vermeiden machen?

Answer 1

es die folgenden Ändern sollte die katastrophalen Rückzieher verhindern:

(?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 
) 
) 

Die einzige Änderung, die vorgenommen wurde, war die + nach den ersten [^\s()<>] in jedem des „balanced Pars“ Abschnitte des regex zu entfernen. Hier

ist die einzeilige Version zum Testen mit 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") 

Das Problem Teil des ursprünglichen Regex ist der symmetrische Klammer Abschnitt, zur Vereinfachung der Erklärung, warum der Rückzieher auftritt Ich werde vollständig die verschachtelte Klammern Teil davon entfernen, da es hier nicht relevant ist:

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

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

Überlegen sie, was hier mit der Zeichenfolge geschieht '(AAAAA', würde die wörtliche ( passen und dann AAAAA würde von der Gruppe verbraucht werden, und die ) würde nicht übereinstimmen. An diesem Punkt würde die Gruppe eine A aufgeben, AAAA gefangen lassen und versuchen, das Spiel an dieser Stelle fortzusetzen. Da die Gruppe eine * hat, die ihr folgt, kann die Gruppe mehrere Male übereinstimmen, so dass Sie jetzt übereinstimmten AAAA und dann A auf den zweiten Durchlauf haben. Wenn dies fehlschlägt, würde eine zusätzliche A durch die ursprüngliche Erfassung aufgegeben und durch die zweite Erfassung verbraucht werden.

Dies würde gehen für eine lange Zeit in den folgenden Versuchen resultierenden zu entsprechen, wobei jeder durch Kommata getrennte Gruppe eine andere Zeit zeigt an, dass die Gruppe abgestimmt ist, und wie viele Zeichen, die Instanz angepasst:

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

Ich habe vielleicht falsch gezählt, aber ich bin mir ziemlich sicher, dass es zu 16 Schritten addiert, bevor festgestellt wird, dass die Regex nicht übereinstimmen kann. Wenn Sie der Zeichenfolge weitere Zeichen hinzufügen, wächst die Anzahl der Schritte exponentiell.

Indem Sie die + entfernen und diese in \(([^\s()<>])*\) ändern, würden Sie dieses Backtracking-Szenario vermeiden.

Wenn Sie die Alternation wieder hinzufügen, um nach verschachtelten Klammern zu suchen, treten keine Probleme auf.

Beachten Sie, dass Sie möglicherweise eine Art von Anker bis zum Ende der Zeichenfolge hinzuzufügen, weil zur Zeit "http://google.com/?q=(AAAAAAAAAAAAAAAAAAAAAAAAAAAAA" wird kurz vor den ( zusammenpassen, so würde re.test(...)true weil http://google.com/?q= Matches zurück.