Hacker News a relancé l’essai de Nikita Popov sur les regex, rouvrant une fracture cruciale

Hacker News a remis en circulation un essai de Nikita Popov vieux de 14 ans, ravivant un conflit que les raccourcis du monde de la programmation masquent souvent. L’article soutient que les moteurs de regex modernes peuvent reconnaître des langages qui dépassent largement le cadre des langages réguliers formels. Les réactions sur Hacker News se sont concentrées sur le prix de cette expressivité supplémentaire.

Popov a publié cet essai le 15 juin 2012, alors qu’il répondait fréquemment à des questions sur PHP sur Stack Overflow. Il s’attaquait à une interdiction bien connue : HTML ne peut pas être traité avec des expressions régulières, car HTML n’est pas régulier.

Cette règle reste utile, mais Popov a montré pourquoi son explication théorique peut induire en erreur. Un motif PCRE ne se limite pas à l’objet mathématique appelé expression régulière. La récursion, les références arrière, les assertions, les conditionnelles et les appels de sous-routines confèrent à certains moteurs une portée bien plus vaste.

Le débat relancé ne porte donc pas sur la capacité de Popov à concevoir un motif astucieux. Il concerne ce que les développeurs entendent par regex, les garanties qui subsistent selon les choix d’implémentation, et le moment où la reconnaissance devient un mauvais substitut à l’analyse syntaxique.

Pourquoi Hacker News a relancé un débat sur les regex datant de 2012

L’essai est revenu parce que sa distinction centrale reste non résolue dans le vocabulaire courant du logiciel.

L’essai de 2012 de Popov commence par dissocier deux sens que les développeurs confondent régulièrement. Les expressions régulières formelles décrivent des langages réguliers. Les moteurs de regex de production implémentent souvent des opérateurs supplémentaires qui dépassent cette classe formelle.

Un langage régulier peut être reconnu avec un état fini, ce qui signifie que le moteur de correspondance n’a pas besoin d’une pile non bornée liée à la profondeur de l’entrée. Les exemples courants incluent les identifiants, les formats numériques simples, les motifs de jetons fixes et de nombreux filtres de recherche.

PCRE, pour Perl-Compatible Regular Expressions, ajoute des constructions qui modifient cette situation. Un sous-motif peut s’appeler lui-même, permettant au moteur de suivre des structures imbriquées. Une référence arrière peut exiger qu’un texte ultérieur soit identique à un texte capturé auparavant.

Ces fonctionnalités font du terme « expression régulière » une appellation historiquement familière mais mathématiquement imprécise. Les développeurs emploient généralement regex comme nom générique pour une famille de langages de motifs. Les spécialistes des langages formels peuvent réserver le terme aux expressions équivalentes à des automates finis.

Cette distinction a structuré la discussion d’août. Un camp estimait que l’essai risquait de confondre les véritables expressions régulières avec la mise en correspondance spécifique à PCRE. D’autres ont répondu que Popov annonçait explicitement cette distinction avant d’examiner le sens plus large qu’en donnent les programmeurs.

Les deux lectures soulignent un point important. L’essai précise soigneusement son périmètre, mais son titre provocateur invite les lecteurs à considérer des moteurs dissemblables comme une seule technologie. Un motif PCRE utilisant la récursion en dit peu aux développeurs sur ce que JavaScript, RE2, Rust, POSIX ou une autre implémentation acceptent.

La discussion a aussi dépassé la théorie. Les commentateurs ont évoqué la lisibilité, les différences entre moteurs, l’utilisation de la mémoire, le backtracking, l’exposition au déni de service et les expressions générées par l’IA. Ces préoccupations expliquent pourquoi un essai de 2012 semble toujours d’actualité.

Les assistants de code modernes peuvent produire des motifs denses sans garantir que les mainteneurs comprennent leur exécution. Ils peuvent aussi suggérer une syntaxe non prise en charge par le moteur visé. Un accès accru à la génération de regex ne dispense pas de choisir le bon moteur de correspondance.

