Parser, ne pas valider (2019)

 (lexi-lambda.github.io)
3 points par GN⁺ 2024-07-23 | 1 commentaires | Partager sur WhatsApp
  • Dans la conception guidée par les types, le parsing, qui conserve le résultat de la vérification sous forme d’un type plus précis, améliore la sûreté du code ultérieur par rapport à la validation, qui se contente de vérifier l’entrée puis de jeter l’information
  • Une fonction qui échoue pour certaines entrées, comme head:: [a] -> a, peut affaiblir son type de retour, mais l’appelant devra alors continuer à gérer inutilement des branches d’échec
  • NonEmpty a préserve dans le type l’état « liste non vide », ce qui réduit les vérifications redondantes et le traitement d’erreurs « qui ne devraient jamais arriver »
  • Si l’on mêle des validations ad hoc un peu partout dans le code de traitement, on obtient du shotgun parsing, avec le risque de ne découvrir une erreur d’entrée qu’après certaines modifications d’état
  • En pratique, il faut d’abord exprimer la représentation de données souhaitée dans les signatures de fonctions, puis faire remonter les invariants aux frontières de types avec Map, des types abstraits, des smart constructors, etc.

Le point de départ de la conception guidée par les types

  • « Parse, don’t validate » est une formule qui résume la conception guidée par les types en trois mots
  • Un système de types statique fait apparaître, avant même d’écrire le code, la question « peut-on écrire cette fonction ? »
  • Dans l’exemple Haskell, foo :: Integer -> Void ne peut pas produire de valeur réelle, car Void ne contient aucune valeur
  • head :: [a] -> a n’est pas non plus définie pour toutes les entrées, puisqu’une liste vide [] peut être fournie
    • GHC signale que le filtrage par motif ne traite pas le cas []
    • C’est une fonction partielle, non définie pour toutes les entrées possibles

Deux façons de transformer une fonction partielle en fonction totale

  • Affaiblir le type de retour

    • En remplaçant par head :: [a] -> Maybe a, on peut renvoyer Nothing pour une liste vide, ce qui en fait une fonction totale
    • L’implémentation devient plus simple, mais l’appelant doit toujours gérer la possibilité de Nothing
    • L’article donne un exemple où, même après avoir lu la variable d’environnement CONFIG_DIRS et déjà vérifié que la liste n’est pas vide, main doit de nouveau traiter la branche Nothing du résultat de head
    • Les vérifications redondantes encombrent le code et, dans les cas complexes, peuvent aussi s’accumuler en coût de performance
    • Même si la vérification en amont est supprimée, l’erreur en aval « qui ne devrait jamais arriver » n’apparaît pas dans les types
    • Au final, cela crée une faille dans le système de types, et la détection des bugs dépend des tests ou des revues manuelles

  • Renforcer le type de l’argument

    • En renforçant le type de l’argument sans affaiblir le type de retour, on peut éliminer la possibilité d’appeler head sur une liste vide
    • NonEmpty a de Data.List.NonEmpty représente une liste non vide
    • Sa définition est data NonEmpty a = a :| [a]
    • En séparant le premier élément a du reste de la liste [a], on garantit qu’un premier élément existe toujours, même si la queue est vide
    • head :: NonEmpty a -> a s’implémente avec un seul motif et devient une fonction totale
    • En changeant le type de retour, par exemple getConfigurationDirectories :: IO (NonEmpty FilePath), le fait que la liste soit non vide est préservé dans le type
    • nonEmpty :: [a] -> Maybe (NonEmpty a) transforme une liste ordinaire en NonEmpty
    • Le traitement de Nothing n’est effectué qu’une seule fois, à la frontière d’entrée
    • Dans main, on peut utiliser initializeCache (head configDirs) sans branche redondante
    • Si getConfigurationDirectories change plus tard et ne garantit plus que la liste est non vide, son type de retour devra aussi changer, et main échouera à la vérification de types

