Chapter 3 Les états mémoires

3.1 Aspects théoriques des états mémoires

Les paragraphes suivants ont pour but d'aborder la partie réalisation et implantation des états mémoires d'un point de vue théorique. Cependant, afin d'illustrer les propos, des allusions à la réalisation technique ont été faites.

3.1.1 But de la structure de données

Les états mémoires ont pour but de représenter en mémoire la pile d'exécution du programme. Cette entité est utilisée par les deux interpréteurs. Du point de vue extérieur, les états mémoires modélisent un empilement de quadruplets <i,v,t,s> sur lequel diverses opérations sont possibles.
Un quadruplet <i,v,t,s> est composé des quatre éléments suivants :

i : l'identifiant.
v : la valeur correspondant à l'identifiant.
t : l'objet : var, cst.
s : le type : entier ou booléen.

On distingue trois types d'opérations possibles sur les états mémoires :

Les opérations de manipulation/gestion de la pile.
Les opérations de modification des valeurs contenues dans l'entité.
Les opérations d'accès aux informations de la mémoire.

Figure 3.1: Exemple de représentation externe

3.1.2 Choix d'implantation

Au cours du projet, deux implantations différentes ont été faites pour réaliser la structure de données. La première, réalisée à l'aide de l'objet LinkedList en Java a été rapidement développée. La seconde, plus élaborée et plus performante a nécessité plus de temps de développement. Dans un premier temps, le fait d'avoir développé une version rapidement disponible a permis aux équipes chargées des interpréteurs de commencer leur travail sans attendre la version finale. Du point de vue utilisateur, les deux implantations proposent strictement les mêmes services et fonctions. Les deux parties suivantes traitent des avantages et inconvénients de chacune des implantations.

Liste chaînée

La LinkedList est un objet Java natif qui met à disposition une structure de données sous forme de liste chaînée. Techniquement, peu de manipulations sont nécessaires pour la transformer en pile. Il suffit d'ajouter en fin de liste les éléments qu'on ajoute à la pile, et de les prendre en fin pour dépiler. Avantage : l'implantation est rapide. En effet, l'objet natif de java possède de nombreuses fonctions :