L’article original reste précieux parce qu’il remet en cause une limite trop simplifiée. La discussion relancée importe parce qu’elle apporte la question opérationnelle manquante : quel est le coût de cette expressivité supplémentaire ?

La puissance des regex PCRE provient de fonctionnalités extérieures aux langages réguliers

Le résultat central de l’article concerne les moteurs de style PCRE, et non tous les systèmes portant l’étiquette regex.

Popov commence par la hiérarchie de Chomsky, qui regroupe les langages formels selon la grammaire nécessaire pour les générer. Les langages réguliers s’inscrivent dans les langages hors contexte, eux-mêmes inclus dans les langages sensibles au contexte.

Les expressions régulières traditionnelles occupent le groupe le plus restreint. La concaténation, l’alternance, les classes de caractères et la répétition peuvent décrire chaque langage régulier. Elles ne peuvent pas, à elles seules, mémoriser une profondeur d’imbrication illimitée ni dupliquer une sous-chaîne capturée arbitraire.

La récursion de PCRE modifie la première limitation. Popov utilise un groupe récursif pour reconnaître des chaînes contenant autant de caractères a que de caractères b qui les suivent. Ce langage est hors contexte mais non régulier.

Le mécanisme est compact. Un motif consomme un a, invoque récursivement le groupe englobant, puis consomme un b. Chaque appel plus profond ajoute une paire correspondante autour de la correspondance imbriquée.

La documentation actuelle de PCRE2 décrit toujours la syntaxe des motifs récursifs. Elle donne les parenthèses équilibrées comme exemple direct. Un groupe reconnaît une parenthèse ouvrante, des caractères internes ordinaires ou une autre invocation du groupe, puis une parenthèse fermante.

Il s’agit d’une capacité significative. La mise en correspondance traditionnelle à états finis ne peut prendre en charge qu’une limite d’imbrication prédéfinie. La mise en correspondance récursive peut suivre la profondeur d’imbrication de l’entrée, sous réserve des limites de ressources et du comportement du moteur.

Popov transpose ensuite des règles de grammaire hors contexte en sous-motifs PCRE nommés. La construction (?(DEFINE)...) contient des définitions sans consommer l’entrée. Les appels de sous-routines nommées permettent à une règle d’en invoquer une autre.

Son exemple étendu traduit des parties de la grammaire d’e-mail RFC 5322 dans cette notation. Le résultat ressemble à une grammaire intégrée dans un littéral regex, avec les espaces et les commentaires activés via le mode étendu.

Cela étaye l’affirmation marquante de l’essai : la récursion de style PCRE peut reconnaître des langages hors contexte après transformation d’une récursion gauche incompatible. Cela ne signifie pas que chaque regex courte peut traiter tous les langages hors contexte.

Cela ne fait pas non plus du moteur un analyseur syntaxique complet. La reconnaissance répond à la question de savoir si une entrée appartient à un langage. L’analyse syntaxique produit une sortie structurée qui indique comment l’entrée correspond à la grammaire.

Cette différence devient décisive pour HTML. Un moteur de correspondance pourrait déterminer si un fragment bien formé est conforme à une grammaire. Une application a généralement besoin d’éléments, d’attributs, de nœuds de texte, de récupération d’erreurs, de gestion des entités et de parcours du document.

Le HTML réel ajoute une autre complication. Les navigateurs traitent les documents mal formés selon un comportement de récupération spécifié. Reconnaître un langage idéalisé et bien formé ne reproduit pas ce comportement.

Popov reconnaît ces deux limites. Il recommande une bibliothèque DOM pour le traitement HTML générique et réserve les regex aux situations circonscrites. La célèbre affirmation est donc plus limitée que ne le suggèrent de nombreuses reformulations.

Les références arrière ajoutent une étape supplémentaire au-delà des expressions régulières classiques. Une référence arrière reconnaît exactement le texte précédemment capturé par un groupe. Le motif ^(.+)\1$, par exemple, reconnaît une chaîne formée de deux moitiés identiques.

