INF 321 / TD 6

Pierre-Yves Strub

On se propose d’écrire dans un ce TD un mini-compilateur pour le langage While, un langage de programmation procédural. La machine cible est la XVM qui a été présentée en cours et dont vous trouverez une description détaillée dans le polycopié du cours. Une implémentation en ligne de la XVM est fournie à l’adresse suivante:

http://www.enseignement.polytechnique.fr/informatique/INF321/xvm/

Afin de tester votre compilateur, on vous fournit une bibliothèque Java effectuant l’analyse syntaxique (parsing) et le typage de programme While.

Présentation de While

Types

Le langage While est un langage typé statiquement et possède seulement deux types de base: int pour les entiers machines et bool pour les booléens.

Expressions

Les expressions du langage sont construites à partir des variables (qui seront forcément locales à une procédure, il n’est pas possible de déclarer de variables globales), des constantes entières (en base 10), des valeurs booléennes true et false, ainsi que par application d’opérateurs built-in (telles l’addition ou la négation logique).

Les expressions incluent les appels de procédures (cf. section suivante) sous la syntaxe proc(e1, ..., en) où proc est le nom d’une procédure à $n$ arguments et e1, …, en sont des expressions qui tiennent lieu d’argument.

Procédures

Il est possible de définir des procédures en While. Une procédure peut prendre des arguments et peut retourner un résultat. Le corps d’une procédure contient une partie de déclaration de variables (avec optionnellement des valeurs d’initialisation), ainsi que le corps de la procédure sous la forme d’une séquence d’instructions:

rty name(ty1 arg1, ..., tyn argn) {
  tyx1 x1 = e1;
  ...
  tyxk xk = ek;

  $body;
}

Dans l’exemple ci-dessus, name est le nom de la procédure et rty est son type de retour (ou void si la procédure ne retourne pas de résultat). Cette procédure prend $n$ arguments respectivement de type ty1, …, tyn et qui sont nommés arg1, …, argn. Enfin, la procédure déclare $k$ variables locales nommées x1, …, xk, respectivement de type tyx1, …, tyxk et initialisées avec les expressions e1, …, ek - la partie initialisation étant optionnelle.

Les procédures peuvent être mutuellement récursives.

Instructions

Une instruction peut être une affection, une conditionnelle, une boucle while ou une sortie de procédure. Nous donnons leur syntaxe respective ci-dessous, où $block désigne un bloc d’instructions (c’est-à-dire soit une instruction, soit une séquence d’instructions entre accolades):

Instruction	Syntaxe
Affectation	`x = e;`
Evaluation d’une expression	`e;`
Conditionnelle	`if (e) $block else $block`
Conditionnelle (sans `else`)	`if (e) $block`
Boucle while	`while (e) $block`
Sortie de procédure	`return e;`
Sortie de procédure - pas de valeur de retour	`return ;`
Affichage d’une expression (+ NL)	`print e;`

Programme

Un programme est une suite de procédures.

Travail demandé

Installation de la bibliothèque de support

Nous allons commencer par installer et utiliser la bibliothèque de support pour ce projet. Téléchargez les bibliothèques suivantes et sauvez-les (e.g. en les glissant-déposant) à la racine d’un projet que vous créerez à l’occasion:

Ensuite, sélectionnez-les dans l’explorateur d’éclipse (fenêtre de gauche dans la vue par défaut - si elles n’apparaissent pas, rafraîchissez l’explorateur avec F5). Puis, faites un clic droit dessus et sélectionnez Build Path -> Add to Build Path, comme illustré ci-dessous :

Créez un fichier example.wil (vous pouvez créer un fichier via le manu File -> New -> File) à la racine de votre projet et copiez-y le programme While suivant:

int min(int a, int b) {
  if (a < b) return a; else return b;
}

void main() {
  print min(3, 5);
}

Enfin, copiez/coller le code source Java suivant, compilez-le et testez qu’il s’exécute sans erreur:

