Еще раз о регекспах, бэктрекинге и том, как можно положить на лопатки JVM двумя строками «безобидного» кода

[Iv38]

Вспоминается прошлогодний падёж Cloudflare из-за неудачной регулярки и тяжелого бэктрекинга, который она принесла.

[LARII]

Как по мне, это результат отступления от правил.
Если у нас паттерн "(0*)*1", а строка «0000000000000000000000000000000000000000», то последовательность действий такая:
— результат выполнения выражения в группе: «0000000000000000000000000000000000000000». Дошли до конца строки, на остальные инструкции не хватает символов строки. Все, no match.

[DrMefistO]

Иногда вы не знаете, что придёт для матчинга.

[martin_wanderer]

Не всегда будет «no match». Достаточно чуть усложнить:
([01]*)*1
01000000000000000000000

[LARII]

Смотрим. 0 или 1. Первый символ. 0. Совпадение. Квантификатор {0, }. Следующий символ строки. 1. Если не 0 или 1 тогда следующая инструкция паттерна. Иначе читаем до тех пор, пока будет другой символ. Конец строки. Следующая инструкция паттерна. Квантификатор {0, } пропускаем. Следующая инструкция паттерна. 1. Конец строки. No match.

[martin_wanderer]

Так в данном случае таки есть match: «01»

[LARII]

Релятивизм. Если паттерн — последовательность команд слева-направо, то таки нет. Если маска, с которой сравнивается строка, то таки да.

[LARII]

Дубль.