Почему движок Java regex создает исключение StringIndexOutOfBoundsException для + повторения?

Я написал шаблон регулярных выражений, чтобы найти числа Фибоначчи (не важно, почему, я только что сделал). Он прекрасно работает, как и ожидалось ( см. На 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

Притяжное повторение (т.е. ++ на основной "петле") имеет решающее значение, потому что вы не хотите возвращаться с этим алгоритмом сопоставления. Тем не менее, делая повторение обратно (то есть просто + на главном "цикле") приводит не к несоответствиям, а к исключению времени выполнения!!! ( как видно на 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)

Может кто-нибудь объяснить, что здесь произошло? Это ошибка в движке Java regex?

Источник

1 ответ

Ошибка ID 6984178

Есть много ошибок, связанных с броском двигателя StringIndexOutOfBoundsException ( см. результаты поиска. Об этом, в частности, было сообщено и внутренне принято как идентификатор ошибки 6984178 (может потребоваться некоторое время, чтобы это отобразилось во внешней базе данных).

Вот гораздо более простой шаблон, который воспроизводит ошибку ( см. Также на ideone.com):

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

Обратите внимание, что с помощью *? или же *+ просто возвращается false как и ожидалось.

Похоже, что проблема вызвана попыткой отследить жадное повторение, когда есть ссылка на группу захвата внутри предвидения: индекс вне границ - это разница в длине между первым и вторым a+ (например "aabaaaaab" получает -3).

Скорее всего, придется отлаживать java.util.regex.Pattern исходный код, чтобы точно определить природу ошибки.

Изучение паттерна Фибоначчи

На движке Java, с жадным возвратом +

Вот более подробный фрагмент, показывающий, как сходит с ума двигатель по этому шаблону:

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);
    }
}

Вывод (слегка отредактированный) ( как видно на 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> ...

Так что каким-то образом движок пытается получить доступ к строковым индексам в -1, -3, -8, -21, -55, -144 и т. Д. Обратите внимание, что это все остальные числа Фибоначчи, но отрицательные. Также обратите внимание, что после первых нескольких чисел остальные совпадения (6, 14, 35, ...) НЕ являются числами Фибоначчи.

На движке.NET, с жадным возвратом +

Хотя шаблон изначально был написан с учетом необходимости обладания квантификатором, на самом деле повторение в обратном направлении все равно даст правильный ответ (при условии, что движок не глючит, как в Java). Вот реализация C# на движке.NET ( см. Также на 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

Как видите, вывод правильный, даже с возвратом + "Петля". На самом деле, именно потому, что это цикл возврата, особый случай может быть ограничен только .{0,1} вместо .{0,2},

На движке Java, с неохотным возвратом +?

Это работает в Java, как и ожидалось. Кроме того, поскольку он неохотно, мы также можем ограничить особый случай просто .{0,1} ( см. также на ideone.com):

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

По алгоритму

Формула

Шаблон использует вторую идентичность чисел Фибоначчи:

альтернативный текст

Это можно доказать по индукции.

Шаблон

Давайте использовать эту версию паттерна (которая работает в Java, а при привязке также работает в 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")

Генерация последовательности Фибоначчи проста, основанная на [$1, $2] := [$2, $2+$1] переход. Поскольку утверждения выполняются последовательно, вводится временная переменная (так же, как версия с псевдокодом для одного назначения).

Источник
Другие вопросы по тегам