import java.io.*;
import java.util.*;

import edu.polytechnique.mjava.ast.topdecl.*;
import edu.polytechnique.mjava.parser.*;
import edu.polytechnique.mjava.toplevel.*;
import edu.polytechnique.mjava.typing.exn.*;

public final class TestParseAndType {
  public final static String PATH = "example.wil";

  public static void main(String[] args) throws IOException {
    try {
      MJavaTop.parseAndTypeProgramFromFile(PATH);
    } catch (MJavaParseError | MJavaTypingError e) {
      System.err.println(e.getMessage());
    }
  }
}

Ce code lit le contenu du fichier example.wil, puis en fait son analyse syntaxique et son typage en tant que programme While.

Écrire, en While, la fonction factorielle:
```
int fact(int x) {
  ...
}
```
et vérifier que cette dernière est acceptée par l’analyseur de syntaxe/types précédent.

Implémentation de référence

On vous fournit également une implémentation de référence:

mjava.jar

Vous pouvez exécuter l’implémentation de référence via la commande suivante:

 java -jar mjava.jar example.wil

Production d’un flux d’opcode

La bibliothèque xvmlib fournit une représentation des opcodes de la XVM (tels que ADD ou GSB) et des étiquettes logiques de saut. Ces étiquettes représentent des adresses logiques de code, i.e. qu’ils représentent une position nommée du code. Chaque instruction est représentée par une classe Java héritant de la classe abstraite AsmInstruction. Les étiquettes sont, quant à elles, directement représentées par le type String. Vous pouvez obtenir la description de toutes les instructions en consultant documentation de la bibliothèque.

Nous allons commencer par créer une classe permettant de créer un flux d’opcode et d’y placer en son sein des étiquettes logiques. Copiez dans votre projet la classe Java suivante:

import java.util.*;

import edu.polytechnique.xvm.asm.*;
import edu.polytechnique.xvm.asm.interfaces.*;

public final class CodeGen {
  private Vector<AsmInstruction>  instructions;
  private Map<String, Integer> labels;

  public CodeGen() {
    this.instructions = new Vector<AsmInstruction>();
    this.labels = new HashMap<String, Integer>();
  }

  public void pushLabel(String label) {
    throw new UnsupportedOperationException(); // FIXME
  }

  public void pushInstruction(AsmInstruction asm) {
    throw new UnsupportedOperationException(); // FIXME
  }

  @Override
  public String toString() {
    return Printer.programToString(this.instructions, this.labels);
  }
}

Cette dernière contient deux champs: instructions qui stocke la liste d’instructions en cours de construction et labels qui est un dictionnaire associant à chaque étiquette sa position dans la liste des instructions.

Implémentez les méthodes pushLabel et pushInstruction qui respectivement pousse une étiquette dans le dictionnaire labels ou une instruction en fin de la liste d’instructions instructions. (L’étiquette ne sera pas poussée à proprement parler dans la liste d’instructions instructions, mais son index sera sauvé dans le dictionnaire labels. L’index de l’étiquette devra pointer juste derrière la dernière instruction de la liste instructions au moment de l’insertion)
La classe TestCodeGen (source) contient une fonction main qui cré un programme XVM et affiche son code source en console. Utilisez la XVM en ligne pour exécuter le programme. Que fait ce dernier ?

Digression : le patron de conception de visiteur

Dans la suite de ce TD, nous allons utiliser le patron de conception de visiteur. Ce patron de conception est une manière de séparer un algorithme d’une structure de données. Le principe de base est de déporter dans une classe externe le comportement algorithme pour un ensemble de classes, en mettant en place un traitement adapté à chaque classe dudit ensemble.