La différence entre validation et parsing

  • validateNonEmpty :: [a] -> IO () et parseNonEmpty :: [a] -> IO (NonEmpty a) vérifient toutes deux qu’une liste est vide et déclenchent une erreur en cas d’échec
  • La différence se situe dans le type de retour
    • validateNonEmpty renvoie (), qui ne contient aucune information, et jette donc le résultat de la vérification
    • parseNonEmpty renvoie NonEmpty a, ce qui conserve dans le système de types la connaissance obtenue par la vérification
  • On peut voir un parseur comme une fonction qui consomme une entrée moins structurée et produit une sortie plus structurée
  • Dans cette définition, parseNonEmpty est un parseur simple qui transforme une liste en liste non vide
  • Le parsing permet de terminer les vérifications à la frontière entre le programme et le monde extérieur, puis d’éviter de répéter les mêmes vérifications ensuite

Les frontières de parsing dans l’écosystème Haskell

  • Les applications Haskell utilisent plusieurs types de parseurs aux points de contact avec le monde extérieur
    • aeson : fournit le type Parser pour parser des données JSON vers des types du domaine
    • optparse-applicative : fournit des combinateurs de parseurs pour les arguments en ligne de commande
    • persistent, postgresql-simple : fournissent des mécanismes pour parser les valeurs venant de stockages de données externes
    • servant : parse des types de données Haskell à partir de composants de chemin, de paramètres de requête, d’en-têtes HTTP, etc.
  • Le monde extérieur ne parle pas en types produit et types somme, mais en flux d’octets ; le parsing est donc inévitable
  • Parser les données en amont, avant de les utiliser, permet d’éviter de nombreux types de bugs, dont certains peuvent mener à des vulnérabilités de sécurité
  • Pour tout parser en amont, il peut être nécessaire de parser des valeurs bien avant leur utilisation réelle
  • Avec un système de types statique, si la logique de parsing et la logique de traitement divergent, le programme ne compile pas

Les risques d’une approche centrée sur la validation

  • La validation ad hoc peut mener au shotgun parsing décrit dans le domaine de la language-theoretic security
  • Dans l’article de 2016 The Seven Turrets of Babel: A Taxonomy of LangSec Errors and How to Expunge Them, le shotgun parsing est un antipattern où le code de parsing et de validation des entrées est mélangé et dispersé dans le code de traitement
  • Si l’entrée n’est pas entièrement parsée en amont, le programme peut traiter certaines parties valides avant de découvrir tardivement une erreur dans une autre partie
    • Dans ce cas, il faut annuler les modifications d’état déjà effectuées
    • C’est possible dans certains cas, comme avec les transactions d’un SGBDR, mais ce n’est généralement pas toujours possible
  • Une approche fondée sur la validation rend difficile, voire impossible, de vérifier que toutes les validations ont réellement été faites en amont
  • Le parsing divise le programme en une phase de parsing et une phase d’exécution, limitant à la première phase les échecs dus à des entrées invalides

Comment l’appliquer en pratique

  • On conçoit d’abord une fonction en écrivant dans sa signature de type la représentation de données qu’elle souhaite, puis en comblant l’écart avec la représentation actuellement disponible
  • Si une fonction reçoit une liste [(k, v)] qui ne doit pas autoriser les clés en double, une vérification séparée checkNoDuplicateKeys :: ... => [(k, v)] -> m () peut facilement être oubliée
  • Une meilleure approche consiste à prendre en argument un Map, qui n’autorise pas structurellement les clés en double
    • Les sites d’appel peuvent alors échouer à la vérification de types
    • La transformation de la liste en Map est repoussée vers le haut de la chaîne d’appels
    • Lorsqu’on atteint l’endroit où la valeur est créée, ou celui où les doublons doivent réellement être autorisés, on ajoute une vérification de la forme [(k, v)] -> m (Map k v)
  • Comme le résultat de cette vérification est nécessaire à l’exécution ultérieure, elle ne peut pas être omise
  • Deux principes reviennent régulièrement
    • Utiliser des structures de données qui rendent les états impossibles impossibles à représenter
    • Faire remonter autant que possible la charge de la preuve, sans la pousser plus loin que nécessaire

