Les entrailles d’un moteur d’expressions régulières sous forme de bibliothèque

 (blog.burntsushi.net)
1 points par GN⁺ 2023-07-06 | 1 commentaires | Partager sur WhatsApp
  • Après plusieurs années de réécriture, le crate Rust regex a exposé une grande partie de son moteur interne via l’API du crate regex-automata, versionné séparément, et la transition a été achevée avec regex 1.9
  • Cette réécriture est partie de la difficulté à combiner les stratégies de recherche, de la complexité des tests par moteur interne, du besoin d’une API multi-motifs plus fine que RegexSet, et de la nécessité de partager des DFA entièrement compilés
  • regex-automata organise le traitement des expressions régulières selon le flux Ast → Hir → extraction de littéraux/Prefilter → NFA de Thompson → PikeVM·BoundedBacktracker·DFA one-pass·DFA·DFA lazy → meta engine
  • Les performances sont obtenues en privilégiant autant que possible la recherche de littéraux et les moteurs de la famille DFA, puis en complétant avec PikeVM, un bounded backtracker ou un DFA one-pass pour les groupes de capture et les cas particuliers
  • L’API publique et les abstractions réutilisables ont facilité les tests et l’expérimentation, mais ont augmenté le volume de code, la taille des binaires et les temps de compilation ; les DFA entièrement compilés restent opt-in, tandis que regex-lite a été ajouté comme alternative légère

Réécriture de regex et ouverture de regex-automata

  • Le crate regex de Rust a été réécrit pendant plusieurs années afin d’améliorer la composition interne, de faciliter l’ajout d’optimisations et de préserver la correction
  • Ce travail a donné naissance à regex-automata, qui expose via une API séparée une grande partie de l’implémentation interne du crate regex
  • regex-automata est présenté comme le premier cas où les entrailles d’une bibliothèque d’expressions régulières sont publiées à ce niveau sous forme de bibliothèque versionnée séparément
  • regex 1.9 est sorti le 5 juillet 2023 et a finalisé cette réécriture
  • Le projet s’adresse aux programmeurs Rust et aux personnes intéressées par l’implémentation de moteurs d’expressions régulières fondés sur des automates finis, et suppose une expérience préalable des expressions régulières

Les problèmes avant la réécriture

  • L’ancien crate regex utilisait en interne plusieurs stratégies de recherche dans la tradition de RE2, mais ces stratégies ayant été ajoutées progressivement, leur combinaison était devenue difficile
    • PikeVM, conçu comme première stratégie, ne gérait pas suffisamment le démarrage et l’arrêt de recherches sur des sous-tranches, nécessaires lorsqu’il était combiné avec un DFA lazy
    • Il était difficile de déduire quelle stratégie était utilisée pour une expression régulière donnée
    • Plusieurs expressions match réimplémentaient la même logique, ce qui rendait les désynchronisations faciles
    • Même pour des expressions régulières où Aho-Corasick aurait suffi, un NFA de Thompson inutilisé pouvait être construit inutilement
  • Les tests des moteurs internes étaient eux aussi délicats
    • L’API publique donne l’impression d’un seul moteur d’expressions régulières, mais plusieurs stratégies existent en interne et doivent se comporter de manière identique sur les mêmes entrées
    • Avant regex 1.9, les stratégies internes ne faisaient pas partie de l’API publique, ce qui rendait difficile le test indépendant de chaque moteur
    • Les tests existants reposaient sur une structure proche du bricolage : exposition d’API internes, implémentations From non documentées, macros et cibles de test propres à chaque moteur
  • Plusieurs demandes d’API de niche s’intégraient mal à la surface de l’API existante
    • RegexSet indique seulement quels motifs correspondent quelque part dans le haystack, sans fournir les offsets de correspondance ni ceux des groupes de capture
    • Il fallait pouvoir exécuter une recherche anchored sans ajouter ^ au motif
    • Il était demandé de pouvoir passer directement un scratch space mutable sans synchronisation interne pendant la recherche
    • Des demandes concernaient aussi l’exécution d’expressions régulières sur des haystacks non contigus, comme des flux ou des ropes
  • Exposer les composants internes dans un crate versionné séparément permet d’expérimenter des API expertes avec un rythme de breaking changes plus rapide, sans compliquer l’API généraliste de regex

