URL: https://linuxfr.org/users/lovasoa/journaux/tous-les-parsers-json-sont-mauvais Title: Tous les parsers JSON sont mauvais Authors: lovasoa Date: 2017年10月22日T21:59:54+02:00 License: CC By-SA Tags: parsing, json, programmation, programmation_fonctionnelle, bug et parser Score: 47 Introduction ============ Ce weekend, je me suis intéressé au langage JSON, aux parsers JSON par défaut de plusieurs langages de programmation, et j'ai fait des découvertes intéressantes. Je pense que le langage JSON n'est plus à présenter à personne, mais au cas où vous vivriez dans une grotte depuis 1999, petit résumé rapide: JSON est un format de données, très utilisé notamment sur le web, et qui a l'avantage d'être plutôt compact, assez lisible par les êtres humains, et surtout implémenté dans tous les langages de programmation courants. Une valeur JSON peut être un nombre, un booléen, une chaîne de caractères, la valeur NULL, un tableau de valeurs JSON, ou un tableau associatif (aussi appelé Map, ou objet) associant des chaînes de caractères à des valeurs JSON. Voici un petit exemple de document JSON: {"clef": "valeur", "un nombre": 42, "tableau": [1,2,3], "objet imbrique": {"a" : "b"} } Pour plus de détails, le site [json.org](http://json.org/) donne la définition formelle du langage et de nombreux détails intéressants, dont une impressionnante liste d'implémentation dans différents langages. Énigme ========== Commençons par une énigme, un défi: Ce journal va parler d’un petit fichier json de 27Ko, qui est parfaitement valide selon la spécification de json, et qu’aucun des parsers json les plus courants n’arrive à parser. Pouvez-vous deviner comment construire un tel fichier ? Sur quel principe ? Comment écrire un parser ======================== Si vous ne trouvez pas, prenez quelques secondes pour imaginer comment vous implémenteriez un *parser* pour JSON dans votre langage de programmation préféré. C’est-à-dire une fonction qui prend en entrée un flux de caractères représentant un objet JSON et retourne un objet facilement manipulable dans votre langage de programmation qui représente le même document. Allez-y, réfléchissez aux grandes lignes de votre programme... Si vous avez déjà travaillé sur des compilateurs ou autres parsers complexes, vous avez peut-être pensé utiliser un [générateur de compilateur](https://fr.wikipedia.org/wiki/Compilateur_de_compilateur). Sinon, vous avez probablement pensé à un programme qui a la même forme que [le parser JSON de la bibliothèque standard de python](https://github.com/python/cpython/blob/master/Lib/json/decoder.py): 1. Une fonction principale qui peut parser n’importe quelle valeur JSON. Cette fonction peut parser toutes les valeurs brutes comme les nombres, les booléens ou la valeur nulle. 2. Mais lorsque cette fonction rencontre le caractère ‘[‘ (début d’un tableau), elle appelle une fonction spécialisée qui parse le contenu d’un tableau. De même pour le caractère ‘{‘, on créer une fonction capable de parser le contenu d’un objet. 3. La fonction qui parse le contenu d’un tableau va s’assurer que les valeurs sont bien séparées par des virgules, que le tableau est bien terminé par le caractère ‘]’, mais pour parser les valeurs contenues dans le tableau elles-mêmes, elle va faire appel à la fonction définie au début, qui peut parser n’importe quelle valeur JSON. Cette approche permet de structurer son code de manière claire et expressive, avec des fonctions spécialisées pour les types complexes de JSON. Il est facile de se représenter la manière dont le code fonctionne : si on a un objet dans un tableau, par exemple, alors notre fonction de parsing de tableau est appelée, puis elle appelle notre fonction de parsing d’objet. Problème ---------- Cependant, cette approche a un inconvénient. C’est une approche dite récursive, où une fonction peut s’appeler elle-même (dès qu’une structure JSON est imbriquée dans une autre). Notre ordinateur a une pile d’exécution de taille limitée, c’est-à-dire que seul un nombre limité de fonctions peuvent être actives en même temps. Dès qu’une fonction en appelle une autre, cela occupe de la place dans la pile d’exécution, et ce jusqu’à ce que la fonction appelée retourne une valeur. Dans notre cas, quand nous voulons parser par exemple un tableau qui contient un tableau qui contient un tableau, nous occupons au minimum trois places dans la pile d’exécution. Comme sa taille est très limitée, au bout d’un certain nombre de tableaux imbriqués, on n’a plus de place dans la pile pour appeler une nouvelle fonction, et une erreur est levée. Implication ------------- La réponse à l’énigme posée plus haut est donc très simple. Il suffit de créer un fichier json qui contient beaucoup de structures imbriquées. La manière la plus succincte de créer un tel fichier est donc simplement de concaténer un grand nombre de ‘[‘ avec un grand nombre de ‘]’. C’est-à-dire de créer un tableau qui contient un tableau qui contient [...] qui contient un tableau vide. Et combien de tableaux imbriqués faut-il pour faire planter un parser JSON ? ET bien dans certains langages, très peu. J’ai créé un petit projet sur github pour mesurer les limites de différentes bibliothèques de parsing JSON dans différents langages de programmetion : [github.com/lovasoa/bad_json_parsers](https://github.com/lovasoa/bad_json_parsers). Et les résultats sont très variés selon les langages, de 100 arrays imbriqués maximum en ruby (c’est-à-dire qu’il peut planter sur un fichier de tout juste 202 octets), à 13786 en C++ avec [nlohmann::json](https://github.com/nlohmann/json). De tous les langages testés, seul haskell sort son épingle du jeu, puisqu’il optimise correctement les appels récursifs. Je vous encourage à faire des tests avec votre langage/bibliothèque préférés et à poster vos résultats sur ce dépôt github ! Conclusion ============== Qu’en pensez-vous ? Est-ce juste un cas limite inintéressant ? Ou faut-il réécrire la grande majorité des parsers JSON pour adopter une approche sans appels de fonction récursifs ?

AltStyle によって変換されたページ (->オリジナル) /