Retroceso catastrófico no debería estar sucediendo en esta expresión regular

¿Alguien puede explicar por qué el motor de expresiones regulares de Java entra en modo de retroceso catastrófico en esta expresión regular? Cada alternancia es mutuamente excluyente con cualquier otra alternancia, por lo que puedo decir.

^(?:[^'\"\\s~:/@#\\|\\^\\&\\[\\]\\(\\)\\\\\\{\\}][^\"\\s~:/@#\\|\\^\\&\\[\\]\\(\\)\\\\\\{\\}]*| \"(?:[^\"]+|\"\")+\"| '(?:[^']+|'')+') 

Texto: 'pão de açúcar itaucard mastercard platinum SUSTENTABILIDADE])

Agregar una coincidencia posesiva a algunas de las alternancias soluciona el problema, pero no tengo idea de por qué: la biblioteca de expresiones regulares de Java debe ser extremadamente defectuosa para rastrear twigs mutuamente excluyentes.

  ^(?:[^'\"\\s~:/@#\\|\\^\\&\\[\\]\\(\\)\\\\\\{\\}][^\"\\s~:/@#\\|\\^\\&\\[\\]\\(\\)\\\\\\{\\}]*| \"(?:[^\"]++|\"\")++\"| '(?:[^']++|'')++') 

EDITAR: Se agregó una versión de Java al final, a pesar de ser intrínsecamente torpe, ilegible e imposible de mantener.


¡No más patrones feos!

Lo primero que debe hacer es escribir su expresión regular de una manera que pueda soportar cualquier posible esperanza de ser legible, y consecuentemente mantenible, por los seres humanos. Lo segundo que debe hacer es perfilar esto para ver qué está haciendo realmente.

Eso significa que, como mínimo, debe comstackrlo en el modo Pattern.COMMENTS (o en el prefijo "(?x)" ) y luego agregar espacios en blanco para dar un poco de margen visual. Por más que pueda entenderlo, el patrón con el que realmente intentan coincidir es este:

 ^ (?: [^'"\s~:/@\#|^&\[\]()\\{}] # alt 1: unquoted [^"\s~:/@\#|^&\[\]()\\{}] * | " (?: [^"]+ | "" )+ " # alt 2: double quoted | ' (?: [^']+ | '' )+ ' # alt 3: single quoted ) 

Como puede ver, introduje el espacio en blanco vertical y horizontal en los lugares en los que podía, a fin de guiar el ojo y la mente como una especie de agrupamiento cognitivo. También eliminé todas tus barras invertidas externas. Esos son todos o errores claros u ofuscadores que no hacen más que confundir al lector.

Observe cómo al aplicar espacios en blanco verticales, hice que las partes iguales de una línea a la siguiente aparezcan en la misma columna para que pueda ver inmediatamente qué partes son iguales y qué partes son diferentes.

Después de haber hecho eso, finalmente puedo ver que lo que está aquí es una coincidencia anclada al principio, que es seguida por una elección de tres alternativas. Por lo tanto, he etiquetado esas tres alternativas con un comentario descriptivo para que no tenga que adivinar.

También noté que tu primera alternativa tiene dos clases de caracteres sutilmente diferentes (negadas) con corchetes cuadrados. El segundo carece de la exclusión de cotización única vista en el primero. Es esto intencional? Incluso si lo es, encuentro demasiada duplicación para mis gustos; algunos o todos deberían estar en una variable para que no corra el riesgo de actualizar los problemas de coherencia.


Perfilado

La segunda y más importante de las dos cosas que tienes que hacer es perfilar esto. Necesita ver exactamente en qué progtwig de expresiones regulares se está comstackndo ese patrón, y debe rastrear su ejecución a medida que se ejecuta sobre sus datos.

La clase de Pattern de Java no es actualmente capaz de hacer esto, aunque ya he hablado extensamente al respecto con el actual custodio de código en OraSun, y está ansioso por agregar esta capacidad a Java y piensa que sabe exactamente cómo hacerlo. Incluso me envió un prototipo que hace la primera parte: la comstackción. Así que espero que esté disponible uno de estos días.

Mientras tanto, volvamos a una herramienta en la que las expresiones regulares son una parte integral del lenguaje de progtwigción propiamente dicho, no algo atornillado como una incómoda idea de último momento. Aunque varios idiomas cumplen ese criterio, en ninguno el arte de la coincidencia de patrones alcanzó el nivel de sofisticación visto en Perl.

Aquí, entonces, hay un progtwig equivalente.

 #!/usr/bin/env perl use v5.10; # first release with possessive matches use utf8; # we have utf8 literals use strict; # require variable declarations, etc use warnings; # check for boneheadedness my $match = qr{ ^ (?: [^'"\s~:/@\#|^&\[\]()\\{}] [^"\s~:/@\#|^&\[\]()\\{}] * | " (?: [^"]+ | "" )+ " | ' (?: [^']+ | '' )+ ' ) }x; my $text = "'pão de açúcar itaucard mastercard platinum SUSTENTABILIDAD])"; my $count = 0; while ($text =~ /$match/g) { print "Got it: $&\n"; $count++; } if ($count == 0) { print "Match failed.\n"; } 

Si ejecutamos ese progtwig, obtenemos la respuesta esperada de que el partido falló. La pregunta es por qué y cómo.

Ahora queremos ver dos cosas: queremos ver qué progtwig regex comstack ese patrón, y luego queremos rastrear la ejecución de ese progtwig regex.

Ambos están controlados con el

 use re "debug"; 

pragma, que también se puede especificar en la línea de comando a través de -Mre=debug . Esto es lo que haremos aquí para evitar piratear el código fuente.

Comstackción Regex

El pragma de depuración mostrará normalmente tanto la comstackción del patrón como su ejecución. Para separarlos, podemos usar el modificador “comstackr solo” de Perl, -c , que no intenta ejecutar el progtwig que ha comstackdo. De esa forma, todo lo que vemos es el patrón comstackdo. Hacer esto produce las siguientes 36 líneas de salida:

 $ perl -c -Mre=debug /tmp/bt Compiling REx "%n ^ (?: [^'%"\s~:/@\#|^&\[\]()\\{}]%n [^%"\s~:/"... Final program: 1: BOL (2) 2: BRANCH (26) 3: ANYOF[^\x09\x0a\x0c\x0d "#&-)/:@[-\^{-~][^{unicode}+utf8::IsSpacePerl] (14) 14: STAR (79) 15: ANYOF[^\x09\x0a\x0c\x0d "#&()/:@[-\^{-~][^{unicode}+utf8::IsSpacePerl] (0) 26: BRANCH (FAIL) 27: TRIE-EXACT["'] (79) <"> (29) 29: CURLYX[0] {1,32767} (49) 31: BRANCH (44) 32: PLUS (48) 33: ANYOF[\x00-!#-\xff][{unicode_all}] (0) 44: BRANCH (FAIL) 45: EXACT <""> (48) 47: TAIL (48) 48: WHILEM[1/2] (0) 49: NOTHING (50) 50: EXACT <"> (79) <'> (55) 55: CURLYX[0] {1,32767} (75) 57: BRANCH (70) 58: PLUS (74) 59: ANYOF[\x00-&(-\xff][{unicode_all}] (0) 70: BRANCH (FAIL) 71: EXACT <''> (74) 73: TAIL (74) 74: WHILEM[2/2] (0) 75: NOTHING (76) 76: EXACT <'> (79) 78: TAIL (79) 79: END (0) anchored(BOL) minlen 1 /tmp/bt syntax OK Freeing REx: "%n ^ (?: [^'%"\s~:/@\#|^&\[\]()\\{}]%n [^%"\s~:/"... 

Como puede ver, el progtwig de expresiones regulares comstackdo es algo así como un “lenguaje de ensamblaje regex”. (También se parece mucho a lo que escuchó el prototipo de Java que se me mostró, así que imagino que algún día verás este tipo de cosas también en Java.) Todos los detalles no son esenciales para esto, pero señalaré que la instrucción en el nodo 2 es una SUCURSAL, que si falla pasa a ejecutar la twig 26, otra SUCURSAL. Esa segunda SUCURSAL, que es la única otra parte del progtwig de expresiones regulares, consiste en un único nodo TRIE-EXACT, porque sabe que las alternativas tienen cadenas literales de partida diferentes. Lo que sucede entre esas dos twigs se discutirá en el presente.

Ejecución de Regex

Ahora es el momento de ver qué pasa cuando se ejecuta. La cadena de texto que está utilizando causa una cantidad bastante considerable de retroceso, lo que significa que tendrá muchos resultados que recorrer antes de que finalmente falle. ¿Cuánto producción? Bueno, esto:

 $ perl -Mre=debug /tmp/bt 2>&1 | wc -l 9987 

Supongo que a los 10 000 pasos es a lo que se refería con “modo de retroceso catastrófico”. Veamos que no podemos reducir eso a algo más comprensible. Su cadena de entrada tiene 61 caracteres de longitud. Para ver mejor lo que está sucediendo, podemos reducirlo a solo 'pão , que tiene solo 4 caracteres. (Bueno, en NFC, es decir, son cinco puntos de código en NFD, pero eso no cambia nada aquí). Eso resulta en 167 líneas de salida:

 $ perl -Mre=debug /tmp/bt 2>&1 | wc -l 167 

De hecho, aquí están las líneas de perfiles de ejecución regex (comstackción plus) que obtiene cuando su cadena tiene muchos caracteres de este largo:

 chars lines string 1 63 ‹'› 2 78 ‹'p› 3 109 ‹'pã› 4 167 ‹'pão› 5 290 ‹'pão › 6 389 ‹'pão d› 7 487 ‹'pão de› 8 546 ‹'pão de › 9 615 ‹'pão de a› 10 722 ‹'pão de aç› .... 61 9987 ‹'pão de açúcar itaucard mastercard platinum SUSTENTABILIDAD])› 

Miremos la salida de depuración cuando la cadena es el 'pão los cuatro caracteres. He omitido la parte de comstackción esta vez para mostrar solo la parte de ejecución:

 $ perl -Mre=debug /tmp/bt Matching REx "%n ^ (?: [^'%"\s~:/@\#|^&\[\]()\\{}]%n [^%"\s~:/"... against "'p%x{e3}o" UTF-8 string... 0 <> <'p%x{e3}o> | 1:BOL(2) 0 <> <'p%x{e3}o> | 2:BRANCH(26) 0 <> <'p%x{e3}o> | 3: ANYOF[^\x09\x0a\x0c\x0d "#&-)/:@[-\^{-~][^{unicode}+utf8::IsSpacePerl](14) failed... 0 <> <'p%x{e3}o> | 26:BRANCH(78) 0 <> <'p%x{e3}o> | 27: TRIE-EXACT["'](79) 0 <> <'p%x{e3}o> | State: 1 Accepted: N Charid: 2 CP: 27 After State: 3 1 <'>  | State: 3 Accepted: Y Charid: 0 CP: 0 After State: 0 got 1 possible matches TRIE matched word #2, continuing only one match left, short-circuiting: #2 <'> 1 <'>  | 55: CURLYX[0] {1,32767}(75) 1 <'>  | 74: WHILEM[2/2](0) whilem: matched 0 out of 1..32767 1 <'>  | 57: BRANCH(70) 1 <'>  | 58: PLUS(74) ANYOF[\x00-&(-\xff][{unicode_all}] can match 3 times out of 2147483647... 5 <'p%x{e3}o> <> | 74: WHILEM[2/2](0) whilem: matched 1 out of 1..32767 5 <'p%x{e3}o> <> | 57: BRANCH(70) 5 <'p%x{e3}o> <> | 58: PLUS(74) ANYOF[\x00-&(-\xff][{unicode_all}] can match 0 times out of 2147483647... failed... 5 <'p%x{e3}o> <> | 70: BRANCH(73) 5 <'p%x{e3}o> <> | 71: EXACT <''>(74) failed... BRANCH failed... whilem: failed, trying continuation... 5 <'p%x{e3}o> <> | 75: NOTHING(76) 5 <'p%x{e3}o> <> | 76: EXACT <'>(79) failed... failed... 4 <'p%x{e3}>  | 74: WHILEM[2/2](0) whilem: matched 1 out of 1..32767 4 <'p%x{e3}>  | 57: BRANCH(70) 4 <'p%x{e3}>  | 58: PLUS(74) ANYOF[\x00-&(-\xff][{unicode_all}] can match 1 times out of 2147483647... 5 <'p%x{e3}o> <> | 74: WHILEM[2/2](0) whilem: matched 2 out of 1..32767 5 <'p%x{e3}o> <> | 57: BRANCH(70) 5 <'p%x{e3}o> <> | 58: PLUS(74) ANYOF[\x00-&(-\xff][{unicode_all}] can match 0 times out of 2147483647... failed... 5 <'p%x{e3}o> <> | 70: BRANCH(73) 5 <'p%x{e3}o> <> | 71: EXACT <''>(74) failed... BRANCH failed... whilem: failed, trying continuation... 5 <'p%x{e3}o> <> | 75: NOTHING(76) 5 <'p%x{e3}o> <> | 76: EXACT <'>(79) failed... failed... failed... 4 <'p%x{e3}>  | 70: BRANCH(73) 4 <'p%x{e3}>  | 71: EXACT <''>(74) failed... BRANCH failed... whilem: failed, trying continuation... 4 <'p%x{e3}>  | 75: NOTHING(76) 4 <'p%x{e3}>  | 76: EXACT <'>(79) failed... failed... 2 <'p> <%x{e3}o> | 74: WHILEM[2/2](0) whilem: matched 1 out of 1..32767 2 <'p> <%x{e3}o> | 57: BRANCH(70) 2 <'p> <%x{e3}o> | 58: PLUS(74) ANYOF[\x00-&(-\xff][{unicode_all}] can match 2 times out of 2147483647... 5 <'p%x{e3}o> <> | 74: WHILEM[2/2](0) whilem: matched 2 out of 1..32767 5 <'p%x{e3}o> <> | 57: BRANCH(70) 5 <'p%x{e3}o> <> | 58: PLUS(74) ANYOF[\x00-&(-\xff][{unicode_all}] can match 0 times out of 2147483647... failed... 5 <'p%x{e3}o> <> | 70: BRANCH(73) 5 <'p%x{e3}o> <> | 71: EXACT <''>(74) failed... BRANCH failed... whilem: failed, trying continuation... 5 <'p%x{e3}o> <> | 75: NOTHING(76) 5 <'p%x{e3}o> <> | 76: EXACT <'>(79) failed... failed... 4 <'p%x{e3}>  | 74: WHILEM[2/2](0) whilem: matched 2 out of 1..32767 4 <'p%x{e3}>  | 57: BRANCH(70) 4 <'p%x{e3}>  | 58: PLUS(74) ANYOF[\x00-&(-\xff][{unicode_all}] can match 1 times out of 2147483647... 5 <'p%x{e3}o> <> | 74: WHILEM[2/2](0) whilem: matched 3 out of 1..32767 5 <'p%x{e3}o> <> | 57: BRANCH(70) 5 <'p%x{e3}o> <> | 58: PLUS(74) ANYOF[\x00-&(-\xff][{unicode_all}] can match 0 times out of 2147483647. .. failed... 5 <'p%x{e3}o> <> | 70: BRANCH(73) 5 <'p%x{e3}o> <> | 71: EXACT <''>(74) failed... BRANCH failed... whilem: failed, trying continuation... 5 <'p%x{e3}o> <> | 75: NOTHING(76) 5 <'p%x{e3}o> <> | 76: EXACT <'>(79) failed... failed... failed... 4 <'p%x{e3}>  | 70: BRANCH(73) 4 <'p%x{e3}>  | 71: EXACT <''>(74) failed... BRANCH failed... whilem: failed, trying continuation... 4 <'p%x{e3}>  | 75: NOTHING(76) 4 <'p%x{e3}>  | 76: EXACT <'>(79) failed... failed... failed... 2 <'p> <%x{e3}o> | 70: BRANCH(73) 2 <'p> <%x{e3}o> | 71: EXACT <''>(74) failed... BRANCH failed... whilem: failed, trying continuation... 2 <'p> <%x{e3}o> | 75: NOTHING(76) 2 <'p> <%x{e3}o> | 76: EXACT <'>(79) failed... failed... failed... 1 <'>  | 70: BRANCH(73) 1 <'>  | 71: EXACT <''>(74) failed... BRANCH failed... failed... failed... BRANCH failed... Match failed Match failed. Freeing REx: "%n ^ (?: [^'%"\s~:/@\#|^&\[\]()\\{}]%n [^%"\s~:/"... 

Lo que ocurre allí es que el trie se ramifica rápidamente al nodo 55, que es la última de las tres alternativas una vez que ha coincidido con la comilla simple, porque la cadena de destino comienza con una comilla simple. Ese es este:

  | ' (?: [^']+ | '' )+ ' # alt 3: single quoted 

El nodo 55 es esta twig trie:

  <'> (55) 55: CURLYX[0] {1,32767} (75) 57: BRANCH (70) 58: PLUS (74) 59: ANYOF[\x00-&(-\xff][{unicode_all}] (0) 70: BRANCH (FAIL) 71: EXACT <''> (74) 

Y aquí está el seguimiento de la ejecución que muestra dónde está ocurriendo su desaceleración catastrófica:

  1 <'>  | 74: WHILEM[2/2](0) whilem: matched 0 out of 1..32767 1 <'>  | 57: BRANCH(70) 1 <'>  | 58: PLUS(74) ANYOF[\x00-&(-\xff][{unicode_all}] can match 3 times out of 2147483647... 5 <'p%x{e3}o> <> | 74: WHILEM[2/2](0) whilem: matched 1 out of 1..32767 5 <'p%x{e3}o> <> | 57: BRANCH(70) 5 <'p%x{e3}o> <> | 58: PLUS(74) ANYOF[\x00-&(-\xff][{unicode_all}] can match 0 times out of 2147483647... failed... 5 <'p%x{e3}o> <> | 70: BRANCH(73) 5 <'p%x{e3}o> <> | 71: EXACT <''>(74) failed... BRANCH failed... whilem: failed, trying continuation... 5 <'p%x{e3}o> <> | 75: NOTHING(76) 5 <'p%x{e3}o> <> | 76: EXACT <'>(79) failed... failed... 4 <'p%x{e3}>  | 74: WHILEM[2/2](0) whilem: matched 1 out of 1..32767 4 <'p%x{e3}>  | 57: BRANCH(70) 4 <'p%x{e3}>  | 58: PLUS(74) ANYOF[\x00-&(-\xff][{unicode_all}] can match 1 times out of 2147483647... 5 <'p%x{e3}o> <> | 74: WHILEM[2/2](0) whilem: matched 2 out of 1..32767 

El nodo 58 engulló los 3 caracteres restantes en la cadena, pão . Eso provocó que la coincidencia exacta de terminación de una cita única fallara. Por lo tanto, intenta su alternativa, que es un par de comillas simples, y que también falla.

Es en este punto que tengo que cuestionar tu patrón. No debería

 ' (?: [^']+ | '' )+ ' 

realmente solo es esto?

 ' [^']* ' 

Entonces, lo que está sucediendo es que hay muchas maneras de retroceder buscando algo que lógicamente nunca puede ocurrir. Usted tiene un cuantificador nested, y eso está causando todo tipo de trabajo ocupado sin esperanza y sin sentido.

Si intercambiamos simplificamos el patrón en esto:

 ^ (?: [^'"\s~:/@\#|^&\[\]()\\{}] + | " [^"]* " | ' [^']* ' ) 

Ahora da el mismo número de líneas de salida de rastreo sin importar el tamaño de la cadena de entrada: solo 40, y eso incluye la comstackción. Sea testigo tanto de la comstackción como de la ejecución en la cadena completa:

 Compiling REx "%n ^ (?: [^'%"\s~:/@\#|^&\[\]()\\{}]%n [^%"\s~:/"... Final program: 1: BOL (2) 2: BRANCH (26) 3: ANYOF[^\x09\x0a\x0c\x0d "#&-)/:@[-\^{-~][^{unicode}+utf8::IsSpacePerl] (14) 14: STAR (61) 15: ANYOF[^\x09\x0a\x0c\x0d "#&()/:@[-\^{-~][^{unicode}+utf8::IsSpacePerl] (0) 26: BRANCH (FAIL) 27: TRIE-EXACT["'] (61) <"> (29) 29: STAR (41) 30: ANYOF[\x00-!#-\xff][{unicode_all}] (0) 41: EXACT <"> (61) <'> (46) 46: STAR (58) 47: ANYOF[\x00-&(-\xff][{unicode_all}] (0) 58: EXACT <'> (61) 60: TAIL (61) 61: END (0) anchored(BOL) minlen 1 Matching REx "%n ^ (?: [^'%"\s~:/@\#|^&\[\]()\\{}]%n [^%"\s~:/"... against "'p%x{e3}o de a%x{e7}%x{fa}car itaucard mast ercard platinum S"... UTF-8 string... 0 <> <'p%x{e3}o > | 1:BOL(2) 0 <> <'p%x{e3}o > | 2:BRANCH(26) 0 <> <'p%x{e3}o > | 3: ANYOF[^\x09\x0a\x0c\x0d "#&-)/:@[-\^{-~][^{unicode}+utf8::IsSpacePerl](14) failed... 0 <> <'p%x{e3}o > | 26:BRANCH(60) 0 <> <'p%x{e3}o > | 27: TRIE-EXACT["'](61) 0 <> <'p%x{e3}o > | State: 1 Accepted: N Charid: 2 CP: 27 After State: 3 1 <'>  | State: 3 Accepted: Y Charid: 0 CP: 0 After State: 0 got 1 possible matches TRIE matched word #2, continuing only one match left, short-circuiting: #2 <'> 1 <'>  | 46: STAR(58) ANYOF[\x00-&(-\xff][{unicode_all}] can match 60 times out of 2147483647... failed... BRANCH failed... Match failed Match failed. Freeing REx: "%n ^ (?: [^'%"\s~:/@\#|^&\[\]()\\{}]%n [^%"\s~:/"... 

Sé que pensabas que la coincidencia posesiva podría ser la respuesta aquí, pero creo que el verdadero problema es la lógica defectuosa en el patrón original. ¿Ves cuán más sensatamente funciona esto ahora?

Si lo ejecutamos con sus posesivos en el viejo patrón, aunque no creo que tenga sentido, todavía tenemos un tiempo de ejecución constante, pero requiere más pasos. Con este patrón

  ^ (?: [^'"\s~:/@\#|^&\[\]()\\{}] + # alt 1: unquoted | " (?: [^"]++ | "" )++ " # alt 2: double quoted | ' (?: [^']++ | '' )++ ' # alt 3: single quoted ) 

El perfil de comstackción más ejecución es el siguiente:

 Compiling REx "%n ^ (?: [^'%"\s~:/@\#|^&\[\]()\\{}]%n [^%"\s~:/"... Final program: 1: BOL (2) 2: BRANCH (26) 3: ANYOF[^\x09\x0a\x0c\x0d "#&-)/:@[-\^{-~][^{unicode}+utf8::IsSpacePerl] (14) 14: STAR (95) 15: ANYOF[^\x09\x0a\x0c\x0d "#&()/:@[-\^{-~][^{unicode}+utf8::IsSpacePerl] (0) 26: BRANCH (FAIL) 27: TRIE-EXACT["'] (95) <"> (29) 29: SUSPEND (58) 31: CURLYX[0] {1,32767} (55) 33: BRANCH (50) 34: SUSPEND (54) 36: PLUS (48) 37: ANYOF[\x00-!#-\xff][{unicode_all}] (0) 48: SUCCEED (0) 49: TAIL (53) 50: BRANCH (FAIL) 51: EXACT <""> (54) 53: TAIL (54) 54: WHILEM[1/2] (0) 55: NOTHING (56) 56: SUCCEED (0) 57: TAIL (58) 58: EXACT <"> (95) <'> (63) 63: SUSPEND (92) 65: CURLYX[0] {1,32767} (89) 67: BRANCH (84) 68: SUSPEND (88) 70: PLUS (82) 71: ANYOF[\x00-&(-\xff][{unicode_all}] (0) 82: SUCCEED (0) 83: TAIL (87) 84: BRANCH (FAIL) 85: EXACT <''> (88) 87: TAIL (88) 88: WHILEM[2/2] (0) 89: NOTHING (90) 90: SUCCEED (0) 91: TAIL (92) 92: EXACT <'> (95) 94: TAIL (95) 95: END (0) anchored(BOL) minlen 1 Matching REx "%n ^ (?: [^'%"\s~:/@\#|^&\[\]()\\{}]%n [^%"\s~:/"... against "'p%x{e3}o de a%x{e7}%x{fa}car itaucard mastercard platinum S"... UTF-8 string... 0 <> <'p%x{e3}o > | 1:BOL(2) 0 <> <'p%x{e3}o > | 2:BRANCH(26) 0 <> <'p%x{e3}o > | 3: ANYOF[^\x09\x0a\x0c\x0d "#&-)/:@[-\^{-~][^{unicode}+utf8::IsSpacePerl](14) failed... 0 <> <'p%x{e3}o > | 26:BRANCH(94) 0 <> <'p%x{e3}o > | 27: TRIE-EXACT["'](95) 0 <> <'p%x{e3}o > | State: 1 Accepted: N Charid: 2 CP: 27 After State: 3 1 <'> | State: 3 Accepted: Y Charid: 0 CP: 0 After State: 0 got 1 possible matches TRIE matched word #2, continuing only one match left, short-circuiting: #2 <'> 1 <'> | 63: SUSPEND(92) 1 <'> | 65: CURLYX[0] {1,32767}(89) 1 <'> | 88: WHILEM[2/2](0) whilem: matched 0 out of 1..32767 1 <'> | 67: BRANCH(84) 1 <'> | 68: SUSPEND(88) 1 <'> | 70: PLUS(82) ANYOF[\x00-&(-\xff][{unicode_all}] can match 60 times out of 2147483647... 64  <| 82: SUCCEED(0) subpattern success... 64  <| 88: WHILEM[2/2](0) whilem: matched 1 out of 1..32767 64  <| 67: BRANCH(84) 64  <| 68: SUSPEND(88) 64  <| 70: PLUS(82) ANYOF[\x00-&(-\xff][{unicode_all}] can match 0 times out of 2147483647... failed... failed... 64  <| 84: BRANCH(87) 64  <| 85: EXACT <''>(88) failed... BRANCH failed... whilem: failed, trying continuation... 64  <| 89: NOTHING(90) 64  <| 90: SUCCEED(0) subpattern success... 64  <| 92: EXACT <'>(95) failed... BRANCH failed... Match failed Match failed. Freeing REx: "%n ^ (?: [^'%"\s~:/@\#|^&\[\]()\\{}]%n [^%"\s~:/"... 

Todavía me gusta mi solución mejor. Es más corto.


EDITAR

Parece que la versión de Java realmente está tomando 100 veces más pasos que la versión de Perl de un patrón idéntico, y no tengo idea de por qué, aparte de eso, el comstackdor de expresiones regulares de Perl es 100 veces más inteligente en optimizaciones que el comstackdor de expresiones regulares Java, que no hace nada de lo que hablar, y debería.

Aquí está el progtwig equivalente de Java. He eliminado el anclaje principal para poder hacer un bucle correctamente.

 $ cat java.crap import java.util.regex.*; public class crap { public static void main(String[ ] argv) { String input = "'pão de açúcar itaucard mastercard platinum SUSTENTABILIDAD])"; String regex = "\n" + "(?: [^'\"\\s~:/@\\#|^&\\[\\]()\\\\{}] # alt 1: unquoted \n" + " [^\"\\s~:/@\\#|^&\\[\\]()\\\\{}] * \n" + " | \" (?: [^\"]++ | \"\" )++ \" # alt 2: double quoted \n" + " | ' (?: [^']++ | '' )++ ' # alt 3: single quoted \n" + ") \n" ; System.out.printf("Matching ‹%s› =~ qr{%s}x\n\n", input, regex); Pattern regcomp = Pattern.compile(regex, Pattern.COMMENTS); Matcher regexec = regcomp.matcher(input); int count; for (count = 0; regexec.find(); count++) { System.out.printf("Found match: ‹%s›\n", regexec.group()); } if (count == 0) { System.out.printf("Match failed.\n"); } } } 

Cuando se ejecuta, eso produce esto:

 $ javac -encoding UTF-8 crap.java && java -Dfile.encoding=UTF-8 crap Matching ‹'pão de açúcar itaucard mastercard platinum SUSTENTABILIDAD])› =~ qr{ (?: [^'"\s~:/@\#|^&\[\]()\\{}] # alt 1: unquoted [^"\s~:/@\#|^&\[\]()\\{}] * | " (?: [^"]++ | "" )++ " # alt 2: double quoted | ' (?: [^']++ | '' )++ ' # alt 3: single quoted ) }x Found match: ‹pão› Found match: ‹de› Found match: ‹açúcar› Found match: ‹itaucard› Found match: ‹mastercard› Found match: ‹platinum› Found match: ‹SUSTENTABILIDAD› 

Como se puede ver claramente, la coincidencia de patrones en Java tiene mucho que decir al respecto, absolutamente nada de lo que pasaría con la policía de la boca abierta. Es simplemente un dolor real en el culo.

Tengo que admitir que esto también me sorprendió, pero obtengo el mismo resultado en RegexBuddy: deja de intentarlo después de un millón de pasos. Sé que las advertencias sobre retrocesos catastróficos tienden a centrarse en cuantificadores nesteds, pero en mi experiencia la alternancia es al menos tan peligrosa. De hecho, si cambio la última parte de su expresión regular de esto:

 '(?:[^']+|'')+' 

…a esto:

 '(?:[^']*(?:''[^']*)*)' 

… falla en solo once pasos. Este es un ejemplo de la técnica de “lazo desenrollado” de Friedl , que analiza así:

 opening normal * ( special normal * ) * closing ' [^'] '' [^'] ' 

Las estrellas anidadas son seguras siempre y cuando:

  1. special y normal nunca puede coincidir con lo mismo,
  2. special siempre coincide con al menos un personaje, y
  3. special es atómico (debe haber una sola manera para que coincida).

La expresión regular no podrá coincidir con un retroceso mínimo y tendrá éxito sin retroceder en absoluto. La versión de alternancia, por otro lado, está casi garantizada para retroceder, y cuando no es posible una coincidencia, se sale rápidamente de control a medida que aumenta la longitud de la cuerda objective. Si no retrocede excesivamente en algunos sabores, es porque tienen optimizaciones incorporadas específicamente para contrarrestar este problema, algo que muy pocos sabores hacen, hasta ahora.

¿Alguien puede explicar por qué el motor de expresiones regulares de Java entra en modo catastrófico en esta expresión regular?

Para la cadena:

 'pão de açúcar itaucard mastercard platinum SUSTENTABILIDADE]) 

Parece que esta parte de la expresión regular sería el problema:

 '(?:[^']+|'')+' 

Coincidencia de la primera ' luego no coinciden con el cierre ' y, por tanto, retroceder todas las combinaciones de los cuantificadores nesteds.

Si permite que la expresión regular retroceda, retrocederá (cuando falle). Use grupos atómicos y / o cuantificadores posesivos para evitar eso.


Por cierto, no necesitas la mayoría de los escapes en esa expresión regular. Lo único que (podría) necesitar para escapar en las clases de caracteres ( [] ) son los caracteres ^-] . Pero por lo general, puede ubicarlos de modo que tampoco necesiten escaparse. Por supuesto, el \ y cualquier cosa con la que estés coartando, la cadena todavía tiene que ser (doble) escapada.

 "^(?:[^]['\"\\s~:/@#|^&(){}\\\\][^][\"\s~:/@#|^&(){}\\\\]*|\"(?:[^\"]++|\"\")++\"|'(?:[^']++|'')++')"