Journal Tous les parsers JSON sont mauvais

Posté par lovasoa (site web personnel) le 22 octobre 2017 à 21:59. Licence CC By‑SA.

Étiquettes :

oct.

2017

Sommaire

Introduction
Énigme
Comment écrire un parser
- Problème
- Implication
Conclusion

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 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.

Sinon, vous avez probablement pensé à un programme qui a la même forme que le parser JSON de la bibliothèque standard de python:

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.
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.
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.

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.

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 ?

# Pas convaincu

Posté par Kalenx le 22 octobre 2017 à 22:41. Évalué à 10.
Pour ce genre de cas, il faut considérer deux possibilités :
1. Ces limitations risquent-elles de faire échouer le décodage d'un code JSON valable?
2. Dans le cas d'un code non-valable (autrement dit, conçu expressément pour faire échouer le parser), est-ce que cela constitue une faille de sécurité? Cette faille peut principalement prendre deux formes : A) permettre l'accès à une zone non autorisée de la mémoire voire, pire, une exécution de commande à distance ou B) crasher le parser et provoquer à la longue un DDoS.
Personnellement, je réponds à (1) par la négative. Plus de 100 niveaux d'intrication au minimum avant un crash (on parle de près de 1000 pour Python) n'est pas limitatif pour l'extrême majorité des usages.
En ce qui concerne (2), je pense que 2A est fort peu probable (à moins qu'un langage soit assez mal conçu pour laisser aller un débordement de pile sans conséquence). 2B est possible, mais il présuppose que l'attaquant contrôle le JSON parsé, ce qui n'est pas forcément évident.

En ce qui concerne la résolution, une possibilité éventuelle est de réécrire le code sous la forme d'une boucle et d'une pile explicite. Au lieu d'appeler récursivement une nouvelle fonction à chaque ouverture de liste ou de dictionnaire rencontrée, on ajoute le symbole d'ouverture sur la pile. Lorsque l'on rencontre un symbole de fermeture, on dépile et on s'assure que le précédent symbole d'ouverture correspond bien (sinon c'est une erreur de syntaxe). À la fin du décodage, la pile devrait être vide (sinon c'est toujours une erreur). La taille de cette pile peut être dynamiquement agrandie au fil de l'exécution.

Le code résultant est moins joli et plus difficilement extensible cependant. Je pense que la plupart des implémentations ont cependant fait le choix de la clarté. L'important est que l'erreur éventuelle soit claire. Par exemple, dans le cas de Python (je n'ai pas testé les autres), une exception est levée :

RecursionError: maximum recursion depth exceeded while decoding a JSON array from a unicode string

Ce qui est très clair, facilement attrapable si besoin est par le programmeur d'une section critique d'une application et ne cause aucun effet de bord indésirable.

Je ne sais pas si c'est la même chose pour tous les parsers, mais de manière générale je ne m'inquièterais pas trop de ce problème.
- [^] # Re: Pas convaincu
  
  Posté par lovasoa (site web personnel) le 22 octobre 2017 à 23:37. Évalué à 7.
  Bien sûr, le titre était un peu aguicheur, tous les persers json ne sont pas mauvais, et dans la plupart des cas, le problème évoqué ici n’est pas limitant.
  
  Cependant, je pense que le souci du déni de service et de la faille de sécurité peuvent être réels. En tout cas, il est bon que les développeurs soient au courant des limitations des bibliothèques utilisées et des erreurs qui peuvent être levées. Beaucoup de bibliothèques ne mentionnent pas cette limitation de niveaux d’imbrication, et ne lèvent pas une erreur du bon type lorsque le cas se présente.
  
  Par exemple, en python, pour parser du JSON et catcher une erreur éventuelle, on fait:
```
try: json.loads(s)
except json.JSONDecodeError: print("JSON invalide")
```
  Un tel code donne l'impression qu'aucune erreur ne pourra être levée même sur une chaîne de caractères qui contient du JSON invalide. Pourtant, json.loads peut retourner une RecursionError qui n'est pas une JSONDecodeError, et planter.
  
  Et bien sûr, on peut refaire les parsers en utilisant une pile explicite, mais on se retrouve avec du code encore moins compréhensible. Et quand on voit par exemple le parser de python, il y a déjà tellement de cas à traiter et de micro-optimisations que le code n'est pas très clair. Je pense que la bonne solution est d'utiliser des générateurs de parser, qui ont une grammaire explicite et claire, et qui peuvent générer des parsers non-récursifs.
  - [^] # Re: Pas convaincu
    
    Posté par Kalenx le 23 octobre 2017 à 09:04. Évalué à 4.
    
    La documentation Python de ce module indique :
    
    JSONDecodeError will be raised if the given JSON document is not valid.
    
    Or, le document est valide, lancer cette exception serait donc techniquement ne pas respecter l'interface promise au développeur. Ceci étant dit, oui, la possibilité d'une RecursionError devrait être au moins évoquée dans la doc.
    
    Il reste que dans la plupart des langages interprétés, il y a certaines erreurs qui peuvent presque toujours se produire. En Python, les MemoryError en sont de bons exemples. Même si dans 99.9% des cas, cette erreur n'est lancée que si l'utilisateur fait quelque chose d'incorrect, elle peut techniquement se produire dans n'importe quelle opération.
    
    S'il est critique d'attraper toutes les exceptions, alors le modèle except ExceptionPrecise (pour les cas prévus) suivi de except (tout court), suivi éventuellement de else et finally est probablement le meilleur à adopter. Mais dans tous les cas, ce genre d'exceptions "système" peuvent toujours jouer des tours et je ne pense pas que ce soit le rôle de chaque module de le considérer.
    - [^] # Re: Pas convaincu
      
      Posté par freem le 23 octobre 2017 à 11:46. Évalué à 2.
      
      En Python, les MemoryError en sont de bons exemples. Même si dans 99.9% des cas, cette erreur n'est lancée que si l'utilisateur fait quelque chose d'incorrect, elle peut techniquement se produire dans n'importe quelle opération.
      
      Voir ne pas se produire du tout et avoir l'OOM killer qui entre dans la danse sur pas mal de distributions basées sur Linux, vu que par défaut sur Debian, le kernel est optimiste et considère que les applications n'ont pas besoin de toute la mémoire qu'ils réclament.
      - [^] # Re: Pas convaincu
        
        Posté par lasher le 20 novembre 2017 à 15:22. Évalué à 2.
        
        En même temps, quand tu vois que GNU sort alloue (allouait ?) des GIGA octets histoire d'avoir toujours de la place quand il en a besoin (et qu'il s'appuie sur l'allocation de pages à la demande effectuée par le noyau en pratique), Debian a bien raison…
  - [^] # Re: Pas convaincu
    
    Posté par feth le 25 octobre 2017 à 09:30. Évalué à 10.
    
    Je ne pense pas que le déni de service en utilisant JSON soit une hypothèse plausible.
    En effet, la licence de JSON précise le point suivant :
    
    The Software shall be used for Good, not Evil.
    
    Dont je vais oser une traduction brouilonne vers le français.
    
    Le logiciel sera utilisé pour le Bien et non pour le Mal.
    
    Du coup, paf, infraction à la licence, contrefaçon, piratage, c'est inconcevable, non ?
    
    Alors on me glisse dans l'oreillette que des licences «pour faire le mal» ont été concédées à de grandes entreprises, mais jai vérifié, elles ont toutes un comité d'éthique.
    - [^] # Re: Pas convaincu
      
      Posté par Elfir3 le 26 octobre 2017 à 13:26. Évalué à 3.
      
      Alors on me glisse dans l'oreillette que des licences «pour faire le mal» ont été concédées à de grandes entreprises, mais jai vérifié, elles ont toutes un comité d'éthique.
      
      Parfois, elles ont aussi un département légal qui demande de retirer le logiciel pour cause de «licence trop floue».
- [^] # Re: Pas convaincu
  
  Posté par totof2000 le 23 octobre 2017 à 09:45. Évalué à 8.
  
  En ce qui concerne (2), je pense que 2A est fort peu probable (à moins qu'un langage soit assez mal conçu pour laisser aller un débordement de pile sans conséquence). 2B est possible, mais il présuppose que l'attaquant contrôle le JSON parsé, ce qui n'est pas forcément évident.
  
  Question : un JSON envoyé à une API Rest par exemple, est-ce que tu ranges ça dans la catégorie "controlé par l'attaquant" ?
- [^] # Re: Pas convaincu
  
  Posté par karl.forner le 23 octobre 2017 à 11:51. Évalué à 1.
  
  Personnellement, je réponds à (1) par la négative. Plus de 100 niveaux d'intrication au minimum avant un crash (on parle > de près de 1000 pour Python) n'est pas limitatif pour l'extrême majorité des usages.
  
  Pas d'accord sur ce point. Une structure de graphe implémentée avec des tableaux ou dictionnaires peut rapidement dépasser 100 niveaux.
  - [^] # Re: Pas convaincu
    
    Posté par Christophe "CHiPs" PETIT (site web personnel) le 23 octobre 2017 à 13:49. Évalué à 3.
    
    Mais le cas d'usage le plus courant pour du JSON à ma connaissance est pour représenter une liste d'objets…
# C'est pas pour me la pêter mais...

Posté par Babelouest (site web personnel) le 22 octobre 2017 à 22:50. Évalué à 3.
En langage C avec le programme suivant qui utilise la bibliothèque Jansson chère à mes yeux:
```
#include <jansson.h>

int main(int argc, char ** argv) {
  json_t * j_test = json_loads(argv[1], JSON_DECODE_ANY, NULL);
}
```
J'arrive au résultat suivant:
```
moi@localhost:~/workspace/bad_json_parsers$ ./test_parser.sh parser_c/parser_c
100000
```
Et si j'augmente la limite du script à 1000000, j'obtins 1000000 aussi.

Après, est-ce que les cas limites sont gages d'une bonne qualité d'un langage? Je ne me sens pas assez a l'aise pour répondre…
- [^] # Re: C'est pas pour me la pêter mais...
  
  Posté par lovasoa (site web personnel) le 22 octobre 2017 à 23:40. Évalué à 1.
  
  Ah, voilà un bon parser ! Et comment est-il structuré, pour éviter le problème des appels récursifs ? Il y a une grosse boucle principale et une pile qui représente l'état actuel ?
  - [^] # Re: C'est pas pour me la pêter mais...
    
    Posté par Babelouest (site web personnel) le 22 octobre 2017 à 23:54. Évalué à 2. Dernière modification le 22 octobre 2017 à 23:56.
    
    Pas évident à analyser comme ca mais je dirais qu'il se prend pas la tête et fait du bon vieux récursif tel que Dieu l'a créé pour: https://github.com/akheron/jansson/blob/master/src/load.c
    
    d'abord https://github.com/akheron/jansson/blob/master/src/load.c#L865
    puis https://github.com/akheron/jansson/blob/master/src/load.c#L769
    
    et rebelote
    
    Mais… en C quoi…
    
    Edit: voilà, tu l'as vu aussi
- [^] # Re: C'est pas pour me la pêter mais...
  
  Posté par lovasoa (site web personnel) le 22 octobre 2017 à 23:46. Évalué à 2.
  
  Bon, je suis allé regarder le code, et il semblerait qu'il utilise des appels récursifs, comme les autres:
  
  La fonction parse_array appelle parse_value: https://github.com/akheron/jansson/blob/master/src/load.c#L780 .
  Et la fonction parse_value appelle parse_array: https://github.com/akheron/jansson/blob/master/src/load.c#L866 .
- [^] # Re: C'est pas pour me la pêter mais...
  
  Posté par lovasoa (site web personnel) le 23 octobre 2017 à 00:07. Évalué à 6. Dernière modification le 23 octobre 2017 à 00:11.
  Il faut lire le json depuis l'entrée standard. Le programme correct à utiliser est:
```
#include <stdio.h>

int main(int argc, char ** argv) {
  json_t* j_test = json_loadf(stdin, JSON_DECODE_ANY, NULL);
  return j_test == NULL ? 1 : 0;
}
```
  Et le résultat: 2048 niveaux d'imbrication maximum. Donc pas le moins bon, mais pas le meilleur non plus…
  
  Je l'ai ajouté sur le github.
  - [^] # Re: C'est pas pour me la pêter mais...
    
    Posté par Babelouest (site web personnel) le 23 octobre 2017 à 00:13. Évalué à 3.
    
    Anéfé, j'avais pas du tout compris comment ca marchait ton script en fait, au temps pour moi :p
  - [^] # Re: C'est pas pour me la pêter mais...
    
    Posté par Babelouest (site web personnel) le 07 novembre 2017 à 20:08. Évalué à 2.
    
    Après avoir ouvert un bug sur le projet, je me suis vu répondre que le problème était déjà réglé.
    
    En fait, la profondeur maximale de 2048 pour le parseur est décidée arbitrairement et n'était pas mentionnée dans la doc…
    - [^] # Re: C'est pas pour me la pêter mais...
      
      Posté par Babelouest (site web personnel) le 07 novembre 2017 à 20:27. Évalué à 2.
      
      Et je me réponds à moi-même, en enlevant le bridage du parseur, j'arrive à un score de 209630 en testant sur un RPI2…
# "Le JSON, c'est pour les hipsters"

Posté par Enzo Bricolo 🛠⚙🛠 le 23 octobre 2017 à 07:42. Évalué à 4.

Les vrais professionnels échangent du XML … et les gogols échangent encore du CSV.
- [^] # Re: "Le JSON, c'est pour les hipsters"
  
  Posté par redo_fr le 23 octobre 2017 à 08:52. Évalué à 6.
  
  Tsss…
  
  Le XML n'est pas pour les humains
  
  Et je suis bien d'accord! :-)
  
  Celui qui pose une question est bête cinq minutes, celui qui n'en pose pas le reste toute sa vie.
  - [^] # Re: "Le JSON, c'est pour les hipsters"
    
    Posté par Enzo Bricolo 🛠⚙🛠 le 24 octobre 2017 à 01:15. Évalué à 1.
    
    Quand j'écris "les professionnels échangent du XML" … je n'ai jamais dit qu'ils le lisaient (et encore moins avec notepad). Si jamais un professionnel doit éditer un XML, il va le faire à l'aide d'un éditeur qui sait correctement éditer un XML.
    - [^] # Re: "Le JSON, c'est pour les hipsters"
      
      Posté par gnumdk (site web personnel) le 24 octobre 2017 à 08:33. Évalué à 2.
      
      Donc Google, Apple, Spotify, … Ce ne sont pas des professionnels?
      
      Moi j'aurais plutôt dit certains professionnels sont toujours en retard…
      - [^] # Re: "Le JSON, c'est pour les hipsters"
        
        Posté par Enzo Bricolo 🛠⚙🛠 le 25 octobre 2017 à 00:45. Évalué à 2.
        
        chez Google je lis "XML est un format d'informations structuré relativement abouti utilisé pour l'échange de données. Bien qu'il ne soit pas aussi léger que JSON, le format XML prend en charge davantage de langages et fournit des outils puissants."
        
        Par ailleurs, leurs factures dématérialisées sont en XML …
        
        "Le JSON, c'est pour les hipsters" est un extrait de fortune de la tribune … ceci dit, je n'ai toujours pas vu de demande pertinente au boulot pour des échanges propres en JSON …
- [^] # Re: "Le JSON, c'est pour les hipsters"
  
  Posté par Gof (site web personnel) le 23 octobre 2017 à 08:54. Évalué à 7.
  
  Tu es dépassé. JSON c'est mainstream. Les hipsters utilisent YAML
  
  (D'ailleurs, les parseurs YAML (qui parsent aussi le JSON) ne semblent pas avoir été testés par l'auteur du journal.)
  - [^] # Re: "Le JSON, c'est pour les hipsters"
    
    Posté par damaki le 23 octobre 2017 à 11:32. Évalué à 8.
    
    Les parseurs yaml sont pas dans un état fou non plus. Celui utilisé par ansible, par exemple, ne sait toujours pas te dire précisément la nature et l'emplacement d'une erreur de syntaxe. Tout comme dans pas mal de parseurs json, d'ailleurs. En XML, ça marche à tous les coups.
    J'me souvent ce temps rigolo où le simple fait de mettre une tabulation dans un yml faisait péter un plomb au parseur en java et t'indiquait pas l'emplacement de l'erreur. Les mainteneurs comprenaient pas pourquoi c'était un problème. C'était la bonne ambiance.
    - [^] # Re: "Le JSON, c'est pour les hipsters"
      
      Posté par Pilou le 23 octobre 2017 à 23:29. Évalué à 1.
      Celui utilisé par ansible, par exemple, ne sait toujours pas te dire précisément la nature et l'emplacement d'une erreur de syntaxe.
      
      Cela a été amélioré avec la version 2.0 d'Ansible. Par exemple avec le playbook ci-dessous:
      
      - hosts: 'localhost' gather_facts: 'no' tasks: - debug: msg: 'test1' vars: key: 'value' - invalid: 'invalid' - debug: msg: 'test2'
      
      l'emplacement de l'erreur de syntaxe est précisé dans le message d'erreur:
      
      ERROR! Syntax Error while loading YAML. The error appears to have been in 'test.yml': line 8, column 9, but may be elsewhere in the file depending on the exact syntax problem. The offending line appears to be: key: 'value' - invalid: 'invalid' ^ here
      - [^] # Re: "Le JSON, c'est pour les hipsters"
        
        Posté par damaki le 25 octobre 2017 à 11:58. Évalué à 2.
        
        but may be elsewhere in the file depending on the exact syntax problem.
        
        Je tombe souvent sur ce cas là :'-(
  - [^] # Yaml est une usine à gaz
    
    Posté par freem le 23 octobre 2017 à 12:00. Évalué à 4.
    
    Pour avoir utilisé libyaml, le truc utilisé par le module de python, ben, je ne conseille pas d'utiliser ce truc, en tout cas pas si on veut de la performance et de la stabilité…
    Je me suis tapé des segfaults que j'ai pu corriger en moins de 4H (patch envoyé à l'époque en même temps que le rapport de bug, je ne suis pas certain que le rapport ait été accepté, vu que le dépôt semblait mort. Du coup, itou pour le patch logiquement). Et non, ce n'était pas un cas d'utilisation à la con, c'était même un truc très simple.
    Pour la performance, quand on commence a hijacker malloc pour qu'il alloue toujours au moins 1 octet, ça crains, et dans la pratique, quand mon code tournait, le CPU faisait du malloc de petites quantités de RAM en permanence, et prenait plusieurs minutes pour parser un fichier de quelques kibi octets.
    
    Du coup, j'ai cherché d'autres lib qui correspondraient à mes standards et dont le code me semblait assez propre. Je n'ai rien trouvé de satisfaisant.
    Conséquence, j'ai commencé à lire le standard de yaml, et j'ai compris l'état de l'existant: certes, le yaml, c'est joli et lisible… mais une horreur à traiter, les règles sont floues et multiples et de mémoire, le comportement quand on rencontre un token dépend du contexte…
  - [^] # Re: "Le JSON, c'est pour les hipsters"
    
    Posté par laurentb (site web personnel) le 23 octobre 2017 à 16:07. Évalué à 5.
    
    Non ça fait longtemps qu'ils sont passés à TOML.
  - [^] # Re: "Le JSON, c'est pour les hipsters"
    
    Posté par Maxime (site web personnel) le 23 octobre 2017 à 23:14. Évalué à 2.
    
    java.lang.StackOverflowError avec org.yaml.snakeyaml.parser (Java) malheureusement :)
