Оптимизация регулярных выражений: избегаем взрыва…

Производительность regex: одно выражение может положить весь сервер

Катастрофический возврат (Catastrophic Backtracking) может увеличить время сопоставления регулярного выражения с миллисекунд до часов.

Сценарий	Regex	Длина ввода	Время
Нормальное сопоставление	`/^abc$/`	100	<1мс
Линейный возврат	`/a*b/`	100	~1мс
Экспоненциальный возврат	`/(a+)+b/`	30	~10с
Экспоненциальный возврат	`/(a)b/`	30	~10с

I. Принцип механизма возвратов

Как работает движок NFA

JavaScript использует движок NFA (Недетерминированный Конечный Автомат) с алгоритмом возвратов:

Ввод: "aaaac"
Regex: /(a+)+c/

Процесс сопоставления:
1. (a+) совпадает с "aaaa" → пробует +c → не совпадает с 'c'
2. Возврат: (a+) совпадает с "aaa" → (a+) совпадает с "a" → пробует +c → не совпадает
3. Возврат: (a+) совпадает с "aa" → (a+) совпадает с "aa" → пробует +c → не совпадает
4. Возврат: (a+) совпадает с "aa" → (a+) совпадает с "a" → (a+) совпадает с "a" → ...
5. ... экспоненциальный возврат

Расчёт количества возвратов

Для /(a+)+b/ при сопоставлении с "aaa..." (n букв a):

Количество возвратов ≈ 2^n

n=10: ~1 024 раза
n=20: ~1 048 576 раз
n=30: ~1 073 741 824 раза

II. Распространённые паттерны катастрофических возвратов

Паттерн 1: Вложенные квантификаторы

// Катастрофический возврат
/(a+)+b/     // Вложенный + квантификатор
/(a*)*b/     // Вложенный * квантификатор
/(\w+)+@/    // Вложенный \w+

// Исправление: избегать вложенных квантификаторов
/a+b/        // Одноуровневый квантификатор
/(\w+)@/     // Одноуровневый квантификатор

Паттерн 2: Упорядоченная альтернатива

// Катастрофический возврат: варианты альтернативы с общим префиксом
/(a|ab)+c/

// При вводе "abababab..." без совпадения движок пробует все комбинации
// Количество возвратов ≈ O(2^n)

// Исправление: извлечь общий префикс
/a(b?)+c/

Паттерн 3: Перекрывающиеся квантификаторы

// Катастрофический возврат
/.*.*=/

// Оба .* могут совпадать с одним содержимым, создавая множество возвратов

// Исправление: объединить квантификаторы
/.*=/

Паттерн 4: Ловушка обратной ссылки

// Катастрофический возврат
/^(b+)(a+)\1$/

// При вводе "bbbbaaaa" \1 пробует все подразделения b+

// Исправление: по возможности избегать обратных ссылок или ограничивать диапазон квантификатора
/^(b+)(a+)\1$/.test(input) // Только для коротких вводов

III. Техники оптимизации

Техника 1: Конкретизация классов символов

// Медленно: . совпадает с любым символом, много возвратов
/.*foo/

// Быстро: [^\n]* не совпадает с переносами строк, уменьшает возвраты
/[^\n]*foo/

// Ещё быстрее: если известно, что перед foo только буквы
/[a-z]*foo/

Техника 2: Привязка для уменьшения пространства поиска

// Медленно: пытается сопоставить с каждой позиции
/foo/

// Быстро: если foo в начале строки
/^foo/

// Быстро: если foo в конце строки
/foo$/

// Быстро: привязка с обеих сторон
/^foo$/

Техника 3: Правильное использование ленивых квантификаторов

// Сценарий: извлечь содержимое тегов <b>

// Медленно: жадный квантификатор + возвраты
/<b>(.*)<\/b>/

// Быстро: ленивый квантификатор (но возвраты возможны)
/<b>(.*?)<\/b>/

// Быстрее всего: исключающий класс символов (ноль возвратов)
/<b>([^<]*)<\/b>/

Способ	Совпадение `<b>hello</b><b>world</b>`	Возвраты
`(.*)`	`hello</b><b>world`	Много
`(.*?)`	`hello`	Мало
`([^<]*)`	`hello`	Ноль

