Pattern.matches() дает StackOverflowError

Я использую java Pattern.matches для сопоставления блока данных с регулярным выражением. Блок данных может быть одной строкой или несколькими строками. Проблема в том, что, как только мои данные станут более 15 строк (обычно более 17-18 строк), я начинаю получать stackoverflowerror. Для данных менее 15 строк регулярное выражение отлично работает.

Regex имеет такой формат:
domainname → space → , → space → number → space → , → space → number → newline

String regex = "^(([a-zA-Z0-9][a-zA-Z0-9\\-]*\\.)+([a-zA-Z]{2,})\\s*,\\s*\\d+\\s*,\\s*\\d+(\\r?\\n)?)+$";

Блок данных, который я использую для проверки этого регулярного выражения, - это

abc.com, 123, 456
abc.com, 123, 456
abc.com, 123, 456
abc.com, 123, 456
abc.com, 123, 456
abc.com, 123, 456
abc.com, 123, 456
abc.com, 123, 456
abc.com, 123, 456
abc.com, 123, 456
abc.com, 123, 456
abc.com, 123, 456
abc.com, 123, 456
abc.com, 123, 456
abc.com, 123, 456
abc.com, 123, 456
abc.com, 123, 456
abc.com, 123, 456

Это код:

String regex = "^(([a-zA-Z0-9][a-zA-Z0-9\\-]*\\.)+([a-zA-Z]{2,})\\s*,\\s*\\d+\\s*,\\s*\\d+(\\r?\\n)?)+$";
boolean valid = Pattern.matches(regex, data); //fails here

Ответ 1

Я не могу сказать вам причину этой ошибки; само регулярное выражение прекрасно и не подвержено катастрофическому обратному отскоку или любой другой очевидной ошибке.

Возможно, вы можете уменьшить количество позиций возврата, которые сохраняет механизм регулярных выражений, используя притяжательные квантификаторы (++ вместо +, *+ вместо *, {2,}+ вместо {2,} и т.д.). Кроме того, вам не нужны группы захвата (спасибо Томасу), поэтому я изменил их на не захватывающие:

"(?:(?:[a-zA-Z0-9][a-zA-Z0-9-]*+\\.)++([a-zA-Z]{2,}+)\\s*+,\\s*+\\d++\\s*+,\\s*+\\d++(\r?+\n)?+)++"

Это не изменит поведение регулярного выражения (за исключением удаления ненужных якорей, поскольку вы используете Pattern.matches()), но, возможно, это помогает избежать StackOverflow. У меня нет Java SDK, поэтому я не могу его тестировать сам.

Ответ 2

Вы можете попробовать и использовать атомные группы ((?>expression)) для предотвращения обратного трассировки:

Здесь тест, который завершился неудачей с блоком из 1000 строк с использованием вашего регулярного выражения, но успешно выполняется (требуется некоторое время, поэтому я тестировал только ~~5000~~ 20000:)):

String regex = "(?>(?>[a-zA-Z0-9][a-zA-Z0-9\\-]*\\.)+(?>[a-zA-Z]{2,})\\s*,\\s*\\d+\\s*,\\s*\\d+(?>\\r?\\n)?)+";

StringBuilder input = new StringBuilder();

for( int i = 0; i < 1000000; ++i) {
  input.append("abc.com, 123, 456\n");
}

Pattern p = Pattern.compile( regex );
Matcher m = p.matcher( input );

System.out.println(m.matches());

В конце концов, это может быть проблема обратного отслеживания.

Обновить: просто позвольте этому тестовому запуску с 20000 строк и все равно не сработает. Это по крайней мере в 20 раз больше, чем раньше.:)

Обновление 2: снова посмотрел мой тест. Я нашел медленную часть, конкатенацию строк. (O..O). Я обновил тест и использовал 1 миллион строк, но все равно не получилось.:)

Ответ 3

Проблема в том, что ваше регулярное выражение слишком сложно. Каждая строка ввода, которую вы обрабатываете, приводит к (по моему мнению) 10 точкам возврата, и по крайней мере некоторые из них, похоже, обрабатываются рекурсивным движком. Это может быть несколько сотен кадров стека, которых было бы достаточно, чтобы дать вам StackOverflowError.

IMO, вам нужно изменить шаблон так, чтобы он соответствовал одной группе/строке данных. Затем вызовите Matcher.find для разбора каждой строки. Я ожидаю, что вы обнаружите, что это быстрее.

Оптимизация регулярного выражения другими способами при одновременном попытке сопоставить весь блок за один проход, вероятно, не будет работать. Вы можете получить его в соответствии с N раз больше строк данных, но по мере увеличения количества строк на входе вы снова столкнетесь с той же проблемой.

И даже если вы заставите его работать как многострочное регулярное выражение, есть вероятность, что он не будет работать с другими реализациями библиотек регулярных выражений Java; например в более ранних версиях Oracle JRE или вне Oracle.

Я согласен с другими ответами, что это не пример "катастрофического возврата". Скорее это взаимодействие между тем, как механизм регулярных выражений обрабатывает точки возврата, и тот факт, что их слишком много, когда вы даете ему несколько строк ввода.

Ответ 4

Я воспроизвел эту проблему, но только для гораздо больших строк.

$ java -version
java version "1.6.0_22"
OpenJDK Runtime Environment (IcedTea6 1.10.2)    (6b22-1.10.2-0ubuntu1~11.04.1)
OpenJDK 64-Bit Server VM (build 20.0-b11, mixed mode)

Мой тестовый код:

public class Testje
{
    public static void main(String... args)
    {
        String regex = "^(([a-zA-Z0-9][a-zA-Z0-9\\-]*\\.)+([a-zA-Z]{2,})\\s*,\\s*\\d+\\s*,\\s*\\d+(\\r?\\n)?)+$";
        String data = "";
        for (int i = 0; i<224; i++) data += "abc.com, 123, 456\n";
        System.out.println(data.matches(regex));
    }
}

Для чего-либо меньшего, чем 224 в этом цикле, код работает нормально. Для 224 и более копий этой строки я получаю огромную трассировку стека.

О, обратите внимание, что использование (?: groups не изменяет размер строки, которая все еще работает.