Conseils de conception supplémentaires et limites

  • Il faut laisser les types de données guider le code, et éviter la tentation d’ajouter simplement un Bool à un enregistrement à cause de la fonction en cours d’écriture
  • Les fonctions qui renvoient m () méritent d’être examinées avec suspicion
    • Elles peuvent être nécessaires lorsqu’elles ne font qu’exécuter des effets impératifs sans résultat significatif
    • Si leur objectif principal est de déclencher une erreur, il existe probablement une meilleure approche
  • Il ne faut pas avoir peur de parser les données en plusieurs étapes
    • Éviter le shotgun parsing signifie ne pas agir sur les données d’entrée avant de les avoir entièrement parsées
    • Il reste possible d’utiliser une partie de l’entrée pour décider comment parser une autre partie
  • Les représentations de données dénormalisées sont à éviter, surtout lorsqu’elles sont mutables
    • Dupliquer les mêmes données à plusieurs endroits rend facile la représentation d’états incohérents entre eux
    • Si la dénormalisation est indispensable, il faut la cacher derrière une frontière d’abstraction et confier la responsabilité de la synchronisation à un petit module de confiance
  • Lorsqu’un invariant est vraiment difficile à représenter uniquement avec les outils Haskell, on peut utiliser un newtype abstrait et des smart constructors pour faire fonctionner le validateur comme un parseur
  • Il n’est pas nécessaire d’introduire singletons et de refactorer toute l’application pour éliminer tous les error "impossible", mais dans ces cas-là il faut rester prudent, par exemple en documentant les invariants dans des commentaires

Lectures complémentaires et mises en garde pratiques

  • Il n’est pas nécessaire d’avoir un PhD ni les dernières extensions de langage GHC pour bien tirer parti du système de types de Haskell
  • Le point de départ ressemble à un principe simple : « écrivez des fonctions totales », mais son application dans du vrai code peut ne pas être facile
  • La communauté Haskell étant petite, certains design patterns et certaines techniques restent transmis oralement plutôt que documentés
  • Parmi les ressources liées figure Type Safety Back and Forth de Matt Parson
  • Sur un sujet plus avancé, l’article de 2018 Ghosts of Departed Proofs de Matt Noonan traite de techniques permettant d’inscrire des invariants plus complexes dans le système de types
  • Dans les programmes réels, certains invariants peuvent être difficiles à faire entrer dans le système de types ; ces principes sont donc davantage un idéal à viser que des exigences strictes

À lire aussi