- [^] # Re: "Le JSON, c'est pour les hipsters"
  
  Posté par ndv le 23 octobre 2017 à 09:06. Évalué à 2. Dernière modification le 23 octobre 2017 à 09:06.
  
  Et BSON alors ? Binary Encoded JSON
- [^] # Re: "Le JSON, c'est pour les hipsters"
  
  Posté par gUI (Mastodon) le 23 octobre 2017 à 09:24. Évalué à 10.
  
  "Le XML c'est comme la violence. Si il ne résoud pas tous tes problèmes, c'est que tu ne l'as pas assez utilisé."
  
  En théorie, la théorie et la pratique c'est pareil. En pratique c'est pas vrai.
- [^] # Re: "Le JSON, c'est pour les hipsters"
  
  Posté par devnewton 🍺 (site web personnel) le 23 octobre 2017 à 10:54. Évalué à 2. Dernière modification le 23 octobre 2017 à 10:57.
  Alors qu'il faudrait utiliser Pyx:
```
    (books
    -\n
    (book
    Atype hardback
    -\n
    (title
    -Atlas Shrugged
    )title
    -\n
    (author
    -Ayn Rand
    )author
    -\n
    (isbn
    Aid 1
    -0525934189
    )isbn
    -\n
    )book
    -\n
    )books
```
  Le post ci-dessus est une grosse connerie, ne le lisez pas sérieusement.
# Petit lien en rapport

Posté par Bruno Michel (site web personnel) le 23 octobre 2017 à 08:59. Évalué à 10.

