#java #regex
#java #регулярное выражение
Вопрос:
Следующий код блокируется в моей системе. Почему?
System.out.println( Pattern.compile(
"^((?:[^'"][^'"]*|"[^"]*"|'[^']*')*)/\*.*?\*/(.*)$",
Pattern.MULTILINE | Pattern.DOTALL ).matcher(
"nnnnnnUPDATE "$SCHEMA" SET "VERSION" = 12 WHERE NAME = 'SOMENAMEVALUE';"
).matches() );
Шаблон (предназначенный для обнаружения комментариев формы, /*...*/ но не внутри ' или " ) должен быть быстрым, поскольку он детерминирован…
Почему это занимает ооочень много времени?
Ответ №1:
Вы сталкиваетесь с катастрофическим возвратом.
Глядя на ваше регулярное выражение, легко увидеть, как .*? и (.*) могут соответствовать одному и тому же содержимому, поскольку оба также могут соответствовать промежуточной */ части (точка соответствует всем, помните). Плюс (и что еще более проблематично), они также могут сопоставлять тот же материал, который ((?:[^'"][^'"]*|"[^"]*"|'[^']*')*) совпадает.
Механизм регулярных выражений увязает в попытке выполнить все перестановки, особенно если строка, с которой вы тестируете, длинная.
Я только что сверил ваше регулярное выражение с вашей строкой в RegexBuddy. Это прерывает попытку сопоставления после 1.000.000 шагов механизма регулярных выражений. Java будет продолжать работать до тех пор, пока не выполнит все перестановки или пока не произойдет переполнение стека…
Вы можете значительно повысить производительность вашего регулярного выражения, запретив возврат к материалам, которые уже были сопоставлены. Для этого вы можете использовать атомарные группы, изменив ваше регулярное выражение на
^((?>[^'"] |"[^"]*"|'[^']*')*)(?>/*.*?*/)(.*)$
или в виде строки Java:
"^((?>[^'"] |"[^"]*"|'[^']*')*)(?>/\*.*?\*/)(.*)$"
Это уменьшает количество шагов, которые должен выполнить механизм регулярных выражений, с> 1 миллиона до 58.
Однако имейте в виду, что при этом будет найдено только первое вхождение комментария, поэтому вам придется применять регулярное выражение повторно, пока оно не завершится сбоем.
Редактировать: я только что добавил две косые черты, которые были важны для работы выражений. И все же мне пришлось изменить более 6 символов …. 🙁
Комментарии:
1. Большое спасибо. Я вообще не знал об атомарных группах. После добавления двух косых черт (по одной для каждого формата) ваше решение работает. С наилучшими пожеланиями, Штеффен
2. Я не знаю, почему я не заметил в прошлом году, но это выражение не соответствует
"TEST /* A */ TEST", например, потому что первый / ist уже связан атомной группой. Мне пришлось изменить его на"^((?:(?>[^'"/] |"[^"]*"|'[^']*')|/)*)(?>/\*.*?\*/)(.*)$". Если у кого-то есть идея оптимизации, добро пожаловать…
Ответ №2:
Я рекомендую вам прочитать Сопоставление регулярных выражений может быть простым и быстрым (но происходит медленно в Java, Perl, PHP, Python, Ruby, …).
Комментарии:
1. Я бы проверил, применимы ли аргументы по-прежнему. Это не значит, что все эти языки не изменили или не оптимизировали определенные элементы за последние четыре года. Также неясно, является ли это справедливым сравнением, решение PCRE перестает выполнять откат на 23 итерациях, что означает, что теоретически в нем могут отсутствовать решения.
2. Даже когда статья была написана, некоторые из этих языков включали способы эффективного навязывания детерминированного поведения. Java всегда поддерживала атомарные группы и притяжательные кванторы; Perl и PCRE поддерживают их, а также управляющие глаголы с обратным отслеживанием для более точного управления; Ruby теперь работает на базе библиотеки Oniguruma , поэтому в нем также есть атомарные группы и притяжательные кванторы. Конечно, пользователи должны знать об этих функциях и научиться их использовать…
Ответ №3:
Я думаю, это из-за этого бита:
(?:[^'"][^'"]*|"[^"]*"|'[^']*')*
Удаление второй и третьей альтернатив дает вам:
(?:[^'"][^'"]*)*
или:
(?:[^'"] )*
Повторные повторы могут занимать много времени.
Комментарии:
1. Проблема не в этом. Ни одна из этих альтернатив не может соответствовать чему-либо, что может сделать одна из других, поэтому повторять это быстро. Поскольку один из них всегда совпадает, возврата нет. Однако части, которые следуют в регулярном выражении, будут приводить к катастрофическому возврату.
Ответ №4:
Для /* и */ обнаружения комментариев я бы предложил использовать такой код:
String str = "nnnnnnUPDATE "$SCHEMA" /*a commentnn*/ SET "VERSION" = 12 WHERE NAME = 'SOMENAMEVALUE';";
Pattern pt = Pattern.compile(""[^"]*"|'[^']*'|(/\*.*?\*/)",
Pattern.MULTILINE | Pattern.DOTALL);
Matcher matcher = pt.matcher(str);
boolean found = false;
while (matcher.find()) {
if (matcher.group(1) != null) {
found = true;
break;
}
}
if (found)
System.out.println("Found Comment: [" matcher.group(1) ']');
else
System.out.println("Didn't find Comment");
Для приведенной выше строки он выводит:
Found Comment: [/*a comment
*/]
Но если я изменю входную строку на:
String str = "nnnnnnUPDATE "$SCHEMA" '/*a commentnn*/' SET "VERSION" = 12 WHERE NAME = 'SOMENAMEVALUE';";
или
String str = "nnnnnnUPDATE "$SCHEMA" "/*a commentnn*/" SET "VERSION" = 12 WHERE NAME = 'SOMENAMEVALUE';";
Вывод такой:
Didn't find Comment