Die Interna der Regex-Engine als Bibliothek

 (blog.burntsushi.net)
1 Punkte von GN⁺ 2023-07-06 | 1 Kommentare | Auf WhatsApp teilen
  • Das Rust-regex-Crate hat nach jahrelanger Neuschreibung große Teile seiner internen Engine als API des separat versionierten regex-automata-Crates offengelegt; der Übergang wurde mit regex 1.9 abgeschlossen
  • Ausgangspunkt der Neuschreibung waren die schwierige Kombinierbarkeit von Suchstrategien, die aufwendigen Tests einzelner interner Engines, der Bedarf an einer feineren Mehrmuster-API als RegexSet sowie die Notwendigkeit, vollständig kompilierte DFAs gemeinsam zu nutzen
  • regex-automata organisiert die Regex-Verarbeitung entlang des Flusses Ast → Hir → Literal-Extraktion/Prefilter → Thompson-NFA → PikeVM·BoundedBacktracker·one-pass DFA·DFA·lazy DFA → Meta-Engine
  • Die Performance wird dadurch erreicht, dass nach Möglichkeit zuerst Literal-Suche und DFA-basierte Engines verwendet werden; für Capture-Gruppen oder Sonderfälle ergänzen PikeVM, der bounded backtracker und die one-pass DFA das Verhalten
  • Die öffentliche API und wiederverwendbare Abstraktionen machten Tests und Experimente einfacher, erhöhten aber Codeumfang, Binärgröße und Compile-Zeit; vollständig kompilierte DFAs bleiben opt-in, und regex-lite kam als leichtgewichtige Alternative hinzu

Die Neuschreibung von regex und die Veröffentlichung von regex-automata

  • Das Rust-regex-Crate wurde über mehrere Jahre hinweg neu geschrieben, um die interne Komposition zu verbessern, Optimierungen leichter ergänzen zu können und dabei die Korrektheit zu bewahren
  • Dabei entstand regex-automata, das große Teile der internen Implementierung des regex-Crates über eine separate API zugänglich macht
  • regex-automata wird als erster Fall vorgestellt, in dem die Interna einer Regex-Bibliothek in diesem Umfang als separat versionierte Bibliothek offengelegt werden
  • regex 1.9 erschien am 5. Juli 2023 und schloss diese Neuschreibung ab
  • Zielgruppe sind Rust-Programmierer und Menschen, die sich für die Implementierung endlicher Automaten-basierter Regex-Engines interessieren; Regex-Erfahrung wird vorausgesetzt

Probleme vor der Neuschreibung

  • Das bisherige regex-Crate nutzte in der RE2-Tradition intern mehrere Suchstrategien, doch durch organisches Wachstum wurden die Strategien schwer kombinierbar
    • PikeVM wurde als erste Strategie entworfen und hatte nicht die nötige Behandlung für Start und Stopp der Teilslice-Suche, die für die Kombination mit der lazy DFA erforderlich war
    • Es war schwer nachzuvollziehen, welche Strategie für welche Regex verwendet wurde
    • Mehrere match-Ausdrücke implementierten dieselbe Logik wiederholt, wodurch sie leicht auseinanderliefen
    • Selbst bei Regexes, für die nur Aho-Corasick nötig war, konnte unnötig ein nicht verwendetes Thompson-NFA erzeugt werden
  • Auch das Testen der internen Engines war schwierig
    • Die öffentliche API wirkt wie eine einzelne Regex-Engine, intern gibt es jedoch mehrere Strategien, die auf derselben Eingabe identisch funktionieren müssen
    • Vor regex 1.9 waren die internen Strategien keine öffentliche API, sodass sich die einzelnen Engines nur schwer unabhängig testen ließen
    • Die bisherigen Tests hatten eine fast schon hackige Struktur, die auf dem Offenlegen interner APIs, undokumentierten From-Implementierungen, Makros und engine-spezifischen Testzielen beruhte
  • Auch mehrere Nischen-API-Anfragen ließen sich nur schwer in die bestehende API-Oberfläche einfügen
    • RegexSet sagt nur, ob irgendein Muster irgendwo im haystack passt, liefert aber weder Match-Offsets noch Offsets von Capture-Gruppen
    • Es wurde eine Funktion benötigt, um eine anchored Suche auszuführen, ohne ^ in das Muster einzubauen
    • Gefordert war auch die Möglichkeit, während der Suche direkt mutable scratch space ohne interne Synchronisation zu übergeben
    • Ebenso wurde angefragt, Regexes auf nicht zusammenhängenden haystacks wie Streams oder Ropes auszuführen
  • Durch die Offenlegung der Interna als separat versioniertes Crate ließ sich experimentelle API für Experten mit schnelleren Breaking-Change-Zyklen erproben, ohne die allgemeine regex-API unnötig zu verkomplizieren

