Plan du site  
pixel
pixel

Articles - Étudiants SUPINFO

Hatchet: Making-Of d'un langage - Partie 2: Le Retour

Par Léo-Paul COUTURIER Publié le 07/12/2017 à 10:59:20 Noter cet article:
(0 votes)
En attente de relecture par le comité de lecture

Résumé de l'épisode précédent: On va coder un langage de script pour le moteur Source avec Rust et LLVM. Ça va être cool.

Vu que maintenant c'est le moment ou je commence à coder, il faut visualiser que tout ce qui se passe ensuite se déroule dans une "montage sequence". Sélectionnez un morceau de musique adéquat (j'ai personnellement opté pour cet extrait de la bande originale d'Owarimonogatari) et let's go !

Chapitre 5: Où il faut qu'on revoie les bases

Il convient tout d'abord de définir ce qu'est un compilateur. J'ai déjà produit une vidéo qui en explique tout le fonctionnement dans le détail, alors pour résumer: un compilateur est un processus qui lit du code source en entrée, y applique une série de transformations, et génère de l'assembleur en sortie. Enfin à peux près. Ici c'est un peux plus compliqué, parce qu'on ne charge pas directement du code mais une map.

Je m'explique: l'éditeur Hammer utilise des fichiers VMF ("Valve Map File"), qui sont ensuite compilés par une série de programmes (d'abord VBSP pour générer les géométries, puis VVIS pour déterminer les lignes de vue, et enfin VRAD pour précalculer l'éclairage), pour finalement générer des fichiers BSP ("Binary Space Partition") pouvant être chargés par le moteur.

Le compilateur Hatchet va ici venir s'intercaler entre Hammer et VBSP: il charge un fichier VMF, le transforme, et en génère un nouveau qui est passé au reste de la chaîne. Les scripts Hatchet sont liés à la carte par le biais d'entités logic_hatchet, qui n'existent pas dans le moteur Source mais seront de toute façon supprimées à la compilation.

Pour ce qui est de l’exécution dudit script, le plan détaillé des opérations est le suivant: après avoir lu et parsé le code, le compilateur dispose alors d'un "AST" (je reviendrais la dessus plus tard). Celui-ci sert alors à guider l'étape de génération de code, qui utilise LLVM pour créer un module contenant du code IR. Ce code subit ensuite des passes d'optimisation (fournies par LLVM), puis est compilé et linké en assembleur (là aussi grâce au MCJIT de LLVM). Enfin, le code est exécuté et la map ainsi transformée peut être sauvegardée dans un nouveau fichier.

Chapitre 6: Où l'idée d’écrire un parser est peux réjouissante mais bon il faut bien passer par là

Bon si vous avez suivi, tout ça signifie que le compilateur doit avoir deux parsers: un pour les fichiers VMF, et un pour les fichiers Hatchet. Toutefois en s'y prenant bien il devrait être possible de réutiliser des morceaux entre les deux ... En fait, on va tout simplement utiliser la librairie nom pour concevoir les deux (pour être précis, son fork allégé synom).

Nom repose sur le principe de la combinaison de parsers: si on considère qu'un parser est une fonction qui prends du code en entrée et retourne un AST en sortie , on peux alors commencer par concevoir une série de parsers simple pour reconnaître des symboles, des noms, des valeurs littérales, des mots clés ... Puis les combiner pour former des fonctions plus complexes capable de reconnaître des structures comme des conditions, des boucles ou des objets.

Comme mentionné précédemment, la sortie d'un parser est ce qu'on appelle un AST ("Abstract Syntax Tree"), une représentation abstraite de la structure du code. Ce type de représentation est très simple à concevoir en Rust, qui supporte des types avancés d'énumérations. Pour le langage Hatchet en lui même, les définitions de l'AST ressemblent à ça:

            /// Fichier de script
pub struct Script {
    pub body: Vec<Statement>,
}

pub enum Statement {
    /// let [name] = [value]
    Binding {
        name: Atom,
        value: Expression,
    },

    /// while [condition] { body }
    Loop {
        condition: Expression,
        body: Vec<Statement>,
    },

    /// if [condition] { [consequent] } else { [alternate] }
    Branch {
        condition: Expression,
        consequent: Vec<Statement>,
        alternate: Option<Vec<Statement>>,
    },
}

pub enum Expression {
    /// Constante tableau
    Array(Vec<Expression>),

    /// Constante objet
    Map(HashMap<Atom, Expression>),

    /// Expression binaire
    Binary {
        lhs: Box<Expression>,
        op: Operator,
        rhs: Box<Expression>,
    },

    /// Nombre / String
    Literal(Literal),
}

pub enum Operator {
    Mul,
    Div,
    Mod,
    Add,
    Sub,
    Lt,
    Lte,
    Gte,
    Gt,
    Eq,
    Neq,
    And,
    Or,
}
        

Et l'AST des fichiers VMF est encore plus simple, puisque le format n'est finalement qu'un stockage clé-valeur structuré. Cet AST est d'ailleurs converti en un ensemble de HashMap à la fin de l'étape de parsing, beaucoup plus simple à parcourir par la suite.

Chapitre 7: Où une structure se voit attribuer le nom malheureux de Builder

Une fois que le fichier VMF a été chargé (et transformé), et que les scripts ont étés parsés a leur tour, il est temps de commencer à générer du code. Et pour moi, de générer du code capable de générer du code.

Mais d'abords, une abstraction s'impose. Si j'ai mentionné précédemment que l'IR de LLVM est un langage typé, il s'agit d'un typage de niveau machine et donc limité a quelques primitives: booléen ( i1), entiers ( i8, u8, i16, u16, ...), float ( f32, f64), structures, tableaux (de taille statique) et pointeurs. Il convient donc de construire un wrapper autour de ce système capable de représenter les types plus avancés utilisés par le langage Hatchet: les vecteurs (tableaux dynamiques), ou encore chaînes de caractères. Ce qui est aussi l'occasion d'encapsuler le fonctionnement de LLVM (écrit en C++) pour l'utiliser en Rust.

