:: Enseignements :: ESIPE :: E4INFO :: 2017-2018 :: Java Avancé ::

Examen de Java Avancé

Ce TP a pour but de créer une structure de données VariableLookup que l'on trouve communément dans les compilateurs (enfin que l'on trouvait, car maintenant on fait mieux) et qui associe à un nom de variable une position dans la pile.
En supposant que l'on utilise un langage qui ressemble à du C, on peut voir le code comme une succession de:

création de variable (ça correspond à réserver une case sur la pile),
accès au contenu d'une case correspondant à une variable.

Lors de la création d'une variable, on associe une case mémoire à cette variable. Et lors de l'accès au contenu d'une variable (représentée par le nom de la variable suivi d'un point d'interrogation dans les exemples) on détermine dans quelle case mémoire se trouve le contenu de la variable, donc il faut pouvoir savoir à quelle case mémoire elle est associée.
On supposera que, comme en C, les variables n'existent plus après l'accolade fermante du bloc qui déclare cette variable.

  {
      int a;  // case 0
      int z;  // case 1

      a?      // valeur de la case 0

      {
          int a;    // case 2
          a?        // valeur de la case 2

          int c;    // case 3
          z?        // valeur de la case 1
      }

      a?      // valeur de la case 0

      {
          int c;    // case 2
      }

      c?      // ahhh, erreur
      int a;  // ahhh, erreur
  }

VariableLookup est une classe qui permet de gérer les variables d'un bloc. Lorsqu'un bloc est lui-même imbriqué dans un autre bloc (englobant), on utilisera un VariableLookup parent pour accéder à la gestion du bloc englobant. Le VariableLookup parent d'un bloc qui n'est imbriqué dans aucun autre sera null.
La classe VariableLookup possède les méthodes suivantes:

une méthode create qui prend en paramètre une autre VariableLookup ou null qui servira de parent lors de la recherche.
une méthode addVariable qui prend en paramètre le nom de la variable et ajoute cette nouvelle variable en lui associant un numéro de case mémoire. Elle renvoie l'indice de la case mémoire correspondante ou lève une exception si la variable existe déjà dans l'instance VariableLookup courante.
une méthode size qui renvoie le nombre de variables déclarées par le VariableLookup et ses ancêtres (le parent, le parent du parent, etc).
une méthode find qui prend en paramètre le nom de la variable et renvoie soit l'indice de la case mémoire associée, soit rien, si aucune variable avec ce nom n'est trouvée. Il s'agit donc d'une valeur optionnelle (un Optional en Java).
Lorsque l'on recherche une variable, on cherche d'abord dans le VariableLookup courant et si on ne trouve rien, on va chercher dans le VariableLookup du parent (celui fourni lors de la création), etc.

Voilà le même code que précédemment annoté avec les appels de méthodes correspondant

  {           // lookup = VariableLookup.create(null);
      int a;  // lookup.addVariable("a");
      int z;  // lookup.addVariable("z");

      a?      // lookup.find("a");

      {              // lookup2 = VariableLookup.create(lookup);
          int a;     // lookup2.addVariable("a");
          a?         // lookup2.find("a");

          int c;     // lookup2.addVariable("c");
          z?         // lookup2.find("z");
      }

      a?      // lookup.find("a");

      {              // lookup3 = VariableLookup.create(lookup);
          int c;     // lookup3.addVariable("c");
      }

      c?      // lookup.find("c");
      int a;  // lookup.addVariable("a");
  }

Rappel: vous devez configurer le workspace d'Eclipse (File > Switch WorkSpace) pour qu'il corresponde au répertoire EXAM que vous avez dans le home de votre session de TP noté.
Vous pouvez consulter les transparents de cours ainsi que la documentation de l'API Java 9. Cette dernière est disponible en local ici: file:///usr/local/apps/java9/docs/index.html.

Afin de faciliter la correction, on vous demande de tout écrire dans le fichier VariableLookup.java: il est interdit d'écrire du code dans un fichier auxiliaire.

Exercice 1 - VariableLookup

Les tests JUnit pour toutes les questions du TP sont dans la classe VariableLookupTest.java.

Écrire la classe VariableLookup ainsi que les méthodes create, addVariable, size et find. Dans un premier temps, ne vous préoccupez pas de la notion de parent (vous le ferez à la question suivante).
Modifier le code de la classe VariableLookup de façon à prendre en compte la notion de parent. La méthode size doit toujours avoir une implantation en temps constant.
Écrire une méthode forEach qui prend en paramètre un consommateur à deux arguments et appelle celui-ci pour chaque nom de variable et l'indice de sa case mémoire. Cette méthode doit passer en revue l'ensemble des variables contenues dans le VariableLookup et ses ancêtres (le parent, le parent du parent, etc).
Note: il est possible d'avoir plusieurs fois le même nom de variable avec des indices différents. Donc on doit toujours parcourir les variables d'un VariableLookup avant celles de son parent, par contre pour un VariableLookup l'ordre dans lequel les variables doivent être parcourues n'est pas défini.
Ajouter une méthode createWithInsertionOrder qui créé VariableLookup qui garantit que le forEach (ainsi que toutes les futures méthodes de parcours) va parcourir les variables dans l'ordre d'insertion.
Attention: on ne veut pas qu'un VariableLookup créé avec create paie le coût de conserver l'ordre.
Attention 2: ne dupliquez PAS le code.
Conseil: si vous ne voyez pas, passez à la suite, cette question est indépendante du reste.
Écrire une méthode sizeIterator qui renvoie un itérateur indiquant la taille (size) de chaque VariableLookup, en envoyant d'abord celui du VariableLookup courant, puis celui de son parent, puis celui du parent du parent, etc.
Par exemple, avec l'exemple de code donné plus haut, l'itérateur pour lookup3 devra renvoyer 3 puis 2.
L'itérateur devra être non mutable.
On souhaite écrire une méthode stream qui renvoie les couples (nom de la variable/indice de la case mémoire) sous forme de Map.Entry pour l'ensemble des variables contenues dans un VariableLookup et ses ancêtres.
L'idée est que l'on peut:
- créer un Stream sur la liste chaînée des parents, et
- pour chaque VariableLookup, lui associer l'ensemble des variables qu'il contient.
Pour le premier point, il faut utiliser la méthode Stream.iterate à 3 arguments. Pour le second point, à vous de trouver.
Écrire la méthode stream.
Commenter le code de la méthode stream et ré-implanter celle-ci en utilisant votre propre Spliterator.
Note: on ne demande pas que le Stream soit parallélisable.
Si ce n'est pas déjà le cas, assurez-vous que le test testStreamUserDefinedFastEnough passe.
Question Bonus: à ne faire que si vous avez déjà correctement répondu à l'ensemble des questions précédentes.
Si l'on oublie les tests sur les préconditions, la méthode find peut s'écrire sur une ligne, en une seule expression... Comment faire ? (garder l'ancien code en commentaire !).