Un automate fini ne peut généralement pas mémoriser une première moitié arbitraire et la comparer à la seconde. Le moteur doit conserver le contenu capturé et explorer les points de division possibles. Cet état supplémentaire modifie à la fois le champ expressif et le comportement computationnel.

Popov combine également récursion et assertions lookaround pour reconnaître au moins certains langages sensibles au contexte. Un lookaround vérifie le texte environnant sans le consommer à cette position.

Il ne va pas jusqu’à affirmer que PCRE reconnaît tous les langages sensibles au contexte. Cette retenue importe. L’essai distingue les constructions démontrées des questions sans réponse, tout en employant un titre délibérément large.

Les regex formelles et les moteurs à backtracking privilégient des promesses différentes

Le conflit principal n’oppose pas la théorie à la pratique ; il oppose une exécution prévisible à un langage de motifs plus vaste.

Un moteur limité aux constructions des langages réguliers peut exécuter des motifs au moyen d’automates. Il suit l’ensemble des états atteignables après chaque caractère d’entrée plutôt que de s’engager dans un chemin puis de revenir en arrière après un échec.

Un moteur à backtracking suit les alternatives davantage comme une recherche en profondeur. Il choisit une branche, continue, puis revient à une décision antérieure lorsque la correspondance ultérieure échoue. Cette approche prend en charge les captures et des comportements avancés avec une sémantique intuitive.

Elle peut aussi répéter du travail. Des quantificateurs imbriqués ambigus peuvent créer de nombreuses façons de découper la même entrée. Un suffixe presque correspondant peut contraindre le moteur à explorer ces combinaisons avant de signaler un échec.

Ce risque ne survient pas uniquement lorsqu’un motif utilise la récursion ou les références arrière. Une implémentation à backtracking peut prendre un temps excessif sur un motif formellement régulier. La classe syntaxique et la stratégie d’exécution sont liées, mais elles ne sont pas identiques.

Ce point a corrigé une simplification excessive dans le débat en ligne. Retirer les extensions non régulières ne rend pas automatiquement chaque implémentation linéaire. Le moteur doit également utiliser un algorithme qui évite l’exploration exponentielle des chemins.

Le moteur à temps linéaire de Google effectue un compromis délibéré. RE2 garantit un temps de correspondance asymptotiquement linéaire selon la longueur de l’entrée et fonctionne dans une enveloppe mémoire configurable.

RE2 exclut les références arrière et les assertions lookaround, car ses concepteurs ne savent pas comment prendre en charge ces constructions tout en préservant la même garantie. Il exclut également les appels de sous-routines récursifs.

Le résultat est moins expressif que PCRE2, mais plus prévisible pour les services acceptant des motifs non fiables ou traitant du texte non fiable. Cette différence relève d’une décision architecturale, et non de la preuve qu’un moteur remplace universellement l’autre.

PCRE2 fournit des contrôles que les systèmes de production peuvent utiliser, notamment des limites de correspondance, des limites de profondeur, des chemins d’exécution alternatifs et une construction prudente des motifs. Ces contrôles réduisent l’exposition, mais exigent une configuration et des tests délibérés.

Le choix pratique dépend de qui contrôle le motif et l’entrée. Une expression détenue par un développeur appliquée à des enregistrements bornés présente un risque différent d’une expression fournie par un utilisateur qui analyse de grandes charges utiles dans un service partagé.

La sortie requise compte également. Une commande de recherche peut ne nécessiter qu’une correspondance booléenne ou quelques captures. Un compilateur, un processeur de documents ou un lecteur de configuration a besoin de résultats structurés et d’emplacements d’échec utiles.

C’est pourquoi « regex peut le reconnaître » tranche rarement une décision d’ingénierie. La capacité établit la possibilité. Elle n’établit ni la maintenabilité, ni les bornes de ressources, ni la qualité des diagnostics, ni la compatibilité.

