Чому алгоритм зворотного пошуку у регулярних виразах може тихо заблокувати ваш сервер

Шаблон перевірки імені користувача пройшов перегляд коду, успішно пройшов усю набір тестів, але через кілька тижнів після розгортання змусив API-кінцеву точку зупинитися на одинадцять секунд через одну вхідну заявку. Не було жодних збоїв чи винесених винятків — процес просто перестав відповідати, залишаючись на рівні 100% використання CPU під час обробки рядка, довжина якого становила ледве сорок символів.

У звичайному розумінні жодних помилок не було внесено. Сам регулярний вираз був коректним та точно відповідав тому, що мав знаходити. Однак він мав приховану особливість, на яку більшість розробників ніколи не навчаються звертати увагу, а щоб її зрозуміти, потрібно подивитися за символами та зрозуміти, що насправді робить регулярний вираз під час виконання, що більшість навчальних матеріалів ігнорують, пояснюючи лише такі токени, як \d та +.

Регулярний вираз — це мініатюрна діаграма потоку, а не послідовність символів

Розгляньмо шаблон, призначений для перевірки коду продукту, який складається з двох великих літер, за якими йдуть чотири цифри:

const productCode = /^[A-Z]{2}\d{4}$/;
console.log(productCode.test("LM4821")); // true
console.log(productCode.test("LM482"));  // false

Природно уявляти це як скорочений опис форми рядка. Кращою ментальною моделлю, яка принесе користь пізніше, є розгляд його як мініатюрної діаграми потоку: спочатку потрібні саме дві великі літери, потім — саме чотири цифри, а після цього вхідний даний має завершитися. Механізм обробки просувається по вхідному даним по одному символу, намагаючись знайти шлях у цій діаграмі від початкового до кінцевого вузла. Якщо він успішно досягає кінця, це означає збіг. Якщо він натрапляє на перешкоду, а позаду все ще є неперевірена гілка, він відступає та пробує іншу гілку замість неї.

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

Групи перетворюють „Чи збігається?“ на „Що саме там є“

Виклик функції .test() повертає лише значення true або false. Блокування частин шаблону дужками дозволяє окремо зафіксувати фрагменти знайденого тексту, що робить регулярні вирази справді корисними для парсингу, а не лише для верифікації:

const logPattern = /^\[(\w+)\] (\d{4}-\d{2}-\d{2}T\d{2}:\d{2}:\d{2}) (.+)$/;
const line = "[ERROR] 2026-08-15T10:22:01 Failed to connect to database";

const match = logPattern.exec(line);
console.log(match[1]); // "ERROR"
console.log(match[2]); // "2026-08-15T10:22:01"
console.log(match[3]); // "Failed to connect to database"

Кожен ділянок у форматі з дужками стає окремим елементом у масиві результатів, впорядкованим за тим, де знаходиться відкриваюча дужка у форматі. Це перетворює просту перевірку наявності/відсутності певних умов — підтвердження того, що рядок має формат запису журналу — на щось набагато корисніше: рівень серйозності, час створення та сам текст повідомлення стають трьома окремими значеннями, готовими до використання. Саме ця можливість пояснює, чому регулярні вирази так часто використовуються під час обробки журналів, парсингу конфігурацій та в будь-яких ситуаціях, коли текст нестрогої структури потрібно перетворити на щось, з чим програма може працювати безпосередньо.

Жадібне зіставлення бере більше, ніж планувалося

Ця наступна помилка — одна з тих, яку майже кожен розробник робить принаймні один раз. Уявіть ситуацію, коли потрібно видалити легкі HTML-теги з поля тексту:

const html = "<b>Featured</b> item, <i>on sale</i> now";
console.log(html.replace(/<.*>/g, ""));
// "Featured item, on sale now" — wait, that actually looks right...

const html2 = "<b>Sale</b> ends <i>Friday</i>";
console.log(html2.replace(/<.*>/g, ""));
// "" — everything vanished

Друга рядок виявляє цю помилку. За замовчуванням .* є жадібним — він намагається поглинути якомога більше символів, повертаючи їх лише тоді, коли це абсолютно необхідно за правилами шаблону. Оскільки цей рядок містить два окремі теги, шаблон <.*> не зупиняється на першому закриваючому тегу </b>. Він продовжує обробляти все, що знаходиться після нього — повз ends, прямо до останнього тегу > у рядку, всередині </i> — адже один жадібний шаблон .*> вважається задоволеним, якщо він знаходить останній доступний тег > в тексті, незалежно від того, наскільки він далеко розташований.