En pratique, le modèle est réalisé de la façon suivante : chaque classe pouvant être visitée doit mettre à disposition une méthode publique accepter prenant comme argument un objet du type visiteur. La méthode accepter appellera la méthode visite de l’objet du type visiteur avec pour argument l’objet visité. De cette manière, un objet visiteur pourra connaître la référence de l’objet visité et appeler ses méthodes publiques pour obtenir les données nécessaires au traitement à effectuer.

En Java, ceci donne cela:

/* A simple class hierarchy (A/B/C tree) */
class A {
  public int value;

  public void accept(Visitor v) {
    v.visit(this);
  }
}

class B {
  public A   refa;
  public int value;

  public void accept(Visitor v) {
    v.visit(this);
  }
}

class C {
  public A refa;
  public B refb;

  public void accept(Visitor v) {
    v.visit(this);
  }
}

/* Visitor interface for that hierarchy */
interface Visitor {
  public void visit(A a);
  
  public void visit(B b);
  
  public void visit(C c);
}

/* A visitor counting the number of nodes in a given A/B/C tree */
class CountVisitor implements Visitor {
  protected int counter = 0;
  
  @Override
  public void visit(A a) {
    ++this.counter;
  }
  
  @Override
  public void visit(B b) {
    ++this.counter;
    b.refa.accept(this);
  }
  
  @Override
  public void visit(C c) {
    c.refa.accept(this);
    c.refb.accept(this);    
  }
}

/* A visitor summing all the values stored in a given A/B/C tree */
class SumVisitor implements Visitor {
  protected int sum = 0;
  
  @Override
  public void visit(A a) {
    this.sum += a.value;
  }
  
  @Override
  public void visit(B b) {
    this.sum += b.value;
    b.refa.accept(this);
  }
  
  @Override
  public void visit(C c) {
    c.refa.accept(this);
    c.refb.accept(this);    
  }
}

Compilation des expressions

Nous allons en premier lieu nous intéresser à la compilation des expressions - à l’exception des appels de procédures. Le résultat de la compilation sera un programme XVM qui évalue la-dite expression et pousse le résultat de cette évaluation en tête de pile.

Les expressions sont représentées par la classe abstraite Expr, chaque construction étant matérialisée par une sous-classe concrète de Expr. Vous pouvez obtenir la description de toutes les expressions en consultant la documentation de la bibliothèque.

Les expressions qui nous intéressent dans cette question sont EBool, EInt, EVar, EUniOp et EBinOp qui représentent respectivement les littéraux booléens, les littéraux entiers, les variables, les opérateurs arithmético-logique unaires et les opérateurs arithmético-logique binaires.

Copiez le code ci-dessous et implémentez les méthodes visit(XXX e), où chaque méthode visit(XXX e) implémente la génération de code pour une expression de type XXX. Cette classe, outre le champ CodeGen codegen qui sert à stocker les instructions générées lors de l’assemblage, contient un dictionnaire Map<String, Integer> offsets qui fournit les indices (ou offsets, ou positions), par rapport au registre FP, des variables locales — on rappelle que ce langage ne supporte pas la déclaration de variables globales.

Pour le moment, vous n’avez pas à vous préoccuper de la construction du dictionnaire offsets qui ne sera pas modifié pendant l’assemblage des expressions.

En exemple, on vous fournit l’implémentation de la méthode visit(UniOp uniop). Notez qu’il vous est possible d’appeler le générateur de code sur des sous-expressions par un simple appel récursif de la méthode visit. E.g., dans le cas des opérateurs unaires, this.visit(esub) appelle le générateur de code sur l’opérande esub.

On ne vous demande pas d’implémenter le short-circuiting des opérateurs booléens (e.g., l’assemblage de e1 && e2 évaluera toujours les deux opérandes e1 et e2).

import java.util.*;

import edu.polytechnique.mjava.ast.*;
import edu.polytechnique.mjava.ast.expr.*;
import edu.polytechnique.mjava.ast.visitor.*;
import edu.polytechnique.xvm.asm.interfaces.*;
import edu.polytechnique.xvm.asm.opcodes.*;