des accesseurs (permet de retourner l'élément de début ou de fin de liste);
des manipulateurs (permet d'ajouter, de supprimer au début ou à la fin de la liste);
des itérateurs (objet en surcouche de la LinkedList qui permet de parcourir la liste chaînée).

Ces procédures permettent de satisfaire toutes les attentes des fonctions implantées pour la gestion des états mémoires. Inconvénients : L'inconvénient majeur résulte directement de la façon dont la structure de données est implantée. En effet, pour les fonctions d'accès à un endroit précis de la pile, le fait d'utiliser un iterator n'est pas optimal. Pour pallier ce problème, une autre implantation des états mémoires est possible, elle se base sur les tables de hachage.

Table de hachage

Principe général : dans cette configuration, les quadruplets sont communs à deux structures de données. Ils sont à la fois composants de la pile et éléments de la table de hachage. La table de hachage les indexe afin de pouvoir facilement accéder à la valeur qu'ils contiennent, et la pile permet d'avoir la structure souhaitée (Fig. 3.2).

Figure 3.2: Schéma sommaire

Caractéristiques de la table de hachage :

Les clés de la table de hachage sont les identifiants contenus dans les quadruplets.
Lors de l'utilisation des états mémoires, c'est-à-dire au moment de l'exécution d'un programme MiniJaja ou JaJaCode, il peut arriver que plusieurs quadruplets dans la pile possèdent le même identifiant. Comme nous l'avons vu précédemment, on souhaite cependant y avoir accès depuis la table de hachage (lors d'un accès direct), du moins pour la dernière occurrence. Pour permettre cela, une gestion des conflits doit être mise en place dans la table de hachage.

Gestion des conflits : Lorsque deux quadruplets possèdent le même identifiant (par exemple y apparaît deux fois) la table de hachage doit tous les référencer, et ce pour deux raisons :

pour permettre d'accéder directement au quadruplet de cet identifiant le plus haut sur la pile.
pour permettre l'accès au suivant, une fois le premier dépilé.

La table de hachage fonctionne de la manière suivante : une clé référence un emplacement. Si, lorsqu'on ajoute un élément dans la table, un objet est déjà dans l'emplacement pointé par la clé, on ne peut l'écraser pour mettre le nouveau. On se doit de gérer le conflit. Dans notre cas, le nouvel élément est accroché via un chaînage au bout de(s) l'élément(s) déjà présent(s). Ainsi, avec cette méthode d'ajout en détournant le conflit, l'élément le plus récent est ajouté au bout de la chaîne.

Figure 3.3: La gestion du conflit dans la table de hachage

Les deux quadruplets grisés (Fig 3.3) possèdent le même identifiant, ils sont donc chaînés à la suite depuis la table de hachage. Cependant ils ne sont pas chaînés à la suite sur la pile, car cela dépend de leur apparition dans le programme. L'implantation finale des états mémoires a été faite en utilisant ce procédé. Le chaînage des différents éléments s'est fait par référence entre objets. Pour ce qui est de la table de hachage, l'objet HashTable de Java a été utilisé. Les autres choix techniques d'implantation sont décrits dans la partie suivante.

3.2 Compte-rendu de réalisation

Les paragraphes suivants ont pour but d'expliquer l'implantation technique des états mémoires.

3.2.1 Choix techniques d'implantation

Le concept

Trois classes principales et deux annexes participent à l'implantation des états mémoires. L'imbrication de celles-ci se fait de la manière suivante : Classes principales :

EtatMemoire
ElementTableDeHachage
Quadruplet

Classes annexes :

Tas (fourni par le module tas)
HashTable (natif dans Java)

Figure 3.4: Interaction entre classes

Les classes

La classe `Quadruplet`

Cette classe permet de modéliser un quadruplet. Une instance de cette classe comporte quatre champs :

Un identifiant de type String.
Une valeur de type Object (dans notre cas on a soit un entier soit un booléen).
Un type de type String (ex : cst, var).
Une sorte de type String (ex : entier, booléen).

La classe `ElementTableDeHachage`

Les instances de cette classe ont pour objectif d'encapsuler les quadruplets dans la structure de données. A une instance de ElementTableDeHachage correspond une instance de la classe Quadruplet. Elles permettent de réaliser le chaînage dans la pile et dans la gestion de conflits de la table de hachage.

Figure 3.5: Vue d'un élément du chaînage

Une instance de la classe ElementTableDeHachage contient une instance de la classe Quadruplet (Fig. 3.5). Le double chaînage, que ce soit pour la pile ou pour la résolution des conflits de la table de hachage, a été choisi pour permettre un meilleur parcours des listes chaînées. Pour la pile, cela permet de parcourir de bas en haut ou inversement. Pour la table de hachage, cela permet un parcours aisé des éléments de même identifiant. Le but premier a été d'avoir une implantation générique de la structure de données afin de faciliter tout développement en surcouche.

La classe `EtatMemoire`

Cette classe correspond à la structure mère des états mémoires. Elle possède en données privées :

la table de hachage;
la référence sur une instance de ElementTableDeHachage pour indiquer le haut de la pile;
la référence sur une instance de ElementTableDeHachage pour indiquer le bas de la pile;
Le tas (instance de la classe Tas).

Toutes les fonctions suivantes, qui permettent une manipulation des états mémoires sont membres (soit en privé, soit en public) de cette classe.

3.2.2 Implantation des fonctions de manipulation des structures

private void insererDansTable(ElementTableHachage elmt)
Cette fonction permet d'insérer dans la table de hachage une instance de la classe ElementTableDeHachage. Pour ce faire, l'identifiant du quadruplet encapsulé dans cette instance est récupéré. Ensuite on utilise l'identifiant comme clé de la table et on regarde si l'emplacement concerné est pris. Si c'est le cas, on résout le conflit, sinon on l'ajoute à cet endroit.
private void retirerDansTable(ElementTableHachage elmt)
Cette fonction permet de retirer un élément de la table de hachage. A partir de l'identifiant du quadruplet encapsulé on regarde si l'élément est seul à sa place, si c'est le cas on le retire simplement. Sinon on retire l'élément de la chaîne de résolution de conflits et on raccroche les deux bouts.
private void insererAvant(ElementTableHachage elmt, ElementTableHachage elmtCourant)
Cette fonction permet d'insérer un élément avant un autre dans la pile. Pour ce faire on utilise le chaînage et la connaissance du haut de la pile. De ce fait on redescend dans la pile jusqu'à trouver l'élément concerné. De plus l'élément est ajouté dans la table de hachage.
private void insererAvantEtNonDansLaTable(ElementTableHachage elmt, ElementTableHachage elmtCourant)
Cette fonction permet d'insérer un élément avant un autre dans la pile. Pour ce faire on utilise le chaînage et la connaissance du haut de la pile. De ce fait on redescend dans la pile jusqu'à trouver l'élément concerné. Cette fonction à la particularité de n'insérer les quadruplets que dans la pile et non dans la table de hachage.
private void retirerElmt(ElementTableHachage EltADepiler)
Cette fonction a pour but de retirer un élément (et donc un quadruplet) de la structure de données générale. Il est retiré d'une part du chaînage de la pile, et retiré d'autre part de la table de hachage (avec conservation du chaînage s'il y avait conflit).
private ElementTableHachage dernierInsereDansTable(String Id)
Cette fonction retourne le dernier élément inséré dans la table de hachage pour un identifiant donné. Pour ce faire, à partir d'un identifiant, on accède à l'emplacement concerné de la table, on regarde si un chaînage est présent. Si c'est la cas, on parcourt toute la liste pour aller à la fin et chercher le dernier élément. Sinon on retourne simplement le seul élément présent à l'emplacement.

3.2.3 Opérations de manipulation externe de la mémoire

Ces fonctions correspondent aux fonctions membres de la classe EtatMemoire déclarées en public. Elles correspondent pour la plupart aux spécifications des états mémoires du cours. Chacune de ces fonctions utilise soit les fonctions privées vues précédemment, soit directement les données membres. Par exemple, la fonction creer initialise chaque donnée membre directement, tandis que la fonction depiler fait appel à la fonction privée retirerElmt. Remarques : l'interfaçage avec le tas est réalisé implicitement dans les fonctions qui l'utilisent. En plus des fonctions décrites dans les spécifications, des fonctions d'interfaçage ont été développées.

3.2.4 Opérations supplémentaires

Affichage de la mémoire

Pour ce faire, deux fonctions sont possibles : toString() et toHtml(). La première produit une sortie ascii en mode texte (sous forme de chaîne de caractères) qui représente la pile et les différents quadruplets qui la composent. La seconde permet aussi une sortie en ascii mais avec un texte enrichi de balises HTML pour permettre un affichage esthétique de la pile.

Affichage de la table de hachage

L'affichage de la table de hachage est permis grâce à la chaîne de caractères retournée par la fonction hashTableToString(), contrairement aux autres, cette fonction doit être appelée explicitement depuis une instance de la classe EtatMemoire. Elle permet de représenter avant tout la gestion des conflits entre les quadruplets de même identifiant.

3.2.5 Finesses et subtilités

Un des points noirs du développement des états mémoires est la gestion du Omega. En effet, lorsqu'un quadruplet est inséré dans la mémoire (par exemple, par la fonction empiler) et que celui-ci a un identifiant de type Omega (c'est-à-dire nul), on se doit de ne pas l'insérer dans la table de hachage. Une clé nul ne marche pas et une clé Omega est dangereuse car si une des variables du code source s'appelle Omega, alors il y a conflit. Pour pallier ce problème, lors de l'insertion d'un quadruplet, on teste l'identifiant. Si celui-ci est nul alors on ne gère l'insertion que dans la pile (le quadruplet encapsulé n'est chaîné que dans la pile). Sinon l'insertion se fait normalement : chaînage dans la pile et ajout dans la table de hachage.

3.2.6 Gestion des erreurs

Afin d'avertir les utilisateurs (les interpréteurs) de la mauvaise utilisation des états mémoires, différentes exceptions peuvent être levées.

EtatMemoireExceptionDeclarVarIncorrect: Exception levée par la fonction DeclarVar1 si l'interpréteur tente de déclarer une variable dans la pile (en général pour un passage de paramètre) là où il n'a pas le droit. C'est-à-dire là où l'identifiant du quadruplet n'est pas nul.
EtatMemoireExceptionElementPasDansTable: Exception levée par la fonction retirerDecl si l'identifiant de quadruplet passé par l'interpréteur n'est pas connu dans les états mémoires.
EtatMemoireExceptionPileVide: Exception levée par la fonction dépiler. Intervient si l'interpréteur fait appel à la fonction dépiler alors que la pile est vide.
EtatMemoireExceptionSwapIncorrect: Exception levée par la fonction de swap si la pile de dispose pas de suffisamment d'éléments (deux) pour échanger son sommet avec l'élément précédent.

La mailbox

Les exceptions précedentes sont lancées lorsqu'un problème d'interprétation est révelé. En effet, si le fichier MiniJaja original est correct, les deux interpréteurs ne doivent pas déclancher ces exceptions. Pour ce qui est des autres erreurs possibles (pile pleine, tas plein, accès incorrect en mémoire) un système différent a été utilisé: la mailbox (boîte de messages). Si au cours de l'utilisation des états mémoires une erreur de ce genre est décelée, un message est posté dans une boite temporaire. L'IHM vient relever la boite de messages après chaque appel à l'interpréteur. Si un message est présent, l'utilisateur en est directement averti. Ce système a été choisi pour les erreurs qui doivent être transmises à l'utilisateur. En effet, les exception auraient pu être utilisés mais la gestion de leur renvoi à travers les différentes couches objets (Interpréteur, Etats Mémoires et Tas) s'est avérée plus complexe à gerer.

3.3 Scénarii de test

Détails de scénarii globaux:

Validation de la structure interne et des fonctions de manipulation interne;
Validation des fonctions d'accès externe;
Test général de stress et de charge de la mémoire.

3.3.1 Données nécessaires au passage des tests

Ci-dessous la liste des données nécessaires pour passer les tests

Package Memoire
Package ASA
Classe Tas

3.3.2 Références des exigences testées

Bon chaînage de la pile.
Bon chaînage de la gestion des conflits dans la table de hachage.
Présence correcte dans la pile.
Présence correcte dans la table de hachage.
Respect des spécifications pour la fonction testée.

3.3.3 Détail des cas de test

Ci-dessous le détail des cas de test :

Chaînage avant de la pile.
Chaînage arrière de la pile.
Accès haut de la pile.
Accès bas de la pile.
Insertion d'un élément dans la pile.
Retrait d'un élément dans la pile.
Insertion de plusieurs éléments dans la pile.
Retrait de plusieurs éléments dans la pile.
Chaînage avant de la gestion des conflits sur la table de hachage.
Chaînage arrière de la gestion des conflits sur la table de hachage.
Test de la fonction creer() sur mémoire normale et chargée.
Test de la fonction empiler() sur mémoire normale et chargée.
Test de la fonction depiler() sur mémoire normale et chargée.
Test de la fonction echanger() sur mémoire normale et chargée.
Test de la fonction declVar() sur mémoire normale et chargée.
Test de la fonction declVar1() sur mémoire normale et chargée.
Test de la fonction declCst() sur mémoire normale et chargée.
Test de la fonction declTab() sur mémoire normale et chargée.
Test de la fonction declMeth() sur mémoire normale et chargée.
Test de la fonction affecterVal() sur mémoire normale et chargée.
Test de la fonction affecterValT() sur mémoire normale et chargée.
Test de la fonction affecterType() sur mémoire normale et chargée.
Test de la fonction RetirerDecl() sur mémoire normale et chargée.
Test de la fonction expParam() sur mémoire normale et chargée.
Test de la fonction val() sur mémoire normale et chargée.
Test de la fonction valT() sur mémoire normale et chargée.
Test de la fonction objet() sur mémoire normale et chargée.
Test de la fonction sorte() sur mémoire normale et chargée.
Test de la fonction parametre() sur mémoire normale et chargée.
Test de la fonction corps() sur mémoire normale et chargée.
Test de charge par insertion massive de quadruplets identiques (charge de la table).
Test de charge par insertion massive de quadruplets redondants (charge de la table).
Test de charge par insertion massive de quadruplets différents (charge de la pile).

3.3.4 Analyse des résultats de test

Cette partie a été rendue possible grâce aux fonctions d'affichage en mode texte des états mémoires. En effet, un test retourne directement sous forme de fichier les états de la mémoire à des intants choisis pendant le test. Il suffit alors d'observer l'évolution de la pile d'une part et de la table de hachage d'autre part pour obtenir le verdict du test. Au cours de la campagne de test de ce module, des corrections ont été faites sur la structure de donnée et plus précisement sur le chaînage des quadruplets. En ce qui concerne les tests de charge, la mémoire a très bien supportée l'insertion d'un très grand nombre de quadruplets que ce soit en mode identique , redondant ou différent.