Durch vollständig kompilierte DFAs entstandene Abstraktionsgrenzen

  • Die anfängliche Motivation für regex-automata war, vollständig kompilierte DFAs zu erzeugen und zu serialisieren, um anschließend eine minimale Laufzeitumgebung für die Suche per Zero-Copy-Deserialisierung bereitzustellen
  • Frühes regex-automata wurde zum Erzeugen von DFAs für die Unicode-Algorithmus-Implementierung von bstr verwendet
  • Beim Bau der DFAs zeigte sich, dass NFA-Datenstrukturen und Compiler ähnlich wie im regex-Crate nötig waren, und mit wachsender Komplexität dieses Codes stieg der Bedarf nach gemeinsamer Nutzung
  • Zunächst wurde ein separates Crate wie regex-nfa erwogen, aber es gab mehr Code – etwa den Determinisierungsprozess –, der zwischen regex und regex-automata geteilt werden konnte
  • Die passende Abstraktionsgrenze lag eher bei einer Regex-Engine als bei einem „NFA“, und schließlich wurde regex-automata als Sammlung mehrerer Engines neu definiert
  • Der langfristige Plan war, alle Regex-Engines in regex-automata unterzubringen und das regex-Crate zu einem dünnen Wrapper darüber zu machen

Interne Struktur mit regex-cli untersuchen

  • regex-cli ist ein im Repository des regex-Crates gepflegtes Programm, das Kommandozeilenzugriff auf verschiedene APIs von regex-syntax, regex-automata und regex bietet
  • Die Installation ist mit folgendem Befehl möglich
cargo install regex-cli
  • regex-cli debug kann AST, HIR, Literale, Thompson-NFA, one-pass DFA, dense DFA, sparse DFA usw. ausgeben
  • Die Regex . mit aktiviertem Unicode erzeugt ein deutlich komplexeres Thompson-NFA, um UTF-8-Scalar-Values zu verarbeiten, während (?-u:.) mit deaktiviertem Unicode ein einfacheres NFA erzeugt
  • Mit regex-cli find lassen sich Ad-hoc-Suchen ausführen; über die Meta-Engine sind auch Mehrmustersuche und die Ausgabe von Capture-Gruppen möglich

Datenfluss der Regex-Verarbeitung

  • Die an Regex::new übergebene Musterzeichenfolge wird zunächst zu Ast geparst
  • Ast wird in Hir umgewandelt
    • Hir enthält weniger Details als Ast; Unicode-Case-Folding und Verweise auf Unicode-Zeichenklassen werden während der Umwandlung expandiert
  • Aus Hir entstehen zwei Dinge
    • Literal-Sequenzen für Suchoptimierungen
    • ein Thompson-NFA
  • Das NFA bildet die Grundlage für mehrere Engines
    • PikeVM: verarbeitet alle parsbaren Regexes und meldet Capture-Gruppen-Offsets
    • BoundedBacktracker: meldet Capture-Gruppen-Offsets per bounded backtracking
    • one-pass DFA: meldet bei eingeschränkten Regexes Capture-Gruppen-Offsets schnell
    • dense DFA: sehr schnell, meldet aber nur Start und Ende des Gesamt-Matches; die Konstruktion kann im Worst Case O(2^m) Zeit und Speicher benötigen
    • lazy DFA: erzeugt die DFA während der Suche aus dem NFA, ist meist fast so schnell wie eine vollständige DFA und vermeidet die exponentiellen Konstruktionskosten der full DFA
  • Diese Engines und Prefilter werden zu einer einzigen Meta-Regex-Engine kombiniert; das regex-Crate ist ein dünner Wrapper um diese Meta-Engine

Literal-Optimierung

  • Die Extraktion von Literalen ist eine zentrale Optimierung innerhalb von regex
    • Zum Beispiel beginnt jeder Match von (foo|bar|quux)(\s+\w+) mit einem von foo, bar oder quux
  • Literale sind wichtig, weil Algorithmen zur Suche nach einer einzelnen oder wenigen Zeichenfolgen sehr schnell sind
    • Mit Vektor-Instruktionen lassen sich mehrere Bytes des Haystacks auf einmal verarbeiten
    • Allgemeine Regex-Matching-Algorithmen lassen sich auf dieselbe Weise nur schwer konsistent beschleunigen
  • Gut optimierte Substring-Suche war häufig mindestens um eine Größenordnung schneller als allgemeine Regex-Engines
  • Die Extraktion von Literalen ist heuristisch
    • Die False-Positive-Rate von Kandidaten-Matches muss gesenkt werden
    • Auch der Einfluss des Prefilters auf die Gesamtlatenz muss gering bleiben
    • Beide Bedingungen hängen vom Haystack ab, aber wenn man den Haystack vor der Suche analysiert, kann sich die gesamte Suchzeit verschlechtern
  • Eine Literal-Sequenz ist keine Menge, sondern eine geordnete Sequenz
    • Das regex-Crate folgt einer Perl-ähnlichen leftmost-first-Semantik, daher ist | nicht kommutativ
    • Aus sam|samwise kann nur sam extrahiert werden, bei samwise|sam werden jedoch beide berücksichtigt
  • Für die Suche nach einer einzelnen Zeichenfolge wird das Modul memmem aus dem Crate memchr verwendet
    • Der Hauptalgorithmus ist Two-Way mit O(n)-Laufzeit im Worst Case und konstantem Speicherbedarf
    • Für kurze Needle und Haystack wird Rabin-Karp verwendet
    • Auf x86_64 kommen generische SIMD-Varianten zum Einsatz
  • Für die Suche nach mehreren Zeichenfolgen ist Teddy, aus Hyperscan portiert, der wichtigste Algorithmus; in manchen Fällen wird auch Aho-Corasick verwendet