J'ai donc créé une énumération pour les différent types:

            pub enum TypeId {
    /// Types primitifs
    Void,
    f64,
    bool,
    i64,

    /// Pointeur vers la map
    Context,

    /// Types de chaines de caractères (je reviendrai la dessus aussi)
    Atom,
    Entity,
    String,

    /// Tableau statique
    Array {
        len: u32,
        ty: Box<TypeId>,
    },
    /// Tableau dynamique
    Vec {
        ty: Box<TypeId>,
    },

    /// Structure
    Object {
        items: Vec<(Atom, TypeId)>,
    },

    /// "Porte de sortie" pour représenter un autre type supporté par LLVM si nécessaire
    Other(LLVMTypeRef),
}
        

N'importe quelle valeur peut ainsi être représentée par un struct très simple:

            pub struct ValueRef {
    /// Pointeur vers la valeur dans l'IR
    pub ptr: LLVMValueRef,
    /// Type de la valeur associée
    pub ty: TypeId,
}
        

Une fois cette base posée, j'ai définit une structure Builder contenant tous les objets nécessaires a la génération de code et exposant une soixantaine de méthodes au total permettant de générer toutes les instructions d'IR (et 60 c'est seulement une petite partie du langage) utilisées par Hatchet.

Pour boucler la boucle, la génération de code se fait au final de manière grâce a une collection de seulement fonctions utilisées pour convertir les nodes d'AST en code:

            /// Injecte une série de statements (en général un bloc) dans le builder
pub fn statements<'a>(list: Vec<Statement>, mut scope: Scope<'a>, builder: &mut Builder);

/// Injecte le code d'une expression dans le builder, retourne le résultat
pub fn expression<'a>(exp: Expression, scope: &Scope<'a>, builder: &mut Builder) -> ValueRef;

/// Appelle une fonction avec son chemin et ses arguments, retourne le résultat
pub fn call<'a>(path: Path, args: Vec<Expression>, scope: &Scope<'a>, builder: &mut Builder) -> ValueRef;
        

En plus des types déjà présentés auparavant, on peux remarquer le paramètre scope. Pour simplifier, la structure Scope contient une HashMap faisant le lien entre le nom de chaque variable présente dans le contexte actuel, et sa valeur dans l'IR (spécifiquement le bloc de mémoire alloué à celle-ci). Il est intéressant de remarquer que si les fonctions expression et call prennent une référence au Scope, la fonction statement "consomme" l'objet, obligeant donc à créer un nouveau Scope pour chaque appel à la fonction: un bon exemple d'utilisation du système de type de Rust pour simplifier la détection d'erreurs (puisqu'en règle générale, chaque bloc dispose de son propre Scope).

Chapitre 8: Où il est question des différent types de String

Si vous êtes attentif (et j'espère que vous l'êtes), vous aurez remarqué le type Atom présent depuis le début dans mes morceaux de code. Ce type provient de la librairie string_cache, qui permet de placer les chaînes de caractères (ici les noms des entités et des variables) dans une table globale, et d'y référer ensuite par un simple nombre (en interne la structure Atom ne contient qu'un u64), permettant de simplifier la copie et la comparaison des chaînes de caractères dans le compilateur. De plus, la librairie permet de pré-remplir la table avec une liste de chaînes (par exemple les noms des fonctions), qui peuvent ensuite être pré-calculés avec la macro hct_atom!.

Pour des raisons pratiques, les entités sont aussi représentées en mémoire sous forme d'un Atom, mais sont considérées comme un type différent dans le code Hatchet (enum TypeId) , toujours dans l'optique d'utiliser le typage pour éviter les erreurs.

Enfin, il existe tout de même un type String pour manipuler de véritables chaînes de caractères. Comme tous les autres objets (tout ce qui n'est pas une valeur au type non-primitif, ce qui englobe aussi les Atom et les Vec) pouvant être alloués dynamiquement pendant l’exécution du script, leur mémoire est gérée par un allocateur de type Arena: toutes les allocations se font dans un bloc de mémoire qui est libéré dans son intégralité à la fin de l’exécution. Cette stratégie à l'avantage évident d'être largement plus simple à implémenter qu'un Garbage Collector complet, qui aurait eu de plus un impact négatif sur les performances puisque l’exécution d'un script Hatchet ne devrait de toute façon pas durer plus de 5 secondes.

Ouh la, bon c'est pas tout ça mais je viens de regarder l'heure là et il faut que je file, c'est bientôt l'heure de l'acte 3. Enfin avant de partir, laisser moi vous lâcher un petit cliffhanger:

Les FONCTIONS ! [ Musique dramatique]

A suivre ...

A propos de SUPINFO | Contacts & adresses | Enseigner à SUPINFO | Presse | Conditions d'utilisation & Copyright | Respect de la vie privée | Investir
Logo de la société Cisco, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société IBM, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Sun-Oracle, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Apple, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Sybase, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Novell, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Intel, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Accenture, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société SAP, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Prometric, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Toeic, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo du IT Academy Program par Microsoft, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management

SUPINFO International University
Ecole d'Informatique - IT School
École Supérieure d'Informatique de Paris, leader en France
La Grande Ecole de l'informatique, du numérique et du management
Fondée en 1965, reconnue par l'État. Titre Bac+5 certifié au niveau I.
SUPINFO International University is globally operated by EDUCINVEST Belgium - Avenue Louise, 534 - 1050 Brussels