Перейти к основному содержимому

Дополнительный механизм RegExp без обратного отслеживания

· 7 мин. чтения
Мартин Бидлингмайер

Начиная с версии v8.8, V8 поставляется с новым экспериментальным механизмом RegExp без обратного отслеживания (в дополнение к существующему движку Irregexp), который гарантирует выполнение за линейное время относительно размера входной строки. Экспериментальный механизм доступен за флагами функций, упомянутыми ниже.

Время выполнения /(a*)*b/.exec('a'.repeat(n)) для n ≤ 100

Вот как вы можете настроить новый механизм RegExp:

  • --enable-experimental-regexp_engine-on-excessive-backtracks включает резервный механизм без обратного отслеживания при избыточных обратных переходах.
  • --regexp-backtracks-before-fallback N (по умолчанию N = 50 000) указывает, сколько обратных переходов считается «избыточными», то есть когда срабатывает резервный механизм.
  • --enable-experimental-regexp-engine включает распознавание нестандартного флага l («линейный») для регулярных выражений, например /(a*)*b/l. Регулярные выражения, созданные с этим флагом, всегда выполняются новым механизмом; Irregexp вообще не используется. Если новый механизм RegExp не может обработать шаблон регулярного выражения с флагом l, то при создании выбрасывается исключение. Мы надеемся, что эта функция в какой-то момент может быть использована для повышения безопасности приложений, которые работают с регулярными выражениями для недоверенных данных. Пока функция остается экспериментальной, так как Irregexp в разы быстрее нового механизма для большинства распространенных шаблонов.

Резервный механизм не применяется ко всем шаблонам. Чтобы резервный механизм сработал, регулярное выражение должно:

  • не содержать обратных ссылок,
  • не содержать предварительных или последующих проверок,
  • не содержать больших или глубоко вложенных конечных повторений, как, например, в /a{200,500}/, и
  • не иметь флагов u (Unicode) или i (нечувствительность к регистру).

Предыстория: катастрофическое обратное отслеживание​

Сопоставление RegExp в V8 обрабатывается движком Irregexp. Irregexp компилирует регулярные выражения в специализированный родной код (или в байткод) и, таким образом, чрезвычайно быстр для большинства шаблонов. Однако для некоторых шаблонов время выполнения Irregexp может возрастать экспоненциально к размеру входной строки. Пример выше, /(a*)*b/.exec('a'.repeat(100)), не завершается в течение нашего жизненного времени, если его выполнит Irregexp.

Так что же здесь происходит? Irregexp — это движок обратного отслеживания. Когда сталкивается с выбором, как продолжить сопоставление, Irregexp полностью исследует первый альтернативный вариант, а затем возвращается назад, если необходимо, чтобы исследовать второй вариант. Например, рассмотрим сопоставление шаблона /abc|[az][by][0-9]/ со строкой 'ab3'. Здесь Irregexp сначала пытается сопоставить /abc/ и терпит неудачу после второго символа. Затем он возвращается на два символа и успешно сопоставляет вторую альтернативу /[az][by][0-9]/. В шаблонах с квантификаторами, такими как /(abc)*xyz/, Irregexp должен выбирать после совпадения тела, сопоставлять ли тело снова или продолжать с оставшейся частью шаблона.

Попробуем понять, что происходит при сопоставлении /(a*)*b/ с меньшей входной строкой, например, 'aaa'. Этот шаблон содержит вложенные квантификаторы, так что мы просим Irregexp сопоставить последовательность последовательностей из 'a', а затем сопоставить 'b'. Очевидно, что совпадения нет, так как входная строка не содержит 'b'. Однако /(a*)*/ сопоставляется, и делает это многими экспоненциально различными способами:

'aaa'           'aa', 'a'           'aa', ''
'a', 'aa'       'a', 'a', 'a'       'a', 'a', ''
…

Irregexp изначально не может исключить, что неудача сопоставления заключительного /b/ вызвана неправильным выбором способа сопоставления /(a*)*/, поэтому он вынужден проверить все варианты. Эта проблема известна как «экспоненциальное» или «катастрофическое» обратное отслеживание.

Регулярные выражения как автоматы и байткод​

Чтобы понять альтернативный алгоритм, который невосприимчив к катастрофическому обратному отслеживанию, нам нужно сделать короткий экскурс через автоматы. Каждое регулярное выражение эквивалентно автомату. Например, регулярное выражение /(a*)*b/, приведенное выше, соответствует следующему автомату:

Автомат, соответствующий /(a*)*b/

Обратите внимание, что автомат не определяется уникально шаблоном; тот, который вы видите выше, создается механическим процессом перевода и используется в новом механизме RegExp в V8 для /(a*)*/. Необозначенные края представляют собой переходы с эпсилон: они не потребляют ввод. Переходы с эпсилон необходимы, чтобы размер автомата оставался примерно равным размеру шаблона. Пытаться наивно устранить переходы с эпсилон может привести к квадратичному увеличению числа переходов. Переходы с эпсилон также позволяют построить автомат, соответствующий регулярному выражению, из следующих четырех базовых типов состояний:

Регулярные выражения байткод инструкции

Здесь мы классифицируем только переходы из состояния, в то время как переходы в состояние могут быть произвольными. Автоматы, построенные только из этих типов состояний, могут быть представлены как байткод-программы, где каждое состояние соответствует инструкции. Например, состояние с двумя переходами с эпсилон представлено как инструкция FORK.

Алгоритм бэктрекинга​

Давайте вернемся к алгоритму бэктрекинга, на котором основан Irregexp, и опишем его с точки зрения автоматов. Предположим, нам предоставлен массив байткода code, соответствующий шаблону, и нужно проверить, совпадает ли input с этим шаблоном. Предположим, что code выглядит примерно так:

const code = [
  {opcode: 'FORK', forkPc: 4},
  {opcode: 'CONSUME', char: '1'},
  {opcode: 'CONSUME', char: '2'},
  {opcode: 'JMP', jmpPc: 6},
  {opcode: 'CONSUME', char: 'a'},
  {opcode: 'CONSUME', char: 'b'},
  {opcode: 'ACCEPT'}
];

Этот байткод соответствует шаблону (sticky) /12|ab/y. Поле forkPc инструкции FORK является индексом («программным счетчиком») альтернативного состояния/инструкции, в которую мы можем перейти, и аналогично для jmpPc. Индексы начинаются с нуля. Алгоритм бэктрекинга теперь можно реализовать на JavaScript следующим образом.

let ip = 0; // Позиция ввода.
let pc = 0; // Программный счетчик: индекс следующей инструкции.
const stack = []; // Стэк для бэктрекинга.
while (true) {
  const inst = code[pc];
  switch (inst.opcode) {
    case 'CONSUME':
      if (ip < input.length && input[ip] === inst.char) {
        // Ввод соответствует ожидаемому: продолжаем.
        ++ip;
        ++pc;
      } else if (stack.length > 0) {
        // Неправильный символ ввода, но можем откатиться.
        const back = stack.pop();
        ip = back.ip;
        pc = back.pc;
      } else {
        // Неправильный символ, откат невозможен.
        return false;
      }
      break;
    case 'FORK':
      // Сохраняем альтернативу для последующего бэктрекинга.
      stack.push({ip: ip, pc: inst.forkPc});
      ++pc;
      break;
    case 'JMP':
      pc = inst.jmpPc;
      break;
    case 'ACCEPT':
      return true;
  }
}

Эта реализация зацикливается бесконечно, если программа байткода содержит циклы, которые не потребляют никакой символ, то есть если автомат содержит цикл, состоящий только из переходов с эпсилон. Эту проблему можно решить с помощью предварительного анализа одного символа. Irregexp гораздо сложнее, чем эта простая реализация, но в конечном счете основан на том же алгоритме.

Алгоритм без бэктрекинга​

Алгоритм бэктрекинга соответствует поиску в глубину автомата: мы всегда полностью исследуем первую альтернативу инструкции FORK, а затем возвращаемся ко второй альтернативе, если это необходимо. Альтернативный подход — алгоритм без бэктрекинга, который, неудивительно, основан на поиске в ширину автомата. Здесь мы учитываем все альтернативы одновременно, в шагах, соответствующих текущей позиции в строке ввода. Таким образом, мы поддерживаем список текущих состояний, а затем продвигаем все состояния, совершая переходы, соответствующие каждому символу ввода. Важно, чтобы из списка текущих состояний удалялись дубли.

Простая реализация на JavaScript выглядит примерно так:

// Позиция ввода.
let ip = 0;
// Список текущих значений pc или `'ACCEPT'`, если был найден соответствующий элемент. Мы начинаем с
// pc 0 и следуем переходам с эпсилон.
let pcs = followEpsilons([0]);

while (true) {
  // Мы закончили, если был найден соответствующий элемент…
  if (pcs === 'ACCEPT') return true;
  // …или если мы исчерпали строку ввода.
  if (ip >= input.length) return false;

  // Продолжаем только с теми pc, которые CONSUME корректный символ.
  pcs = pcs.filter(pc => code[pc].char === input[ip]);
  // Продвигаем оставшиеся pc к следующей инструкции.
  pcs = pcs.map(pc => pc + 1);
  // Следуем переходам с эпсилон.
  pcs = followEpsilons(pcs);

  ++ip;
}

Здесь followEpsilons — это функция, которая принимает список программных счетчиков и вычисляет список программных счетчиков на инструкциях CONSUME, которые могут быть достигнуты через переходы с эпсилон (то есть только используя FORK и JMP). Возвращенный список не должен содержать дублей. Если можно достигнуть инструкции ACCEPT, функция возвращает 'ACCEPT'. Она может быть реализована так:

function followEpsilons(pcs) {
  // Набор pc, которые мы видели до сих пор.
  const visitedPcs = new Set();
  const result = [];

  while (pcs.length > 0) {
    const pc = pcs.pop();

    // Мы можем игнорировать pc, если видели его раньше.
    if (visitedPcs.has(pc)) continue;
    visitedPcs.add(pc);

    const inst = code[pc];
    switch (inst.opcode) {
      case 'CONSUME':
        result.push(pc);
        break;
      case 'FORK':
        pcs.push(pc + 1, inst.forkPc);
        break;
      case 'JMP':
        pcs.push(inst.jmpPc);
        break;
      case 'ACCEPT':
        return 'ACCEPT';
    }
  }

  return result;
}

Поскольку благодаря устранению дубликатов с помощью множества visitedPcs мы знаем, что каждый программный счетчик проверяется только один раз в followEpsilons. Это гарантирует, что список result не содержит дубликатов, а время выполнения followEpsilons ограничено размером массива code, то есть размером шаблона. followEpsilons вызывается максимум input.length раз, поэтому общее время выполнения сопоставления RegExp ограничено 𝒪(pattern.length * input.length).

Алгоритм без обратного отслеживания можно расширить для поддержки большинства функций JavaScript RegExp, например, границ слов или вычисления границ (под)совпадений. К сожалению, обратные ссылки, просмотр вперед и назад не могут быть поддержаны без серьезных изменений, которые изменяют асимптотическую сложность в худшем случае.

Новый механизм RegExp в V8 основан на этом алгоритме и его реализации в библиотеках re2 и Rust regex. Алгоритм обсуждается гораздо более подробно, чем здесь, в отличной серии блогов Русса Кокса, который также является оригинальным автором библиотеки re2.