console.log(html2.replace(/<.*?>/g, ""));
// "Sale ends Friday"

Розміщення ? безпосередньо після * змінює його з режиму «жадібного» на режим «лінивого»: движок тепер намагається знайти якомога менше символів, розширюючи пошук лише тоді, коли немає іншого способу задовольнити наступний елемент. Завдяки цій зміні кожна послідовність <...> закривається біля найближчого >, а не біля останнього в усьому рядку, тож теги видаляються по одному, як і планувалося. Ця різниця у один символ — * проти *? — пояснює значну частину проблем типу «регулярні вирази видаляють набагато більше тексту, ніж очікувалося», з якими стикаються розробники.

Баг, який насправді зупинив сервер

Розгляньмо спрощену версію шаблону, відповідального за це одинадцятисекундне затримку: перевірку імені користувача, яка має вимагати однієї або кількох частин з літер, можливо розділених пробілами, після чого йде знак @.

const badPattern = /^(\w+)+@/;
console.log(badPattern.test("valid_user@example.com")); // true, fast
console.log(badPattern.test("this_is_a_fairly_long_username_with_no_at_sign"));
// hangs, sometimes for a very long time, depending on length

Проблема полягає у вкладеній повторюваності: (\w+)+, тобто послідовність одного або кількох символів-слів, яка сама знаходиться всередині групи, що повторюється один або кілька разів. Коли вхідний рядок дійсно містить @, движок майже миттєво знаходить збіг. Але якщо надати йому рядок без жодного @, движок не може просто так здатися — йому потрібно повністю перевірити, що жоден з можливих варіантів не підходить. Кількість таких варіантів для перевірки є вражаючою: внутрішній + може захопити один символ, поки зовнішня група повторюється для решти, або може захопити два символи та дозволити зовнішній групі повторюватися для того, що залишилося, і так далі — пробується кожен можливий спосіб розділення. Движок перевіряє кожну з цих комбінацій, перш ніж погодитися оголосити про невдачу, і кожен додатковий символ приблизно подвоює кількість комбінацій.

Існують такі обмеження. Це означає, що 40-символьний логін, який не відповідає критеріям, не просто відхиляється у десять разів повільніше, ніж 4-символьний, — швидкість його обробки зменшується експоненційно, що пояснює, чому регулярний вираз, який успішно пройшов тестування, коли мав справу лише з коректними логінами, може раптово зависнути при отриманні довгої строки, з якою він ніколи не мав працювати.

const fixedPattern = /^\w+@/;

Як тільки ви зрозумієте кореневу причину, рішення здається майже занадто простим: взагалі не було потреби у вкладеній повторенні. \w+ сам по собі означає точно те саме, що й (\w+)+ для будь-якого вхідного даних, яке має успішно обробитися, але без ризику експоненційного зворотного пошуку, який ховається за цим. Ця проблема має відому назву — катастрофічний зворотний пошук, і ознакою є використання будь-якого оператора повторення щодо групи, яка вже містить власний оператор повторення; шаблони на кшталт (x+)+, (x*)+ або (x+)* є різновидами однієї й тієї самої підставної проблеми.

Що це насправді навчає нас шукати

Вам не потрібно запам’ятовувати кожну існуючу небезпечну форму шаблону. Важливо усвідомити одну основну істину: двигун regex не обчислює шаблон миттєво, він шукає відповідність, по одному шляху за раз, відступаючи та пробуючи інший шлях щоразу, коли поточний зазнає невдачі. Звичайні шаблони мають настільки мало можливих шляхів для перевірки, що цей пошук завершується раніше, ніж ви взагалі помітите затримку. Справжня небезпека виникає саме при вкладених, перекриваючихся повтореннях, де кількість шляхів для перевірки не лише поступово зростає, а й множиться з кожною додатковою літерою вхідних даних, яка не відповідає шаблону. Тож тестуйте свої regex-вирази не лише на рядках, які ви очікуєте побачити у відповідності, а й на довгих рядках, створених навмисно для отримання невдачі. Саме ті дані, які ваш набір тестів ніколи не розглядав, зрештою з’являються у реальних умовах використання.