public class ExprCodeGen extends DefaultExprVisitor {
  protected final CodeGen              codegen;
  protected final Map<String, Integer> offsets;

  public void push(AsmInstruction asm) {
    this.codegen.pushInstruction(asm);
  }

  public void push(String label) {
    this.codegen.pushLabel(label);
  }

  @Override
  public void visit(EBool ebool) {
    final boolean value = ebool.getValue(); // Literal value
    throw new UnsupportedOperationException(); // FIXME
  }

  @Override
  public void visit(EInt eint) {
    final int value = eint.getValue(); // Literal value
    throw new UnsupportedOperationException(); // FIXME
  }

  @Override
  public void visit(EVar evar) {
    final String name = evar.getName(); // Variable name
    throw new UnsupportedOperationException(); // FIXME
  }

  @Override
  public void visit(EBinOp ebin) {
    final Expr eleft = ebin.getLeft(); // Left operand
    final Expr eright = ebin.getRight(); // Right operand
    final EBinOp.Op op = ebin.getOp(); // Operator
    throw new UnsupportedOperationException(); // FIXME
  }

  @Override
  public void visit(EUniOp euni) {
    final Expr esub = euni.getExpr(); // Operand
    final EUniOp.Op op = euni.getOp(); // Operator

    switch (op) {
    case NOT:
      this.visit(esub);
      this.push(new NOT());
      break;

    case NEG:
      this.push(new PUSH(0));
      this.visit(esub);
      this.push(new SUB());
      break;
    }
  }

  public ExprCodeGen(CodeGen codegen, Map<String, Integer> offsets) {
    this.codegen = codegen;
    this.offsets = offsets;
  }
}

La classe TestExprCodeGen (source) contient une fonction main qui créé un programme XVM à partir d’une expression et affiche son code source en console. (Le dictionnaire des positions des variables locales est construit pour vous, et utilise le fait qu’au démarrage la XVM positionne les registers FP/SP à 0) Utilisez ce code pour produire un programme XVM et utilisez la XVM en ligne pour l’exécuter.

Compilation des instructions

Nous allons maintenant nous intéresser à la compilation des expressions - à l’exception de l’instruction return. Le résultat de la compilation sera un programme XVM qui évalue la-dite instruction.

Les instructions sont représentées par la classe abstraite Instruction, chaque construction étant matérialisée par une sous-classe concrète de Instruction. Vous pouvez obtenir la description de toutes les instruction en consultant la documentation de la bibliothèque.

Les instructions qui nous intéressent dans cette question sont IBlock, IAssign, IIf, IWhile, IPrint qui représentent respectivement les blocs d’instructions, les affectations de variables, les conditionnelles, les boucles et l’instruction d’affichage.

Ici, la principale difficulté est la compilation du flot de contrôle. En effet, certaines instructions, telles la conditionnelle ou la boucle while, casse la linéarité de l’exécution. Par exemple, si la condition d’une boucle while est fausse, le flot doit passer à la première instruction après la boucle, ce qui s’effectuera par un saut via les instructions GTZ (saut conditionnel) et GTO (saut non-conditionnel). Nous donnons ci-dessous une représentation graphique d’assemblage de la boucle while:

Nous voyons que le résultat de l’assemblage de la condition et du corps de la boucle sont côte à côte dans le flot d’instructions. Cependant, des instructions de saut ont été intercalés: une après l’évaluation de la condition et qui fait un saut si cette dernière est fausse; et une à la fin du corps de la boucle qui permet de revenir à l’évaluation de la condition.

Copiez le code ci-dessous et implémentez les méthodes generateLabel et visit(XXX i), où chaque méthode visit(XXX i) implémente la génération de code pour une instruction de type XXX. On vous donne le début de l’implémentation de l’assemblage de la boucle while.

import java.util.*;

