Regex Pattern Catastrophic backtracking

Question

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

Может ли кто-нибудь предложить лучший способ переписать этот шаблон или инструмент, который поможет мне сделать это?

Выкройка:

^\[(([\p{N}]*\]\,\[[\p{N}]*)*|[\p{N}]*)\]$ 

Значения рабочего:

[1234567],[89023432],[124534543],[4564362],[1234543],[12234567],[124567],[1234567],[1234567] 

Катастрофические значения по отслеживанию - если что-то неправильно в значениях (дополнительная распорка добавлена ​​в конце):

[1234567],[89023432],[124534543],[4564362],[1234543],[12234567],[124567],[1234567],[1234567]] 

Answer 1

Никогда не используйте *, если + - это то, что вы имеете в виду. Первое, что я заметил о вашем регулярном выражении, это то, что почти все необязательно. Требуются только квадратные скобки открытия и закрытия, и я уверен, что вы не хотите обрабатывать [] в качестве допустимого ввода.

Одна из самых больших причин беглого возвращения - это иметь две или более альтернативы, которые могут соответствовать одним и тем же вещам. Это то, что у вас есть с частью |[\p{N}]*. Двигатель регулярных выражений должен пробовать каждый мыслимый путь через строку перед тем, как он сдастся, поэтому все те конструкции \p{N}* попадают в бесконечный перетягивание каната по каждой группе цифр.

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

^\[\p{N}+\](?:,\[\p{N}+\])*$ 

После потребляет первый маркер ([1234567]), если следующая вещь в строке не запятая или конец строки, он не сразу. Если он делает, см. Запятую, он должен продолжаться, чтобы соответствовать другому полному токену ([89023432]), или он не срабатывает немедленно.

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

Answer 2

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

Answer 3

Вы можете использовать атомарную группировку или притяжательные кванторы, чтобы избежать этого катастрофического возврата. Вот пример с атомной группировкой, которая занимает всего 60 шагов, чтобы вычислить до отказа с «плохим», например:

^(?>\[((\p{N}*\]\,\[\p{N}*)*|\p{N}*)\])$ 

См demo here.