1 commentaires

 
GN⁺ 2024-07-23
Avis de Hacker News

  • Très bon conseil et excellent article. Ce n’est pas pour rien qu’il remonte de temps en temps sur ce site.
    Même pour les personnes qui n’utilisent pas de langages fonctionnels à typage statique, cette idée dépasse les paradigmes. On trouve des concepts très proches dans la littérature orientée objet des années 80-90, par exemple le Design by Contract, et on pourrait sans doute remonter encore plus loin dans des articles, discussions et spécifications.
    TypeScript aussi est souvent écrit de manière à affiner les types à l’exécution. Le Design by Contract a probablement aussi influencé spec dans Clojure, qui est un langage dynamique.
    Fondamentalement, c’est une question d’hypothèses et de garanties. Si l’on peut vérifier certaines hypothèses pour produire des garanties, les autres parties du programme n’ont plus besoin de revérifier ces mêmes hypothèses.
    Ce qui me perturbe le plus quand je lis du code, c’est de voir des propriétés déjà garanties être à nouveau testées ailleurs. Cela rend le raisonnement et les améliorations plus difficiles.

    • Cette « propriété déjà garantie » peut disparaître à un moment donné. Plus précisément, la procédure qui implémente et applique cette garantie peut, pour une raison ou une autre, ne plus remplir son rôle.
      Statistiquement, cela finit par arriver, et à ce moment-là les autres processus, scripts ou morceaux de code qui dépendaient de la procédure de validation « d’origine » se retrouvent dans une situation très délicate.
    • Dans les langages dotés d’un système de types fort, c’est finalement l’un des avantages pratiques qui donnent de la liberté à mesure que le programme grandit et devient plus complexe.
      Encore faut-il vraiment l’utiliser. Par exemple, on peut avoir des classes UncheckedEmail, ValidEmail et VerifiedEmail, et imposer qu’un passage d’une étape à la suivante passe nécessairement par le processus de vérification de l’e-mail.
      Ainsi, plus besoin de deviner si une adresse e-mail est non vérifiée, valide au niveau du format ou déjà vérifiée, ni d’avoir un booléen comme is_email_verified qu’on peut oublier de mettre à jour ou de vérifier. Si une mauvaise valeur est utilisée au mauvais endroit, le vérificateur de types se met à crier, et l’humain peut se concentrer sur les choses importantes.
    • En parcourant les commentaires d’anciens articles, j’ai l’impression que l’un des principaux problèmes de celui-ci est son titre. Le titre agit comme une ancre, et beaucoup de gens réfutent des choses qui ne sont pas dans le texte, mais que le titre suggère hors contexte.
      Certains comprennent donc que l’auteur proposerait de ne jamais valider et de seulement parser, alors que l’article parle en réalité de l’endroit où l’on valide les données et de ce que l’on fait du résultat. Ce n’est pas un texte qui dit de supprimer toute validation.

  • C’est un article de 2019, mais le conseil reste plutôt bon. Ce pattern s’applique très bien au C# moderne, et il permet aussi de gagner de la place puisqu’on peut omettre les déclarations explicites de variables.
    if(!Whatever.TryParse(input, out var output)) output = some-sane-default;
    Ou
    if(!Whatever.TryParse(input, out var output)) throw new ApplicationException($"Not a valid Thingy: {input}");
    Astuce de pro : ne faites pas le second dans un driver en mode noyau.

    • Astuce de pro : ne faites ni l’un ni l’autre. Surtout pas le premier.
      Un traitement explicite est toujours préférable à une valeur par défaut implicite utilisée à la place d’une valeur qu’on croyait correcte, mais qui ne l’est pas.
      Ce qu’il faut faire, c’est lever la main dès le début et traiter cela comme un échec de parsing, puis définir très clairement le processus et le protocole de gestion des fichiers impossibles à charger. Cela vous forcera à vous poser les questions difficiles que ces deux options ne traitent pas.
      Le vrai problème du récent driver en mode noyau de CrowdStrike qui n’a pas réussi à parser un fichier def/config, c’est que les développeurs, responsables produit et analystes métier ne se sont pas demandé : « que se passe-t-il si l’on tente de charger un fichier invalide ? »
    • Pourquoi seulement « plutôt bon » ? Et quel rapport avec l’année de publication ? Est-ce que cela veut dire que si l’article avait été publié avant 2019, ses conseils auraient eu plus d’autorité ?
    • J’aimerais qu’on évite la première approche. Il faut gérer les mauvais cas. Le repli vers une « valeur par défaut raisonnable » devrait être extrêmement rare.
      Traitement explicite > traitement implicite
    • if(!Whatever.TryParse(input, out var output)) output = some-sane-default;
      Je déteste vraiment cette approche. À mon avis, les erreurs d’entrée invalide doivent être traitées en dehors de la fonction de parsing. En F#, c’est facile.
      type Whatever =
      static member create input =
      match input with
      | ValidWhatever x -> Some x
      | _ -> None
      match Whatever.create input with
      | Some x -> // traiter les données parsées
      | None -> // traiter le cas où le parsing a échoué
      Ou bien on peut aussi utiliser Option.map/Option.bind pour rendre plus confortable un pipeline d’opérations en chaîne.
      Ainsi, on ne peut créer une instance qu’en passant par la méthode create qui parse l’entrée.
      En pratique, il y a toutefois de fortes chances qu’on veuille utiliser result plutôt que option, mais c’est un détail secondaire.
    • J’ai du mal à imaginer une situation où j’aimerais voir du code comme if(!Whatever.TryParse(input, out var output)) output = some-sane-default; ; en fait, peut-être aucune.
      Si l’entrée n’a pas du tout été fournie, c’est-à-dire si le paramètre est optionnel, alors utiliser une valeur par défaut raisonnable a du sens.
      Mais si une entrée incorrecte a été fournie, j’aimerais qu’on ne fasse pas comme si tout allait bien.
      Si quelqu’un entre chez un fleuriste et demande un café, la bonne réponse n’est pas de lui tendre une rose. S’il essaie de la boire, il va se déchirer la bouche.
      Pour cet ensemble d’entrées, la méthode, le module ou le programme n’a pas de sortie définie. Il faut rendre ce fait explicite, plutôt que de faire quelque chose de silencieusement faux ou ambigu qui rendra vite le programme impossible à raisonner. Mieux vaut faire échouer clairement le problème et laisser une stack trace qui mène directement à l’endroit en cause, plutôt que de le laisser réapparaître des mois plus tard sous forme de bug au comportement étrange.

  • C’est le conseil consistant à exploiter un système de types fort pour rendre les états erronés impossibles à représenter. C’est excellent pour réduire les bugs dans l’ensemble d’un logiciel
    Réfléchir plus profondément au problème et concevoir ce type de design prend davantage de temps, mais dans beaucoup de cas ce temps en vaut largement la peine

    • J’oserais dire que, dans un langage qui prend en charge les types de données algébriques, cette approche ne prend pas plus de temps. Cela vient simplement naturellement
      Bien sûr, dans des langages comme C++, Java, C#, Python, Go ou JavaScript, où la modélisation des données demande beaucoup de démarches conscientes, cela prend plus de temps

  • « J’ai maintenant une devise courte et percutante qui résume ce que le design guidé par les types signifie pour moi, et le mieux, c’est qu’elle ne tient qu’en trois mots : Parse, don’t validate. »
    Ma devise serait plutôt proche de valider toujours uniquement dans un constructeur unique. Peu importe qu’il s’agisse d’une fonction constructeur
    Ainsi, un objet invalide ne peut tout simplement pas exister, et l’on dispose toujours d’une source unique de vérité. Si l’on veut modifier un objet, on peut implémenter cela en rappelant le même constructeur pour créer un nouvel état

    • Ce n’est pas la même chose
      L’idée centrale est que, si l’on se contente de valider, cette information disparaît par la suite
      Par exemple, le simple fait de vérifier qu’un int est positif n’apporte qu’un bénéfice limité. Si l’on ne parse pas cette valeur comme un entier positif, cette information ne subsiste pas ensuite au niveau du type. Il en va de même pour un tableau ou une liste non vide : le consommateur en aval peut devoir vérifier à nouveau que la liste n’est réellement pas vide
      Ce type d’information ne peut pas toujours être encodé dans un objet ou un constructeur

  • Ressource liée : Making Impossible States Impossible de Richard Feldman
    https://www.youtube.com/watch?v=IcgmSRJHu_8

  • Il y a déjà eu de bonnes discussions auparavant
    https://news.ycombinator.com/item?id=35053118
    https://news.ycombinator.com/item?id=21476261

  • Chaque fois que ce sujet revient, je pense à la section 5 de https://cr.yp.to/qmail/guarantee.html. On y trouve des phrases comme « ne parsez pas » et « dans l’univers de l’informatique, il existe deux types d’interfaces de commande : les bonnes interfaces et les interfaces utilisateur »
    Si je donnais un cours sur la programmation à moyenne échelle, plutôt que sur la petite ou la grande échelle, j’aimerais demander aux étudiants de rédiger un essai comparant et opposant ces propositions. Chacune offre quelque chose à apprendre, et elles ne sont peut-être pas aussi contradictoires qu’elles en ont l’air au premier abord

  • Cela me rappelle un commentaire que j’avais lu au milieu des années 2000, pendant la mode XML. Il disait que si de nombreuses organisations avaient implémenté des langages spécifiques à un domaine, y compris des langages de configuration, en XML, c’était probablement parce que XML fournissait un parseur et que la plupart des organisations ne voulaient pas écrire le leur
    Je ne sais pas pourquoi les gens n’aimaient pas écrire des parseurs. Écrire un parseur n’est pas si difficile, et c’est même assez amusant

  • C’est l’un de mes articles préférés parmi ceux que j’ai lus au cours de ma carrière. J’ai souvent vu des gens lire seulement le titre et supposer que parsing et validation seraient somehow mutuellement exclusifs, mais en réalité ce n’est pas le cas. Le parsing inclut souvent la validation
    Ce point est abordé dans la section « Use abstract datatypes to make validators ‘look like’ parsers » de l’article
    Cela relève du même registre que l’idée d’éviter l’obsession des types primitifs