¿Por qué el motor de expresiones regulares de Java lanza la excepción StringIndexOutOfBoundsException en una repetición+?

regex fibonacci

Question

He escrito un patrón de expresiones regulares para encontrar los números de Fibonacci (no importa por qué, acabo de hacerlo). Funciona maravillosamente como se esperaba ( ver en ideone.com ):

 String FIBONACCI =
"(?x) .{0,2} | (?: (?=(//2?)) (?=(//2//3|^.)) (?=(//1)) //2)++ . ";
for (int n = 0; n < 1000; n++) {
String s = new String(new char[n]);
if (s.matches(FIBONACCI)) {
System.out.print(n + " ");
}
} // 0 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 

Una repetición possessive (es decir, ++ en el "bucle" principal) es crucial, ya que no quiere dar marcha atrás con este algoritmo de coincidencia. Sin embargo, al hacer que la repetición se pueda retroceder (es decir, solo + en el "bucle principal") no se producen desajustes, ¡¡sino una excepción de tiempo de ejecución! ( como se ve en ideone.com ):

Exception in thread "main" java.lang.StringIndexOutOfBoundsException:
String index out of range: -1
at java.lang.String.charAt(String.java:686)
at java.lang.Character.codePointAt(Character.java:2335)
at java.util.regex.Pattern$CharProperty.match(Pattern.java:3344)
at java.util.regex.Pattern$GroupCurly.match0(Pattern.java:3994)
at java.util.regex.Pattern$GroupCurly.match0(Pattern.java:3966)
at java.util.regex.Pattern$GroupCurly.match(Pattern.java:3916)
at java.util.regex.Pattern$Branch.match(Pattern.java:4114)
at java.util.regex.Matcher.match(Matcher.java:1127)
at java.util.regex.Matcher.matches(Matcher.java:502)
at java.util.regex.Pattern.matches(Pattern.java:930)
at java.lang.String.matches(String.java:2090)

¿Alguien puede explicar lo que pasó aquí? ¿Es este un error en el motor de expresiones regulares de Java?

Answer 1

ID de error 6984178

Hay muchos errores relacionados con el lanzamiento del motor StringIndexOutOfBoundsException ( ver: resultados de búsqueda . Este en particular se ha informado y aceptado internamente como ID de error 6984178 (puede tardar un tiempo en aparecer en la base de datos externa).

Aquí hay un patrón mucho más simple que reproduce el error ( vea también en ideone.com ):

System.out.println(
"abaab".matches("(?x) (?: (?=(a+)) //1 b )* x")
); // StringIndexOutOfBounds: -1

Tenga en cuenta que utilizando *? o *+ simplemente devuelve false como se esperaba.

Parece que el problema se desencadena por el intento de retroceder una repetición codiciosa cuando hay una referencia a un grupo de captura dentro de un lookahead: el índice de fuera de límites es la diferencia de longitud entre la primera y la segunda a+ (por ejemplo, "aabaaaaab" obtiene -3 ).

Es probable que uno tenga que depurar el código fuente java.util.regex.Pattern para identificar la naturaleza exacta del error.

Explorando el patrón de Fibonacci

En el motor de Java, con retroceso codicioso +

Aquí hay un fragmento más detallado para mostrar cómo funciona el motor en este patrón:

String FIBONACCI =
"(?x) .{0,2} | (?: (?=(//2|^)) (?=(//2//3|^.)) (?=(//1)) //2)+ . ";
for (int n = 0; n < 1000; n++) {
String s = new String(new char[n]);
try {
if (s.matches(FIBONACCI)) {
System.out.printf("%n%s", n);
}
} catch (StringIndexOutOfBoundsException e) {
String index = e.getMessage().replace("String index out of range: ", "");
System.out.printf(" <%s:%s>", n, index);
}
}

La salida (ligeramente editada) es ( como se ve en ideone.com ):

0 1 2 3 <5:-1>
6 <7:-1> ... <12:-1> <13:-3>
14 <15:-3> ... <33:-3> <34:-8>
35 <36:-8> ... <88:-8> <89:-21>
90 <91:-21> ... <232:-21> <233:-55>
234 <235:-55> ... <609:-55> <610:-144>
611 <612:-144> ...

Entonces, de alguna manera, el motor intenta acceder a los índices de cadena en -1, -3, -8, -21, -55, -144, etc. Tenga en cuenta que estos son todos los demás números de Fibonacci, pero negativos. Tenga en cuenta también que más allá de los primeros números, el resto de las coincidencias (6, 14, 35, ...) NO son números de Fibonacci.

En el motor .NET, con codicioso retroceso +

Si bien el patrón se escribió originalmente teniendo en cuenta la necesidad de contar con un cuantificador posesivo, de hecho, una repetición de retroceso seguirá siendo la respuesta correcta (suponiendo que el motor no tenga errores como el de Java). Aquí hay una implementación de C # en el motor .NET ( vea también en ideone.com ):

Regex r = new Regex(
@"(?x) ^.{0,1}$ | ^(?: (?=(/2?)) (?=(/2/3|^.)) (?=(/1)) /2)+ . $ "
);
for (int n = 0; n < 1000; n++) {
if (r.IsMatch("".PadLeft(n))) {
Console.Write("{0} ", n);
}
}
// 0 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 

Como puede ver, la salida es correcta, incluso con un retroceso + "bucle". De hecho, precisamente porque es un bucle de seguimiento, el caso especial se puede limitar a solo .{0,1} lugar de a .{0,2} .

¿En el motor de Java, con retroceso reticente +?

Esto funciona en Java como se esperaba. Además, como es reacio, también podemos limitar el caso especial a solo .{0,1} ( consulte también en ideone.com ):

String FIBONACCI =
"(?x) .{0,1} | (?: (?=(//2|^)) (?=(//2//3|^.)) (?=(//1)) //2)+? . ";

En el algoritmo

La formula

El patrón explota la segunda identidad de los números de Fibonacci :

Esto puede comprobarse por inducción.

El patrón

Usemos esta versión del patrón (que funciona en Java, y cuando está anclado, también funciona en C #):

 summation
free-space! "loop"
↓ ↓
(?x) .{0,1} | (?: (?=(/2|^)) (?=(/2/3|^.)) (?=(/1)) /2)+? .
/____/ /___________________________________/ ↑ ↑
base case inductive case +Fi +1
for n = 0,1
(assertions don''t "count" toward sum)!
$1 := $2 (or initialized with 0)
$2 := $2+$3 (or initialized with 1)
$3 := $1 (a temporary variable for the "swap")

La generación de secuencias de Fibonacci es sencilla, basada en la transición de [$1, $2] := [$2, $2+$1] . Dado que las aserciones se realizan de forma secuencial, se introduce una variable temporal (al igual que la versión "pseudocódigo" de asignación única).