Parsing JSON is a minefield
- [^] # Re: Petit lien en rapport
  
  Posté par xseticon le 23 octobre 2017 à 13:38. Évalué à 1.
  
  Anecdote : le rendu de ce site est horrible sous Firefox 52.4.0 (ça semble fonctionner sous Chromium).
  - [^] # Re: Petit lien en rapport
    
    Posté par Benoît Sibaud (site web personnel) le 23 octobre 2017 à 13:42. Évalué à 6.
    
    Je n'ai pas noté de souci avec un Firefox 56.
  - [^] # Re: Petit lien en rapport
    
    Posté par Chris K. le 23 octobre 2017 à 14:00. Évalué à 4.
    
    J'ai aussi un firefox ESR en 52.4.0 et je n'ai pas de soucis non plus : c'est le même rendu que sous chromium.
    Tu aurais pas un module qui te mets la zone ?
  - [^] # Re: Petit lien en rapport
    
    Posté par Le Gab le 25 octobre 2017 à 12:41. Évalué à 1.
    
    Anecdote : le rendu de ce site est horrible sous Firefox 52.4.0 (ça semble fonctionner sous Chromium).
    
    T'as sans doute un greffon qui altère la page.
    ublock? adblock? disconnect? etc,…
    
    Démarre Firefox depuis un nouveau profile et retest le lien:
    firefox -ProfileManager
    - [^] # Re: Petit lien en rapport
      
      Posté par xseticon le 27 octobre 2017 à 15:49. Évalué à 1.
      
      J'ai testé avec firefox -safe-mode et le rendu du site est toujours horrible …
# Comportement conforme

Posté par Eric Vialas le 23 octobre 2017 à 09:03. Évalué à 7.

La RFC 7159 précise bien (Chapitre 9) que les parseurs peuvent imposer des limitations, en particulier sur la profondeur d'imbrication.

An implementation may set limits on the size of texts that it accepts. An implementation may set limits on the maximum depth of nesting. An implementation may set limits on the range and precision of numbers. An implementation may set limits on the length and character contents of strings.

Il serait, a mon sens, plus pertinent de tester le comportement des implémentations lorsque les limites sont atteintes.
# Et en Java ?

Posté par Glandos le 23 octobre 2017 à 09:37. Évalué à 1.

Donc voilà, j'ai fait le même test en Java : https://gist.github.com/Glandos/8c42a5766eecfbd177cb473bbeb6a17a

Et donc on a :
javac TestRecursion.java TestRecursion.java:101: error: error while writing TestRecursion.TestRecursion0.TestRecursion1.TestRecursion2.TestRecursion3.TestRecursion4.TestRecursion5.TestRecursion6.TestRecursion7.TestRecursion8.TestRecursion9.TestRecursion10.TestRecursion11.TestRecursion12.TestRecursion13.TestRecursion14.TestRecursion15.TestRecursion16.TestRecursion17.TestRecursion18.TestRecursion19.TestRecursion20.TestRecursion21.TestRecursion22.TestRecursion23.TestRecursion24.TestRecursion25.TestRecursion26.TestRecursion27.TestRecursion28.TestRecursion29.TestRecursion30.TestRecursion31.TestRecursion32.TestRecursion33.TestRecursion34.TestRecursion35.TestRecursion36.TestRecursion37.TestRecursion38.TestRecursion39.TestRecursion40.TestRecursion41.TestRecursion42.TestRecursion43.TestRecursion44.TestRecursion45.TestRecursion46.TestRecursion47.TestRecursion48.TestRecursion49.TestRecursion50.TestRecursion51.TestRecursion52.TestRecursion53.TestRecursion54.TestRecursion55.TestRecursion56.TestRecursion57.TestRecursion58.TestRecursion59.TestRecursion60.TestRecursion61.TestRecursion62.TestRecursion63.TestRecursion64.TestRecursion65.TestRecursion66.TestRecursion67.TestRecursion68.TestRecursion69.TestRecursion70.TestRecursion71.TestRecursion72.TestRecursion73.TestRecursion74.TestRecursion75.TestRecursion76.TestRecursion77.TestRecursion78.TestRecursion79.TestRecursion80.TestRecursion81.TestRecursion82.TestRecursion83.TestRecursion84.TestRecursion85.TestRecursion86.TestRecursion87.TestRecursion88.TestRecursion89.TestRecursion90.TestRecursion91.TestRecursion92.TestRecursion93.TestRecursion94.TestRecursion95.TestRecursion96.TestRecursion97.TestRecursion98.TestRecursion99: /home/adrien/TestRecursion$TestRecursion0$TestRecursion1$TestRecursion2$TestRecursion3$TestRecursion4$TestRecursion5$TestRecursion6$TestRecursion7$TestRecursion8$TestRecursion9$TestRecursion10$TestRecursion11$TestRecursion12$TestRecursion13$TestRecursion14$TestRecursion15$TestRecursion16$TestRecursion17$TestRecursion18$TestRecursion19$TestRecursion20$TestRecursion21$TestRecursion22$TestRecursion23$TestRecursion24$TestRecursion25$TestRecursion26$TestRecursion27$TestRecursion28$TestRecursion29$TestRecursion30$TestRecursion31$TestRecursion32$TestRecursion33$TestRecursion34$TestRecursion35$TestRecursion36$TestRecursion37$TestRecursion38$TestRecursion39$TestRecursion40$TestRecursion41$TestRecursion42$TestRecursion43$TestRecursion44$TestRecursion45$TestRecursion46$TestRecursion47$TestRecursion48$TestRecursion49$TestRecursion50$TestRecursion51$TestRecursion52$TestRecursion53$TestRecursion54$TestRecursion55$TestRecursion56$TestRecursion57$TestRecursion58$TestRecursion59$TestRecursion60$TestRecursion61$TestRecursion62$TestRecursion63$TestRecursion64$TestRecursion65$TestRecursion66$TestRecursion67$TestRecursion68$TestRecursion69$TestRecursion70$TestRecursion71$TestRecursion72$TestRecursion73$TestRecursion74$TestRecursion75$TestRecursion76$TestRecursion77$TestRecursion78$TestRecursion79$TestRecursion80$TestRecursion81$TestRecursion82$TestRecursion83$TestRecursion84$TestRecursion85$TestRecursion86$TestRecursion87$TestRecursion88$TestRecursion89$TestRecursion90$TestRecursion91$TestRecursion92$TestRecursion93$TestRecursion94$TestRecursion95$TestRecursion96$TestRecursion97$TestRecursion98$TestRecursion99.class: Nom de fichier trop long public class TestRecursion99 { ^ 1 errorJ'ai pas trouvé de limites écrites quelque part concernant cette syntaxe.

# D'autres versions

Posté par rewind (Mastodon) le 23 octobre 2017 à 10:53. Évalué à 5.

En go, ça passe

package main

import (
    "encoding/json"
    "log"
    "os"
)

func main() {
    dec := json.NewDecoder(os.Stdin)

    for {
        var v interface{}
        if err := dec.Decode(&v); err != nil {
            log.Println(err)
            return
        }
    }
}

En C++ avec RapidJson, ça casse vers 74000 (mais il y a moyen d'utiliser une version itérative, j'ai pas encore trouvé comment, je posterai une mise à jour) :

#include <rapidjson/document.h>
#include <rapidjson/filereadstream.h>
#include <cstdio>

int main() {
  char readBuffer[2048];
  rapidjson::FileReadStream frs(stdin, readBuffer, sizeof(readBuffer));

  rapidjson::Document d;
  d.ParseStream(frs);

  return 0;
}

[^] # Re: D'autres versions

Posté par UnixJunkie le 23 octobre 2017 à 13:16. Évalué à 10.

En go, ça passe

A croire que plus c'est go plus ça passe…
- [^] # Re: D'autres versions
  
  Posté par Axioplase ıɥs∀ (site web personnel) le 30 octobre 2017 à 13:55. Évalué à 2.
  
  Trop go, passera pas.

[^] # Re: D'autres versions

Posté par rewind (Mastodon) le 23 octobre 2017 à 13:39. Évalué à 3.

En fait, pas grand chose à faire de plus pour avoir une version itérative avec rapidjson:

#include <rapidjson/document.h>
#include <rapidjson/filereadstream.h>
#include <cstdio>

int main() {
  char readBuffer[2048];
  rapidjson::FileReadStream frs(stdin, readBuffer, sizeof(readBuffer));

  rapidjson::Document d;
  d.ParseStream<rapidjson::kParseIterativeFlag>(frs);

  return 0;
}

# La récursion serait le seul problème ?

Posté par damaki le 23 octobre 2017 à 12:01. Évalué à 2.
Si on enlève la récursion dans le code, ça ne résout pas totalement le soucis. On met alors plus de temps à atteindre la limite, puisque c'est la taille max de la pile de stockage du chemin vers le nœud actuellement traité, mais la limite existe toujours.
J'ai un peu de mal à comprendre cette fixation sur ce point, alors que les parseurs json ont des points d'incompatibilité plus gênants que ça. J'sais plus avec quel parseur c'était, mais j'ai souvenir des champs mis volontairement à null virés de l'arbre en mémoire, parce qu'allez vous faire voir avec les standards.
Avec en entrée
```
{ "toto": null }
```
ça donnait en sortie :
```
{}
```
Il fallait alors activer un flag pour être compatible avec le standard.
Sans parler des fonctionnalités utiles mais pas dans le standard pour des raisons dogmatiques, comme les commentaires. Vu que c'est pratique, forcément, il y a des parseurs qui l'intègrent. Et quand on tombe sur un autre parseur pas compatible, on déchante.

Ceci dit, ça reste toujours moins pire que le CSV qui est l'absence totale de standard.
- [^] # HS CSV
  
  Posté par Zenitram (site web personnel) le 23 octobre 2017 à 12:40. Évalué à 4.
  
  Ceci dit, ça reste toujours moins pire que le CSV qui est l'absence totale de standard.
  
  Pas "standard" ("This memo provides information for the Internet community. It does not specify an Internet standard of any kind." explicite), mais bon "absence totale" pour un standard de fait, je trouve que ça va trop fort : je dirai qu'il n'y a pas de standard mais malgré tout un standard de fait.
  
  IETF Common Format and MIME Type for Comma-Separated Values (CSV) Files
  - [^] # Re: HS CSV
    
    Posté par damaki le 23 octobre 2017 à 16:17. Évalué à 1. Dernière modification le 23 octobre 2017 à 16:19.
    
    Ok, donc on peut parser le CSV qu'on me file qui est forcément en win1252, séparé par des tabulations, avec des retours de chariot windows, avec les tabulations échappées par des doubles quotes, en omettant les champs de fin de ligne comme Excel et avec des champs vides signifiants null avec mon parser CSV qui ne lit que l'UTF-8, séparé par des points-virgule avec des retours de chariot de mac, des points virgule échappés par des \, où les champs vide signifient chaîne vide et qui part du principe qu'on a forcément toujours 10 champs, c'est supposé passer.
    
    Le CSV n'est pas un standard, c'est un meta-standard. A moins qu'on te file la description complète du format de CSV qu'on le file, tu ne peux que très très difficilement deviner comment le parser. La dernière fois que j'ai bossé sur du CSV, on du aller jusqu'à sortir des heuristiques pour détecter le charset et se protéger des caractères \0 fournis au pif en plus du caractère de fin de ligne par certains de nos clients.
    - [^] # Re: HS CSV
      
      Posté par Gil Cot ✔ (site web personnel, Mastodon) le 09 novembre 2017 à 15:44. Évalué à 0.
      
      Attention que beaucoup d'outils prétendent faire du CSV mais font en fait n'importe quoi !
      
      avec les tabulations […] des points-virgule
      
      Là c'est plus du CSV (coma…) mais du TSV (tab…) ou autre (semi-colon…)
      
      avec des retours de chariot de mac
      
      Là aussi, la RFC indique d'utiliser CRLF même quand on vient de MacOs ou d'un compatible Unix (règle 1)
      
      où les champs vide signifient chaîne vide et qui part du principe qu'on a forcément toujours 10 champs
      
      Il faut toujours le même nombre de champs par enregistrement (règle 4)
      
      mon parser CSV qui ne lit que l'UTF-8 […] n du aller jusqu'à sortir des heuristiques pour détecter le charset
      
      Malheureusement la RFC n'impose pas de charset (lequel choisir en dehors de l'ASCII ?) Mais il y a des outils pour deviner l'encodage
      
      “It is seldom that liberty of any kind is lost all at once.” ― David Hume
