StackOverflowError при сопоставлении большого ввода с использованием RegEx

Question

Я получил StackOverflowError при сопоставлении результата с использованием шаблона RegEx.

Узор (\d\*?(;(?=\d))?)+. Это регулярное выражение используется для проверки ввода:

12345;4342;234*;123*;344324

вход является строка состоит из значений (только цифры), разделенные ;. Каждое значение может включать один * в конце (используется в качестве подстановочного знака для другого соответствия). В конце строки нет ;.

Проблема в том, что это регулярное выражение отлично работает, какое небольшое количество значений. Но когда число значений слишком велико (более 300), это вызовет StackOverflowError.

final String TEST_REGEX = "(\\d\\*?(;(?=\\d))?)+"; 

// Generate string 
StringBuilder builder = new StringBuilder(); 
int number = 123456; 
for (int count = 1; count <= 300; count++) { 
    builder.append(Integer.toString(number).concat(";")); 
    number++; 
} 
builder.deleteCharAt(builder.lastIndexOf(";")) 

builder.toString().matches(TEST_REGEX); //<---------- StackOverflowError 

И StackTrace:

java.lang.StackOverflowError 
    at java.util.regex.Pattern$BmpCharProperty.match(Pattern.java:3715) 
    at java.util.regex.Pattern$GroupHead.match(Pattern.java:4556) 
    at java.util.regex.Pattern$Loop.match(Pattern.java:4683) 
    at java.util.regex.Pattern$GroupTail.match(Pattern.java:4615) 
    at java.util.regex.Pattern$Ques.match(Pattern.java:4079) 
    at java.util.regex.Pattern$Ques.match(Pattern.java:4079) 
    at java.util.regex.Pattern$BmpCharProperty.match(Pattern.java:3715) 
    at java.util.regex.Pattern$GroupHead.match(Pattern.java:4556) 
    at java.util.regex.Pattern$Loop.match(Pattern.java:4683) 
    at java.util.regex.Pattern$GroupTail.match(Pattern.java:4615) 
    at java.util.regex.Pattern$Ques.match(Pattern.java:4079) 
    at java.util.regex.Pattern$Ques.match(Pattern.java:4079) 
    at java.util.regex.Pattern$BmpCharProperty.match(Pattern.java:3715) 
    at java.util.regex.Pattern$GroupHead.match(Pattern.java:4556) 
    at java.util.regex.Pattern$Loop.match(Pattern.java:4683) 
    at java.util.regex.Pattern$GroupTail.match(Pattern.java:4615) 
    ... 

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

Я действительно ценю любое предложение, так как я не испытываю в RegEx.

Answer 1

Перед установкой проблемы с StackOverflowError ...

1. Я хотел бы указать на то, что ваше текущее регулярное выражение (\d\*?(;(?=\d))?)+ не в состоянии проверить это условие.

   Каждое значение может включать в себя один * в конце (используется в качестве шаблона для другого согласования)

   Это не может отклонить случай 23*4*4*;34*434*34, как видно here .

2. Ваше регулярное выражение будет выполнять ненужное отступление на несоответствующем входе.

3. Java использует один стек кадра для каждого повторения группы (\d\*?(;(?=\d))?) (который повторяется 1 или более раз +).

Правильное регулярное выражение будет:

\d+\*?(?:;\d+\*?)* 

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

Это не устраняет проблему StackOverflow, так как каждое повторение группы (?:;\d+\*?) также будет использовать стек. Чтобы исправить это, сделать все кванторы притяжательных, так как нет необходимости в возвратах, так как грамматика не является неоднозначной:

\d++\*?+(?:;\d++\*?+)*+ 

Ввода в строковый литерале:

"\\d++\\*?+(?:;\\d++\\*?+)*+" 

Я тестировал регулярное выражение выше с совпадающим и несоответствующим входом, который имеет более 3600 токенов (разделенных ;).

Сноска

: regex101 использует PCRE аромат, который немного отличается от Java регулярное выражение вкуса. Однако функции, используемые в вашем регулярном выражении, являются общими между ними, поэтому не должно быть расхождений.

Приложение

• На самом деле, из моего тестирования с вашим регулярным выражением (\d\*?(;(?=\d))?)+ (который неправильного согласно вашему требованию), что делает внешними наиболее + притяжательные ++, кажется, исправить StackOverflowError проблемы, в по крайней мере, в моем тестировании с около 3600 токенов (разделенных ;, строка длиной около 20 тыс. символов). Это также, похоже, не приводит к длительному времени выполнения при тестировании на несоответствующую строку.

• В моем решении сделать * квантором для группы (?:;\d+\*?) притяжательных достаточно для разрешения StackOverflowError.

  "\\d+\\*?(?:;\\d+\\*?)*+" 
  

  Однако я делаю все притяжательным, чтобы быть на безопасной стороне.

Answer 2

Возможно, вам нужно увеличить максимальный размер вашего стека, чтобы он не переполнялся. You can read about how to do that here.

В принципе, вы запускаете свою программу с помощью опции -Xss. Например, -Xss4m Когда я начал свой код с -Xss4m, ваша программа работала без переполнения стека для меня (она возвращает true).

Answer 3

Вы regexp немного неэффективны и не соответствуют вашему описанию. У вас есть '\ d \ *?' - это один разряд внизу опция *. Затем необязательно '; (? = \ D)' - ';' с контрольной цифрой. String '1 * 2 * 3 *' будет соответствовать вашему регулярному выражению, но не вашему описанию. Вы можете использовать regexp. Он соответствует вам ввода и немного более эффективно.

final String TEST_REGEX = "(\\d+\\*?)(?:;\\d+\\*?)+"; 

Он пройдет тест, когда счетчик < 300, но по-прежнему не для больших значений. Используйте операцию простой строки, например indexOf и подстрока для проверки ввода.