28. regexp. Регулярные выражения

Философия RE2: Безопасность и линейное время

История регулярных выражений неразрывно связана с Bell Labs: еще в 1968 году Кен Томпсон описал элегантный алгоритм симуляции недетерминированного конечного автомата (NFA), работающий за строго линейное время от длины текста. Однако на протяжении десятилетий мир веб-разработки находился под гипнозом PCRE (Perl Compatible Regular Expressions), где ради обратных ссылок и заглядываний вперед пожертвовали математической предсказуемостью, выбрав рекурсивный бэктрекинг (backtracking).

Пакет regexp в Go кардинально отличается от реализаций в PHP, Python или Ruby. Вместо классического PCRE (Perl Compatible Regular Expressions), использующего рекурсивный бэктрекинг, Go использует движок RE2, спроектированный Рассом Коксом.

Главный принцип RE2 — гарантированное линейное время выполнения O(n) относительно длины входной строки. Это означает, что движок никогда не войдет в экспоненциальную рекурсию из-за неудачных совпадений. На практике это делает Go-приложения полностью иммунными к атакам ReDoS (Regular Expression Denial of Service), где злоумышленник отправляет специально составленный паттерн или строку, вызывающую 100% загрузку CPU на других языках.

Цена этой безопасности — отсутствие обратной совместимости с некоторыми фичами PCRE: в Go нет обратных ссылок (\1, (?P=name)), опережающих/ретроспективных проверок ((?=...), (?!...)) и атомарных групп. В теории формальных языков доказано, что обратные ссылки превращают задачу поиска подстроки в NP-полную проблему. Для 95% задач валидации, парсинга логов и замены текста возможностей RE2 более чем достаточно, а оставшиеся 5% задач в Go решаются специализированными парсерами или простым кодом на срезах.

Under the hood. Компиляция, байткод и отсутствие отката

Когда вы вызываете regexp.Compile(), происходит многоступенчатый процесс:

1. Парсинг: Строка паттерна преобразуется в AST с помощью пакета regexp/syntax.
2. Оптимизация: AST упрощается, вложенные группы сворачиваются, константы объединяются.
3. Компиляция в байткод: AST транслируется в последовательность низкоуровневых инструкций (instMatch, instSave, instNop, instSplit и др.).
4. Исполнение: Движок использует симуляцию NFA с отслеживанием множества активных состояний. В типичных случаях он работает как DFA, проходя по строке за один проход без возвратов.

flowchart LR
    classDef process  fill:#1e293b,stroke:#38bdf8,stroke-width:1px,color:#f8fafc
    classDef success  fill:#064e3b,stroke:#34d399,stroke-width:1px,color:#f8fafc
    classDef error    fill:#7f1d1d,stroke:#f87171,stroke-width:1px,color:#f8fafc
    classDef warning  fill:#78350f,stroke:#fbbf24,stroke-width:1px,color:#f8fafc
    classDef entry    fill:#1e3a5f,stroke:#38bdf8,stroke-width:2px,color:#f8fafc
    classDef aux      fill:#334155,stroke:#64748b,stroke-width:1px,color:#f8fafc
    classDef system   fill:#312e81,stroke:#a78bfa,stroke-width:1px,color:#f8fafc
    classDef data     fill:#132d29,stroke:#2dd4bf,stroke-width:1px,color:#f8fafc
    classDef network  fill:#881337,stroke:#fb7185,stroke-width:1px,color:#f8fafc
    classDef accent   fill:#1e1b4b,stroke:#818cf8,stroke-width:1px,color:#f8fafc
    A["Строка паттерна"]:::process --> B["Парсинг в AST<br>пакет regexp_syntax"]
    B --> C["Оптимизация дерева"]
    C --> D["Генерация байткода<br>инструкции split, save, match"]
    D --> E["Создание Regexp"]
    E --> F["Передача входных данных"]
    F --> G{"Проход по байткод<br>без рекурсии"}
    G --> H["Совпадение найдено"]
    G --> I["Возврат nil"]
    H --> J["Завершение за O n"]
    I --> J
  

Отсутствие бэктрекинга означает, что движок не тратит время на отмену неудачных совпадений. Если паттерн требует проверки нескольких ветвей, RE2 выполняет их параллельно, поддерживая активные состояния в компактном массиве. Это гарантирует предсказуемое время выполнения и защищает CPU от перегрузки.

Mechanical Sympathy. Аллокации, кэш и переиспользование

Самая распространенная ошибка при работе с regexp — создание новых инстансов в циклах или HTTP-обработчиках. Компиляция регулярного выражения — дорогая операция, требующая аллокаций и парсинга.

// ❌ КАТЕГОРИЧЕСКИ НЕЛЬЗЯ: Компиляция на каждый запрос
func validateEmail(email string) bool {
    re := regexp.MustCompile(`^[a-z0-9._%+-]+@[a-z0-9.-]+\.[a-z]{2,}$`)
    return re.MatchString(email)
}

Идиоматичный подход: Компилируйте один раз при инициализации пакета.

// ✅ ИДИОМАТИЧНО: Глобальная переменная или пакетный уровень
var emailRegex = regexp.MustCompile(`^[a-z0-9._%+-]+@[a-z0-9.-]+\.[a-z]{2,}$`)

func validateEmail(email string) bool {
    return emailRegex.MatchString(email)
}

Оптимизация аллокаций через индексы

Методы FindString, FindAllString, FindStringSubmatch всегда создают новые строки в куче. В высоконагруженных системах (парсинг миллионов строк логов) это генерирует значительное давление на GC.

Вместо копирования строк используйте *Index версии, которые возвращают смещения в исходной строке. Вы можете нарезать оригинальную строку без аллокаций.

func extractMetrics(logLine string, re *regexp.Regexp) (string, float64, error) {
    // Возвращает слайс индексов: [полное_совпадение, группа1, группа2]
    matches := re.FindStringSubmatchIndex(logLine)
    if matches == nil {
        return "", 0, errors.New("metric not found")
    }

    // Zero-copy извлечение подстрок через нарезку
    name := logLine[matches[2]:matches[3]]

    // Парсим число напрямую из подстроки, избегая создания string
    valStr := logLine[matches[4]:matches[5]]
    val, err := strconv.ParseFloat(valStr, 64)
    if err != nil {
        return "", 0, fmt.Errorf("parse float: %w", err)
    }
    return name, val, nil
}

Ловушки и хардкорные вопросы с собеседований

Сравнение с экосистемами других языков

Итог

1. Go использует движок RE2, гарантирующий линейное время O(n) и защиту от ReDoS-атак.
2. Никогда не компилируйте regexp в циклах или обработчиках. Используйте глобальные переменные с MustCompile.
3. *regexp.Regexp потокобезопасна. Один инстанс может обслуживать тысячи запросов параллельно.
4. Для снижения нагрузки на GC используйте FindStringSubmatchIndex и нарезайте оригинальную строку, избегая копирования в кучу.
5. Якоря ^/$ и точка . работают иначе, чем в PCRE. Используйте флаги (?m) и (?s) при необходимости.
6. Заменяйте регулярные выражения на функции из strings/bytes, когда логика допускает простые проверки.

Освоив парсинг текстовых паттернов, мы переходим к самой распространенной задаче сериализации данных в бэкенде. Как Go обрабатывает JSON, почему стандартная библиотека выбирает безопасность над скоростью и как обойти ограничения кодировщика? В следующей статье: 29. encoding/json. JSON в стандартной библиотеке.