La frontière d’abstraction imposée par les DFA entièrement compilés

  • La motivation initiale de regex-automata était de fournir un runtime minimal capable de créer et sérialiser des DFA entièrement compilés, puis de rechercher via une désérialisation zero-copy
  • La première version de regex-automata a été utilisée pour créer les DFA servant à l’implémentation des algorithmes Unicode de bstr
  • En construisant les DFA, il est apparu qu’une structure de données NFA et un compilateur similaires à ceux du crate regex étaient nécessaires ; à mesure que ce code se complexifiait, le besoin de le partager a grandi
  • Au départ, un crate séparé comme regex-nfa a été envisagé, mais davantage de code, notamment le processus de déterminisation, pouvait être partagé entre regex et regex-automata
  • La frontière d’abstraction relevait davantage du moteur d’expressions régulières que du simple « NFA », et regex-automata a finalement été redéfini comme un ensemble de plusieurs moteurs
  • Le plan à long terme était de placer tous les moteurs d’expressions régulières dans regex-automata et de faire du crate regex un mince wrapper par-dessus

Inspecter la structure interne avec regex-cli

  • regex-cli est un programme maintenu dans le dépôt du crate regex ; il fournit un accès en ligne de commande à plusieurs API de regex-syntax, regex-automata et regex
  • Il peut être installé avec la commande suivante
cargo install regex-cli
  • regex-cli debug peut afficher l’AST, le HIR, les littéraux, le NFA de Thompson, le DFA one-pass, le DFA dense, le DFA sparse, etc.
  • L’expression régulière . avec Unicode activé crée un NFA de Thompson bien plus complexe afin de traiter les scalar values UTF-8, tandis que (?-u:.), avec Unicode désactivé, produit un NFA plus simple
  • regex-cli find permet d’exécuter des recherches ponctuelles, et le meta engine peut aussi effectuer des recherches multi-motifs et afficher les groupes de capture

Flux de données du traitement des expressions régulières

  • La chaîne de motif passée à Regex::new est d’abord analysée en Ast
  • Ast est converti en Hir
    • Hir contient moins de détails que Ast, et le case folding Unicode ainsi que les références aux classes de caractères Unicode sont développés pendant la conversion
  • Deux éléments sont produits à partir de Hir
    • des séquences de littéraux utilisées pour optimiser la recherche
    • un NFA de Thompson
  • Le NFA sert de base à la construction de plusieurs moteurs
    • PikeVM : traite toutes les expressions régulières analysables et indique les offsets des groupes de capture
    • BoundedBacktracker : indique les offsets des groupes de capture via du backtracking borné
    • DFA one-pass : indique rapidement les offsets des groupes de capture pour un sous-ensemble limité d’expressions régulières
    • DFA dense : très rapide, mais ne rapporte que le début et la fin de la correspondance complète ; sa construction requiert dans le pire cas O(2^m) en temps et en espace
    • DFA lazy : construit un DFA à partir du NFA pendant la recherche ; il est généralement aussi rapide qu’un full DFA tout en évitant le coût exponentiel de construction d’un full DFA
  • Ces moteurs et le Prefilter sont combinés en un meta regex engine, et le crate regex n’est qu’un mince wrapper autour de ce meta engine

Optimisation des littéraux

  • L’extraction de littéraux est une optimisation centrale au sein de regex
    • Par exemple, toutes les correspondances de (foo|bar|quux)(\s+\w+) commencent par l’un de foo, bar ou quux
  • Les littéraux sont importants parce que les algorithmes de recherche d’une chaîne unique, ou d’un petit nombre de chaînes, sont très rapides
    • Les instructions vectorielles permettent de traiter plusieurs octets du haystack à la fois
    • Les algorithmes généraux de matching d’expressions régulières sont difficiles à accélérer de manière cohérente de la même façon
  • Une recherche de substring bien optimisée s’est souvent révélée au moins un ordre de grandeur plus rapide qu’un moteur d’expressions régulières généraliste
  • L’extraction de littéraux est une heuristique
    • Il faut réduire le taux de faux positifs des correspondances candidates
    • Il faut aussi limiter l’impact du préfiltre sur la latence totale
    • Ces deux conditions dépendent du haystack, mais analyser le haystack avant la recherche peut dégrader le temps de recherche total
  • Une séquence de littéraux n’est pas un ensemble, mais une séquence ordonnée
    • La crate regex suit une sémantique de type Perl leftmost-first, donc | n’est pas commutatif
    • sam|samwise ne peut extraire que sam, tandis que samwise|sam prend les deux en compte
  • Pour la recherche d’une seule chaîne, on utilise le module memmem de la crate memchr
    • L’algorithme principal est Two-Way, avec un temps au pire en O(n) et un espace constant
    • Rabin-Karp est utilisé pour les needle et haystack courts
    • Sur x86_64, une variante SIMD générique est exploitée
  • Pour la recherche multi-chaînes, l’algorithme principal est Teddy, porté depuis Hyperscan, et Aho-Corasick est aussi utilisé dans certains cas