Le désaccord sur Hacker News devient plus clair dans ce cadre. Popov décrit ce que certains moteurs peuvent exprimer. Les critiques demandent quelles garanties les applications abandonnent lorsqu’elles s’appuient sur cette portée.

Ces positions ne sont pas opposées. Elles traitent de différentes couches du même système. L’erreur importante consiste à transférer une affirmation d’une couche à une autre sans la nuancer.

La question HTML révèle la limite pratique de la reconnaissance

Reconnaître un langage n’est pas la même tâche que construire une représentation fiable d’un document.

L’avertissement courant contre le traitement du HTML par regex combine plusieurs arguments. HTML est imbriqué, les documents réels sont mal formés, les langages intégrés compliquent les frontières entre jetons, et les applications ont généralement besoin d’une sortie structurée.

Seul le premier argument concerne directement l’expressivité des langages formels. La récursion de PCRE peut traiter l’imbrication. Elle ne peut pas, par ce seul fait, résoudre les autres exigences.

Considérez une application qui extrait des liens. Une expression simple peut fonctionner sur un balisage contrôlé généré par un seul modèle. Elle peut échouer lorsqu’un > apparaît dans un attribut entre guillemets ou lorsque du texte de script ressemble à une balise.

Les commentaires, références de caractères, espaces de noms, balises facultatives et règles de récupération des navigateurs ajoutent d’autres cas. Chaque nouvelle condition étend le motif tout en laissant sa sortie moins structurée qu’un DOM.

Cela ne rend pas toute regex HTML irresponsable. Une expression ciblée peut convenir lorsque le contrat d’entrée est strict et que les conséquences d’un échec sont limitées.

Le périmètre doit être explicite. « Trouver un marqueur connu dans notre fragment généré » est une tâche textuelle bornée. « Interpréter des pages web arbitraires comme un navigateur » est une tâche de traitement de documents.

Un analyseur attribue un rôle nommé à chaque construction. Il peut associer des emplacements source, signaler un jeton inattendu, récupérer après une erreur et exposer un arbre pour des transformations ultérieures.

Une grande regex compresse souvent ces distinctions dans des groupes et du flux de contrôle. Les sous-motifs nommés et le formatage étendu aident, mais le moteur renvoie toujours des correspondances plutôt qu’un arbre syntaxique natif.

L’écart de maintenance se creuse lorsque les exigences évoluent. Prendre en charge une autre production grammaticale dans un analyseur implique généralement d’ajouter ou de modifier une règle. Dans une regex étroitement couplée, cela peut modifier le comportement du backtracking et des captures ailleurs.

Les tests doivent donc couvrir davantage que des exemples valides représentatifs. Les équipes ont besoin d’entrées invalides, de quasi-correspondances, de grandes entrées, d’entrées imbriquées, de cas Unicode et de chaînes adverses conçues pour déclencher des chemins coûteux.

C’est aussi là que la documentation devient opérationnelle plutôt que décorative. Une expression complexe devrait préciser son moteur, ses indicateurs, son contrat d’entrée accepté, les captures attendues, les limites de taille et la raison pour laquelle un analyseur n’est pas utilisé.

Les équipes qui préservent leurs décisions techniques peuvent conserver ces contraintes à côté d’archives d’implémentation consultables. Une base de connaissances d’ingénierie partagée aide les futurs mainteneurs à retrouver l’intention derrière un code de correspondance laconique.

La décision clé n’oppose pas regex et analyseur comme des identités rivales. Elle consiste à déterminer si la tâche requiert de la reconnaissance, de l’extraction, de la transformation, de la récupération ou une interprétation complète.

Les regex restent excellentes pour la tokenisation, la validation selon des règles bornées, la recherche, le filtrage de logs et de petites extractions. Un analyseur devient préférable lorsque la structure grammaticale constitue les données de travail de l’application.

La propre conclusion de Popov suit cette frontière. Il rejette l’interdiction théorique absolue tout en conservant la recommandation pratique d’utiliser une bibliothèque DOM pour le traitement générique du HTML.