# Et OCaml ?

Posté par Dinosaure (site web personnel) le 23 octobre 2017 à 16:06. Évalué à 4.
J'ai essayé avec ce petit script OCaml qui utilise Jsonm (qui n'est qu'un lexer) et le parser utilise le style CPS pour être sûr que les fonctions soient tail-rec. Bien entendu, il y a la présence d'un accumulateur qui grossit en fonction du nombre d'éléments.

Bref, comme la version en C, le test passe les 1 000 000. Le style CPS permet de ne pas faire exploser la stack. Niveau performance par contre, je ne sais pas.

Pour compiler, je conseille d'avoir opam. J'utilise actuellement la version 4.03.0 du compilation OCaml. Ensuite, il faut installer Jsonm, Fmt et ocamlbuild:
```
$ opam install jsonm fmt ocamlbuild
```
Pour compiler et tester avec ceci:
```
$ ls
main.ml
$ ocamlbuild -use-ocamlfind -package jsonm -package fmt main.native
$ ./main.native < test
```
- [^] # Re: Et OCaml ?
  
  Posté par j_m le 23 octobre 2017 à 16:43. Évalué à 2. Dernière modification le 23 octobre 2017 à 16:46.
  
  le parser utilise le style CPS pour être sûr que les fonctions soient tail-rec.
  
  Ca a l'air bien complique cette histoire de CPS. On ne peut pas s'en passer?
  
  Sinon, un truc rigolo a l'etranger:
  
  Ah bon, t'es Francais? Tu connais OCaml?
  
  Ca a l'air interressant mais non. Puis je suis plutot Belge, en fait.
  - [^] # Re: Et OCaml ?
    
    Posté par Dinosaure (site web personnel) le 23 octobre 2017 à 17:00. Évalué à 1.
    
    Hmmhmm, pour le coup non. Mais la transformation d'une fonction récursive en une fonction tail-récurvise à l'aide du style CPS est quelque chose de très commun en OCaml (et dans les langages fonctionnels en général - pour peu que ces derniers optimisent les fonctions tail-rec).
    
    Après, il est vrai que ce n'est pas spontané mais avec un peu de logique et de pratique, on y arrive sans trop de mal.
    - [^] # Re: Et OCaml ?
      
      Posté par j_m le 23 octobre 2017 à 17:39. Évalué à 2.
      
      Hmmhmm, pour le coup non. Mais la transformation d'une fonction récursive en une fonction tail-récurvise à l'aide du style CPS est quelque chose de très commun en OCaml (et dans les langages fonctionnels en général - pour peu que ces derniers optimisent les fonctions tail-rec).
      
      Après, il est vrai que ce n'est pas spontané mais avec un peu de logique et de pratique, on y arrive sans trop de mal.
      
      Si c'est tres commun il doit y avoir moyen que j'y arrive.
      
      Pour rendre mes fonctions tail-rec, j'ajoutais juste un accumulateur dans mes arguments. Mais ca n'est pas toujours possible. CPS permet de repousser un peu les limites, c'est ca?
      
      Mais quand je vois les exemples wikipedia, j'ai l'impression que ca rend la lecture quand mem plus compliquee. Ca ne vaut pas le coup de repasser au style imperatif dans ces cas la?
      - [^] # Re: Et OCaml ?
        
        Posté par foobarbazz le 23 octobre 2017 à 18:03. Évalué à 1. Dernière modification le 23 octobre 2017 à 18:04.
        
        Pour rendre mes fonctions tail-rec, j'ajoutais juste un accumulateur dans mes arguments. Mais ca n'est pas toujours possible. CPS permet de repousser un peu les limites, c'est ca?
        
        Oui, c'est ça. C'est un peu ce que fait Haskell spontanément. L'idée, c'est qu'au lieux de faire grossir ton calcul sur la pile, avant de l'évaluer, tu le fais grossir sur le tas.
        
        En haskell parce que c'est plus lisible (pour moi) :
        
        data A = N A A | F -- un arbre avec des Noeuds et des Feuilles size a = let size' (N a b) k = size' a (\ra -> ra + 1 + size' b k) -- c'est là qu'est la magie, au lieu d'empiler le second appel pour l'arbre droit, on va le rajouter dans la pile -- dans une continuation, ça veut dire : ok, d'abord je fais l'appel sur sous arbre gauche, et quand j'aurais le resultat ra, je pourrais m'occuper du b size' F k = k 0 -- le cas de base, on a une continuation qui attend la taille du sous arbre qu'on traite, ici 0 in size' a id -- initialisation, on veut la taille de l'arbre a, qu'on va renvoyer tel quel
        
        Mais quand je vois les exemples wikipedia, j'ai l'impression que ca rend la lecture quand mem plus compliquee. Ca ne vaut pas le coup de repasser au style imperatif dans ces cas la?
        
        Et oui, le style CPS est imbitable :-). C'est pour ça qu'Haskell est fantastique.
- [^] # Re: Et OCaml ?
  
  Posté par Axioplase ıɥs∀ (site web personnel) le 30 octobre 2017 à 13:57. Évalué à 5.
  
  Le style CP, oui.
  Le CPS, oui.
  Le style CPS, non ! Pas de "style continuation-passing style" !
# Intérêt ?

Posté par Arthur Accroc le 23 octobre 2017 à 19:09. Évalué à 6.
Et combien de tableaux imbriqués faut-il pour faire planter un parser JSON ?

L’intérêt est-il de pouvoir manipuler des données légitimes qui utiliseraient disons 10000 niveaux (ça existe ?) ou de se protéger contre des fichiers JSON volontairement malformés ?

Le module JSON de Perl fixe la limite arbitrairement à 512. Extrait de son manuel :

max_depth
$json = $json->max_depth([$maximum_nesting_depth])

Sets the maximum nesting level (default 512) accepted while encoding or decoding. If a higher nesting level is detected in JSON text or a Perl data structure, then the encoder and decoder will stop and croak at that point.

À l’essai, si on remonte la limite beaucoup plus haut, le parser en pur Perl s’arrête à 100000, alors que le parser de JSON::XS (écrit en C pour une plus grande rapidité) plante un peu après 74800 sur mon système (JSON utilise un parser ou l’autre suivant si JSON::XS est installé ou non).

ET bien dans certains langages, très peu.

Peut-être devrais-tu regarder si les limites que tu atteins avec d’autre langages ne sont pas aussi fixées arbitrairement pour éviter des problèmes…