Thompson-NFA und Optimierungen

  • Die zentrale Datenstruktur im Inneren des regex-Crates ist ein Thompson-NFA
  • Thompsons Konstruktion erzeugt aus der strukturierten Darstellung eines regulären Ausdrucks in O(m) Zeit ein NFA, wobei m proportional zur Größe des regulären Ausdrucks nach der Erweiterung gezählter Wiederholungen ist
  • Das NFA kann direkt als Regex-Engine verwendet oder in andere Typen wie ein DFA umgewandelt werden und so als Grundlage für andere Engines dienen
  • Die wichtigste Optimierung des neuen NFA-Compilers konzentriert sich darauf, Epsilon-Transitionen zu reduzieren
    • Thompson-NFAs sind bei der Konstruktion günstig, verwenden aber viele Epsilon-Transitionen
    • Die Berechnung von Epsilon-Closures kann bei der Suche oder beim DFA-Aufbau wiederkehrende Kosten verursachen
  • Die sparse-State-Optimierung stellt mehrere Bereichsübergänge in einem Zustand dar und reduziert so die bisher nötigen mehreren Split-Instruktionen
    • Bei regulären Ausdrücken wie [A-Za-z0-9] entfernt sie unnötige Epsilon-Transitionen
    • In der aktuellen Darstellung kann es durch Indirektion Auswirkungen auf den Cache und mehr Heap-Speicherverbrauch geben
  • Die Optimierung des minimalen UTF-8-Automaten verkleinert die NFA-Größe bei großen Unicode-Klassen deutlich
    • Im früheren byte-orientierten NFA konnte \w 3.564 Zustände erzeugen
    • Der neue Compiler verwendet Daciuks Algorithmus, um eine Struktur mit deutlich weniger Zuständen und null Epsilon-Transitionen zu erzeugen
    • Das Shrinking des reverse NFA ist standardmäßig deaktiviert, weil es Compile-Time-Kosten verursacht
  • Die Literal-Trie-Optimierung kompiliert gemeinsame Strukturen bei Literal-Alternationen wie zap|z|zapper oder abc|xyz in einen Trie und reduziert dadurch Epsilon-Transitionen
    • Um die leftmost-first-Semantik zu bewahren, werden Transition-Chunks an jeder Stelle aufgeteilt, an der ein Match auftreten kann
  • Als künftige NFA-Arbeiten werden ein Glushkov-NFA und die Speicherung in einer einzelnen zusammenhängenden Allokation geprüft
    • Das Glushkov-NFA hat keine Epsilon-Transitionen, aber eine schlechtere Compile-Time-Komplexität
    • Eine zusammenhängende Allokation könnte Cache-Freundlichkeit und Zero-Copy-Serialisierung/-Deserialisierung ermöglichen, bringt aber möglicherweise mehr Code-Komplexität und den Einsatz von unsafe mit sich