NFA de Thompson et optimisations

  • La structure de données centrale au sein de la crate regex est le NFA de Thompson
  • La construction de Thompson crée un NFA à partir d’une représentation structurée d’une expression régulière en temps O(m), où m est proportionnel à la taille de l’expression régulière après expansion des répétitions comptées
  • Le NFA peut être utilisé directement comme moteur d’expressions régulières, ou converti vers d’autres types comme un DFA pour servir de base à d’autres moteurs
  • Les principales optimisations du nouveau compilateur de NFA se concentrent sur la réduction des transitions epsilon
    • Le NFA de Thompson offre un bon temps de construction, mais utilise beaucoup de transitions epsilon
    • Le calcul de l’epsilon closure peut créer un coût répété pendant la recherche ou la construction d’un DFA
  • L’optimisation des états sparse représente plusieurs transitions par intervalles dans un seul état, réduisant ainsi les nombreuses instructions Split existantes
    • Elle élimine des transitions epsilon inutiles dans des expressions régulières comme [A-Za-z0-9]
    • Dans la représentation actuelle, l’indirection peut avoir un impact sur le cache et augmenter la mémoire heap
  • L’optimisation des automates UTF-8 minimaux réduit fortement la taille du NFA pour les grandes classes Unicode
    • Dans l’ancien NFA orienté octets, \w pouvait produire 3 564 états
    • Le nouveau compilateur utilise l’algorithme de Daciuk pour produire une structure avec beaucoup moins d’états et zéro transition epsilon
    • La réduction du NFA inverse est désactivée par défaut en raison de son coût en temps de compilation
  • L’optimisation par trie de littéraux compile la structure commune des alternances de littéraux comme zap|z|zapper ou abc|xyz sous forme de trie afin de réduire les transitions epsilon
    • Pour préserver la sémantique leftmost-first, les chunks de transitions sont découpés à chaque point où une correspondance apparaît
  • Parmi les travaux futurs envisagés sur les NFA figurent le NFA de Glushkov et un stockage en une seule allocation contiguë
    • Le NFA de Glushkov n’a pas de transitions epsilon, mais sa complexité en temps de compilation est moins bonne
    • Une allocation contiguë pourrait apporter une meilleure cache friendliness et permettre une sérialisation/désérialisation zero-copy, mais avec une complexité de code accrue et un possible recours à unsafe