import edu.polytechnique.mjava.ast.*;
import edu.polytechnique.mjava.ast.expr.*;
import edu.polytechnique.mjava.ast.instruction.*;
import edu.polytechnique.mjava.ast.visitor.*;
import edu.polytechnique.xvm.asm.opcodes.*;

public class InstrCodeGen extends DefaultInstructionVisitor {
  private static int labelc = 0;

  public static String generateLabel() {
    // Generate a fresh label using `labelc'.
    // For example, lXXX where XXX is the value of labelc.
    // Two generated labels should never be equal.
    // A label must start with a lowercase letter.
    throw new UnsupportedOperationException();
  }

  protected final ExprCodeGen codegen;

  @Override
  public void visit(IIf iif) {
    final Expr cond = iif.getCondition(); // Condition
    final Instruction i1 = iif.getIftrue(); // 'then' branch
    final Instruction i2 = iif.getIffalse(); // 'else' branch
    throw new UnsupportedOperationException(); // FIXME
  }

  @Override
  public void visit(IWhile iwhile) {
    final Expr cond = iwhile.getCondition(); // Loop condition
    final Instruction body = iwhile.getBody(); // Loop body

    String lbl1 = generateLabel();
    String lbl2 = generateLabel();

    // Push start of loop label
    this.codegen.push(lbl1);
    // Assemble condition
    this.codegen.visit(cond);
    // If condition is 0, jump to lbl2
    this.codegen.push(new GTZ(lbl2));
    // Generate code for the body
    this.visit(body);
    // To be continued...
    
    throw new UnsupportedOperationException(); // FIXME
  }

  @Override
  public void visit(IBlock iblock) {
    final List<Instruction> is = iblock.getBody(); // Seq of instructions
    throw new UnsupportedOperationException(); // FIXME
  }

  @Override
  public void visit(IAssign iassign) {
    final String target = iassign.getLName().orElse(null); // Lvalue (can be null)
    final Expr expr = iassign.getRvalue(); // Expr to assign
    throw new UnsupportedOperationException(); // FIXME
  }

  @Override
  public void visit(IPrint iprint) {
    final Expr expr = iprint.getExpr(); // Expr to print
    throw new UnsupportedOperationException(); // FIXME
  }

  public InstrCodeGen(CodeGen codegen, Map<String, Integer> offsets) {
    this.codegen = new ExprCodeGen(codegen, offsets);
  }
  
  public InstrCodeGen(ExprCodeGen codegen) {
    this.codegen = codegen;
  }
}

La classe TestInstrCodeGen (source) contient une fonction main qui créé un programme XVM à partir d’une instruction et affiche son code source en console. (Le dictionnaire des positions des variables locales est construit pour vous, et utilise le fait qu’au démarrage la XVM positionne les registers FP/SP à 0) Utilisez ce code pour produire un programme XVM et utilisez la XVM en ligne pour l’exécuter.

Compilation des appels de procédure

Nous allons maintenant procéder à l’assemblage des procédures et de leurs appels. Pour cela, il faut décider de comment les arguments, variables locales, adresses de retour, etc… (ce qu’on appelle bloc d’activation) sont stockés et qui est en charge de construire et de nettoyer les différentes parties de ces blocs d’activation. L’ensemble de ces règles, qui varient d’une architecture et d’un langage à l’autre, est ce qu’on appelle la convention d’appel.

Nous allons maintenant définir la convention d’appel pour le langage While. Le bloc d’activation d’une procédure While est illustré sur le schéma ci-dessous où les deux derniers blocs d’activation actifs sont dessinés respectivement en vert et saumon:

On y voit que la pile sert à stocker plusieurs éléments: les arguments de la procédure, l’adresse de retour (qui servira quand on sortira de la procédure), une copie du registre FP de l’ancienne procédure et les variables locales. Il y a autant de blocs d’activation qu’il y a de procédures en cours d’exécution. Le dernier bloc d’activation est celui de la procédure active (i.e. de la procédure dernièrement appelée).

