Rustre

Rustre est un compilateur Lustre écrit en Rust. Le but de ce projet est de fournir un compilateur plus agréable à utiliser que le compilateur officiel (meilleurs messages d'erreur, meilleure documentation, interface en ligne de commande plus intuitive), mais aussi d'explorer de nouvelles idées pour le design de compilateurs, s'inspirant notamment des travaux de Rust Analyzer et de rustc.

Éventuellement, nous aimerions aussi fournir un framework pour manipuler du code source Lustre, permettant de développer des outils en plus du compilateur (formattage de code par exemple).

Architecture classique d'un compilateur

Avant de présenter l'architecture du compilateur Rustre, nous allons présenter l'architecture classique d'un compilateur, afin d'en exposer les limites et expliquer pourquoi nous avons décidé de ne pas adopter cette approche.

Un compilateur est un programme qui prend du code source (lisible et rédigé par des humains) en entrée, et qui génère un fichier binaire (généralement exécutable). Dans le cas de Lustre, avec les outils officiels, on peut :

• générer l'extended code d'un programme (inlining de tous les nœuds pour n'en avoir plus qu'un seul)
• générer du code C équivalent à un programme
• générer un binaire équivalent à un programme
• générer un automate équivalent à un programme
• simuler un programme (sans compiler son code source)
• faire du model-checking sur un programme

Ici, on va se concentrer sur le cas où on veut générer un binaire.

Passes et représentations intermédiaires

Un compilateur se divise en plusieurs « passes » (comprendre « étapes ») successives, ayant chacune un rôle précis dans la manipulation du code source. Chaque passe utilise ses propres structures de données pour se représenter le code source, appelées « représentations intermédiaires » (en réalité, plusieurs passes consécutives peuvent utiliser la même représentation intermédiaire).

Généralement, on distingue ces passes :

• le lexeur, prend le code source sous forme de texte et produit une liste de tokens (~ mots) distints
• le parseur, utilise la liste des tokens pour construire un arbre représentant de manière abstraite le programme
• différentes passes de vérification (qui dépendent du langage et de ses règles), par exemple vérifier que les types sont cohérents
• différentes passes d'optimisation
• une passe finale qui génère du binaire

Lexeur

Le lexeur prend en entrée du code source et génère une liste de tokens, pré-découpant le code source pour faciliter son analyse. Cette étape élimine (généralement) des informations inutiles comme les espaces ou les commentaires.

On peut imaginer un lexeur Lustre qui prendrait ce code source :

const n = 4;

-- Multiplexeur à deux entrées
function multiplex (a, b, s : bool) returns (f : bool)
let
    f = (a and s) or (b and not s);
tel;

Et qui renvoie cette liste de tokens :

#![allow(unused)]
fn main() {
Const, Ident("n"), Egal, Int(4), PointVirgule,
Function, Ident("multiplex"), ParenGauche,
Ident("a"), Virgule, …
}

Parseur

Le parseur construit une représentation intermédiaire qu'on appelle AST (Abstract Syntax Tree). C'est une représentation du code source sous forme d'arbre.

Un parseur Lustre pourrait produire l'arbre suivant pour le code source précédent.

#![allow(unused)]
fn main() {
FichierLustre {
    declarations: [
        Constante { nom: "n", valeur: Entier(4) },
        Fonction {
            nom: "multiplex",
            entrees: [
                ("a", Bool),
                ("b", Bool),
                ("c", Bool),
            ],
            sorties: [
                ("f", Bool),
            ],
            equations: [
                "f", Or(
                    And(Var("a"), Var("s")),
                    And(Var("b"), Not(Var("s"))),
                ),
            ],
        },
    ],
}
}

Passes suivantes

Les passes suivantes vont vérifier certaines propriétés sur l'AST, le transformer et l'enrichir de nouvelles informations (ce qui demandera d'autres représentations intermédiaires, mais qui resteront généralement sous forme d'arbres).

Ces passes sont dans un ordre bien défini, et vont « en avant » (on exécute la première passe, puis on passe son résultat à la seconde, et ainsi de suite).

Inconvénients de cette approche

On a peu de résilience face aux erreurs : concevoir un AST qui peut être partiellement valide n'est pas possible (ou du moins, demande un travail spécial). Une erreur dans une passe fait s'arrêter la compilation entièrement, même si une partie du programme est valide et aurait pu être analysée d'avantage.

On doit également multiplier les représentations intermédiaires. Par exemple si on veut ajouter le type de chaque variable et de chaque expression, on doit redéfinir entièrement chaque type de l'AST. Puis, si dans une passe suivante on veut ajouter un compteur du nombre d'utilisation de chaque variable/fonction/nœud (pour émettre un avertissement si certains sont définis sans jamais être utilisés), on doit à nouveau redéfinir l'AST avec ce nouveau champ dans chaque type.

Rajouter une passe peut être compliqué, surtout dans le cas où on développe des outils parallèles au compilateur (plugin d'IDE, linter).

Pour palier aux inconvénients de l'architecture traditionnelle des compilateurs, on propose une nouvelle architecture basée sur :

1. un lexeur assez classique
2. un arbre de syntaxe qui hiérarchise les tokens dans un arbre, mais sans construire un AST dans lequel les informations sont synthétisées
3. un AST fonctionnel qui exploite les tokens dans l'arbre de syntaxe pour mettre en évidence la structure de l'arbre et les propriétés de chaque nœud
4. un système de queries (« demandes » / « requêtes ») inter-dépendantes

Pour celà, on s'appuie sur des crates déjà existantes, qui sont respectivement :

1. logos
2. rowan et nom
3. ungrammar
4. salsa

S'appuyer sur ces bibliothèques nous permet de gagner du temps, et de profiter d'implémentations performantes et bien testées des algorithmes dont nous avons besoin.

Arbre de syntaxe

Les arbres de syntaxe que l'on construit sont des arbres d'arité arbitraire, où chaque nœud est étiqueté par un token.

Les tokens sont représentés par un type énuméré, sans données associée aux constructeurs. Mais en plus des tokens produits par le lexeur (identifiant, mot-clé, constante, etc.), cette énumération contient des variantes qui permettent de donner une sémantique à l'arbre (« déclaration de fonction » par exemple).

Prenons le code suivant :

function id (x : bool) returns (f : bool)
let
    f = x;
tel;

Le lexeur produit une liste de token qui ressemble à :

#![allow(unused)]
fn main() {
Function
Ident // « id »
LeftParen
Ident // « x »
Colon
Bool
RightParen
Returns
LeftParen
Ident // « f »
Colon
Bool
RightParen
Let
Ident // « f »
Equal
Ident // « x »
Semicolon
Tel
Semicolon
}

Le « parseur » (étape 2 dans la liste donnée plus haut), va alors hiérarchiser les tokens de cette manière :

#![allow(unused)]
fn main() {
FunctionDeclaration
  Function
  Ident // « id »
  Parameters
    LeftParen
    VariableDeclaration
      Ident // « x »
      Colon
      Bool
    RightParen
  Return
  Outputs
    LeftParen
    VariableDeclaration
      Ident // « f »
      Colon
      Bool
    RightParen
  Let
  FunctionBody
    Equation
      EquationLHS
        Ident // « f »
      Equal
      EquationRHS
        Ident // « x »
    Semicolon
  Tel
  Semicolon
}

Naviguer dans l'arbre de syntaxe

Pour parcourir cette arbre de syntaxe facilement, on met en place une API fonctionnelle.

Les différentes fonctions de parcours de l'arbre étant très répétitives, on génère ce code à l'aide d'ungrammar. Cette crate permet à partir d'un fichier décrivant une grammaire, de générer du code source Rust arbitraire au moment de la compilation.

Par exemple, cette règle ungrammar :

Root = IncludeStatement* PackageBody? PackageList?

Genère ce code (pas besoin de le lire en détail, faut juste voir qu'avec une petite ligne on peut générer beaucoup de code répétitif) :

#![allow(unused)]
fn main() {
// Root

#[derive(Debug, Clone, PartialEq, Eq, Hash)]
pub struct Root {
    pub(crate) syntax: SyntaxNode,
}

impl AstNode for Root {
    fn can_cast(kind: Token) -> bool {
        kind == Token::Root
    }

    fn cast(syntax: SyntaxNode) -> Option<Self> {
        if Self::can_cast(syntax.kind()) {
            Some(Self { syntax })
        } else {
            None
        }
    }

    fn syntax(&self) -> &SyntaxNode {
        &self.syntax
    }
    fn expect(syntax: SyntaxNode) -> Self {
        Self::cast(syntax).expect("Failed to cast to Root")
    }
}

impl Root {
    pub fn all_include_statement(&self) -> impl Iterator<Item = IncludeStatement> {
        self.syntax().children().filter_map(IncludeStatement::cast)
    }
    pub fn package_body(&self) -> Option<PackageBody> {
        self.syntax().children().find_map(PackageBody::cast)
    }
    pub fn package_list(&self) -> Option<PackageList> {
        self.syntax().children().find_map(PackageList::cast)
    }
}
}

Manipuler l'arbre : le système de queries

Le système de queries est ce qui va permettre d'implémenter les différentes passes du compilateur.

Une query peut être vue comme une fonction : elle prend des paramètres en entrée, et calcule un résultat de sortie. Cependant cette fonction doit être pure : si les entrées sont les mêmes, alors les sorties seront les mêmes. De cette manière, on peut mettre en cache le résultat des queries et éviter de refaire plusieurs fois le même calcul.

Une query va généralement dépendre du résultat d'autres queries, qu'elle peut demander à exécuter. Mais contrairement à un système de passes classique, c'est la query qui indique de quoi elle dépend, et pas le système qui lui passe le résultat des passes précédentes en entrée.

Le système fonctionne donc « à l'envers » : on lance la query « génère du binaire », qui va demander à exécuter les passes précendentes, en remontant jusqu'aux premières passes (« construit un arbre de syntaxe pour tel fichier »).

Pour certaines queries, il est intéressant d'écrire leur cache sur le disque en plus de la mémoire, pour pouvoir les réutiliser la prochaine fois que le compilateur est lancé.

Avantages de cette architecture

On peut reconstruire facilement une petite partie de l'arbre de syntaxe (utile si on veut développer un « language server » ou un plugin d'IDE qui réagit dès que le code est modifié dans l'éditeur).

On ne perd aucune information : tous les tokens sont préservés, les commentaires et les espaces peuvent rester dans l'AST, sans pour autant nous gêner la plupart du temps (utile si on veut développer un formatteur automatique ou un générateur de documentation, mais aussi pour afficher des erreurs pertinentes).

C'est possible de créer un arbre de syntaxe partiellement valide. Si on arrive pas à parser quelques tokens, on peut les englober dans un nœud « Error » et passer à la suite.

On peut enrichir l'AST facilement en ajoutant des queries, sans avoir à redéfinir des représentations intermédiaires.

Lustre ayant des sorties variées (extended code, binaire, C, etc.), le système de queries est particulièrement adapté. On définit une query par type de sortie, et on les laisse définir leur dépendances, sans avoir à redéfinir toute la suite de passes à chaque fois.

Lustre étant un langage pur, on peut définir une query d'interprétation d'un nœud/fonction et mettre ses résultats en cache, pour créer un interpréteur intégré au compilateur qui soit efficace.

Lexeur (logos)

Code source

Pour écrire un lexeur facilement, on utilise la crate logos.

Cette crate fournit une macro procédurale qu'on peut appliquer à un enumération. Chaque variante de l'énumération est un token possible, et on les annote avec un attribut indiquant comment reconnaître ce token.

use logos::Logos; // on importe la macro

#[derive(Logos)] // on l'utilise pour générer le code du lexeur
enum Token {
    #[token("let")]
    Let,

    #[token("function")]
    Function,

    #[regex(r"[ \t\n\f]+", logos::skip)]
    Space,

    // etc.
}

fn main() {
    // la fonction Token::lexer est générée par logos
    let mut lexer = Token::lexer("let let function let");
    // lexer est un itérateur, donc on peut récupérer la liste de tous les
    // tokens avec un collect
    let tokens: Vec<_> = lexer.collect();
    assert_eq!(
        tokens,
        vec![ Token::Let, Token::Let, Token::Function, Token::Let ],
    );
}

Pour les différents attributs disponibles, voir la documentation de logos.

Normalement le lexeur est complet, mais si besoin d'autres tokens pourront être ajoutés.

Attention, beaucoup de variantes de l'énumaration Token ne sont en fait pas des tokens qu'on peut retrouver dans le code source, mais des étiquettes pour l'arbre de syntaxe (cf. le chapitre suivant). Seuls ceux avec un attribut de logos sont de vrais tokens.

Limitations

TODO

Sources

https://github.com/rust-lang/rust-analyzer/blob/master/docs/dev/syntax.md https://rustc-dev-guide.rust-lang.org/query.html