Moteurs d’expressions régulières individuels

  • Les moteurs de regex-automata partagent des API similaires
    • Input : configure le haystack, la plage de recherche, le mode anchored et l’arrêt anticipé
    • Match : contient le span d’octets correspondant et le PatternID
    • MatchError : représente une erreur empêchant de déterminer le résultat de la recherche

  • PikeVM

    • Prend en charge l’ensemble des fonctionnalités que regex-syntax peut analyser, et fonctionne avec des haystack de n’importe quelle longueur
    • Suit les positions des groupes de capture et calcule les états actifs en lock-step, garantissant un temps au pire en O(m * n)
    • Les performances sont son principal point faible, car il faut suivre de nombreux états et positions de groupes de capture
    • Il a la particularité, parmi les moteurs de regex-automata, de ne pas renvoyer d’erreur pendant la recherche

  • BoundedBacktracker

    • Utilise le backtracking au-dessus du NFA de Thompson, mais conserve un état supplémentaire pour éviter de retracer un travail déjà effectué
    • Garantit un temps au pire en O(m * n), mais utilise un espace O(m * n)
    • Dans des expériences approximatives, il est généralement environ 2 fois plus rapide que PikeVM
    • Il peut échouer si la longueur du haystack et la taille de l’expression régulière dépassent la capacité visited configurée

  • one-pass DFA

    • Rapporte très rapidement les offsets des groupes de capture à partir d’un NFA one-pass limité
    • Il est considéré comme la méthode la plus rapide pour rapporter les groupes de capture
    • Ne prend en charge que les recherches anchored, et beaucoup d’expressions régulières ne sont pas one-pass
    • En mode Unicode, une expression régulière qui n’était pas one-pass à cause du chevauchement des transitions au niveau des octets peut le devenir si Unicode est désactivé

  • fully compiled DFA

    • Composé de deux DFA, un forward et un reverse, pour trouver la fin et le début de la correspondance complète
    • La construction prend au pire O(2^m) en temps et en espace, et un DFA dense consomme beaucoup de mémoire
    • Le moteur full DFA est désactivé par défaut dans la crate regex et doit être activé via la feature perf-dfa-full
    • Fonctionne sans Cache mutable, et peut être sérialisé en octets bruts afin d’utiliser le runtime de recherche même dans des environnements ne disposant que de core

  • hybrid NFA/DFA, lazy DFA

    • Similaire au full DFA, mais construit la table de transitions pendant la recherche
    • Si une transition déjà calculée est présente dans le cache, elle est réutilisée ; sinon, seule cette transition est calculée par powerset construction du NFA
    • Le temps de recherche au pire est O(m * n), et l’espace est limité par la capacité de cache fixée lors de la construction
    • Dans les cas courants, la plupart des états et transitions sont mis en cache et le comportement moyen ressemble à O(n) ; en pratique, pour de nombreuses expressions régulières, les performances de recherche sont proches de celles d’un full DFA
    • Si le cache se remplit de façon répétée et devient inefficace, une erreur est renvoyée ; dans le meta engine, une nouvelle tentative est généralement effectuée avec un autre moteur

Le rôle du meta regex engine

  • Le meta regex engine regroupe plusieurs moteurs et cherche à fournir à l’appelant une API infallible
  • L’appelant n’a pas besoin de créer et de passer lui-même un Cache à chaque recherche
    • Le meta engine gère en interne un pool de caches thread-safe
    • Une API de plus bas niveau permet aussi de passer explicitement un Cache si l’on veut éviter le coût de synchronisation
  • regex::Regex, regex::RegexSet, regex::bytes::Regex et regex::bytes::RegexSet sont tous de fines surcouches du meta engine
  • La stratégie interne du meta engine ressemble grosso modo à ceci
    • S’il est possible de traiter le cas uniquement avec une recherche de sous-chaîne simple ou multiple, sans moteur d’expressions régulières, la construction de la NFA est elle aussi évitée
    • Quand c’est possible, une séquence de littéraux en préfixe est extraite et utilisée comme Prefilter
    • Si le préfixe n’est pas adapté, il tente des optimisations reverse anchored, reverse suffix et reverse inner
    • Sinon, il se rabat sur une core strategy incluant PikeVM, un backtracker borné, un DFA one-pass, un DFA lazy et un DFA complet
  • La stratégie globale tient en deux phrases
    • Rechercher des littéraux autant que possible
    • Éviter autant que possible d’utiliser PikeVM
  • Les optimisations reverse suffix et reverse inner peuvent, si elles sont mal appliquées, mener à un pire cas en O(m * n^2) par rapport à la taille du haystack
    • Le meta engine détecte les cas où le scan inversé risque de dépasser la fin de la précédente correspondance de suffixe, puis se rabat sur la core strategy afin de préserver les garanties de complexité temporelle

Différences avec RE2

  • Le crate regex et RE2 ont de nombreux points communs
    • RE2 possède aussi une NFA correspondant à PikeVM, un backtracker bitstate, une NFA one-pass, un DFA lazy et une structure combinant plusieurs moteurs
    • Parmi les moteurs ci-dessus, celui qui n’existe pas dans RE2 est le DFA entièrement compilé
  • Les principales différences sont les suivantes
    • RE2 prend en charge en option la sémantique POSIX leftmost-longest en plus de leftmost-first
    • Le support Unicode de RE2 est plus limité, et il n’existe pas d’option pour utiliser \w, \s, \d et \b selon les définitions Unicode
    • RE2 a une prise en charge limitée des opérations sur les ensembles de classes de caractères, en dehors de l’union
    • Le PikeVM de RE2 est susceptible d’être plus efficace en mémoire
    • Les optimisations de littéraux de RE2 sont limitées, tandis que le crate regex effectue davantage d’optimisations de ce type
    • Le DFA lazy de RE2 partage le même cache de transitions entre plusieurs threads, ce qui nécessite une synchronisation, alors que le crate regex exige un cache distinct par thread et consomme donc plus de mémoire
    • Le crate regex publie regex-syntax et regex-automata comme bibliothèques versionnées séparément, ce que RE2 ne prend pas en charge
    • regex-automata prend en charge les expressions régulières multi-pattern comme éléments de première classe dans tous les moteurs, et peut aussi rapporter la correspondance de chaque motif ainsi que les offsets des groupes de capture

