Blog de Julian Ibarz

Un article de tanek    Pas de commentaires

Le parsing de fichier est souvent une tâche ingrate et compliquée que l’on doit parfois faire pour charger des données dans un certain format. Alors il existe maintenant le standard XML qui permet de mâcher le travail grâce aux APIs DOM et compagnie mais parfois on se retrouve avec des formats anciens non XML ou tout simplement le XML n’est pas adapté (fortes contraintes de performance, etc.).

Souvent la solution que prennent la majorité des gens (y compris moi) est de faire un analyseur tout à la main j’entends par là qu’on se met à écrire plein de code qui coupe le fichier en ligne, qui coupe la ligne en petit morceau, qui teste les petits morceaux, les regroupe, les mélange, fait des conversions chaîne données, fait des blocs if else de partout, etc. et on en arrive finalement, pardonnez-moi l’expression, à un vrai merdier. Et parfois cela peut aller très loin comme je vais vous l’expliquer un peu plus loin. Mais pourquoi je vous parle de tout ça ? Mais à cause du raytracer bien sûr ! Quoi, Vous ne comprenez pas le lien ? Je vous explique…

Les graphistes n’aiment pas le libre et les programmeurs ne savent pas desssiner !

Après avoir affiché mes 3 sphères dans mon raytracer en temps réel (voir le précédent billet), j’ai décidé qu’il serait temps de charger quelque chose de plus gros pour voir jusqu’où on pouvait aller sans optimisation.

Je me suis donc renseigné sur les scènes disponibles sur le net gratuitement et fort est de constater que je n’en ai pas trouvé ! J’ai trouvé quelques modèles par ci par là, rarement texturés mais jamais de scène entière 3D (si vous en connaissez, n’hésitez pas à me contacter !). Après discussion avec l’un de mes professeurs de rendu 3D, il m’a clairement dit que vu qu’ils n’avaient pas de graphistes dans leurs équipes, ils étaient obligés d’acheter des scènes lorsqu’ils voulaient faire des démos de leurs algorithmes de rendus. C’est surprenant mais en fait assez logique : comme presque tous les programmeurs 3D, je suis incapable de dessiner un simple modèle sous blender ou de créer une texture :D.

J’en ai donc profité pour lui demander une des scènes qu’ils avaient acheté. Le format de la scène est un format obj somme toute pas très compliqué et de type texte (comprendre : les données ne sont pas stockées en binaire) mais assez pour pouvoir se prendre la tête. En même temps j’en ai profité pour lui demander s’il n’avait pas un loader de fichier obj histoire de ne pas avoir à le faire et c’est là qu’il me file carrément un visualiseur de scène obj. Je n’en demandais pas tant !

Couper un coeur avec des geometry shaders ?

Entre temps j’ai quelqu’un qui me demande de lui faire une démo de coupe de modèles 3D de coeur pas simplement suivant un plan (car un simple clip plane aurait suffit) mais suivant des fonctions de décision plus complexes (coupe sphérique, cylindrique, etc.) histoire de faire plaisir aux docteurs et qu’ils puissent couper de façon plus personnaliser le coeur et voir dedans. Et grande chance : le format du modèle est aussi le format obj. Mais comme cela arrive souvent en informatique, j’essaye de le visualiser et cela ne marche pas. Que se passe-t-il ? Et bien apparemment le format du modèle 3D ne respecte pas strictement le format officiel et le parser le rejette.

Où l’encapsulation de code permet parfois de cacher des horreurs

Je me décide donc à ouvrir le capôt, en l’occurence à regarder le code du parser plus en détail et là c’est un véritable monstre que je vois : le parser est en gros constitué d’une fonction de pas moins de 2000 lignes de code illisibles, pouvant atteindre à certains endroits un niveau d’imbrication de 5 ou 6 if/else à la suite, des copiés collés en veux-tu, en voilà, utilisant mal et inutilement des templates variadics (voir la prochaine norme du C++0x), bref du code qui marche que sur la dernière version de gcc et même pas sur la dernière version de vc++ et qui ne marchera plus quand le C++0x sortira. Génial, je ne pensais pas que cela soit possible. Qu’à cela ne tienne, je modifie le parser pour qu’il arrive à lire mon obj et je me dis que j’en ai fini avec ça.

Du GNU GPL qui n’est pas libre

Mais voilà ces satanés licences qui continuent de m’embêter ! En effet, Je le préviens que j’ai mis son visualiseur sur le site de gitorious avec mon raytracer car je développe sur 3 PCs (mon portable qui n’a pas CUDA mais qui me permet de coder tranquilou quelques trucs, à la fac où j’ai CUDA et où j’en profite pour tester mon code fait la veille et enfin chez mes parents le week-end où j’ai un PC fixe avec CUDA) et que cela me facilite la vie. Mais voilà, même si les en-têtes de fichiers indiquent clairement que le code est sous licence GNU GPL, il me dit que le code du loader OBJ ne doit pas être accessible sur l’Internet car en fait il n’est pas sous licence libre. Entre le fait que le code soit horrible et qu’il soit protégé, s’en est trop, je décide de le réécrire.

Finalement, une fois avoir terminé mon parser, je me suis rendu compte que le parser de mon prof était en fait celui-ci :

http://www.cs.kuleuven.ac.be/~ares/libobj/index.html

Et qui est en fait en GNU GPL. D’ailleurs si vous l’utilisez, je vous encourage à utiliser plutôt le miens car il est quand même deux fois plus rapide (voir plus loin).

Un compilateur qui fait un compilateur, ou le problème de la poule et de l’oeuf ?

