Eine zusätzliche nicht-backtracking RegExp-Engine

Ab Version v8.8 wird V8 mit einer neuen experimentellen nicht-backtracking RegExp-Engine ausgeliefert (zusätzlich zur bestehenden Irregexp-Engine), die garantiert, dass die Ausführung in linearer Zeit in Bezug auf die Größe der Eingabestrings erfolgt. Die experimentelle Engine ist hinter den unten erwähnten Feature-Flags verfügbar.

So können Sie die neue RegExp-Engine konfigurieren:

• --enable-experimental-regexp_engine-on-excessive-backtracks aktiviert das Fallback zur nicht-backtracking Engine bei übermäßigem Backtracking.
• --regexp-backtracks-before-fallback N (Standard N = 50.000) gibt an, wie viele Backtracks als „übermäßig“ angesehen werden, d.h. wann das Fallback einsetzt.
• --enable-experimental-regexp-engine aktiviert die Erkennung des nicht-standardmäßigen Flags l („linear“) für RegExps, wie z.B. /(a*)*b/l. RegExps, die mit diesem Flag erstellt wurden, werden immer direkt mit der neuen Engine ausgeführt; Irregexp wird überhaupt nicht verwendet. Kann die neue RegExp-Engine das Muster eines l-RegExps nicht verarbeiten, wird beim Erstellen eine Ausnahme ausgelöst. Wir hoffen, dass diese Funktion irgendwann zur Härtung von Apps verwendet werden kann, die RegExps mit nicht vertrauenswürdigen Eingaben ausführen. Vorerst bleibt sie experimentell, da Irregexp bei den meisten gängigen Mustern um Größenordnungen schneller ist als die neue Engine.

Der Fallback-Mechanismus gilt nicht für alle Muster. Damit der Fallback-Mechanismus ausgelöst werden kann, muss der RegExp:

• keine Rückverweise enthalten,
• keine Vor- oder Rückwärtssuchen enthalten,
• keine großen oder tief verschachtelten endlichen Wiederholungen enthalten, wie z.B. /a{200,500}/, und
• die Flags u (Unicode) oder i (Unterschied beachtet Groß-/Kleinschreibung) dürfen nicht gesetzt sein.

Hintergrund: Katastrophales Backtracking

Die RegExp-Verarbeitung in V8 erfolgt durch die Irregexp-Engine. Irregexp JIT-kompiliert RegExps zu spezialisiertem nativen Code (oder Bytecode) und ist daher für die meisten Muster extrem schnell. Für einige Muster kann Irregexps Laufzeit jedoch exponentiell ansteigen, abhängig von der Größe der Eingabestrings. Im obigen Beispiel, /(a*)*b/.exec('a'.repeat(100)), wird die Ausführung durch Irregexp innerhalb unserer Lebenszeit nicht abgeschlossen.

Was geschieht hier also genau? Irregexp ist eine Backtracking-Engine. Bei einer Auswahl, wie ein Muster fortgesetzt werden kann, erkundet Irregexp zunächst die erste Alternative vollständig und backtracked dann bei Bedarf, um die zweite Alternative zu untersuchen. Betrachten Sie z. B. das Muster /abc|[az][by][0-9]/, das mit dem Eingabestring 'ab3' abgeglichen wird. Hier versucht Irregexp zunächst, /abc/ zu matchen und scheitert nach dem zweiten Zeichen. Es backtracked dann um zwei Zeichen zurück und matcht erfolgreich die zweite Alternative /[az][by][0-9]/. In Mustern mit Quantifizierern wie /(abc)*xyz/ muss Irregexp nach einem Treffer des Hauptteils entscheiden, ob der Hauptteil erneut gematcht oder das restliche Muster fortgesetzt werden soll.

Lassen Sie uns versuchen zu verstehen, was geschieht, wenn /(a*)*b/ mit einem kleineren Eingabestring wie 'aaa' abgeglichen wird. Dieses Muster enthält verschachtelte Quantifizierer, sodass wir Irregexp bitten, eine Sequenz von Sequenzen von 'a' zu matchen und dann 'b' zu matchen. Offensichtlich gibt es keinen Treffer, da der Eingabestring kein 'b' enthält. Jedoch matcht /(a*)*/, und dies in exponentiell vielen verschiedenen Wegen:

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