Stratégie de test et benchmarks

  • La nouvelle stratégie de test consiste à faire des moteurs internes des API indépendantes de première classe et à tester directement chaque moteur
  • Tous les tests d’expressions régulières sont définis dans des fichiers TOML
  • Le crate regex-test lit les tests TOML et les convertit en représentation structurée
  • Pour chaque configuration de moteur, un Rust unit test est prévu, et tous les tests TOML applicables à ce moteur sont exécutés
  • Comme le framework de unit tests de Rust n’est pas extensible, une infrastructure maison à base de variables d’environnement a été ajoutée pour filtrer certains tests
  • regex-automata compte à lui seul plus de 450 documentation tests
  • Lors de la préparation de regex 1.9, de nombreuses cibles de fuzz testing ont également été ajoutées, et plusieurs bugs ont été trouvés avec l’aide d’Addison Crump
  • Les benchmarks sont publiés via un regex barometer appelé rebar
    • rebar benchmarke plusieurs moteurs d’expressions régulières, et pas seulement le crate regex
    • Sur 242 benchmarks, regex 1.9 est en moyenne 1,5 fois plus rapide que regex 1.7.3 en temps de recherche
    • Le temps de construction des expressions régulières a quelque peu régressé
    • 1.8 étant une version de transition incluant une partie des travaux de migration, 1.7 a été utilisé comme base de comparaison

Coûts et alternative légère

  • La réécriture a occupé la majeure partie du temps libre de l’auteur au cours des dernières années, et des projets comme ripgrep n’ont pas pu sortir de nouvelle version pendant un certain temps
  • Les abstractions publiques réutilisables tendent à nécessiter davantage de code que les abstractions réservées à un usage interne
    • En conséquence, la taille des binaires et le temps de compilation augmentent
  • Comme l’API des moteurs internes est publiée avec un versionnement séparé, toute rupture d’API nécessite une version de regex-automata introduisant les breaking changes appropriés
  • Deux mesures ont été mises en place pour atténuer ces coûts
    • Le moteur DFA entièrement compilé est désactivé par défaut et proposé comme feature opt-in
    • regex-lite a été publié comme nouveau crate
  • regex-lite vise à être un remplacement presque drop-in du crate regex, mais se concentre sur l’optimisation de la taille des binaires et du temps de compilation
    • Il renonce à certaines fonctionnalités liées à Unicode et aux performances
    • Il conserve la garantie de complexité temporelle en O(m * n)
    • Il n’a aucune dépendance et ne partage pas de code avec le crate regex, y compris pour son propre parseur d’expressions régulières
  • regex-lite reste une mesure d’atténuation expérimentale, mais montre que même en désactivant des fonctionnalités d’optimisation et Unicode via les features du crate regex, il est difficile de se rapprocher de la taille de binaire et du temps de compilation de regex-lite

À lire aussi