Einzelne Regex-Engines

  • Die Engines von regex-automata teilen sich ähnliche APIs
    • Input: setzt Haystack, Suchbereich, ob anchored gesucht wird und ob früh gestoppt werden soll
    • Match: enthält den gematchten Byte-Span und die PatternID
    • MatchError: steht für Fehler, bei denen das Suchergebnis nicht bestimmt werden kann

  • PikeVM

    • Unterstützt den vollen Funktionsumfang, den regex-syntax parsen kann, und arbeitet mit Haystacks beliebiger Länge
    • Verfolgt die Positionen von Capture-Gruppen und berechnet aktive Zustände im Lock-Step-Verfahren, wodurch im Worst Case O(m * n) Laufzeit garantiert ist
    • Die Leistung ist die Hauptschwäche, weil viele Zustände und Positionen von Capture-Gruppen verfolgt werden müssen
    • Unter den Engines von regex-automata hat sie die einzigartige Eigenschaft, während der Suche keine Fehler zurückzugeben

  • BoundedBacktracker

    • Verwendet Backtracking auf einem Thompson-NFA, nutzt aber zusätzlichen Zustand, damit bereits geleistete Arbeit nicht erneut verfolgt wird
    • Garantiert im Worst Case O(m * n) Laufzeit, benötigt aber O(m * n) Speicher
    • In groben Experimenten ist er typischerweise etwa 2x schneller als PikeVM
    • Kann fehlschlagen, wenn Haystack-Länge und Regex-Größe die konfigurierte visited capacity überschreiten

  • one-pass DFA

    • Meldet Capture-Gruppen-Offsets auf einem eingeschränkten one-pass-NFA sehr schnell
    • Gilt als schnellste Methode, um Capture-Gruppen zu melden
    • Unterstützt nur anchored Search, und viele reguläre Ausdrücke sind nicht one-pass
    • Im Unicode-Modus können reguläre Ausdrücke wegen überlappender Transitionen auf Byte-Ebene nicht one-pass sein; ohne Unicode können sie one-pass werden

  • fully compiled DFA

    • Besteht aus zwei DFAs, einem vorwärts laufenden und einem rückwärts laufenden DFA, um Ende und Anfang eines vollständigen Matches zu finden
    • Der Aufbau hat im Worst Case O(2^m) Zeit- und Speicheraufwand, und ein dichtes DFA benötigt viel Speicher
    • Die Full-DFA-Engine ist im regex-Crate standardmäßig deaktiviert und muss über das Feature perf-dfa-full explizit aktiviert werden
    • Arbeitet ohne veränderbaren Cache, lässt sich als rohe Bytes serialisieren und kann die Such-Laufzeit auch in Umgebungen nutzen, in denen nur core verfügbar ist

  • hybrides NFA/DFA, lazy DFA

    • Ähnelt einem Full DFA, baut die Transition-Tabelle aber erst während der Suche auf
    • Wenn eine bereits berechnete Transition im Cache liegt, wird sie wiederverwendet; andernfalls wird genau diese Transition per NFA-Powerset-Konstruktion berechnet
    • Die Suchzeit beträgt im Worst Case O(m * n), der Speicher ist durch die beim Aufbau festgelegte Cache-Kapazität begrenzt
    • Im Normalfall werden die meisten Zustände und Transitionen gecacht, sodass sich im Mittel ein Verhalten wie O(n) ergibt; in der Praxis zeigt sich bei vielen regulären Ausdrücken eine ähnliche Suchleistung wie beim Full DFA
    • Wenn sich der Cache wiederholt füllt und dadurch ineffizient wird, wird ein Fehler zurückgegeben; in der Meta-Engine wird dann meist mit einer anderen Engine erneut versucht

Die Rolle der meta regex engine

  • meta regex engine bündelt mehrere Engines in einer und soll dem Aufrufer eine infallible API bieten
  • Der Aufrufer muss nicht für jede Suche selbst ein Cache erzeugen und übergeben
    • Die Meta-Engine verwaltet intern einen thread-sicheren Cache-Pool
    • Um Synchronisierungskosten zu vermeiden, stellt sie auch eine Lower-Level-API bereit, an die man explizit ein Cache übergeben kann
  • regex::Regex, regex::RegexSet, regex::bytes::Regex, regex::bytes::RegexSet sind allesamt dünne Wrapper um die Meta-Engine
  • Die interne Strategie der Meta-Engine sieht grob so aus
    • Wenn sich etwas allein mit einer einzelnen oder mehreren Substring-Suchen ohne Regex-Engine erledigen lässt, wird sogar der Aufbau einer NFA vermieden
    • Wenn möglich, werden Prefix-Literalsequenzen extrahiert und als Prefilter verwendet
    • Wenn ein Prefix ungeeignet ist, werden Optimierungen wie reverse anchored, reverse suffix und reverse inner versucht
    • Andernfalls erfolgt ein Fallback auf die Kernstrategie mit PikeVM, bounded backtracker, one-pass DFA, lazy DFA und full DFA
  • Die Gesamtstrategie lässt sich auf zwei Sätze verdichten
    • So weit wie möglich nach Literalen suchen
    • Den Einsatz von PikeVM nach Möglichkeit vermeiden
  • Die Optimierungen reverse suffix und reverse inner können im schlimmsten Fall in Bezug auf die Größe des Haystacks zu O(m * n^2) führen
    • Die Meta-Engine erkennt Situationen, in denen ein Reverse-Scan über das Ende eines vorherigen Suffix-Matches hinauslaufen würde, und fällt auf die Kernstrategie zurück, um die Garantien für die Zeitkomplexität zu bewahren

Unterschiede zu RE2

  • Die regex-Crate und RE2 haben viele Gemeinsamkeiten
    • Auch RE2 hat eine NFA entsprechend der PikeVM, einen bitstate backtracker, eine one-pass NFA, eine lazy DFA und eine Struktur, die mehrere Engines kombiniert
    • Von den oben genannten Engines fehlt in RE2 nur die fully compiled DFA
  • Die wichtigsten Unterschiede sind folgende
    • RE2 unterstützt optional neben leftmost-first auch eine POSIX-artige leftmost-longest-Semantik
    • Die Unicode-Unterstützung von RE2 ist stärker eingeschränkt, und es gibt keine Option, \w, \s, \d, \b mit Unicode-Definitionen zu verwenden
    • RE2 unterstützt bei Character-Class-Set-Operationen abgesehen von Union nur eingeschränkt weitere Operationen
    • Die PikeVM von RE2 ist möglicherweise speichereffizienter
    • Die Literal-Optimierungen von RE2 sind begrenzt, während die regex-Crate mehr Literal-Optimierungen durchführt
    • Die lazy DFA von RE2 erfordert Synchronisierung, weil mehrere Threads denselben Transition-Cache teilen, während die regex-Crate getrennte Caches pro Thread verlangt und dadurch mehr Speicher verbraucht
    • Die regex-Crate veröffentlicht regex-syntax und regex-automata als Bibliotheken mit eigener Versionierung, RE2 unterstützt das nicht
    • regex-automata unterstützt first-class Multi-Pattern-Regexe in allen Engines und kann außerdem Matches und Capture-Group-Offsets für jedes passende Pattern melden