A priori kann Irregexp nicht ausschließen, dass das Scheitern beim Matchen des finalen /b/ daran liegt, dass die falsche Möglichkeit gewählt wurde, /(a*)*/ zu matchen, sodass es alle Varianten ausprobieren muss. Dieses Problem wird als „exponentielles“ oder „katastrophales“ Backtracking bezeichnet.

RegExps als Automaten und Bytecode

Um einen alternativen Algorithmus zu verstehen, der gegen katastrophales Backtracking immun ist, müssen wir einen kurzen Exkurs über Automaten machen. Jeder reguläre Ausdruck ist einem Automaten äquivalent. Der RegExp /(a*)*b/ oben entspricht z. B. dem folgenden Automaten:

Beachten Sie, dass der Automat nicht eindeutig durch das Muster bestimmt ist; der oben gezeigte ist der Automat, der durch einen mechanischen Übersetzungsprozess erzeugt wurde, und er ist derjenige, der in der neuen RegExp-Engine von V8 für /(a*)*/ verwendet wird. Die nicht gekennzeichneten Kanten sind Epsilon-Übergänge: Sie verbrauchen keine Eingabe. Epsilon-Übergänge sind notwendig, um die Größe des Automaten etwa in der Größe des Musters zu halten. Ein naives Eliminieren von Epsilon-Übergängen kann zu einer quadratischen Zunahme der Übergänge führen. Epsilon-Übergänge ermöglichen auch die Konstruktion des Automaten, der einer RegExp entspricht, aus den folgenden vier grundlegenden Typen von Zuständen:

Hier klassifizieren wir nur die Übergänge ausgehend vom Zustand, während die Übergänge in den Zustand weiterhin beliebig sein dürfen. Automaten, die nur aus diesen Arten von Zuständen bestehen, können als Bytecode-Programme dargestellt werden, wobei jeder Zustand einer Anweisung entspricht. Zum Beispiel wird ein Zustand mit zwei Epsilon-Übergängen als eine FORK-Anweisung dargestellt.

Der Backtracking-Algorithmus

Lassen Sie uns den Backtracking-Algorithmus, auf dem Irregexp basiert, noch einmal betrachten und in Bezug auf Automaten beschreiben. Angenommen, wir haben ein Bytecode-Array code, das dem Muster entspricht, und möchten testen, ob eine input-Zeichenkette mit dem Muster übereinstimmt. Angenommen, code sieht ungefähr so aus:

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'}
];

Dieser Bytecode entspricht dem (sticky) Muster /12|ab/y. Das forkPc-Feld der FORK-Anweisung ist der Index („Program Counter“) des alternativen Zustands/der alternativen Anweisung, bei der wir fortfahren können, und ähnlich verhält es sich bei jmpPc. Indizes sind nullbasiert. Der Backtracking-Algorithmus kann nun in JavaScript wie folgt implementiert werden.

let ip = 0; // Eingabeposition.
let pc = 0; // Program Counter: Index der nächsten Anweisung.
const stack = []; // Backtracking-Stack.
while (true) {
  const inst = code[pc];
  switch (inst.opcode) {
    case 'CONSUME':
      if (ip < input.length && input[ip] === inst.char) {
        // Die Eingabe stimmt überein: Weiter.
        ++ip;
        ++pc;
      } else if (stack.length > 0) {
        // Falsches Eingabezeichen, aber wir können zurückgehen.
        const back = stack.pop();
        ip = back.ip;
        pc = back.pc;
      } else {
        // Falsches Zeichen, kann nicht zurückgehen.
        return false;
      }
      break;
    case 'FORK':
      // Alternative für späteres Backtracking speichern.
      stack.push({ip: ip, pc: inst.forkPc});
      ++pc;
      break;
    case 'JMP':
      pc = inst.jmpPc;
      break;
    case 'ACCEPT':
      return true;
  }
}