1 commentaires

 
GN⁺ 2023-07-06
Commentaires Hacker News

  • Je n’ai fait que parcourir rapidement le sujet, mais la crate regex de Rust est vraiment impressionnante
    BurntSushi a créé beaucoup de choses remarquables, mais la crate regex de Rust est légendaire, et le fait que l’écosystème Rust dispose depuis longtemps d’une bibliothèque d’expressions régulières à la fois performante et facile à utiliser est une immense bénédiction pour la communauté
    La série d’articles de Russ Cox sur les expressions régulières est également excellente ; je m’en suis servi pendant un été où je construisais un moteur regex, au moment où les expressions régulières commençaient à me sembler être le point de rencontre parfait entre théorie et pratique
    Les changements de test plus profonds présentés dans cet article sont eux aussi intéressants, et comme il s’agit d’une crate centrale pour l’écosystème, j’apprécie vraiment ce type d’explication sur des sujets aussi profonds
    Les expressions régulières sont parfois difficiles à lire et souvent surutilisées pour des choses comme la validation d’e-mail, mais elles restent l’un des outils les plus denses dans presque tous les langages
    Côté pratique, je ne connais vraiment bien que Mastering Regular Expressions de Jeffrey Friedl ; pour la théorie, les livres sur les compilateurs en parlent, et le Dragon Book m’a semblé correct du point de vue de l’implémentation. Je serais curieux d’avoir d’autres recommandations de livres sur les regex

    • https://www.cs.princeton.edu/courses/archive/fall19/cos226/l... et https://kean.blog/post/lets-build-regex sont d’excellentes introductions à l’implémentation d’un moteur regex simplifié
      L’idée est de construire un automate fini non déterministe à partir d’une expression régulière, puis d’explorer le graphe orienté obtenu ; si l’on peut atteindre un sommet correspondant à un état terminal, on considère qu’il y a correspondance
      Pour ceux qui utilisent les regex, cet exercice aide à comprendre qu’il y a moins de magie qu’on ne l’imagine, et si l’on visualise des billes rebondissant sur un NFA, les bugs de backtracking catastrophique qu’on finit par rencontrer en production prennent aussi un sens physique
      Concernant l’article original, le dernier commentaire de BurntSushi sur https://github.com/rust-lang/regex/issues/822 apporte un contexte utile à la section sur les API de niche https://blog.burntsushi.net/regex-internals/#problem-request.... Rechercher plusieurs expressions régulières simultanément dans un texte est extrêmement complexe mais très utile, donc j’ai hâte de voir ce que la communauté va construire autour de ce modèle
    • Un cas typique où les regex brillent pour des tâches proches du parsing, c’est lorsqu’on doit gérer des formats aux délimiteurs variés
      Par exemple, pour un format à nombre fixe de champs comme header:field1,field2,field3\"data\"hash, ou un format comme suite~split/test1,test2@opt1:opt2^hw1^hw2#flags1#flags2 où la plupart des éléments sont optionnels, des outils de base comme split ne suffisent pas et les regex sont bien adaptées
      C’est aussi pour cela qu’elles deviennent vite difficiles à lire : une seule regex mélange les délimiteurs entre champs, la validation de chaque champ et l’indication de quels champs sont optionnels
      Ce sont à l’origine trois préoccupations distinctes, mais la plupart des API regex ne permettent pas de les séparer par étapes et n’acceptent qu’une seule chaîne qui fusionne tout
    • Je me demande si cette bibliothèque RegEx utilise un JIT comme la plupart des implémentations JavaScript. Si ce n’est pas le cas, ce pourrait être un exemple où JavaScript bat Rust
    • J’ai récemment fait un peu de travail autour de RegEx et j’ai parcouru cet article ; comme le langage utilisé, contrairement à d’autres moteurs, ne renvoyait pas d’erreurs, j’ai eu l’impression qu’il s’agissait d’une PikeVM
      À cause des contraintes du langage et du statut de protection par copyright, j’ai dû recréer moi-même la fonctionnalité RegEx, et les expressions régulières peuvent vraiment parfois donner l’impression d’être du vaudou
      Je ne sais pas à quel point les autres moteurs sont fréquemment utilisés, mais si beaucoup de langages de programmation emploient PikeVM, on comprend pourquoi Google a voulu créer son propre OS pour serveurs et mobiliser un moteur plus rapide dans certains cas afin d’économiser ne serait-ce que quelques cycles d’horloge
      Je sais bien qu’ajouter seulement quelques caractères à la chaîne de recherche peut ralentir fortement le pattern matching. Le proverbe « les petits ruisseaux font les grandes rivières » s’applique très bien aux RegEx et aux cycles d’horloge, et quand on repense aux discussions des années 1990 sur le traitement de millions d’enregistrements par seconde, on se dit que cela a dû rendre certains codeurs très riches
    • Mon plus gros grief concerne les petites différences entre les dialectes regex
      En particulier, selon le dialecte et le contexte, le traitement des guillemets ou la manière de terminer une expression varient tellement que j’ai renoncé à les mémoriser et je cherche des exemples à chaque fois que j’en ai besoin

  • Chez ActiveState, on m’a confié, avec un collègue tout juste sorti d’école, la mission de créer un débogueur regex pour l’éditeur Komodo
    Nous avons embauché le légendaire expert Perl Mark Jason Dominus pour ajouter des hooks au moteur regex de Perl, puis nous avons exposé ces hooks dans l’UI afin que les utilisateurs puissent suivre l’exécution d’une regex pas à pas
    Aujourd’hui, les outils web sont meilleurs, mais en 2001, le Rx Debugger de Komodo était à la pointe et c’était un projet très amusant

    • J’ai déjà eu besoin d’un débogueur regex hors ligne pour ce type d’usage
      Je travaillais sur des réseaux air gap, donc les personnes qui devaient utiliser ces outils n’avaient pas accès aux sites en ligne, et quelle que soit l’architecture retenue, il était absolument exclu d’envoyer des données de travail vers un outil en ligne
      Pourtant, la plupart des efforts se concentrent sur les outils en ligne, et les outils hors ligne sont rares et insuffisants comparés à quelque chose comme https://regex101.com/
    • Je serais curieux d’avoir des recommandations précises d’outils web adaptés à cet usage

  • Je me demande s’il est possible d’utiliser ça aussi sur des listes plutôt que sur des chaînes.
    Il existe des mécanismes puissants pour rechercher et modifier des listes de caractères, mais dès qu’on passe à des listes de nombres ou de dates, tout disparaît, et ça m’a toujours frustré.
    Par exemple, si je veux trouver dans une liste de dates de tentative de connexion toutes les séquences où un succès arrive après au moins 5 échecs, c’est simple avec une expression régulière, mais en pratique il faut écrire soi-même des boucles, des indicateurs et des listes temporaires.
    On pourrait convertir la liste en chaîne, la traiter, puis la reconvertir, mais les inconvénients sont évidents. Même si ce n’est pas aussi rapide que des regex basées sur des chaînes, je ne vois pas pourquoi il ne devrait pas exister des regex pour des listes de type arbitraire.
    J’ai même retrouvé un prototype Python que j’avais fait autrefois : https://github.com/boppreh/listregex
    C’est très lent, mais c’est satisfaisant comme expérimentation d’API, et ça fournit aussi des outils absents des regex, comme l’inversion de motif, l’intersection et l’appariement

    • Non. Cette bibliothèque de regex est fortement couplée à la recherche dans les chaînes, et c’est un choix de conception assumé.
      Faire en sorte qu’un moteur de regex comme celui-ci ait un alphabet générique est irréaliste dès le départ. En particulier, il est concrètement trop difficile de le faire d’une manière qui ne dégrade ni la conception de l’API ni les performances des principaux cas d’usage.
      Un moteur de regex de ce genre, sans se soucier des performances, n’est pas difficile à fabriquer. Par exemple, on peut prendre le crate regex-lite que j’ai publié et le rendre aussi générique qu’on veut, et on rencontrera au passage des difficultés intéressantes.
      Ce n’est pas totalement inexistant non plus. Des gens ont essayé d’en créer[1]. Mais ils ont tendance à surestimer un peu leur utilité générale, donc ça ne semble généralement pas obtenir beaucoup de traction :-)
      [1]: https://docs.rs/automata/latest/automata/trait.Alphabet.html
    • std::basic_regex de la bibliothèque standard C++ essaie cela en exposant une classe template pour des types de caractères définis par l’utilisateur : https://en.cppreference.com/w/cpp/regex/basic_regex
      On peut fournir une classe de traits qui définit le comportement requis pour ces « caractères » personnalisés.
      Mais les performances chutent fortement, et cela a sans doute autant de chances de bien fonctionner que de mettre des objets arbitraires non textuels dans un std::basic_string personnalisé
    • Il faut d’une manière ou d’une autre définir une API qui fasse le matching sur une fenêtre glissante de valeurs.
      Ce n’est pas impossible, mais la plupart des langages n’ont pas de bonne interface pour cela

  • J’utilise Ripgrep tous les jours pour chercher des choses dans du code ou des fichiers texte, et je lui suis reconnaissant à chaque fois que je l’utilise, sur Windows, Linux, Mac, VSCode ou Vim.
    C’est l’un des logiciels qui ont changé ma vie et ma manière de travailler.
    Quand je suis forcé d’utiliser grep, j’ai l’impression de revenir à une époque où tout tournait sur un CPU monocœur et où les données vivaient sur des disques durs mécaniques PATA/IDE lents.
    BurntSushi mérite largement le respect parmi les grands programmeurs

    • ripgrep a une lignée. Avant lui, il y avait ag, et avant ça ack, et tous essayaient d’offrir une interface bien meilleure qu’un simple grep

  • J’ai dû créer un RegexSet avec plus de 10 millions d’expressions régulières pour un problème métier.
    Aucun moteur ne pouvait l’encaisser dans sa configuration par défaut, et le RegexSet de Rust n’était pas suffisant non plus avec les paramètres par défaut.
    Malgré tout, utiliser regex-automata et regex-syntax et lire leur code a été une ressource d’apprentissage très utile, déjà en 2018.
    Au final, le projet professionnel s’est inspiré de l’API de Lucene, mais ça n’aurait pas été possible sans les bases apprises avec les crates regex

    • 10 millions de regex, c’est énorme. Même Aho-Corasick ne gère que tout juste 10 millions de littéraux.
      Le travail à venir consiste à faire en sorte que les moteurs de regex passent mieux à l’échelle avec davantage de motifs. À l’heure actuelle, ça s’effondrerait bien avant 10 millions de regex, et il est difficile d’être certain que cet objectif soit réellement atteignable.
      Cela dit, on peut clairement faire mieux qu’aujourd’hui.
      Bien sûr, pour la recherche multipatron, Hyperscan est en pratique une sorte d’étalon-or. En revanche, je ne sais pas à quel point il gère bien 10 millions de motifs
    • Comme vous n’êtes pas entré dans les détails au départ, j’imagine que la réponse est « non », mais si c’est possible, je serais curieux d’en savoir plus sur ce problème ou ce projet

  • J’avais expérimenté le crate regex-automata il y a quelque temps, et c’était la seule bibliothèque utilisable dans un éditeur de texte parce qu’elle donnait un accès direct au DFA interne.
    Les API de bibliothèques de regex classiques partent du principe que l’entrée est une seule chaîne continue, alors que cette approche est compatible avec n’importe quelle structure de données textuelle

  • Cet article est sorti pendant que j’écrivais du code basé sur le crate regex-automata, et même sur l’ancienne release 0.2.0.
    On dirait que c’est le moment de vérifier s’il faut replonger dans la nouvelle architecture interne.
    Je n’ai pas encore lu l’article, mais ça a l’air très intéressant et parfaitement bien tombé.
    Quelques minutes plus tard, il semblait que la réponse se rapprochait de « peut-être », mais comme c’est une release officielle, ça devrait au contraire simplifier nettement le code.
    Une dizaine de minutes plus tard, c’était plutôt painless, et la nouvelle méthode Builder::patch était une amélioration totale.
    Au passage, je suis encore bloqué sur tous vos dépôts GitHub, et vu à quel point beaucoup de crates sont largement utilisées, je trouve ça un peu injuste. Je ne me souviens plus de l’incident d’origine. Les crates regex elles-mêmes semblent maintenant être sous l’organisation rust-lang, mais il reste des choses avec lesquelles je ne peux toujours pas interagir

    • La documentation de regex-automata 0.2.0 affichait un gros avertissement à ce sujet et recommandait fortement d’utiliser 0.1 : https://docs.rs/regex-automata/0.2.0/regex_automata/
      Moi non plus, je ne me souviens pas de l’incident d’origine. Je bloque beaucoup de gens pour diverses raisons, mais je viens de lever le blocage

  • BioJulia a publié Automa.jl, un moteur d’expressions régulières en Julia pur capable d’insérer du code Julia arbitraire au moment de la compilation
    Il ne s’agit pas de minimiser le fait que regex de Rust soit bien plus avancé qu’Automa, mais il est difficile d’adhérer à l’idée qu’il s’agirait du premier cas où l’intérieur d’un moteur regex est exposé comme une bibliothèque

    • Cela ressemble à deux choses différentes
      Par exemple, PCRE2 prend en charge des « callouts » qui semblent proches de ce qui est décrit : https://www.pcre.org/current/doc/html/pcre2callout.html
      Des outils comme ragel ou re2c font aussi quelque chose de similaire depuis longtemps
      Ce dont parle ce billet de blog, c’est de sortir les composants internes de la bibliothèque regex elle-même pour en faire une bibliothèque séparée, versionnée indépendamment, que d’autres peuvent composer
      Pour les backtrackers, c’est généralement moins naturel, car le moteur n’a souvent qu’un seul backtracker, mais les bibliothèques fondées sur des automates combinent souvent plusieurs moteurs de diverses manières
      Cela dit, même un backtracker pourrait exposer des éléments comme le parseur regex ou l’AST, qui en pratique ne sont généralement pas rendus publics