La convention d’appel est la suivante:

L’appelant pousse sur la pile l’ensemble des arguments de la procédure de gauche à droite.
Ensuite, il pousse sur la pile, dans cet ordre, une copie du register FP et la valeur courante du pointeur d’instruction. Ensuite, il positionne respectivement les registres FP & SP sur la valeur initiale de SP et l’adresse de code de la procédure. L’ensemble de ces opérations peut être fait via l’instruction GSB.
L’appelé commence son exécution et crée de l’espace sur la pile pour ses variables locales. Il a le droit de modifier le registre général R.
Une fois l’exécution terminée, l’appelé utilise le registre R pour retourner son résultat et enlève de la pile ses variables locales, puis saute à l’adresse de retour qui est maintenant en tête de pile et restaure la valeur de FP — ces deux valeurs, qui ont été sauvegardées par l’appelant en haut de pile, doivent être nettoyées. Ces dernières opérations peuvent être faites via l’instruction RET.
Finalement, l’appelant nettoie sa pile en y supprimant les arguments qu’il avait poussés initialement.

L’ajout des appels de procédures se fera à deux endroits. Dans l’assembleur pour les expressions (pour gérer la construction ECall) et dans l’assembleur des instructions (pour gérer la construction IReturn).

Modifiez votre classe ExprCodeGen pour y rajouter une méthode void visit(ECall ecall). Cette dernière implémentera la partie assemblage des appels de procédures, la méthode statique labelOfProcName(name) vous donnant le nom d’étiquette où il faudra sauter pour commencer à exécuter la procédure name.

class ExprCodeGen {
  public static String labelOfProcName(String name) {
    return String.format("P%s", name);
  }

  @Override
  public void visit(ECall ecall) {
    final String name = ecall.getName();     // Proc. name
    final List<Expr> args = ecall.getArgs(); // Proc. args

    throw new UnsupportedOperationException(); // FIXME
  }
}

Modifiez votre classe InstrCodeGen pour y rajouter une méthode void visit(IReturn ir). Cette dernière implémentera la partie assemblage des retours/sorties des appels de procédures.

class InstrCodeGen {
  @Override
  public void visit(IReturn ri) {
    final Optional<Expr> result = ri.getResult(); // Proc. result

    throw new UnsupportedOperationException(); // FIXME
  }
}

Copiez le code ci-dessous et complétez la méthode void visit(TProcDef proc) qui a en charge d’assembler une procédure dans son intégralité du point de vue de l’appelé (i.e. création des variables locales, puis exécutions du corps — le nettoyage de la pile étant fait par l’instruction return).

import java.util.*;

import edu.polytechnique.mjava.ast.*;
import edu.polytechnique.mjava.ast.expr.*;
import edu.polytechnique.mjava.ast.topdecl.*;
import edu.polytechnique.xvm.asm.opcodes.*;

public class ProgramCodeGen {
  public final CodeGen cg = new CodeGen();

  public static String labelOfProcName(String name) {
    return String.format("__%s", name);
  }

  public void visit(TProcDef proc) {
    final List<EVar> args = proc.getArgs(); // Proc. arguments
    final List<EVar> locals = proc.getLocals(); // Proc. locals
    final Instruction is = proc.getBody(); // Proc. body

    throw new UnsupportedOperationException(); // FIXME
  }

  public void visit(List<TProcDef> procs) {
    for (TProcDef proc : procs)
      this.visit(proc);
  }

  public ProgramCodeGen() {
    this.cg.pushInstruction(new GSB(labelOfProcName("main")));
    this.cg.pushInstruction(new STOP());
  }
}

Enfin, copiez/coller le code source Java suivant et servez-vous en pour compiler différent programmes While. Testez les produits de la compilation grâce à la XVM en ligne.

import java.io.*;