Cette nuance disparaît souvent en ligne. « Les regex ne peuvent pas analyser le HTML » perdure parce que cette formule évite des échecs fréquents. « Certains moteurs de regex peuvent reconnaître des structures hors contexte » demeure vrai parce que cette capacité sous-jacente existe.

Une règle d’ingénierie mature peut tenir ces deux affirmations ensemble. Ne confondez pas une valeur par défaut utile avec un théorème, ni une construction théorique avec une conception de production.

Ce que l’argument sur les regex sous-estime encore

Une expressivité accrue crée des obligations de sécurité et de maintenance qu’une suite de tests réussie peut ne pas révéler.

Le déni de service par expression régulière, ou ReDoS, survient lorsqu’un moteur de correspondance passe un temps excessif à explorer des alternatives face à une entrée conçue à cet effet. Un attaquant peut consommer de la capacité de traitement sans envoyer un volume important de trafic.

Les conseils sur le ReDoS décrivent des moteurs atteignant des temps d’exécution extrêmes lorsque des motifs ambigus rencontrent des chaînes adverses. Le danger apparaît souvent à proximité d’une correspondance échouée.

Un validateur peut traiter rapidement une entrée ordinaire parce que la première branche réussit. Un attaquant peut fournir un long préfixe qui correspond à de nombreux chemins, suivi d’un caractère qui invalide chacun d’eux.

Le moteur doit alors revisiter des choix antérieurs. Les répétitions imbriquées, alternatives qui se chevauchent et composants facultatifs peuvent multiplier l’espace de recherche. Un motif concis peut dissimuler ce comportement lors de la revue de code.

Les rétro-références ajoutent une autre dimension de complexité. Les recherches sur leurs limites expressives les considèrent comme une extension substantielle prise en charge par de nombreux moteurs grand public. Leur comportement ne peut pas être réduit à une correspondance ordinaire par automate fini.

L’essai de Popov indique que la correspondance avec rétro-références introduit des cas NP-complets. C’est une affirmation sur le problème général, non une prédiction selon laquelle chaque motif s’exécute lentement.

De nombreuses expressions avec captures et rétro-références se terminent rapidement sur des entrées ordinaires. Les résultats de complexité avertissent qu’aucune solution générale efficace ne couvre tous les cas, sauf si des hypothèses majeures de la théorie de la complexité changent.

La récursion introduit des préoccupations distinctes en matière de ressources. Un motif suivant une entrée profondément imbriquée consomme une profondeur gérée par le moteur ou un état équivalent. Les implémentations appliquent des limites et diffèrent dans la manière dont la récursion interagit avec le backtracking.

La version du moteur compte également. PCRE2 a modifié la sémantique de la récursion au fil du temps afin de s’aligner plus étroitement sur Perl dans certaines situations. Un motif testé avec une version peut se comporter différemment après une migration.

La portabilité est donc limitée, même entre des moteurs décrits comme compatibles avec Perl. La prise en charge syntaxique, les règles Unicode, les valeurs de capture, l’ordre de correspondance et la sémantique de récursion peuvent différer.

Les regex générées par IA augmentent les enjeux, car la génération réduit la friction qui limitait autrefois la complexité. Un développeur peut demander une expression unique pour une grammaire et recevoir en quelques secondes quelque chose de syntaxiquement convaincant.

Le motif généré peut cibler le mauvais dialecte. Il peut réussir les exemples de l’invite tout en omettant les entrées malformées, en consommant des ressources excessives ou en renvoyant des captures à la sémantique inattendue.

Les réviseurs devraient traiter les regex générées comme du code généré. Ils doivent identifier le moteur, comprendre chaque construction non triviale, exécuter des tests adverses et imposer des limites d’entrée et d’exécution.

La lisibilité n’est pas ici une préoccupation cosmétique. Un flux de contrôle illisible empêche les mainteneurs d’identifier les alternatives qui se chevauchent ou de remarquer qu’une petite modification crée un backtracking catastrophique.

