Regex - Catastrophic Backtracking

Одразу попереджаю, що цей пост дуже нудний, але потрібно хоча б відвідати посилання, які я навів на прикінці. Проблеми такого характеру дуже важко знаходити, а тому краще ці проблеми не робити ;).

Отже, нещодавно, стикнувся з цікавим багом у своєму проекті.

В проекті є місце де перевіряється дуже велика кількість поштових адрес. Гарантовано що 99,9% адрес правильні. Перевірку таких адрес зробили за допомогою RegEx. Юніт тести перевіряли декілька комбінації. Все працювало, і юніт тести працювали, поки не прийшла адреса без літери "@", і сервер впав.

Якщо комусь цікаво подивитися можу пошукати цей regex, але краще вже я розповім чому це сталось, і як цьому зарадити.

По-перше, чому це вийшло

Якщо коротко описати ситуацію(я видалив інший опис, бо він виявився занадто великим ;) ) то в нас був шаблон який повинен працювати з двома частинами, але розподіл на ці дві частини не був обо'вязковим.

Тепер уявіть ситуацію коли приходить рядок який підпадає під категорію для якої розподіл не обов'язковий. Обробнику шаблона(Regex Engine) потрібно якось зрозуміти яка частина перша, а яка друга. Для цього йому потрібно перебрати усі комбінації поки не з'явиться одна яка зможе задовольнити обидві частини шаблону.

На пальцях:

Наприклад рядок з 10 літер. Спочатку на першу літеру першу частину шаблону, а потім на все інше другу. Якщо не вийшло. Переходимо до другої літери. Тобто першу частину до перших двох літер, а другу для залишившихся. І так по всім літерам.

А тепер як цьому зарадити

По-перше якщо в шаблоні є частини, то потрібно максимально зменшити кількість можливих комбінацій чих частин.

По-друге це не робити(або принаймні поміркувати над цим) необов'язкові розподілювачі (Наприклад символ "@" в поштовій адресі).

Теретє. Іноді краще поміркувати над тим щоб розбити великий шаблон на декілька малих шаблонів. Наприклад, зробити один шаблон який поверне дві частини, а потім вже працювати з тими частинами. Це дуже зменшить можливість помилок. А отже зменшить витрати на підтримку.

Четверте. Негативне тестування шаблонів дуже потрібне. Не дивіться на те що покриття тестами вже і так 80% ;), краще нехай воно і так залишиться 80%, але шаблон буде протестовано з найбільшою кількістю можливих варіантів. Допомогти в цьому можуть Data Driven Tests.

От і все, далі по темі ще можна почитати:

Формалізований опис проблеми - http://www.regular-expressions.info/regexbuddy/atomicproblem.html

Формалізоване рішення - http://www.regular-expressions.info/regexbuddy/atomicsolution.html

Ще одне рішення - http://www.regular-expressions.info/atomic.html

Опис проблеми з картинками (рекомендую) - http://www.codinghorror.com/blog/archives/000488.html

Тулза яка дозволяє дебажити шаблони, нажаль коштує гроші, добре що тільки 40$ - http://www.regexbuddy.com/