import edu.polytechnique.mjava.ast.*;
import edu.polytechnique.mjava.parser.*;
import edu.polytechnique.mjava.toplevel.*;
import edu.polytechnique.mjava.typing.exn.*;

public final class TestProgramCodeGen {
  public final static String PATH = "example.wil";

  public static void main(String[] args) throws IOException {
    try {
      Program prg = MJavaTop.parseAndTypeProgramFromFile(PATH);
      ProgramCodeGen cg = new ProgramCodeGen();

      cg.visit(prg.procs);
      System.out.print(cg.cg);
    } catch (MJavaParseError | MJavaTypingError e) {
      System.err.println(e.getMessage());
    }
  }
}

Enregistrements (optionnel)

Enregistrements en While

Nous allons étendre le langage While avec un système d’enregistrements (record) extensibles. Un enregistrement est un type composé qui contient d’autres variables (appelées champs) de noms et de types prédéfinis. Ils sont proches des classes Java sans méthode. En While, il est possible de déclarer de nouveaux enregistrements grâce au mot-clef record. Par exemple, le code suivant déclare un nouvel enregistrement point qui contient deux champs x et y de types int.

record point {
  int x;
  int y;
}

A l’instar de Java, il n’est possible que de stocker des références vers les enregistrements, et il faut toujours les allouer dynamiquement via le mot-cles new. Par exemple:

java point p = new point;

La valeur des champs d’un enregistrement fraîchement alloué est non spécifiée. Enfin, il est possible de lire/écrire la valeur d’un champ grâce à la notation pointée var.field. Par exemple:

point p = new point;
int z;

p.x = 0; p.y = 5; // Set  p.x && p.y
z = p.x * p.y;    // Read p.x && p.y

Enfin, les enregistrements sont extensibles, i.e. qu’il est possible de créer de nouveaux types enregistrements par extension d’un ancien. Ceci ce fait grâce au mot-clef extends, comme dans l’exemple suivant où les types rectangle et circle sont des extensions de shape, et possède donc un champ point center à ce titre:

record shape {
  point center;
}

record rectangle extends shape {
  int height;
  int width;
}

record circle extends shape {
  int radius;
}

Tout enregistrement qui en étend un autre peut-être vu (via un cast ou transtypage) comme un enregistrement du type qu’il étend:

void foo(shape s) {
  // some code
}

void main() {
  var circle c = new circle;
  foo(s); // s is cast to `shape`
}

Représentation mémoire

Les enregistrements sont représentés en mémoire par un espace continu qui permet de stocker les champs dans leur ordre de déclaration. Dans le cas d’extension d’enregistrements, la représentation restera contigue, et celle de l’enregistrement étendu précédera celle de l’extension. Par exemple:

Ainsi, la représentation mémoire de l’extension reste une représentation mémoire valide de l’étendu (au dessus, le champ center est à la même position pour shape, rectangle et circle), et l’opération de transtypage n’aura donc aucune incidence sur la représentation mémoire. Notez également que les champs de type enregistrement sont stockés par référence. (Ci-dessus, le champ center est une référence vers un point)

Travail demandé

On s’intéresse maintenant à la partie assemblage des enregistrements, la partie parseur / analyseur de type fournit en début de TD supportant déjà ces derniers. Notamment, le type Program possède un champ records qui contient une liste de tous les enregistrements définis.

Copiez la classe suivante qui va nous servir à stocker, pour chaque enregistrement, sa taille en mémoire ainsi que le décallage auquel sera stocké chaque champ (y compris les champs hérités par extension).

On vous demande de compléter la méthode visit1 qui calcule le RecordGenInfo pour l’enregistrement ty passé en paramètre et stocke le résultat dans le dictionnaire infos. Le premier argument mtypes est un dictionnaire qui contient toutes les définitions de type du programme. Notez qu’il n’est pas garanti que le RecordGenInfo du parent ait été calculé avant celui de son enfant.