Teststrategie und Benchmarks

  • Die neue Teststrategie besteht darin, die internen Engines zu eigenständigen first-class APIs zu machen und jede Engine direkt zu testen
  • Alle Regex-Tests werden in TOML-Dateien beschrieben
  • Die Crate regex-test liest die TOML-Tests ein und wandelt sie in strukturierte Repräsentationen um
  • Für jede Engine-Konfiguration gibt es einen Rust-Unit-Test, der alle auf diese Engine anwendbaren TOML-Tests ausführt
  • Da das Rust-Unit-Test-Framework nicht erweiterbar ist, wurde eine eigene Infrastruktur mit Environment-Variablen zum Filtern bestimmter Tests hinzugefügt
  • Allein in regex-automata gibt es mehr als 450 Documentation-Tests
  • Bei den Vorbereitungen für regex 1.9 kamen auch viele Fuzz-Testing-Targets hinzu, und mit Hilfe von Addison Crump wurden einige Bugs gefunden
  • Benchmarks werden als Regex-Barometer rebar veröffentlicht
    • rebar benchmarkt nicht nur die regex-Crate, sondern auch mehrere andere Regex-Engines
    • Über 242 Benchmarks hinweg ist regex 1.9 bei der Suchzeit im Durchschnitt 1,5-mal schneller als regex 1.7.3
    • Die Zeit zum Erstellen von Regexen hat sich etwas verschlechtert
    • 1.8 war ein Transition-Release mit einigen Umstellungsarbeiten, daher wurde 1.7 als Vergleichsbasis verwendet