Je décide donc de me renseigner sur des techniques pour simplifier le code. je commence par jeter un oeil sur boost regexp qui permet de faire des analyses de chaîne en utilisant les expressions régulières. Comme d’habitude avec boost, c’est très puissant et très concis d’utilisation. J’arrive à supprimer quelques centaines de lignes mais j’arrive à un stade où l’utilisation seule des expressions régulières n’est plus suffisante et où il faudrait pouvoir définir une règle de grammaire pour analyser différents cas possibles pour un même type de donné. De plus, je n’arrive pas à rejoindre les performances du parseur d’origine (qui est codé cradement mais qui est sacrément rapide : il charge ma scène en 23 secondes et je n’arrive qu’à 45 secondes avec mes expressions régulières sachant que je ne les ai utilisé que pour le quart de l’analyse, je me dis que si je continue comme ça, j’arriverai à un code un peu plus simplifié mais qui me chargerait la scène en 2 minutes ce qui n’est pas acceptable).

Le flex du bison fait des calculatrices…

Je décide alors de changer de fusil d’épaule, je regarde dans les technologies de génération de compilateurs. Je regarde s’il en existe pour le langage C++ en licence permissive (LGPL, BSD-like, histoire de pouvoir le réutiliser dans un contexte professionnel fermé si besoin est) mais je n’en trouve aucune. Je regarde ensuite pour le langage C et j’en trouve quelques uns. J’avais le choix entre antlr et yacc/lex. J’ai choisi yacc/lex, allez savoir pourquoi. Et finalement j’ai choisi bison/flex (qui est lui en licence GPL) car les seuls exemples à la « hello world » version génération de compilation (comprendre créer une calculatrice qui sait faire des additions et des multiplications, youhou !) que j’ai trouvé étaient pour lui (mais apparemment il utilise la même syntaxe que yacc/lex donc ce sera facilement portable). Et puis les paquets sont souvent installés partout à la différence de yacc/lex.

…et il cours très vite !

J’installe le monstre en quelques secondes (vive linux et les packages) et je commence à tester la bête. Il me faut une journée pour créer un analyseur de fichier obj minimaliste (comprendre qu’il ne gère pas toute la syntaxe), environ 200 lignes de code ma fois assez claires et je commence à tester ses performances et là bonne surprise : il explose les perfs (6.5 secondes pour parser le fichier !).

Après deux bons jours de développement, j’arrive à finir mon parseur et à le connecter à mon visualiseur et j’arrive à un parsing de l’ordre de 8 secondes au lieu de 22. Et même au niveau de la taille du code, je le divise par trois et il est bien plus clair !

Si vous voulez télécharger ce projet, tappez les commandes suivantes :

git clone http://git.gitorious.org/personal-julian-ibarz/math.git
git clone http://git.gitorious.org/personal-julian-ibarz/obj-parser.git
git clone http://git.gitorious.org/personal-julian-ibarz/obj-viewer.git

Ensuite allez dans les différents projets (math, ensuite obj-parser et enfin obj-viewer) et tappez :

Vous n’avez plus qu’à tester avec une scène obj que vous avez ! Si ça ne marche pas, n’hésitez pas à me contacter !

Pièges à éviter

J’ai eu quelques problèmes en utilisant bison/flex et j’aimerais vous les faire partager. Il faut tout d’abord faire attention au fait que le retour à la ligne sous windows est « \r\n » et sous linux « \n ». Ensuite si vous vous amusez à parser des flottants, il faudra bien faire attention à mettre la locale par défaut. Voici un bout de code qui montre comment faire :

Enfin, pour l’analyse syntaxique, il faut absolument que vos différents types de mots n’aient pas de collision. J’entends par là que si vous définissez par exemple les entiers et les flottants comme suit :

Cela ne marchera pas car si vous définissez la capture du flottant en premier, tous les entiers seront transformés en flottant. Pour éviter cela, vous devez forcer la détection du point (enlever ? après le point) quitte ensuite à gérer dans l’analyse syntaxique le cas où un flottant a été reconnu comme un entier :

Enfin, ne jamais utiliser l’expression régulière suivant « .* » car sinon votre parser va analyser tout votre fichier d’un coup et va même faire un segfault. Si vous voulez parser toute une ligne jusqu’à la fin vous pouvez utiliser « [^\n]* ». Ensuite si vous avez besoin de changer la façon dont votre parser analyse la chaîne suivant qu’il est dans un commentaire par exemple (on ne veut pas s’il y a un nombre qu’il dise qu’il a trouvé un nombre), vous devrez utiliser les exclusions :

Je vous laisse le soin d’aller voir la doc officielle pour plus de détails.

Enfin, si vous programmez en C++ et si vous utilisez flex/bison et non pas flex++/bison++, je vous conseille fortement de ne pas utiliser un pattern singleton car vous allez galérer pour accéder aux données de votre parser. Préférez un pattern module :

Dans parser-private.h on fait comme si c’était de portée privée

Dans parser.h il y a tout ce qui est de portée publique

Dans parser.cpp :

Pour ceux qui ont « Le langage C++ » de Bjarne Soustrup, il l’explique très bien. Cela permettre de pouvoir accéder directement aux membres dans les fichiers parser.y et parser.lex de cette manière :

Au lieu de faire si vous aviez utilisé un singleton :

En plus c’est pas terrible niveau performance. Quelle est la motivation d’accéder directement aux données ? et bien parce que je considère que les fichiers parser.lex et parser.y sont en fait l’implémentation de mon parser donc c’est normal de pouvoir accéder directement à mes données…

Voilà pour les astuces, j’espère que ça vous sera utile !