Pour référence, le code Perl que j’ai utilisé :
```
#!/usr/bin/perl -w
use strict;

use JSON;

my $json = JSON->new;
$json->max_depth(5000000);
my $decoded = $json->decode(<STDIN>);
```
« Le fascisme c’est la gangrène, à Santiago comme à Paris. » — Renaud, Hexagone
- [^] # Re: Intérêt ?
  
  Posté par lovasoa (site web personnel) le 24 octobre 2017 à 08:32. Évalué à 1.
  
  Oui, en ruby ou en PHP aussi, la limite est fixée dans le code. C'est déjà mieux que d'avoir une limite qui dépend juste de la taille de la pile disponible, mais c'est quand même une limite qui est présente simplement pour une petite facilité d'implémentation (utiliser une fonction récursive). C'est quand même étonnant que quasiment aucun parser n'ait opté pour une approche ne nécessitant pas de limite d'imbrication, non ?
  
  Cela empêche d'utiliser JSON, pour, par exemple représenter un arbre, alors que sans cette limite fixée par les implémentations, le format s'y prêterait très bien.
  - [^] # Re: Intérêt ?
    
    Posté par Thomas Douillard le 24 octobre 2017 à 11:52. Évalué à 10. Dernière modification le 24 octobre 2017 à 11:54.
    
    D’une manière générale, dire « aucune limite » c’est un raccourcis pour dire « toute la mémoire dispo ». En vrai, ça finira toujours par planter pour certains niveau d’imbrications - si c’est pas la pile qui explose, ce sera le tas. Si c’est pas le tas, ça sera le dd si t’as été pervers au point d’utiliser un fichier pour compter les accolades. Ça donne un fichier suffisamment grand pour toutes les applications réalistes, mais qui existe tout de même.
    
    Et puis si t’en es à devoir traiter un arbre très très profond - alors que tout le point d’un arbre c’est en général de maintenir un certain niveau d’horizontalité et d’éviter de partir en profondeur (un index typiquement, que tu essayes de maintenir équilibré) t’as probablement d’autres préoccupations. Un arbres très profond, si on le suppose équilibré, ça veut dire que la taille des donnée est exponentiellement plus grande, donc absolument gigantesque. Peu de chances que ça termine dans un fichier json, en somme.
  - [^] # Re: Intérêt ?
    
    Posté par Arthur Accroc le 24 octobre 2017 à 14:54. Évalué à 3.
    
    Oui, en ruby ou en PHP aussi, la limite est fixée dans le code.
    
    Vu les valeurs que tu as trouvées (101 et 512), ça ne m’étonne pas.
    Je soupçonnerais la même chose pour Rust (128), C/jansson (2049 — note que ton programme indique la valeur pour laquelle ça ne fonctionne plus, 513 par exemple en Perl en laissant la limite par défaut à 512)…
    
    Cela empêche d'utiliser JSON, pour, par exemple représenter un arbre, alors que sans cette limite fixée par les implémentations, le format s'y prêterait très bien.
    
    La remarque de Thomas ramène à la réflexion : est-ce qu’un arbre très profond a un sens dans une application réelle ?
    
    S’il est très profond, mais pas très large, l’accès aux données ne semble pas optimal ; mieux vaudrait peut-être utiliser une autre structure (table de hachage ?). S’il est très profond et très large, donc très volumineux, est-ce que les capacités mémoires actuelles permettent de l’avoir entièrement en mémoire (la taille augmente exponentiellement avec la profondeur quand même), ou faut-il le manipuler directement sur disque/SSD ? Dans le deuxième cas, la question n’est pas de le sérialiser, mais d’avoir un format permettant un accès efficace sur disque/SSD.
    
    Vois-tu un exemple d’application pour laquelle un arbre très profond (disons avec une profondeur supérieure à 5000) soit une structure adaptée ?
    
    Si oui, la question de pouvoir le représenter pour le stocker, idéalement sous une forme moins sensible à la plateforme qu’une forme binaire, est effectivement intéressante.
    
    Est-ce que les bibliothèques de sérialisation disponibles pour les divers langages gèrent ça mieux que les bibliothèques JSON ? Y a-t-il une représentation (ou à peu près) standard dont les bibliothèques tiennent mieux la route à ce niveau (XML ?) ?
    
    La seule fois où j’ai eu à stocker un arbre (il y a 25 ans ; on trouvait moins de bibliothèques, à l’époque…), j’avais fait un parcours en profondeur et je stockais un nœud par ligne de fichier avec comme indications sa profondeur et sa valeur. Quand on reconstruisait l’arbre, la profondeur indiquait où greffer le nouveau nœud sur la branche courante. D’un point de vue analyse syntaxique, c’est très simple (en tout cas avec les valeurs de mes nœuds, qui l’étaient). Maintenant, cet arbre passerait en JSON, même avec la limite à 100 du parser Ruby…
    
    « Le fascisme c’est la gangrène, à Santiago comme à Paris. » — Renaud, Hexagone
    - [^] # Re: Intérêt ?
      
      Posté par Sufflope (site web personnel) le 24 octobre 2017 à 16:39. Évalué à 2.
      
      Et puis pour les langages à VM dont la limite est là pour éviter une StackOverflowError ou équivalent (ou qui pètent justement comme ça), si on a vraiment besoin d'aller plus loin et qu'on est prêt à sacrifier la mémoire qu'il faut, on peut toujours augmenter la limite (je pense à Java où on peut fixer au démarrage de la JVM la limite à laquelle il lève cette exception).
    - [^] # Re: Intérêt ?
      
      Posté par foobarbazz le 24 octobre 2017 à 17:11. Évalué à 3. Dernière modification le 24 octobre 2017 à 17:11.
      
      La remarque de Thomas ramène à la réflexion : est-ce qu’un arbre très profond a un sens dans une application réelle ?
      
      Oui… La faire planter en exploitant le fait qu'elle utilise un parseur json foireux :-)
      - [^] # Re: Intérêt ?
        
        Posté par foobarbazz le 24 octobre 2017 à 17:30. Évalué à -1.
        
        Je suis un peu sur le cul en lisant les commentaires ici…
        
        Une fonction prétend parser le json, on est en droit d'attendre qu'elle sache parser le json. Il n'y a pas à ergoter sur la légitimité de l'usage de certains fichiers json…
        
        Vous vous êtes déjà retrouvé dans un cas particulier, à avoir un usage atypique d'un outil, et faire un rapport de bug parce que celui ci ne se comportait pas comme il était supposé le faire ?
        
        Je vais donner un cas très typique d'utilisation d'un fichier JSON avec un arbre très profond : Utiliser un fichier json pour encoder un arbre très profond, tout simplement.
        
        Moi par exemple, ya pas très longtemps j'ai fais un truc vite fait mal fait pour qui générait des fichiers HTML à partir d'objets fractales. Ils n'étaient pas très profond à cause de l’explosion combinatoire, mais ils étaient ridiculement gros (plusieurs dizaines de méga de code HTML par fichier). J'étais bien content que chromium et firefox étaient suffisamment bien fait pour s'en accommoder, et ça m'aurait prodigieusement gonflé que l'un d'eux plante parce qu'un dev se serait dit un jour "C'est bon, un fichier html de plus de 10Mo n'a d'usage légitime dans une application réelle, c'est ok si ça crash dans ce cas là".
        
        [^] # Re: Intérêt ?
        
        Posté par Thomas Douillard le 24 octobre 2017 à 17:40. Évalué à 7.
        
        Donc tu as un cas d’utilisation avec des arbres profonds pas profonds ? cqfd.
        
        Tu es dnc ptete sur le cul mais t’es en plus à côté de la plaque ;) Moi ça me choque pas qu’un programme te dise honnêtement « je suis pas conçu pour ce genre de cas » et s’arrête. Ce qui me choquerait c’est que ça segfaulte salement. D’une manière générale, c’est pas une mauvaise pratique de fixer des limites.
        
        [^] # Re: Intérêt ?
        
        Posté par foobarbazz le 24 octobre 2017 à 17:51. Évalué à -3.
        
        Je vais donner un cas très typique d'utilisation d'un fichier JSON avec un arbre très profond : Utiliser un fichier json pour encoder un arbre très profond, tout simplement.
        
        Donc tu as un cas d’utilisation avec des arbres profonds pas profonds ? cqfd.
        
        Wat?
        
        Moi ça me choque pas qu’un programme te dise honnêtement « je suis pas conçu pour ce genre de cas » et s’arrête.
        
        Non, c'est pas du tout ok de s'arrêter pour quelque raison que ce soit. Si il y a ce genre de limite, a minima elle doivent être clairement écrite dans la doc.
        
        Ce qui me choquerait c’est que ça segfaulte salement.
        
        Là dessus on est d'accord, c'est encore pire.
        
        D’une manière générale, c’est pas une mauvaise pratique de fixer des limites.
        
        Si… Et c'est particulièrement vrai dans le cas d'une bibliothèque où celui qui l'écrit n'a absolument aucune idée de la manière dont elle va être utilisée. Et c'est encore pire si celui qui l'utilise n'a absolument aucune idée du genre de limite qui peut s'y trouver.
        
        [^] # Re: Intérêt ?
        
        Posté par Thomas Douillard le 24 octobre 2017 à 18:24. Évalué à 10.
        
        Ne le prend pas mal, mais c’est de la naïveté. N’importe quel ingénieur sait qu’un composant a un domaine de validité et ne fonctionnera pas correctement en dehors. En informatique on a juste tendance à faire comme-ci on avait des vrais machine de Turing avec des bandes de mémoire illimitées. Ce n’est évidemment jamais le cas.
        
        C’est juste que les données sont en général tellement petites qu’on peut faire « comme si » pour des kilos d’applications. Après dés que tu commences à jouer avec des algos exponentiels sur des problèmes NP-complets, tu comprends que c’est une fiction …
        
        [^] # Limites…
        
        Posté par Arthur Accroc le 24 octobre 2017 à 20:09. Évalué à 10.
        
        Non, c'est pas du tout ok de s'arrêter pour quelque raison que ce soit.
        
        Nous vivons dans un monde fini (je ne sais pas si les chantres de la croissance infinie s’en apercevront avant d’avoir ravagé la planète au point que ce soit la famine globale, mais c’est une autre histoire), ton ordinateur l’est encore plus. Donc il y a forcément des limites.
        
        Si il y a ce genre de limite, a minima elle doivent être clairement écrite dans la doc.
        
        C’est le cas pour Perl. Si ça ne l’est pas pour ton langage, mauvais langage ⇒ changer de langage.
        
        Ce qui me choquerait c’est que ça segfaulte salement.
        
        Là dessus on est d'accord, c'est encore pire.
        
        C’est pour ça que les auteurs de la plupart des bibliothèques ont fixé des limites.
        
        D’une manière générale, c’est pas une mauvaise pratique de fixer des limites.
        
        Si… Et c'est particulièrement vrai dans le cas d'une bibliothèque où celui qui l'écrit n'a absolument aucune idée de la manière dont elle va être utilisée.
        
        Oui, enfin considérons que tu aies un ordinateur avec pas mal de mémoire, 32 Go. Ça fait 2³⁵.
        Considérons un arbre binaire complet de 100 niveaux (la limite la plus basse pour un analyseur JSON selon les test de lovasoa). Il comprend 2¹⁰⁰ - 1 nœuds. Ça n’est pas prêt de rentrer dans ton ordinateur, même si par miracle chaque nœud ne prenait qu’un octet.
        
        Peut-être vas-tu me dire que l’ordinateur de la météo est plus gros. Cela dit, le nombre d’atomes de notre planète est estimé à environ 10⁵⁰, soit environ 2¹⁶⁶. Tu montes un peu la limite par défaut ou tu prends un langage dont l’analyseur JSON a une limite à 512 et ton arbre n’est pas représentable sur Terre, même avec un atome par nœud…
        
        Bon, considérons que l’intérêt est de représenter des arbres incomplets.
        On trouve des analyseurs JSON qui tiennent jusqu’à plus de 50 000 niveaux (éventuellement en changeant la limite par défaut). Ça veut dire que pour accéder à une des feuilles les plus profondes, il faut quand même 50 000 itérations. Ça paraît compromettre l’efficacité.
        
        Alors après, on ne peut pas complètement écarter à priori qu’il existe des cas pour lesquels malgré tout une telle représentation serait adaptée. Mais je serais très curieux d’en avoir un exemple. Et là, on pourra dire « quels idiots les programmeurs de telle bibliothèque JSON, elle ne couvre pas tous les usages », mais pas avant.
        
        En attendant, est-ce que le vendeur de ta voiture t’a prévenu que son moteur ne peut pas fonctionner sans oxygène ? C’est quand même une limite très importante !
        
        « Le fascisme c’est la gangrène, à Santiago comme à Paris. » — Renaud, Hexagone
        
        [^] # Re: Limites…
        
        Posté par foobarbazz le 25 octobre 2017 à 17:04. Évalué à 0.
        
        En attendant, est-ce que le vendeur de ta voiture t’a prévenu que son moteur ne peut pas fonctionner sans oxygène ? C’est quand même une limite très importante !
        
        Analogie foireuse. Là on ne parle pas de la voiture qui cesse de fonctionner sans oxygène, mais de la voiture qui cesse de fonctionner arbitrairement au delà de 1500m d'altitude, parce que le constructeur s'est dit "1500m c'est bien, il faut bien mettre une limite". Non, il faut pas. Et guess what ? les constructeurs ne le font pas. Mieux, les injections s'adaptent au manque d'oxygène, la puissance baisse, mais le moteur continue de marcher tant que c'est possible.
        
        Sauf que là, la limite est plusieurs ordres de grandeurs en dessous de la limite physique (la taille d'une pile contre la taille de la mémoire vive).
        
        [^] # Re: Limites…
        
        Posté par Jérôme FIX (site web personnel) le 28 octobre 2017 à 11:32. Évalué à 4.
        
        Tu en parleras aux concepteurs d'hélicoptères, d'avions, …
        
        [^] # Re: Limites…
        
        Posté par foobarbazz le 29 octobre 2017 à 15:04. Évalué à -8.
        
        Ils ne mettent pas de limite dans l'appareil, la physique et la loi s'en chargent.
        
        Je vous dis merde :-) Cet acharnement et cette mauvaise foi n'honore personne.
        
        [^] # J’attends toujours un exemple…
        
        Posté par Arthur Accroc le 30 octobre 2017 à 02:14. Évalué à 2.
        
        Mauvaise foi ? De la part de qui ?
        
        J’attends toujours un exemple d’application réelle utilisant un arbre dont la représentation en JSON ne passe pas avec les analyseurs actuels.
        
        J’aurais pensé que quelqu’un en trouverait peut-être un au moins pour la limite la plus basse par défaut de 100 (un petit effort !), mais j’attends toujours…
        
        Sinon, que les analyseurs JSON ne puissent pas lire un fichier produit dans une démarche malveillante, de test ou artistique, mais sans utilité réelle, ça ne m’empêchera pas de dormir (surtout si ça ne concerne pas ceux de mes langages de prédilection). Il y a des trucs qui m’ennuient plus en informatique (l’abandon du système de fichiers Intermezzo, par exemple, ou Berkeley DB*).
        
        Note : si on a un arbre de plus de 100 niveaux qui tient en mémoire, il est fortement déséquilibré (c’est vrai que j’ai oublié ce cas dans mes commentaires précédents) ou beaucoup de nœuds sont le seul nœud fils de leur nœud parent. Un arbre correspondant au second cas peut être compacté en regroupant ces nœuds avec leur nœud parent.
        
        Un petit schéma (ASCII parce que c’est plus simple — je sais que c’est moche), pour éclairer le principe :
        
        e / d e / \ / c f bcd / / \ b devient a f / \ a g \ g
        
        Donc, il reste à trouver l’exemple d’une application ayant l’utilité d’un arbre d’une profondeur de plus de 100 (par rapport à la limite par défaut la plus basse) voire 900 (par rapport à la limite de récursion sur Python si elle n’est pas facilement relevable, sinon encore plus) fortement déséquilibré et dont un rééquilibrage fausse le sens.
        
        Cela dit, je n’exclus pas complètement qu’un développeur se retrouve un jour dans ce cas. La page de lovasoa pourrait alors lui être utile… si elle distinguait pour tous les langages ou bibliothèques la limite par défaut et la limite maximale.
        
        * Si je voulais râler contre une brique logicielle, ce serait la base Berkeley DB.
        Ton serveur OpenLDAP est arrêté brusquement (coupure électrique…) alors qu’il était bien pépère à ne faire que des opérations de lecture sur son backend bdb et c’est hyper grave, il faut reconstruire la base en suivant une doc imbitable. Merde !
        Il y a aussi le cas où un fichier Berkeley DB perdu au fin fond du profil Firefox est corrompu et où Firefox ne démarre plus, sans explication pertinente (heureusement, c’est rare ; Firefox ne doit pas les garder ouverts en lecture…).
        Berkeley DB n’est à la fois pas adaptée pour une grosse charge et pénible à gérer pour une faible charge. Malheureusement des logiciels l’utilisent…
        
        « Le fascisme c’est la gangrène, à Santiago comme à Paris. » — Renaud, Hexagone
        
        [^] # Re: J’attends toujours un exemple…
        
        Posté par pulkomandy (site web personnel, Mastodon) le 31 octobre 2017 à 10:19. Évalué à 7.
        
        Ce qui m'inquiète là dedans, c'est pas forcément qu'il y aie une limite. C'est plutôt les langages où ça finit par faire une erreur de segmentation ou un autre truc du genre. Résultat, n'importe qui peut faire planter ton API REST en envoyant une requête de 27Ko (c'est à dire pas grand chose).
        
        S'il y a juste une exception et qu'elle peut être interceptée et testée par l'applicatif, je pense que ça n'est pas vraiment un problème à condition que ce soit documenté et que les applications qui en ont besoin (pour des raisons de sécurité et de continuité de service, pas parce qu'elles ont vraiment besoin de parser des très gros fichiers JSON avec 100 niveaux d'imbrication) puissent réagir en conséquence.
        
        [^] # Re: Intérêt ?
        
        Posté par Kalenx le 25 octobre 2017 à 03:11. Évalué à 8.
        
        J'étais bien content que chromium et firefox étaient suffisamment bien fait pour s'en accommoder
        
        Et pourtant, on a ceci
        Du code parfaitement valide qui fait crasher les navigateurs (j'en ai essayé quelques-uns sous les versions les plus récentes de Chromium et Firefox, ça peut prendre quelques secondes mais la plupart des tests crashent effectivement le navigateur ou l'onglet).
        
        À un certain point, comme l'ont bien expliqué d'autres personnes, il faut poser des limites, même arbitraires. Je suis convaincu que GCC (ou n'importe quel compilateur) n'est pas capable de parser certains fichiers C parfaitement valides (mais complètement tordus). Même chose pour un parser XML ou l'interpréteur Python. À ce propos, connaissez-vous l'erreur "s_push: parser stack overflow"? Pourtant cette erreur apparaît sur du code parfaitement valide et limite certains cas d'application réels. C'est dommage, mais c'est une réalité avec laquelle il faut composer : nos grammaires nous permettent de composer des structures infinies, mais le parser possède par définition un nombre fini d'état, c'est donc inéluctable.
        
        Je suis cependant d'accord que ces limites devraient clairement être indiquées dans la documentation.
        
        [^] # Re: Intérêt ?
        
        Posté par lasher le 20 novembre 2017 à 16:31. Évalué à 2.
        
        Je réponds à la bourre, mais :
        
        Je suis convaincu que GCC (ou n'importe quel compilateur) n'est pas capable de parser certains fichiers C parfaitement valides (mais complètement tordus).
        
        Si tu actives certaines optimisations qui créent des graphes complexes (en gros, -O3 avec quelques options en plus par exemple) tu peux clairement arriver à des plantages du compilateur pour certains codes. Par exemple, le fameux code de ffmpeg a quelques fonctions qui font 3000 lignes pour cause de programmeur ne faisant pas confiance au compilo. Bon ben, si jamais on activait les directives de compilation et vectorisation dessus, on pourrait avoir quelques surprises, euh, intéressantes. :-)
        
        Sinon, avec le compilateur d'Intel, il m'est déjà arrivé d'avoir des plantages du genre « Internal error : graph too deep » (ce n'était pas exactement dit comme ça, mais c'est plus ou moins ce que ça veut dire) : c'était la représentation interne du programme en activant toutes les grosses optimisations qui faisait que le compilateur finissait par faire trop de récursions en parcourant/mettant à jour le graphe…
        
        [^] # Re: Intérêt ?
        
        Posté par Laurent J (site web personnel, Mastodon) le 25 octobre 2017 à 12:50. Évalué à 6.
        
        Je vais donner un cas très typique d'utilisation d'un fichier JSON avec un arbre très profond : Utiliser un fichier json pour encoder un arbre très profond, tout simplement.
        
        Oui. Mais pour cela il faut :
        
        soit assez de mémoire pour que tout le contenu encodé (ou décodé pour les parseurs) tienne d'un seul tenant
        
        soit utiliser des encodeurs/parseurs qui au lieu de stocker le résultat final en mémoire, le fasse vers d'autres types de sorties (disques dur, flux réseaux …). C'est à ça que sert les parseurs SAX dans le monde XML (voir mon commentaire plus bas)
        
        J'étais bien content que chromium et firefox étaient suffisamment bien fait pour s'en accommoder,
        
        Non. Correction : tu étais bien content d'avoir suffisamment de mémoire (et de swap) pour pas que ça plante.
        
        Que ce soit Chrome ou Firefox, quand y a plus de mémoire pour créer des noeuds DOM afin de représenter ton HTML à l'écran, et bien… il n'y a plus de mémoire. Et ça te pète à la figure ou ça t'affiche rien. point barre.
        
        [^] # Re: Intérêt ?
        
        Posté par foobarbazz le 25 octobre 2017 à 16:49. Évalué à -4.
        
        Non. Correction : tu étais bien content d'avoir suffisamment de mémoire (et de swap) pour pas que ça plante.
        Que ce soit Chrome ou Firefox, quand y a plus de mémoire pour créer des noeuds DOM afin de représenter ton HTML à l'écran, et bien… il n'y a plus de mémoire. Et ça te pète à la figure ou ça t'affiche rien. point barre.
        
        Évidement, on ne peut pas attendre qu'un programme fasse quelque chose d'impossible. Mais ce n'est pas de ça dont je parle…
        Je parle d'un cas où il y a largement assez de mémoire pour encoder l'arbre… Où même, on ne se pose même pas la question tant les données sont petites. On parle d'un fichier de 27ko dans ce thread !
        
        Un programme foire sur un fichier de 27ko alors qu'il y a potentiellement 16Go de mémoire sur la machine, et vous me parlez de limite physique et tout ?
        
        J'arrête là, c'est un échange parfaitement insensé.
        
        [^] # Re: Intérêt ?
        
        Posté par Kalenx le 25 octobre 2017 à 22:42. Évalué à 10.
        
        Désolé que tu vois cet échange comme insensé; c'est vrai que ce genre de concept n'est pas forcément facile à appréhender, et qu'il peut être utilisé à mauvais escient pour mal faire les choses (un peu comme le out of spec en ingénierie traditionnelle, où on prend pour excuse que rien n'est garantit en dehors des spécifications pour faire vraiment n'importe quoi alors qu'une simple modification améliorerait beaucoup ce cas de figure).
        
        Ceci étant, la question n'est pas tant de comparer les tailles respectives de la RAM et du fichier incriminé. On peut exploser la RAM tout en étant apparament bien des ordres de grandeur en dessous de sa taille, les zip bombs (ou bombes de décompression ) en étant un bon exemple. Après tout, le fichier original est un ZIP valide, et ne fait que 42 Ko. Quel insensé pourrait oser venir parler de limites physiques? Eh bien celui qui sait que ce fichier, une fois décompressé, fait 4.5 Po (pétaoctets)…
        
        Et là, je ne parle que de la mémoire; discutons un peu du temps d'exécution. En Python (comme dans beaucoup de langages dynamiques), les ensembles pairs/valeurs du JSON sont représentés par des dictionnaires, qui ont un accès O(1) (amorti). Cependant, c'est un accès O(1) à un pointeur sur l'élément voulu. En temps normal, en s'en fiche complètement, une indirection de plus ou de moins, ça ne changera pas grand chose.
        Et si c'était maintenant 15 000 indirections? Soudainement le temps d'accès explose…
        
        Est-ce parce qu'on a dépassé les limites de la RAM? Non. Parce qu'on surcharge le processeur de calculs? Pas vraiment. Et pourtant ça ne va pas, tout simplement parce que la supposition de départ ayant mené à la conception des dictionnaires en Python est que les accès sont, en majorité, à plat.
        
        Est-ce qu'on pourrait imaginer une autre structure de données plus adaptée à ce genre de chose? Bien sûr. Est-ce qu'on veut le faire? Certainement pas, et ce n'est ni par paresse, ni par esprit de contradiction. Les choix de design peuvent être discutés, mais peu importe ce que l'on choisit, il y aura des perdants.
        
        [^] # Re: Intérêt ?
        
        Posté par foobarbazz le 26 octobre 2017 à 01:39. Évalué à -3. Dernière modification le 26 octobre 2017 à 01:41.
        
        Et là, je ne parle que de la mémoire; discutons un peu du temps d'exécution. En Python (comme dans beaucoup de langages dynamiques), les ensembles pairs/valeurs du JSON sont représentés par des dictionnaires, qui ont un accès O(1) (amorti). Cependant, c'est un accès O(1) à un pointeur sur l'élément voulu. En temps normal, en s'en fiche complètement, une indirection de plus ou de moins, ça ne changera pas grand chose.
        Et si c'était maintenant 15 000 indirections? Soudainement le temps d'accès explose…
        
        Je ne comprend pas bien de quoi tu parle… Le boulot d'un parseur json c'est de prendre une chaîne au format json et d'en faire une structure qui permet de se balader dans l'arbre que cette chaîne représentait. Et c'est tout. Et oui, cet arbre devra probablement être entre encodé autrement pour des temps d'accès efficace. Mais c'est pas le problème du parseur.
        
        Ceci étant, la question n'est pas tant de comparer les tailles respectives de la RAM et du fichier incriminé. On peut exploser la RAM tout en étant apparament bien des ordres de grandeur en dessous de sa taille, les zip bombs (ou bombes de décompression ) en étant un bon exemple. Après tout, le fichier original est un ZIP valide, et ne fait que 42 Ko. Quel insensé pourrait oser venir parler de limites physiques? Eh bien celui qui sait que ce fichier, une fois décompressé, fait 4.5 Po (pétaoctets)…
        
        Oui, un autre très bon exemple, c'est pas le problème de la lib qui dézippe, c'est celui de celui qui l'utilise !
        
        c'est vrai que ce genre de concept n'est pas forcément facile à appréhender
        
        Ça ça ressemble beaucoup à de la condescendance que je trouve un chouia déplacée. Mais peut être que je me trompe.
        
        Très prosaïquement, je vois des vois des gens qui sont à la limite de me sortir des arguments de la théorie de l'information pour justifier qu'un parser json ne soit pas capable de parser un fichier json valide qu'un humain pourrait écrire à la main en 15 minutes… C'est techniquement possible facilement, et sans coût, de parser TOUS les fichiers json, avec pour seule limite la mémoire de la machine. Le faire, ne coûte strictement rien (sinon un code un chouia plus compliqué, avec un "push foo" à la place d'un "call bar").
        
        Et qu'est-ce qui ce passe quand le parser json est utilisé dans un contexte un peu compliqué ? Avoir une centaine d'appel de fonction sur la pile c'est pas extra-ordinaire, dans ce cas le parseur va foirer à une profondeur de 30 ? C'est toujours ok, parce qu'il y a forcement une limite ?
        
        En temps normal, en s'en fiche complètement, une indirection de plus ou de moins, ça ne changera pas grand chose.
        Et si c'était maintenant 15 000 indirections? Soudainement le temps d'accès explose…
        
        Pourquoi est-ce que l'argument que tu dis à propos des temps d'accès ne vaut pas pour l'utilisation de la pile ?
        « En temps normal, un appel de plus ou de moins sur la pile, on s'en fou, imagine maintenant que c'est 1000 ? Soudainement on a un stack overflow. »
        
        Pitié… Non, sérieux, c'est ridicule :-)
        
        [^] # Re: Intérêt ?
        
        Posté par Kalenx le 26 octobre 2017 à 04:01. Évalué à 8.
        
        Au risque de sembler condescendant—ce qui n'est réellement pas mon but*—je vais essayer une autre approche.
        
        La discussion semble bloquée parce que nous avons une vision différente. Tu vois le parser json comme une entité théorique, détachée du reste et qui ne devrait obéir qu'aux règles de sa spécification propre indépendemment des conséquences que cela peut avoir. Je vois le parser json comme faisant partie d'un tout et devant donc collaborer avec le reste pour assurer un fonctionnement optimal au système.
        
        Deux exemples de cette dichotomie :
        
        Le boulot d'un parseur json c'est de prendre une chaîne au format json et d'en faire une structure qui permet de se balader dans l'arbre que cette chaîne représentait. Et c'est tout. Et oui, cet arbre devra probablement être entre encodé autrement pour des temps d'accès efficace. Mais c'est pas le problème du parseur.
        
        Si j'étais de mauvaise foi, je dirais que le json est en soi une "structure qui permet de se balader dans l'arbre". Mais surtout, tu mets de côté le fait qu'un parser json n'est jamais utilisé seul. Lorsque tu dis "en faire une structure", c'est donc que c'est le parser qui doit faire un choix de représentation de l'information. Or, ce choix constitue son interface avec le reste du monde. C'est donc le problème du parser que de déterminer et d'appliquer des limites (arbitraires certes) faisant en sorte que cette interface reste utile.
        
        [À propos d'une zip bomb] Oui, un autre très bon exemple, c'est pas le problème de la lib qui dézippe, c'est celui de celui qui l'utilise !
        
        Encore une fois, tu as raison si on observe le décompresseur en vase clos. Après tout, il ne fait que son travail. Pourtant, ton système, lui, sera loin d'avoir un comportement idéal—au contraire, ce sera plutôt une cible idéale. Un décompresseur capable de rejeter les cas totalement hors normes (même si formellement valides) avec une erreur claire sera bien plus utile et correct d'un point de vue global.
        
        Pourquoi est-ce que l'argument que tu dis à propos des temps d'accès ne vaut pas pour l'utilisation de la pile ?
        
        Ça s'applique, justement. Un bon système ne va pas se contenter de supposer qu'il existe dans un monde idéal avec une pile infinie, mais arrêter le massacre à un moment qu'il juge opportun (e.g. trop loin de la "norme" pour être réellement utile).
        
        Pour terminer à propos du JSON : oui, on pourrait écrire des parsers différents. En fait, il semble déjà y en avoir. Mon propos ne réside pas tant dans l'impossibilité de le faire (quoique, soit dit en passant, même ces nouveaux parsers top cool auraient aussi des limites, que d'aucuns pourraient qualifier d'absurdes) mais plutôt dans l'argument général qu'il faudrait toujours pouvoir tout gérer, même les cas à la limite de l'impossible. La simplicité est aussi une belle vertu…
        
        Lorsque je dis qu'un concept n'est pas facile à appréhender, ce n'est pas pour signifier que ceux qui ne le comprennent pas sont des idiots, mais justement pour souligner le fait qu'il est contre-intuitif. Le paradoxe des anniversaires, par exemple, est un concept "pas forcément facile à appréhender". Ça ne signifie pas pour autant que je suis condescendant à l'égard des gens qui ne le saisissent pas de prime abord.
        
        [^] # Re: Intérêt ?
        
        Posté par Sufflope (site web personnel) le 26 octobre 2017 à 04:14. Évalué à 8. Dernière modification le 26 octobre 2017 à 04:15.
        
        un parser json ne soit pas capable de parser un fichier json valide qu'un humain pourrait écrire à la main en 15 minutes…
        
        Oui et ces parsers ingèrent des JSON réalistes en quelques dixièmes de seconde qu'un humain mettrait des heures à se représenter. L'informatique (surtout bête et méchante comme un parser json, pas de l'IA à la limite de la science-fiction) sert à être utile et pas à détecter l'art, quelle surprise.
        
        Oui, un autre très bon exemple, c'est pas le problème de la lib qui dézippe, c'est celui de celui qui l'utilise !
        
        Ah oui donc une limite doit bien être mise en fait, mais pas dans le parser, à la fin. Quand le parser a déjà tué ta machine en essayant d'allouer 5Po. Mmmh mmmh.
        
        C'est techniquement possible facilement, et sans coût, de parser TOUS les fichiers json, avec pour seule limite la mémoire de la machine. Le faire, ne coûte strictement rien (sinon un code un chouia plus compliqué, avec un "push foo" à la place d'un "call bar").
        
        Ah oui voilà "sans coût" à part réécrire une brique essentielle, par exemple dans un style qualifié d'imbitable dans d'autres commentaires. Mais c'est quoi, écrire et maintenir du code ? Y a des asiatiques du sud qui en pissent à la centaine de lignes pour le prix d'un burger.
        
        [^] # Re: Intérêt ?
        
        Posté par Arthur Accroc le 27 octobre 2017 à 00:55. Évalué à 7.
        
        Le boulot d'un parseur json c'est de prendre une chaîne au format json et d'en faire une structure qui permet de se balader dans l'arbre que cette chaîne représentait. Et c'est tout. Et oui, cet arbre devra probablement être entre encodé autrement pour des temps d'accès efficace. Mais c'est pas le problème du parseur.
        
        À mon sens, c’est exactement l’inverse : un format JSON sert à l’encodage d’une structure existante (et qui tient en mémoire) pour pouvoir la recharger lors d’une autre exécution ou la transmettre.
        L’utilité du parser est de permettre de restaurer cette structure.
        
        Du coup, à moins que le programmeur (du premier programme si celui qui produit du JSON n’est pas le même que celui qui le lit) soit idiot, il a choisi une structure un minimum exploitable et pas complètement inefficace pour son application. Si on prend l’exemple utilisé pour le test, la seule information encodée par n tableaux imbriqués sans éléments, c’est… n.
        
        J’attends toujours que quelqu’un trouve un exemple d’application ayant l’utilité d’un arbre très profond qui tient en mémoire (c’est une vraie question, je n’affirme pas que ça n’existe pas)…
        
        « Le fascisme c’est la gangrène, à Santiago comme à Paris. » — Renaud, Hexagone
        
        [^] # Re: Intérêt ?
        
        Posté par fearan le 27 octobre 2017 à 14:33. Évalué à 3.
        
        C'est techniquement possible facilement, et sans coût, de parser TOUS les fichiers json, avec pour seule limite la mémoire de la machine.
        
        Et vas y que je te crée un bug non reproductible. Quand Pika fera son rapport de bug avec fichier joint (attention on parle d'un utilisateur averti qui s'est paluché le rapport de bug, et qui de surcroit à joint le fichier) Son bug va se retrouver non résolu car non reproductible sur la machine de dev.
        
        Il ne faut pas décorner les boeufs avant d'avoir semé le vent
# Non, ils ne sont pas mauvais

Posté par Laurent J (site web personnel, Mastodon) le 25 octobre 2017 à 11:13. Évalué à 10.

Quand on veut parser des JSON représentant un arbre de grande profondeur ou un grand volume de données, on ne veut, à priori, pas tout charger en mémoire, parce qu'on sait qu'à un moment ou à un autre, ça va aboutir à des problèmes de mémoire, quelque soit la manière dont on implémente le parseur (ou alors il s'agit probablement d'un autre souci d'organisation des données, comme évoqué plus haut).

Qu'on déteste XML ou pas, il faut savoir qu'on a très vite rencontré le même souci en XML. Quand on parse du XML, on ne veut pas toujours une représentation en mémoire du document complet (c'est à dire avoir un DOM). On veut simplement pouvoir lire le XML, pour en extraire des données (et pas forcément toutes) et faire des traitements ou les stocker quelque part, au fur et à mesure de la lecture du XML. En clair, avoir comme objectif technique, une occupation mémoire de complexité O(1).

C'est pourquoi il a été inventé le parser SAX, qui permet de lire le XML de manière séquentielle, et donc de traiter les données de manière séquentielle. C'est un parser "bas niveau", en ce sens qu'il ne fait pas de représentation mémoire de ce qu'il lit. Il détecte et renvoi juste chaque token du format. Une sorte de parser qui fait du streaming. À noter d'ailleurs que bon nombre de parser DOM se basent sur un parser SAX…

Bref, la plupart des parsers JSON auxquels tu penses sont des équivalents des parser DOM pour XML. Ils ne sont pas du tout mauvais. Ils ne sont juste pas adaptés à des cas d'utilisation comme le tient. Ce que tu voudrais c'est plutôt un parser JSON de plus bas niveau, comme les parsers SAX pour XML. Une petite recherche sur le web (ex: "SAX for JSON") te renverra quelques projets en ce sens ;-)

D'ailleurs y a des projets du même type pour YAML et certainement d'autres formats de données…
- [^] # Re: Non, ils ne sont pas mauvais
  
  Posté par rewind (Mastodon) le 25 octobre 2017 à 20:33. Évalué à 6.
  
  Ce n'est pas qu'un problème de DOM ou SAX. Comme d'autres l'ont dit avant, la plupart des parsers font une analyse syntaxique descendante qui requiert des appels récursifs (même si on pourrait les implémenter avec une pile explicite, ce n'est que rarement le cas). On pourrait aussi utiliser une analyse syntaxique ascendante telle que sont capables de la produire bison et ses copains. Dans ce cas, il n'y a aucun appel récursif (il y a en revanche toujours une pile explicite) et donc aucun risque de faire exploser a pile d'appels. Une analyse ascendante permettrait de repousser la limite du nombre d'imbrications bien plus loin que les chiffres (ridicules) donnés dans ce journal.
  - [^] # Re: Non, ils ne sont pas mauvais
    
    Posté par Laurent J (site web personnel, Mastodon) le 26 octobre 2017 à 14:11. Évalué à 4.
    
    Un parser SAX ne fait pas d'appel récursif, et surtout, au final tu n'a pas de représentation en mémoire de la totalité du contenu JSON. Ton JSON peut faire 40To, avoir 15 millions de niveaux, ton occupation mémoire ne sera au maximum que celle de la plus "grosse" feuille (dans le cas de JSON donc, que la taille de la plus grosse valeur de type chaîne).
    
    Bien sûr, si tu utilises un parser de type SAX pour tout charger en mémoire, autant utiliser un parser classique, puisqu'on se retrouve à avoir les mêmes problèmes.
# O Fortuna !

Posté par Claude SIMON (site web personnel) le 26 octobre 2017 à 09:09. Évalué à 5.

En lisant ce journal, je me suis dit que j'ai bien de la chance.

Il y a pas mal d'année de cela, j'ai codé, en C++, un parser que j'utilise encore intensivement. Bon, c'est un parser XML, pas JSON, mais la problématique est la même.

J'ai d'abord mis en place un système de callbacks. Le parsage était assuré par une fonction à laquelle je passais en paramètre, en plus du flux contenant les données à parser, une classe abstraite, dont une des méthodes virtuelles était appelée par le parser à chaque fois qu'il rencontrait un token, la méthode appelée dépendant de la nature du token rencontré.

Ce parser me servait essentiellement à désérialiser des structures de données, et, à l'usage, le système de callbacks ne s’avérait guère pratique. Il fallait en effet systématiquement mettre en place un automate pour garder trace du contexte pour pouvoir traiter correctement chaque token rencontré.

J'ai alors modifié le parser de manière à ce qu'il me rende la main à chaque token rencontré, et je le relançais autant de fois que nécessaire jusqu'à ce que l'ensemble des données soient traitées. Du coup, plus besoin de callbacks. Son utilisation consistait, à chaque balise rencontrée, à lancer un fonction dédiée au traitement du contenu de cette balise, et qui retournait à la fonction appelante une fois ce contenu traité. Donc, plus besoin d'automate ; la fonction en cours d'exécution lors du traitement d'un token me renseignait sur le contexte.

Quand j'ai lu ce journal, je me suis dit : "je dois avoir le même problème avec mon parser XML". Mais, après examen du code de mon parser et de la manière dont je l'utilisais, il s'est avéré que non. Pourtant, j'ai écrit ce parser de manière vraiment naïve, sans souci d'optimisation d'aucune sorte. Et je m'en sers notamment, en plus de la désérialisation, pour remplir ce que j'appelle une registry, grosso-modo un arbre auquel on peut affecter des attributs à chaque nœud, arbre qui, entre autres, me sert à stocker les paramètres de configuration de mes logiciels.

Du coup, je ne vois pas trop comment les parser JSON puissent soit-disant être aussi mauvais, compte tenu que, d’après l'expérience que j'ai des parser, la manière dont le parsage est réalisé dépend de la structure des données représentées par le fichier JSON (ou XML) parsé !

Ou alors, comme dit, j'ai simplement de la chance…

Pour nous émanciper des géants du numérique : Zelbinium !
- [^] # Re: O Fortuna !
  
  Posté par Laurent J (site web personnel, Mastodon) le 26 octobre 2017 à 14:13. Évalué à 3.
  
  J'ai d'abord mis en place un système de callbacks. Le parsage était assuré par une fonction à laquelle je passais en paramètre, en plus du flux contenant les données à parser, une classe abstraite, dont une des méthodes virtuelles était appelée par le parser à chaque fois qu'il rencontrait un token, la méthode appelée dépendant de la nature du token rencontré.
  
  C'est le même principe qu'un parser SAX. Tu aurais pu en utiliser un plutôt que de réinventer la roue ;-)
  - [^] # Re: O Fortuna !
    
    Posté par Claude SIMON (site web personnel) le 27 octobre 2017 à 08:35. Évalué à 1.
    
    Il n'existait pas beaucoup de parsers XML à l'époque. J'avais utilisé expat un temps, avant de l'abandonner pour je ne sais plus quelle raison.
    
    Ceci dit, d'avoir codé mon propre parser XML m'a simplifié le développement de mon préprocesseur XML, car j'ai pu facilement rajouter des fonctionnalités au parser . Si j'avais conservé expat comme parser, cela n'aurait pas été aussi simple…
    
    Pour nous émanciper des géants du numérique : Zelbinium !
- [^] # Re: O Fortuna !
  
  Posté par steph1978 le 27 octobre 2017 à 09:01. Évalué à 5.
  
  Tu as implémenté un "pull parser". J'utilisais ça en java avec la bibliothèque xmlpp.
  L'intérêt est l'inversion de contrôle par rapport au parseur SAX. En SAX, c'est le parseur qui contrôle le code applicatif, par l'intermédiaire des callbacks. En PP, c'est le code applicatif qui contrôle le parseur, par l'intermédiaire d'un itérateur de tokens.
# titre racoleur ?

Posté par steph1978 le 26 octobre 2017 à 15:07. Évalué à 2. Dernière modification le 26 octobre 2017 à 15:09.
En gros tu voulais parler récursivité et récursion terminale.

Au fait, pas besoin d'un fichier de 27ko, 9 lignes de bash font l'affaire:
```
for a in {1..994};
do
    printf '{"I":'
done
printf '"b"'
for a in {1..994};
do
    printf "}"
done
```
Python3 craque à 994, car il a une pile d'exécution par défaut limité à 1000.

JQ ne semble pas avoir de limite autre que ma patience à tester.

Après quel cas d'usage va demander d'imbriquer plus de 1000 objets ?
# Dure vie pour Ruby

Posté par lepieru le 26 octobre 2017 à 20:07. Évalué à 3.
La bibliothèque JSON inclue dans Ruby (MRI) nécessite d'expliciter la désactivation de la vérification de la profondeur comme ci-dessous :
```
JSON.parse(ARGF.read, max_nesting: false)
```
Voir la documentation de la fonction JSON.parse.

PS: si la profondeur maximum (max_nesting) est dépassée, la bibliothèque JSON ne « plante » pas, elle soulève une exception :)
# En Lisp tout marche toujours sans se poser de questions

Posté par galex-713 le 12 novembre 2017 à 16:14. Évalué à 0. Dernière modification le 12 novembre 2017 à 16:15.

Alors c’est pas pour dire, mais si quelqu’un implémentait un parseur json en lisp (notamment en scheme, où ce dont je parle est rendu obligatoire par le standard, mais ça vaut aussi pour toute implémentation décente de (common) lisp, et si ça vaut pas pour emacs lisp, ça serait facile de faire en sorte que si), bah yaurait aucun problème, læ programmeuseur n’aurait jamais aucune question à se poser, ça marcherait juste, tant qu’ya assez de ram, au pire ce serait un peu plus lent par rapport à ce qui serait possiblement optimisable, au bout d’un certain niveau…

Le fait est qu’assez généralement en lisp, obligatoirement en scheme, les entiers overflowent naturellement sur des bignum (càd en précision arbitraire, le programme devient juste plus lent, mais toujours fonctionnel, tant qu’ya assez de ram, les nombres peuvent être aussi gros qu’ya de place en ram pour les représenter), et ya de la « tail call recursion » que tout le monde systémise : ie tout appel récursif en fin de fonction (et c’est une bonne pratique de toujours faire ça) revient à faire un goto, et ne grossit en rien la pile (pas moins performant qu’une boucle).

Rappelons que la seule (à part le nouveau « do », un peu compliqué et trop générique, que tout le monde déteste) forme de boucle en scheme est la récursion, on l’utilise pour tout, naturellement elle a été optimisée en conséquence. Et dans les autres lisps c’est un peu pareil, juste pas nécessairement systémique (le bon usage reste à la récursion, mais ya aussi bcp de formes de boucles plus expressives que dans les autres langages, incluant toutes les formes de boucles des autres langages).

Donc voilà, j’dis ça j’dis rien… c’pas comme si en lisp on avait des structures de données plus simples qu’xml/json, plus efficaces, performantes, et qu’on avait l’habitude d’imbriquer par delà la raison depuis… fortran en fait (lisp est le deuxième vrai gros langage de prog de l’Histoire, le premier interprété, et le premier-pas-mal-de-trucs en fait).
- [^] # Et sans CPS
  
  Posté par galex-713 le 12 novembre 2017 à 16:23. Évalué à 0.
  
  Scheme gère les continuations/CPS, et parfois l’utilise pour implémenter la tail-récursion. Toutefois tout comme dans common lisp qui a rarement les continuations/CPS et qui implémente souvent la tail-récursion, scheme aussi peut le faire sans CPS. Rappelons que la possibilité de CPS ralentissent l’exécution du code.

Suivre le flux des commentaires

Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.