import java.util.*;

import org.antlr.v4.runtime.misc.*;

import edu.polytechnique.mjava.ast.*;
import edu.polytechnique.mjava.ast.topdecl.*;

public class RecordGenInfo {
  public TTypeDef             definition;
  public int                  size;
  public Map<String, Integer> offsets;

  public RecordGenInfo(TTypeDef definition,
                       int size,
                       Map<String, Integer> offsets)
  {
    this.definition = definition;
    this.size = size;
    this.offsets = offsets;
  }

  public static void visit1(Map<String, TTypeDef> mtypes,
                            Map<String, RecordGenInfo> infos,
                            TTypeDef ty)
  {
    final String name = ty.getName(); // Record name
    final List<Pair<Type, String>> fields = ty.getFields(); // Record fields
    final TTypeDef parent = ty.getParent().orElse(null); // Parent (can be null)

    throw new UnsupportedOperationException(); // FIXME
  }

  public static Map<String, RecordGenInfo> visit(List<TTypeDef> types) {
    Map<String, TTypeDef> mtypes
        = new HashMap<String, TTypeDef>();
    Map<String, RecordGenInfo> result
        = new HashMap<String, RecordGenInfo>();

    for (TTypeDef def : types)
      mtypes.put(def.getName(), def);
    for (TTypeDef def : types)
      visit1(mtypes, result, def);
    return result;
  }
}

Modifiez ExprCodeGen de manière à ce que cette dernière possède un champ
```
Map<String, RecordGenInfo> types;
```
qui stockera toutes les informations (taille, décalages des champs) sur les enregistrements. Modifiez son constructeur en conséquence et adaptez votre code (InstrCodeGen, ProgramCodeGen) en conséquence. N’oubliez pas qu’à partir d’un programme prg de type Program, vous pouvez désormais construire le dictionnaire qui associe à chaque type son RecordGenInfo via un appel à :
```
RecordGenInfo.visit(prg.records)
```

Rajoutez et complétez les deux méthodes suivantes à ExprCodeGen, qui respectivement alloue un nouvel enregistrement et lit un champ dans une expression de type enregistrement :

  @Override
  public void visit(ENew enew) {
    final String recName = enew.getName(); // Record name
    throw new UnsupportedOperationException(); // FIXME
  }

  @Override
  public void visit(EGet eget) {
    final String recName = eget.getTargetType(); // Record name
    final Expr rec = eget.getTarget(); // Record expression
    final String field = eget.getField(); // Field name
    throw new UnsupportedOperationException(); // FIXME
  }

Modifiez la méthode visit(IAssign iassign) de InstrCodeGen afin que cette dernière prenne en charge l’écriture d’un champ d’un enregistrement:

  @Override
  public void visit(IAssign iassign) {
    // Lvalue (can be null)
    final IAssign.LValue lv = iassign.getLvalue().orElse(null);
    final Expr expr = iassign.getRvalue(); // Expr to assign

    if (lv == null) {
      // Result is dropped (copy your previous code)
      throw new UnsupportedOperationException(); // FIXME
    } else {
      String var = lv.name;
      Expr target = lv.target.orElse(null);

      if (target == null) {
        // Store in local variable `var` (copy your previous code)
        throw new UnsupportedOperationException(); // FIXME
      } else {
        // Store in field `var` of `rec`
        String rec = target.getType().get().asNamed().getName();
        throw new UnsupportedOperationException(); // FIXME
      }
    }
  }

Testez votre implémentation, par exemple avec le programme suivant:

record ipair {
  int x;
  int y;
}

record itriple extends ipair {
  int z;
}

int add2(ipair p) {
  return p.x + p.y;
}

int add3(itriple p) {
  return p.x + p.y + p.z;
}

void main() {
  itriple p = new itriple();
  p.x = 10; p.y = 5; p.z = 7;
  print add2(p);
  print add3(p);
}