Diese Implementierung läuft unendlich oft, wenn das Bytecode-Programm Schleifen enthält, die kein Zeichen verbrauchen, d.h. wenn der Automat eine Schleife enthält, die nur aus Epsilon-Übergängen besteht. Dieses Problem kann durch einen Lookahead mit einem einzelnen Zeichen gelöst werden. Irregexp ist weitaus ausgefeilter als diese einfache Implementierung, basiert jedoch letztendlich auf demselben Algorithmus.

Der Non-Backtracking-Algorithmus

Der Backtracking-Algorithmus entspricht der tiefenorientierten Traversierung des Automaten: Wir erkunden immer die erste Alternative einer FORK-Anweisung vollständig und gehen dann, falls erforderlich, zur zweiten Alternative zurück. Die Alternative dazu, der Non-Backtracking-Algorithmus, basiert daher wenig überraschend auf der breitenorientierten Traversierung des Automaten. Hier betrachten wir alle Alternativen gleichzeitig, im Gleichschritt in Bezug auf die aktuelle Position in der Eingabezeichenkette. Wir führen eine Liste der aktuellen Zustände und gehen dann mit jedem Eingabezeichen durch Übergänge zu allen Zuständen weiter. Wichtig ist, dass wir Duplikate aus der Liste der aktuellen Zustände entfernen.

Eine einfache Implementierung in JavaScript sieht etwa so aus:

// Eingabeposition.
let ip = 0;
// Liste der aktuellen pc-Werte oder `'ACCEPT'`, wenn wir eine Übereinstimmung gefunden haben. Wir starten bei
// pc 0 und folgen Epsilon-Übergängen.
let pcs = followEpsilons([0]);

while (true) {
  // Wir sind fertig, wenn wir eine Übereinstimmung gefunden haben...
  if (pcs === 'ACCEPT') return true;
  // ...oder wenn wir die Eingabezeichenkette erschöpft haben.
  if (ip >= input.length) return false;

  // Nur mit den pcs fortfahren, die das richtige Zeichen CONSUME.
  pcs = pcs.filter(pc => code[pc].char === input[ip]);
  // Die verbleibenden pcs zur nächsten Anweisung weiterleiten.
  pcs = pcs.map(pc => pc + 1);
  // Epsilon-Übergängen folgen.
  pcs = followEpsilons(pcs);

  ++ip;
}

Hier ist followEpsilons eine Funktion, die eine Liste von Programmcountern erhält und die Liste von Programmcountern bei CONSUME-Anweisungen berechnet, die über Epsilon-Übergänge erreicht werden können (d.h. nur durch Ausführen von FORK und JMP). Die zurückgegebene Liste darf keine Duplikate enthalten. Wenn eine ACCEPT-Anweisung erreicht werden kann, gibt die Funktion 'ACCEPT' zurück. Sie kann so implementiert werden:

function followEpsilons(pcs) {
  // Satz der pcs, die wir bisher gesehen haben.
  const visitedPcs = new Set();
  const result = [];

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

    // Wir können pc ignorieren, wenn wir es zuvor gesehen haben.
    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;
}

Aufgrund der Eliminierung von Duplikaten über die visitedPcs-Menge wissen wir, dass jeder Programmzähler in followEpsilons nur einmal untersucht wird. Dies garantiert, dass die result-Liste keine Duplikate enthält und dass die Laufzeit von followEpsilons durch die Größe des code-Arrays, d.h. die Größe des Musters, begrenzt ist. followEpsilons wird höchstens input.length-Mal aufgerufen, sodass die Gesamtlaufzeit des RegExp-Matchings durch 𝒪(pattern.length * input.length) begrenzt ist.

Der nicht-backtracking Algorithmus kann erweitert werden, um die meisten Funktionen von JavaScript-RegExps zu unterstützen, beispielsweise Wortgrenzen oder die Berechnung von (Unter-)Matchgrenzen. Leider können Rückverweise, Lookahead und Lookbehind ohne wesentliche Änderungen, die die asymptotische Worst-Case-Komplexität verändern, nicht unterstützt werden.

Die neue RegExp-Engine von V8 basiert auf diesem Algorithmus und seiner Implementierung in den re2- und Rust regex-Bibliotheken. Der Algorithmus wird in einer hervorragenden Blog-Serie von Russ Cox, der auch der ursprüngliche Autor der re2-Bibliothek ist, wesentlich ausführlicher als hier diskutiert.