Le mode étendu offre des espaces et des commentaires dans les moteurs qui le prennent en charge. Les groupes nommés réduisent la dépendance aux indices numériques changeants. Des motifs plus petits et composés peuvent clarifier les responsabilités.

Ces pratiques aident, mais la composition doit respecter la syntaxe du moteur. Certains langages hôtes interpolent des chaînes avant que le compilateur de regex ne les voie, créant une couche supplémentaire d’échappement et un risque d’injection.

Des fragments non fiables ne doivent jamais être insérés dans un motif sans un échappement adapté au moteur. Des utilisateurs non fiables ne devraient pas bénéficier d’un accès sans restriction à un moteur de backtracking au sein d’un service partagé.

La conclusion sceptique est plus étroite que « n’utilisez jamais de regex avancées ». Chaque construction avancée consomme une part du budget de prévisibilité d’un système.

Les développeurs devraient pouvoir nommer ce qu’ils obtiennent en retour. La récursion peut offrir une reconnaissance concise pour une structure imbriquée bornée. Une rétro-référence peut imposer une contrainte d’égalité qui exigerait autrement du code procédural.

Si le seul bénéfice est d’éviter un petit analyseur, le compromis devient plus difficile à justifier. Les analyseurs fournissent souvent de meilleures erreurs, une évolution plus claire et une sortie que le code en aval peut utiliser directement.

Trois signaux détermineront si la leçon s’ancre durablement

Le résultat durable dépend du choix du moteur, de la revue du code généré et de la question de savoir si les équipes testent les comportements d’échec plutôt que les seuls exemples.

Le premier signal est un choix de moteur plus explicite et plus répandu. Les développeurs devraient cesser de traiter les regex comme un langage portable unique et documenter si un motif cible PCRE2, RE2, JavaScript, Java, .NET, Rust ou une autre implémentation.

Si les bibliothèques et les plateformes rendent les garanties d’exécution visibles, le débat sur Hacker News devient plus facile à trancher. Les développeurs peuvent discuter d’un moteur défini au lieu de débattre d’une étiquette ambiguë.

Le deuxième signal concerne la manière dont les assistants de programmation traitent les demandes de regex. Les systèmes utiles devraient demander le dialecte cible, les limites d’entrée, les hypothèses sur la fiabilité des données et les captures requises avant de générer des expressions complexes.

Ils devraient également expliquer les constructions non prises en charge et proposer un analyseur lorsque la sortie demandée est structurée. Si les assistants continuent à produire des motifs denses sans ces contrôles, les échecs de maintenance et de sécurité augmenteront.

Le troisième signal est la généralisation des tests adverses. Les équipes devraient mesurer les correspondances réussies, les échecs tardifs, les longues entrées répétées, les imbrications profondes, les limites Unicode et les entrées conçues pour maximiser l’ambiguïté.

Un motif qui réussit dix exemples favorables n’a établi sa correction que pour ces exemples. Il n’a pas établi un comportement acceptable dans le pire cas ni sa compatibilité avec les limites de production.

Ces signaux renforcent la leçon plus large de Popov tout en en resserrant l’application. Les moteurs de motifs modernes peuvent dépasser les limites formelles suggérées par leur nom. Ce fait mérite d’être compris, et non utilisé comme approbation universelle d’un choix de conception.

L’essai remis en lumière offre également une correction utile aux deux camps. La théorie formelle compte parce qu’elle explique quelles garanties sont disponibles. Les détails d’implémentation comptent parce que les moteurs déployés ne préservent pas tous ces garanties.

Pour les développeurs qui suivent le débat sur Hacker News, la prochaine action est concrète. Identifiez le moteur derrière votre motif de production le plus complexe, documentez son contrat d’entrée et testez son cas d’échec le plus lent. Demandez-vous ensuite si l’application a besoin de reconnaissance ou d’une analyse structurée.

Si le motif reste clair, borné et mesurable, conservez-le. Si sa correction dépend d’un comportement de dialecte non documenté ou d’un backtracking fragile, remplacez la grammaire cachée par un analyseur explicite.