Kosten und leichtgewichtige Alternative

  • Für die Neuschreibung wurde in den vergangenen Jahren der Großteil der Freizeit des Autors aufgewendet, und Projekte wie ripgrep konnten eine Zeit lang nicht veröffentlicht werden
  • Wiederverwendbare öffentliche Abstraktionen führen tendenziell zu mehr Code als rein interne Abstraktionen
    • Dadurch steigen letztlich Binärgröße und Kompilierzeit
  • Da die interne Engine-API als separat versionierte Bibliothek veröffentlicht wurde, erfordert ein API-Break eine passende Breaking-Change-Release von regex-automata
  • Um die Kosten abzumildern, wurden zwei Maßnahmen umgesetzt
    • Die fully compiled DFA engine ist standardmäßig deaktiviert und als opt-in Feature verfügbar
    • regex-lite wurde als neue Crate veröffentlicht
  • regex-lite zielt darauf ab, nahezu ein Drop-in-Replacement für die regex-Crate zu sein, konzentriert sich aber auf die Optimierung von Binärgröße und Kompilierzeit
    • Dabei wird auf Funktionen im Bereich Unicode und Performance verzichtet
    • Die Garantie der Zeitkomplexität O(m * n) bleibt erhalten
    • Es hat 0 Abhängigkeiten, enthält einen eigenen Regex-Parser und teilt keinen Code mit der regex-Crate
  • regex-lite ist noch eine experimentelle Maßnahme, zeigt aber, dass man selbst durch das Abschalten von Optimierungen und Unicode-Funktionen per Feature in der regex-Crate nur schwer an Binärgröße und Kompilierzeit von regex-lite herankommt

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2023-07-06
Hacker-News-Kommentare

  • Ich habe es nur grob überflogen, aber die Rust-regex-Crate ist wirklich beeindruckend
    BurntSushi hat viele großartige Dinge gebaut, aber die regex-Crate von Rust ist legendär, und dass das Rust-Ökosystem schon seit Langem eine performante und leicht nutzbare Regex-Bibliothek hat, ist ein großer Segen für die Community
    Auch Russ Cox’ Artikelserie über reguläre Ausdrücke ist hervorragend; ich habe sie im Sommer als Referenz benutzt, als ich eine Regex-Engine gebaut habe, zu einer Zeit, als sich Regex wie der perfekte Schnittpunkt von Theorie und Praxis anfühlte
    Die tiefergehenden Änderungen beim Testen in diesem Artikel sind ebenfalls interessant, und da es sich um eine zentrale Crate im Ökosystem handelt, bin ich dankbar für diese Erklärung zu einem so tiefen Thema
    Regex ist manchmal schwer zu lesen und wird etwa für die E-Mail-Validierung missbraucht, aber in fast jeder Sprache ist es eines der dichtesten Werkzeuge überhaupt
    Als Praxisbuch kenne ich im Wesentlichen nur Jeffrey Friedls Mastering Regular Expressions, und auf der Theorieseite behandeln Compiler-Bücher das Thema; auch das Dragon Book war aus Implementierungssicht brauchbar. Ich würde gern weitere Buchempfehlungen zu Regex hören

    • https://www.cs.princeton.edu/courses/archive/fall19/cos226/l... und https://kean.blog/post/lets-build-regex sind hervorragende Einstiege in die Implementierung vereinfachter Regex-Engines
      Dabei baut man für Regex einen nichtdeterministischen endlichen Automaten und durchsucht den daraus entstehenden gerichteten Graphen; wenn ein Knoten erreichbar ist, der einem Endzustand entspricht, gilt das als Match
      Wer Regex benutzt, kann durch diese Übung verstehen, dass darin weit weniger Magie steckt als gedacht, und wenn man sich Bälle vorstellt, die auf einem NFA herumhüpfen, bekommen auch die katastrophalen Backtracking-Bugs, denen man in der Praxis irgendwann begegnet, eine physische Bedeutung
      Im Zusammenhang mit dem Originaltext liefert außerdem der letzte Kommentar von BurntSushi unter https://github.com/rust-lang/regex/issues/822 nützlichen Kontext zum Abschnitt über Nischen-APIs https://blog.burntsushi.net/regex-internals/#problem-request.... Mehrere Regex gleichzeitig in einem Text zu suchen ist sehr komplex, aber auch sehr nützlich, daher bin ich gespannt, was die Community mit diesem Muster bauen wird
    • Ein klassischer Fall, in dem Regex bei parserähnlichen Aufgaben glänzt, ist der Umgang mit Formaten mit unterschiedlichen Trennzeichen
      Zum Beispiel bei Formaten mit fester Feldanzahl wie header:field1,field2,field3\"data\"hash oder bei Formaten wie suite~split/test1,test2@opt1:opt2^hw1^hw2#flags1#flags2, bei denen die meisten Elemente optional sind, reichen einfache Werkzeuge wie split nicht aus und Regex passt gut
      Das ist auch der Grund, warum Regex schnell schwer lesbar wird. In einem einzigen Regex vermischen sich die Trennzeichen zwischen Feldern, die Gültigkeit jedes Felds und die Frage, welche Felder optional sind
      Eigentlich sind das drei getrennte Anliegen, aber die meisten Regex-APIs erlauben nicht, sie schrittweise zu trennen, sondern nehmen nur einen einzigen zusammengesetzten String entgegen
    • Ich frage mich, ob diese RegEx-Bibliothek wie die meisten JavaScript-Implementierungen JIT verwendet. Falls nicht, könnte das ein Fall sein, in dem JavaScript Rust schlägt
    • Ich habe diesen Artikel kürzlich beim Arbeiten mit RegEx etwas überflogen, und da die verwendete Sprache im Gegensatz zu anderen Engines offenbar keine Fehler zurückgab, scheint sie PikeVM zu verwenden
      Wegen Einschränkungen der Sprache und des urheberrechtlich geschützten Status mussten wir RegEx-Funktionalität selbst neu bauen, und Regex fühlt sich manchmal wirklich wie Voodoo an
      Ich weiß nicht, wie häufig andere Engines verwendet werden, aber wenn viele Programmiersprachen PikeVM nutzen, kann ich verstehen, warum Google ein eigenes OS für Server gebaut und in bestimmten Situationen schnellere Engines eingesetzt hat, um auch nur ein paar Taktzyklen zu sparen
      Ich weiß nur zu gut, dass Pattern-Matching deutlich langsamer werden kann, wenn man dem Suchstring nur ein paar Zeichen hinzufügt. Das Sprichwort „Wer den Pfennig nicht ehrt, ist des Talers nicht wert“ passt auch gut auf RegEx und Taktzyklen, und wenn man an Gespräche aus den 90ern zurückdenkt, in denen es um Hunderttausende von Datensätzen pro Sekunde ging, hat das wohl einige Coder sehr reich gemacht
    • Mein größter Ärger sind die kleinen Unterschiede zwischen Regex-Dialekten
      Vor allem unterscheiden sich je nach Dialekt und Kontext die Behandlung von Anführungszeichen oder die Art, wie ein Ausdruck beendet wird, so stark, dass ich aufgegeben habe, mir das merken zu wollen, und stattdessen jedes Mal nach Beispielen suche, wenn ich es brauche

  • Bei ActiveState bekam ich zusammen mit einem Kollegen, der gerade erst die Schule abgeschlossen hatte, die Aufgabe, einen Regex-Debugger für den Komodo-Editor zu bauen
    Wir stellten den legendären Perl-Experten Mark Jason Dominus ein, damit er Hooks in die Perl-Regex-Engine einbaute, und haben diese Hooks dann in der UI sichtbar gemacht, sodass Nutzer die Ausführung eines Regex Schritt für Schritt verfolgen konnten
    Heute sind Web-Tools besser, aber 2001 war der Rx Debugger von Komodo hochmodern, und die Arbeit daran hat großen Spaß gemacht

    • Früher hatte ich einmal Bedarf an einem Offline-Regex-Debugger
      Ich arbeitete mit einem Air-Gap-Netzwerk, sodass die Leute, die das Tool nutzen mussten, keinen Zugriff auf Online-Seiten hatten, und bei keinem Entwurf wäre es auch nur ansatzweise akzeptabel gewesen, Arbeitsdaten in ein Online-Tool einzugeben
      Trotzdem konzentriert sich der Großteil der Bemühungen auf Online-Tools, und Offline-Tools sind im Vergleich zu etwas wie https://regex101.com/ selten und schwach vertreten
    • Ich würde gern konkrete Empfehlungen für Web-Tools hören, die sich für diesen Zweck eignen

  • Ich frage mich, ob sich das auch auf Listen statt auf Strings anwenden lässt
    Es gibt mächtige Werkzeuge zum Durchsuchen und Verändern von Zeichenlisten, aber sobald es um Listen von Zahlen oder Datumswerten geht, verschwindet all das, und das fand ich schon immer frustrierend
    Wenn ich zum Beispiel in einer Liste von Login-Versuchsdaten alle Sequenzen finden will, bei denen nach mindestens 5 Fehlschlägen ein Erfolg kommt, wäre das mit einem regulären Ausdruck einfach, in der Praxis muss man aber direkt Schleifen, Flags und temporäre Listen bauen
    Man könnte die Liste in einen String umwandeln, verarbeiten und dann wieder zurückwandeln, aber die Nachteile liegen auf der Hand. Auch wenn es nicht so schnell wäre wie stringbasierte reguläre Ausdrücke, verstehe ich nicht, warum es keinen regulären Ausdruck für beliebige Listentypen geben sollte
    Ich habe auch einen alten Python-Prototypen wiedergefunden, den ich gebaut hatte: https://github.com/boppreh/listregex
    Er ist sehr langsam, aber für API-Experimente zufriedenstellend und bietet außerdem Werkzeuge, die reguläre Ausdrücke nicht haben, etwa Musterinvertierung, Schnittmenge und Paarabgleich

    • Nein. Diese Regex-Bibliothek ist stark an die Stringsuche gekoppelt, und das ist eine absichtliche Designentscheidung
      So eine Regex-Engine von Anfang an mit einem generischen Alphabet auszustatten, ist von Beginn an kaum realistisch. Vor allem ist es praktisch zu schwierig, das so umzusetzen, dass weder das API-Design noch die Performance für die Hauptanwendungsfälle leiden
      So eine Regex-Engine ohne Performance-Ansprüche zu bauen, ist nicht besonders schwer. Du könntest zum Beispiel die veröffentlichte regex-lite-Crate nehmen und sie so generisch umbauen, wie du willst, und würdest dabei auf einige interessante Hürden stoßen
      Ganz ohne Beispiele ist das auch nicht. Leute haben versucht, so etwas zu bauen[1]. Sie überschätzen dabei aber meist den allgemeinen Nutzen etwas, deshalb scheint es normalerweise keine große traction zu bekommen :-)
      [1]: https://docs.rs/automata/latest/automata/trait.Alphabet.html
    • Die C++-Standardbibliothek versucht so etwas mit std::basic_regex, das eine Template-Klasse für benutzerdefinierte Zeichentypen bereitstellt: https://en.cppreference.com/w/cpp/regex/basic_regex
      Man kann eine Trait-Klasse bereitstellen, die das für benutzerdefinierte „Zeichen“ nötige Verhalten definiert
      Die Performance fällt dabei aber stark ab, und vermutlich funktioniert es ungefähr so gut, wie beliebige Nicht-Zeichen-Objekte in einen benutzerdefinierten std::basic_string zu stecken
    • Irgendwie müsste man ein API definieren, das auf einem Sliding Window von Werten matcht
      Unmöglich ist das nicht, aber die meisten Sprachen haben dafür keine gute Schnittstelle

  • Ich nutze Ripgrep jeden Tag, wenn ich in Code oder Textdateien nach etwas suche, und bin jedes Mal dankbar, egal ob unter Windows, Linux, Mac, VSCode oder Vim
    Es ist eine der Softwares, die mein Leben und meine Arbeitsweise verändert haben
    Wenn ich mich gezwungen sehe, grep zu benutzen, fühlt es sich an, als wäre ich wieder in einer Zeit, in der alles auf einer Single-Core-CPU lief und die Daten auf langsamen rotierenden PATA-/IDE-Festplatten lagen
    BurntSushi verdient unter großartigen Programmierern weit mehr Anerkennung

    • ripgrep hat eine Abstammungslinie. Davor gab es ag, davor ack, und alle wollten eine viel bessere Schnittstelle als simples grep bieten

  • Ich musste für ein Arbeitsproblem ein RegexSet mit mehr als 10 Millionen sehr langen regulären Ausdrücken bauen
    Keine Engine kam im Auslieferungszustand damit zurecht, und auch Rusts RegexSet reichte mit den Standardeinstellungen nicht aus
    Trotzdem war die Arbeit mit regex-automata und regex-syntax sowie das Lesen des Codes schon 2018 extrem lehrreich
    Das Arbeitsprojekt orientierte sich am Ende am Lucene-API, war aber erst möglich, nachdem ich die Grundlagen aus den Regex-Crates gelernt hatte

    • 10 Millionen reguläre Ausdrücke sind eine enorme Größenordnung. Selbst Aho-Corasick kommt mit 10 Millionen Literalen gerade noch so zurecht
      Die künftige Arbeit besteht darin, Regex-Engines so zu verbessern, dass sie bei mehr Mustern besser skalieren. Im Moment würden sie lange vor 10 Millionen Regexes zusammenbrechen, und ich bin mir nicht sicher, ob dieses Ziel überhaupt realistisch erreichbar ist
      Trotzdem kann es definitiv besser werden als heute
      Natürlich ist Hyperscan bei der Suche nach mehreren Mustern de facto der Goldstandard. Ich weiß allerdings nicht, wie gut es mit 10 Millionen Mustern umgehen würde
    • Da du von Anfang an nicht ins Detail gegangen bist, vermute ich, die Antwort ist „nein“, aber falls es möglich ist, würde mich interessieren, ob du mehr über das Problem oder Projekt sagen kannst

  • Ich habe vor einiger Zeit mit der regex-automata-Crate experimentiert, und sie war die einzige Bibliothek, die sich für einen Texteditor eignete, weil man direkten Zugriff auf die internen DFAs bekam
    Normale Regex-Bibliotheks-APIs erwarten, dass die Eingabe ein einzelner zusammenhängender String ist, aber auf diese Weise ist es mit jeder beliebigen Textdatenstruktur kompatibel

  • Dieser Beitrag erschien genau zu der Zeit, als ich Code mit der regex-automata-Crate schrieb, und zwar noch mit der frühen Version 0.2.0
    Es scheint Zeit zu sein zu prüfen, ob ich mich wieder in die neue interne Struktur einarbeiten muss
    Den Artikel habe ich noch nicht gelesen, aber er wirkt sehr interessant und das Timing ist bemerkenswert gut
    Ein paar Minuten später sah es so aus, als wäre die Antwort eher „möglicherweise“, aber da es ein offizielles Release ist, könnte es den Code sogar deutlich vereinfachen
    Noch etwa 10 Minuten später war es ziemlich painless, und die neue Methode Builder::patch war ein vollständiges Upgrade
    PS: Ich bin in all deinen GitHub-Repositories immer noch blockiert, und angesichts der weiten Verbreitung vieler deiner Crates finde ich das etwas unfair. Ich erinnere mich nicht mehr an den ursprünglichen Vorfall. Die Regex-Crates selbst scheinen inzwischen unter der Organisation rust-lang zu liegen, aber es gibt weiterhin Dinge, mit denen ich nicht interagieren kann

    • In der Dokumentation zu regex-automata 0.2.0 gab es dazu einen deutlichen Warnhinweis, und es wurde dringend empfohlen, 0.1 zu verwenden: https://docs.rs/regex-automata/0.2.0/regex_automata/
      Ich erinnere mich auch nicht mehr an den ursprünglichen Vorfall. Ich blockiere viele Leute aus verschiedenen Gründen, aber ich habe die Blockierung jetzt aufgehoben

  • BioJulia hat Automa.jl veröffentlicht, eine reine Julia-Regex-Engine, die es ermöglicht, zur Compile-Zeit beliebigen Julia-Code einzufügen.
    Ich will nicht kleinreden, dass Rusts regex deutlich fortschrittlicher ist als Automa, aber ich finde es schwer, der Formulierung zuzustimmen, dies sei das erste Beispiel dafür, das Innere einer Regex-Engine als Bibliothek offenzulegen.

    • Das klingt für mich nach zwei verschiedenen Dingen.
      Zum Beispiel unterstützt PCRE2 „callouts“, was ähnlich klingt wie das, worüber gesprochen wird: https://www.pcre.org/current/doc/html/pcre2callout.html
      Auch Dinge wie ragel oder re2c machen schon seit Längerem Ähnliches.
      Worum es in diesem Blog geht, ist, das Innere der Regex-Bibliothek selbst herauszulösen, als separat versionierte Bibliothek bereitzustellen und anderen zu ermöglichen, diese Bausteine zu kombinieren.
      Bei Backtracking-Engines ist dieser Ansatz meist weniger naheliegend, weil die Engine in der Regel nur einen einzigen Backtracker hat, aber bei Automaten-basierten Bibliotheken werden oft mehrere Engines auf verschiedene Weise kombiniert.
      Trotzdem könnten auch Backtracking-Engines Dinge wie den Regex-Parser oder den AST offenlegen, die sie in der Praxis normalerweise nicht freigeben.