¿Cómo puedo hacer que esta expresión regular no dé como resultado un "retroceso catastrófico"?

Question

estoy tratando de utilizar una URL que coincida con la expresión regular que obtuve de 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 
) 
) 

Sobre la base de las respuestas a another question, parece que hay casos en los que causan esta expresión regular para backtrack catastrophically. Por ejemplo:

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

... puede tomar un tiempo muy largo para ejecutar (por ejemplo, en Chrome)

Me parece que el problema radica en esta parte del código:

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

... que parece ser más o menos equivalente a (.+|\((.+|(\(.+\)))*\))+, que parece que contiene (.+)+

¿hay un cambio puedo hacer que evitará que?

Answer 1

Si lo cambia a la siguiente debe impedir la vuelta hacia atrás catastrófico:

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

El único cambio que se hizo fue eliminar la + después de la primera [^\s()<>] en cada uno de los "parens equilibradas" porciones de la expresión regular.

Aquí está la versión de una línea para las pruebas con 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") 

La porción problema de la expresión regular original es la sección de paréntesis equilibrados, para simplificar la explicación de por qué el retroceso se produce Voy a por completo eliminar la parte de paréntesis anidado de ella, ya que no es relevante aquí:

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

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

considere lo que sucede aquí con la cadena '(AAAAA', lo literal ( coincidiría y luego AAAAA sería consumido por el grupo, y el ) no coincidiría. En este punto, el grupo renunciaría a uno A, dejando AAAA capturado e intentando continuar el partido en este momento. Debido a que el grupo tiene un * siguiente, el grupo puede coincidir varias veces, por lo que ahora tendría ([^\s()<>]+)* haciendo coincidir AAAA, y luego A en la segunda pasada. Cuando esto falla, la captura original sacrificará A adicional y la segunda captura la consumirá.

Esto iría en durante mucho tiempo lo que resulta en los siguientes intentos de partido, donde cada grupo separado por comas indica un tiempo diferente que el grupo se corresponde, y el número de caracteres que instancia encontrados:

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

Pude haber contado mal, pero estoy bastante seguro de que agrega hasta 16 pasos antes de que se determine que la expresión regular no puede coincidir. A medida que continúe agregando caracteres adicionales a la cadena, la cantidad de pasos para resolver esto aumenta exponencialmente.

Al eliminar + y cambiar esto a \(([^\s()<>])*\), se evitaría este escenario de retroceso.

Agregar la alternancia de nuevo para comprobar el paréntesis anidado no causa ningún problema.

Tenga en cuenta que es posible que desee agregar algún tipo de anclaje al final de la cadena, ya que de momento "http://google.com/?q=(AAAAAAAAAAAAAAAAAAAAAAAAAAAAA" coincidirá con hasta justo antes de la (, por lo re.test(...) volvería true PORQUE http://google.com/?q= partidos.