Rapport du Projet MiniRust

Ce projet m’a permis d’apprendre de nombreuses notions sur la compilation ainsi que sur le système de types de Rust, qui m’a particulièrement fasciné. Dans ce document, je présente :

1. Une vue d’ensemble du projet
2. La partie la plus compliquée : génération des contraintes des durées de vie (Partie 3)
3. L’extension envisagée : génération de code assembleur
4. Conclusion

---

1. Vue d’ensemble du projet

• Objectif général :
  Implémenter un mini‐compilateur pour un sous‐ensemble de Rust (MiniRust), incluant la vérification des durées de vie (lifetimes) et la détection des emprunts invalides.

• Principales étapes :

  1. Analyse syntaxique et construction du MIR (Mid‐level Intermediate Representation).
     • Transformation de la syntaxe Rust simplifiée en une représentation intermédiaire (MIR).
     • Construction d’un graphe de contrôle et d’un graphe de données très rudimentaires.
  2. Vérification des accès mémoire et des emprunts :
     • Parcours du MIR pour vérifier que chaque porteur d’emprunt mutable/partagé respecte bien les règles de Rust.
     • Calcul des variables initialisées / non initialisées à chaque point.
  3. Génération des contraintes de durées de vie (Partie 3) :
     • Construction du graphe d’outlives, qui force la relation « ’l1 outlive ’l2 » quand un emprunt doit survivre plus longtemps qu’un autre.
     • Calcul des ensembles de durées de vie vivantes (lft_sets) en chaque point de programme via un fixpoint.
  4. Détection des conflits d’emprunts à l’aide d’“Active_borrows”.
     • À chaque instruction, vérifier si un emprunt actif s’oppose à l’écriture/lecture demandée.
  5. (Optionnel) Génération de code assembleur :
     • Proposition d’une extension pour transformer le MIR en un graphe de blocs puis en code machine à l’aide de “goto” et d’allocations optimisées.

---

2. Partie 3 : génération des contraintes des durées de vie

2.1. Enjeux et challenge

La partie 3 est, de loin, la plus complexe : il s’agit de déterminer, pour chaque variable de durée de vie (lifetime) introduite dans la fonction, à quels points du programme elle doit rester « vivante », et quelles autres lifetimes elle doit « outliver ».
Rust impose que, si on a un emprunt &'a T puis un emprunt &'b T utilisé à un même endroit, il faut que 'a = 'b ou bien 'a :> 'b (selon le contexte). MiniRust, n’ayant pas de sous‐typage, simplifie cela en demandant toujours l’unification des lifetimes lorsqu’on passe &'a T à un paramètre de type &'b T.

2.2. Construction du graphe outlives

• On maintient un référentiel outlives : LMap.t (map de lifetimes vers ensembles de lifetimes) :

  • add_outlives (l1, l2) ajoute l’arc l1 → l2 signifiant « l1 outlive l2 ».
  • unify_lft l1 l2 crée deux arcs l1 → l2 et l2 → l1, forçant l’unification ('a = 'b).

• Étapes clés :

  1. Contraintes implicites liées aux types des variables locales
     Pour chaque variable locale lv de type τ, on calcule implied_outlives prog τ : si τ contient un emprunt &'x …, on ajoute tous les arcs nécessaires pour mettre à jour outlives.
  2. Pour chaque instruction instr du MIR :
     • Si on a Iassign (pl, RVplace pl') :
       • On récupère tho1 = typ_of_place prog mir pl et tho2 = typ_of_place prog mir pl'.
       • On fait

         outlives := outlives ∪ implied_outlives(tho1) ∪ implied_outlives(tho2)

         pour remonter tous les lifetimes libres.
       • Puis on appelle la fonction récursive unify tho1 tho2 qui, lorsque tho1 = Tborrow(l1, …, inner1) et tho2 = Tborrow(l2, …, inner2), fait unify_lft l1 l2 et redescend (check inner1 inner2).
     • Si on a Iassign (pl, RVborrow (_, pl2)) :
       • On récupère Tborrow (lft1, …) pour la place cible pl.
       • On calcule d’abord implied_outlives pour le type de pl et pour le type de pl2 (le “source” de l’emprunt).
       • On parcourt ensuite récursivement les chaînes PlDeref … dans pl2 pour chaque niveau d’emprunt imbriqué : si pl2 = *p_inner a pour type Tborrow(lf, …), on ajoute add_outlives (lf, lft1) et on redescend.
     • Si on a une construction RVmake (nom_struct, champs) :
       • On appelle fields_types_fresh prog nom_struct pour obtenir (ltho, ctor_typ), c’est‐à‐dire la liste des types de champs « génériques » et le type du constructeur (Tstruct (nom_struct, fresh_lfts)).
       • Pour chaque champ, on fait remonter implied_outlives des deux côtés (generic_field_typ et typ_of_place prog mir place) puis on appelle unify generic_field_typ actual_field_typ.
       • Enfin, si ctor_typ = Tstruct(nom, fresh_lfts) et que la place assignée pl est Tstruct(nom, lfts), on fait List.iter2 unify_lft fresh_lfts lfts.
     • Si on a un appel Icall (f, args, ret_place, _) :
       • fn_prototype_fresh prog f renvoie (ltho, ret_typ, outlives_constraints) où ltho sont les lifetimes génériques du prototype, ret_typ son type de retour (ex : Tborrow('o,_,Tborrow('a,…))), et outlives_constraints une liste d’arcs explicites (l1, l2) déjà déclarés dans la signature ('a :> 'o par exemple).
       • Pour chaque paramètre typ dans ret_typ :: ltho et chaque argument arg, on fait :

         outlives := outlives ∪ implied_outlives(prog, typ) ∪ implied_outlives(prog, typ_of_place prog mir arg);
         unify typ (typ_of_place prog mir arg)

         afin de remonter les lifetimes et d’unifier borrows identiques.
       • Enfin, on ajoute explicitement chaque (l1, l2) issu de outlives_constraints en faisant add_outlives (l1, l2).

2.3. Calcul de l’ensemble living (lifetimes vivantes)

• On initialise living : LMap.t ref à vide, puis on parcourt chaque étiquette de programme:
  1. On obtient la liste des locaux vivants en ce point (live_locals lbl) à partir de Live_locals.go mir.
  2. Pour chaque local loc ∈ live_locals(lbl), on récupère ty = Hashtbl.find mir.mlocals loc puis on collecte free_lfts ty (ensemble des lifetimes libres dans ty). Pour chacun l dans cet ensemble, on fait add_living (PpLocal lbl) l.
  3. On ajoute aussi, pour chaque lifetime générique lft ∈ mir.mgeneric_lfts, un add_living (PpInCaller lft) lft, car toute lifetime générique est considérée « vivante » au point d’appel du caller.

2.4. Construction du fixpoint lft_sets

• On utilise le module Fix.Fix.ForType pour résoudre le plus petit ensemble satisfaisant la règle :