Техника 4: Атомарные группы (ES2024+)

// Атомарная группа (?>...) после совпадения не возвращается
const regex = /^(?>a+)+b$/;

// Эквивалентно: если a+ совпало, не возвращаться для повторной попытки внешним +
// Совпадает "aaab" → успех
// Совпадает "aaa" → немедленный провал (без экспоненциальных возвратов)

Техника 5: Сверхжадные квантификаторы (некоторые движки)

// Сверхжадный квантификатор a++ не освобождает для возвратов после совпадения
// JavaScript не поддерживает, но можно имитировать атомарными группами
const regex = /^(?>(a+))b$/;

Техника 6: Предкомпиляция + повторное использование

// Медленно: каждый раз создаётся новый RegExp
function validate(input) {
  return /^[\w.+-]+@[\w-]+\.[\w.]+$/.test(input);
}

// Быстро: предкомпиляция
const EMAIL_REGEX = /^[\w.+-]+@[\w-]+\.[\w.]+$/;
function validate(input) {
  return EMAIL_REGEX.test(input);
}

IV. Инструменты анализа производительности

Использование инструмента regex ToolsKu

Открыть Инструмент регулярных выражений
Ввести регулярное выражение и тестовый текст
Посмотреть результаты сопоставления и время
Скорректировать regex, сравнить производительность до и после оптимизации

Встроенное измерение в JS

function measureRegex(regex, input, iterations = 1000) {
  const start = performance.now();
  for (let i = 0; i < iterations; i++) {
    regex.test(input);
  }
  const end = performance.now();
  return {
    totalTime: end - start,
    avgTime: (end - start) / iterations,
    iterations,
  };
}

// Сравнение
const slow = measureRegex(/(a+)+b/, 'a'.repeat(25));
const fast = measureRegex(/a+b/, 'a'.repeat(25));
console.log(`Медленно: ${slow.avgTime}мс, Быстро: ${fast.avgTime}мс`);

Библиотека recheck для обнаружения опасных regex

npm install recheck

import { check } from 'recheck';

const result = check(/(a+)+b/);
// { safe: false, complexity: 'exponential' }

const result2 = check(/a+b/);
// { safe: true, complexity: 'linear' }

V. Сравнение производительности распространённых регулярных выражений

Regex	Сложность	Безопасно	Оптимизированная версия
`/(a+)+b/`	Экспоненциальная	❌	`/a+b/`
`/(a\|ab)+c/`	Экспоненциальная	❌	`/a(b?)+c/`
`/..=/`	Экспоненциальная	❌	`/.*=/`
`/(\d+){1,10}/`	Полиномиальная	⚠️	`/\d{1,10}/`
`/^[a-z]+$/`	Линейная	✅	—
`/^\d{4}-\d{2}-\d{2}$/`	Константная	✅	—

VI. Серверная защита

Защита по таймауту

function safeRegexTest(regex, input, timeoutMs = 100) {
  const start = Date.now();
  const result = regex.test(input);
  if (Date.now() - start > timeoutMs) {
    throw new Error('Regex timeout: possible catastrophic backtracking');
  }
  return result;
}

Движок re2 (гарантия линейного времени)

import RE2 from 're2';

// RE2 гарантирует линейное время, без взрыва возвратов
const regex = new RE2('(a+)+b');
regex.test('a'.repeat(100)); // Безопасно, не зависнет

Ограничение длины ввода

function validateWithLimit(regex, input, maxLength = 1000) {
  if (input.length > maxLength) {
    throw new Error(`Input exceeds maximum length: ${maxLength}`);
  }
  return regex.test(input);
}

VII. Контрольный список лучших практик

Избегать вложенных квантификаторов: (a+)+ → a+
Конкретизировать классы символов: . → [^\n] или более конкретный класс
Извлекать общие префиксы: (a|ab) → a(b?)
Использовать исключающие классы вместо ленивых: (.*?) → ([^<]*)
Привязка для уменьшения пространства поиска: ^ / $
Предкомпиляция регулярных выражений: избегать повторного создания
Использовать recheck для проверки: автоматически обнаруживать опасные regex в CI
Серверная защита по таймауту: предотвращать regex DoS
Ограничивать длину ввода: уменьшить влияние худшего случая