Pattern.matches () дает StackOverflowError

Question

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

Regex имеет следующий формат:
имя домена -> пробел ->, -> пробел -> число -> пробел ->, -> пробел -> число -> новая строка

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

Answer 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()), но, возможно, это поможет избежать StackOverflows. У меня не установлен Java SDK, поэтому я сам не могу его протестировать.

Answer 2

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

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

---

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

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

---

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

Answer 3

Вы можете попытаться использовать атомарные группы ((?>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 миллион строк, все еще без сбоев.:)

Answer 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 в цикле for, код работает нормально. Для 224 и более копий этой строки я получаю огромный след стека.

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