Tutoriel sur la compréhension de la machine virtuelle Java

| Yohan Beschi (Soat) | Soat |

Alors que des frameworks apparaissent presque tous les jours, ajoutant de plus en plus d'abstractions et rendant, par conséquent, le travail du développeur beaucoup plus simple, la connaissance du fonctionnement de la JVM n'est plus autant diffusée qu'il y a une dizaine d'années. Pour preuve, aucun livre sur la machine virtuelle Java n'est sorti depuis le début des années 2000. Pour de nombreuses personnes, la JVM est une boîte noire et elles ne cherchent pas à comprendre ce qu'il se cache derrière cet outil magique. Bien que la JVM soit dans son ensemble extrêmement complexe, nous pouvons l'étudier en la découpant en plusieurs parties. De plus, je reste convaincu qu'apprendre comment fonctionne la JVM ou toute autre machine virtuelle fait de nous de meilleurs développeurs, que ce soit dans la compréhension du langage, mais aussi des performances.

Pour cette raison, j'ai décidé de consacrer une quarantaine de parties à la JVM, et d'une manière plus générale aux machines virtuelles.

Un article publié sur le Web a plusieurs avantages. Outre le fait d'être gratuit :

- il n'y a aucune limitation dans le nombre de pages et par conséquent les bouts de code seront complets et présentés sous une forme lisible ;

- toute erreur peut être corrigée rapidement ;

- le côté communautaire d'Internet pourra être utilisé pour améliorer le contenu, partager des connaissances, etc.

Notes importantes

- Tous les outils développés pour cet article ont uniquement un but éducatif.

- Tout le code présenté sera librement disponible sur Github. Chaque partie aura ses propres tag et branche.

- Sauf mention contraire, les termes bytecode et JVM feront respectivement référence au bytecode Java et à toute machine virtuelle Java respectant la Spécification de la JVM (JVMS).

Pour réagir au contenu de cet article, un espace de dialogue vous est proposé sur le forum Commentez .

- Titre : Tutoriel sur la compréhension de la machine virtuelle Java

- Auteurs : Yohan Beschi (Soat), Soat

- Parution : 24 mars 2015

- Mise à jour : 25 août 2016

- Licence : Copyright ® 2016 SOAT. Aucune reproduction, même partielle, ne peut être faite de ce site et de l'ensemble de son contenu : textes, documents, images, etc. sans l'autorisation expresse de l'auteur. Sinon vous encourez selon la loi jusqu'à trois ans de prison et jusqu'à 300 000 € de dommages et intérêts.

Sommaire

- I. Préambule

- I-A. Passé, présent et futur de la JVM

- I-B. Sommaire

- I-C. What's next ?

- I-D. Utiliser le code

- I-D-1. Github

- I-D-2. Chaîne de compilation

- I-D-2-a. ANT

- I-D-3. Organisation du projet

- I-E. Tester les exemples

- I-F. Nombre magique

- I-F-1. Implémentation

- II. Introduction à la JVM

- II-A. Généralités sur la JVM

- II-B. Zones de données d'exécution (Runtime Data Areas)

- II-B-1. Le tas (HEAP)

- II-B-2. Zone de méthodes (METHOD AREA)

- II-B-3. Pool de constantes d'exécution (RUNTIME CONSTANT POOL)

- II-C. Fils d'exécution (THREADS)

- II-D. Pointeur d'instruction (PROGRAM COUNTER)

- II-E. Piles Java (JAVA VIRTUAL MACHINE STACKS)

- II-F. Piles de méthodes natives (NATIVE METHOD STACKS)

- II-G. Cadres (FRAMES)

- II-G-1. Variables locales

- II-G-2. Pile d'opérandes

- II-G-3. Liaison dynamique

- II-H. What's next ?

- III. Bytecode avec Plume Java Bytecode Assembler (PJBA)

- III-A. Getting Started

- III-B. Descripteurs

- III-C. Commentaires

- III-D. Classes

- III-E. Méthodes

- III-F. Noms

- III-G. Encodage

- III-H. Créer un fichier classe en Java

- III-I. Utilisation du code source

- III-I-1. Assembleur

- III-I-2. Scripts de construction Ant

- III-J. What's next ?

- IV. Constantes

- IV-A. Vocabulaire lié à la pile

- IV-B. Les types de la JVM

- IV-C. Convention de nommage des mnémoniques

- IV-D. Arguments et opérandes

- IV-E. Représentation de la pile

- IV-F. Retourner une valeur

- IV-G. Constantes

- IV-H. What's next ?

- V. Manipulation des variables locales

- V-A. Représentation de la pile

- V-B. Initialisation des variables locales

- V-C. Load

- V-D. Store

- V-E. What's next ?

- VI. Mathématiques et Conversions

- VI-A. Représentation de la pile

- VI-B. Opérations arithmétiques

- VI-B-1. Addition

- VI-B-2. Soustraction

- VI-B-3. Multiplication

- VI-B-4. Division

- VI-B-5. Reste

- VI-B-6. Négation

- VI-C. Opérations bit à bit

- VI-C-1. Opérations de décalage de bits

- VI-D. Opérations logiques

- VI-E. Conversions

- VI-F. What's next ?

- VII. Manipulation de la pile

- VII-A. Catégories des types

- VII-B. Représentation de la pile

- VII-C. Opérations sur la pile

- VII-C-1. SWAP

- VII-C-2. POP

- VII-C-3. POP2

- VII-C-3-a. POP2 - Forme 1

- VII-C-3-b. POP2 - Forme 2

- VII-C-4. DUP

- VII-C-5. DUP_X1

- VII-C-6. DUP_X2

- VII-C-6-a. DUP_X2 - Forme 1

- VII-C-6-b. DUP_X2 - Forme 2

- VII-C-7. DUP2

- VII-C-7-a. DUP2 - Forme 1

- VII-C-7-b. DUP2 - Forme 2

- VII-C-8. DUP2_X1

- VII-C-8-a. DUP2_X1 - Forme 1

- VII-C-8-b. DUP2_X1 - Forme 2

- VII-C-9. DUP2_X2

- VII-C-9-a. DUP2_X2 - Forme 1

- VII-C-9-b. DUP2_X2 - Forme 2

- VII-C-9-c. DUP2_X2 - Forme 3

- VII-C-9-d. DUP2_X2 - Forme 4

- VII-D. What's next ?

- VIII. Mon premier analyseur syntaxique

- VIII-A. Grammaire

- VIII-A-1. Décomposer une addition

- VIII-A-2. Reader

- VIII-A-3. Tokenizer

- VIII-A-4. Esquisse du fonctionnement de l'analyseur

- VIII-A-4-a. Eventtype

- VIII-A-4-b. Symbols

- VIII-A-4-c. Production

- VIII-A-4-d. Table de productions

- VIII-A-4-e. Pile de productions

- VIII-A-4-f. Next Event

- VIII-B. Parser

- VIII-C. End of file

- VIII-D. What's next ?

- IX. Mon premier analyseur syntaxique (suite)

- IX-A. Évolution de la grammaire

- IX-B. Multiples opérateurs

- IX-C. Nombres

- IX-D. Nombres à virgule

- IX-E. Nombres signés

- IX-F. Espaces

- IX-G. Nombre variable d'opérandes

- IX-H. Forcer la priorité

- IX-I. Récapitulatif de la syntaxe EBNF

- IX-J. What's next

- X. Résoudre une expression arithmétique

- X-A. Notation préfixée, infixée et postfixée

- X-B. Résolution d'une expression postfixée

- X-C. Typage des symboles terminaux

- X-D. Transformer une expression infixée en expression postfixée

- X-E. What's next ?

- XI. L'unicode et Java

- XI-A. Principes fondamentaux et vocabulaire

- XI-B. Avant l'Unicode

- XI-C. L'Unicode

- XI-C-1. Les concepts

- XI-C-2. Zone d'indirection

- XI-C-3. Les non-caractères

- XI-C-4. Caractères à usage privé

- XI-C-5. Points de code réservés

- XI-C-6. Glyphes et graphème

- XI-C-6-a. Un graphème et plusieurs points de code

- XI-C-6-b. Duplication des graphèmes

- XI-C-6-c. Ligatures

- XI-D. Codage des caractères

- XI-D-1. UTF-32

- XI-D-2. UTF-16

- XI-D-3. UTF-8

- XI-D-3-a. Codage trop long

- XI-D-4. UTF-8 modifié

- XI-D-5. BOM

- XI-D-5-a. UTF-8

- XI-D-5-b. UTF-16 et UTF-32

- XI-E. Longueur d'une chaîne de caractères

- XI-F. Manipulation de chaînes de caractères en Java

- XI-G. What's next ?

- XII. ClassFile

- XII-A. ClassFile

- XII-A-1. magic

- XII-A-2. minorVersion et majorVersion

- XII-A-3. constantPoolCount et constantPool

- XII-A-3-a. ConstantUtf8

- XII-A-3-b. ConstantInt et ConstantFloat

- XII-A-3-c. ConstantLong et ConstantDouble

- XII-A-3-d. ConstantString

- XII-A-3-e. ConstantClass

- XII-A-3-f. Les quatre derniers tags

- XII-A-4. accessFlags

- XII-A-5. thisClass

- XII-A-6. superClass

- XII-A-7. methodsCount et methods

- XII-B. Method

- XII-B-1. accessFlags

- XII-B-2. nameIndex

- XII-B-3. descriptorIndex

- XII-B-4. attributesCount et attributes

- XII-C. Attribute

- XII-C-1. Code

- XII-C-1-a. attributeNameIndex

- XII-C-1-b. attributeLength

- XII-C-1-c. maxStack

- XII-C-1-d. maxLocals

- XII-C-1-e. codeLength et code

- XII-D. What's next

- XIII. Assembleur de bytecode

- XIII-A. Tableaux

- XIII-B. Attribute

- XIII-C. Enrichissement des classes

- XIII-C-1. ClassFile

- XIII-C-1-a. contantPool

- XIII-C-1-b. thisClass et superClass

- XIII-C-1-c. Tableau et liste

- XIII-C-2. Method

- XIII-C-3. Code

- XIII-C-4. Créer une classe

- XIII-C-4-a. Compter le nombre de paramètres d'un descripteur

- XIII-C-5. Génération d'un fichier .class

- XIII-D. What's next?

- XIV. Remerciements

I - Préambule

I-A - Passé, présent et futur de la JVM

Depuis le début, la devise de Java est : « Write once, run everywhere ». Ceci a été possible grâce à sa machine virtuelle qui - elle - est dépendante de la plate-forme, mais qui exécute une forme de code intermédiaire, le bytecode. Il n'aura pas fallu longtemps pour voir apparaître de nombreux langages, anciens ou nouveaux, compilés en bytecode pour s'exécuter sur la JVM. Ce phénomène a été transcendé ces dernières années, depuis l'apparition dans Java 7 de l'instruction invokedynamic rendant - potentiellement - n'importe quel langage typé dynamiquement extrêmement rapide. On compte aujourd'hui près de 250 implémentations de langages pour la JVM.

Les plus connus/nouveaux étant :

- JRuby (2001) ;

- Groovy (2003) ;

- Scala (2003) ;

- Redline Smalltalk (2010) ;

- Ceylon (2011) ;

- Kotlin (2011) ;

- Nashorn - JavaScript (2012) ;

- Golo (2013).

Il est difficile de dire de quoi sera fait l'avenir, mais nous pouvons constater que trois langages de cette liste ont plus d'une décennie et peu nombreux sont ceux à être utilisés dans le monde de l'entreprise, en tout cas en France. Néanmoins, ils ont tous leur personnalité, avec leurs points forts et leurs points faibles, et il faut considérer que l'avenir sera probablement favorable aux polyglottes, avec des applications constituées de plusieurs langages. Mais, il faudra encore compter sur Java pendant de nombreuses années.

Si l'on remonte quelques années en arrière, il est intéressant de mentionner qu'avant les années 2000, le fait de pouvoir charger du code à la volée, depuis une base de données, ou même un serveur externe, était mis en avant. La technologie des applets utilisait pleinement ce concept. Malheureusement, nous savons tous ce qu'il en est advenu…

Aujourd'hui, l'architecture des applications Java est très loin d'être exotique. Nous nous contentons de développer des applications Web - et de moins en moins de clients lourds - que nous packageons en WAR ou EAR. Et l'architecture révolutionnaire du système de sécurité de Java 2 impacte de nombreuses API de la JDK, les rendant plus difficiles à maintenir, sans que nous puissions nous en débarrasser pour des questions de rétrocompatibilité. Jigsaw sera peut-être une solution à ces divers problèmes.

I-B - Sommaire

Cette première partie fera office de sommaire pour toutes les parties à venir.

Au cours de cette série, nous aborderons les sujets suivants :

- le Bytecode Java ;

- l'implémentation de langages pour la JVM ;

- le fonctionnement d'une machine virtuelle.

I-C - What's next ?

Dans la prochaine partie, nous rentrerons de plain-pied dans le monde de la JVM. Seuls les éléments indispensables à la compréhension des parties suivantes seront abordés, puisque l'objectif n'est pas de vous noyer sous une masse d'informations indigestes, mais d'expliquer petit bout par petit bout le fonctionnement de la JVM.

I-D - Utiliser le code

I-D-1 - Github

Tout le code présenté dans cette partie et les suivantes est disponible sur Github. Chaque partie aura son propre tag et sa propre branche, contenant aussi le code des parties précédentes. La branche master contiendra le code du dernier article publié.

Par exemple, le code de cette partie est disponible sur le tag et la branche nommés « part00 » et la branche master jusqu'à la publication de la partie suivante (c'est-à-dire la semaine prochaine).

I-D-2 - Chaîne de compilation

Avant de voir un peu de code, il nous faut évoquer les outils qui nous seront nécessaires tout au long de ces chapitres pour compiler et tester les exemples.

I-D-2-a - ANT

En cours de ces parties, pour compiler, tester et packager les différents projets que nous allons créer, nous utiliserons Ant, un outil souple, simple à utiliser et fonctionnant dans tout environnement ayant une JVM, puisqu'il est écrit en Java.

Je vous invite donc à télécharger Ant, à le désarchiver et à ajouter dans votre variable d'environnement PATH, le chemin vers le répertoire <chemin_de_ant>/bin.

Pour plus de détails sur l'utilisation de Ant, je vous invite à consulter l'ouvrage suivant : Ant in Action.

I-D-3 - Organisation du projet

Ant offrant une liberté infinie, il est nécessaire d'adopter certaines conventions. L'organisation standard d'un projet aura donc la forme suivante :

project
|  +- 01_src (code source)
|  |  +- main
|  |  |  +- java
|  |  |  +- resources
|  |  +- test
|  |  |  +- java
|  |  |  +- resources
|  +- 02_build (généré)
|  |  |  +- classes
|  |  |  +- junit-data
|  |  |  +- junit-reports
|  |  |  +- test-classes
|  +- 03_dist (généré)

Cette série de parties allant couvrir de nombreux sujets différents, nous allons avoir plusieurs projets, il nous faut donc un niveau supplémentaire :

jvm_hardcore
|  +- 01_conf (fichiers de configuration Ant)
|  +- 02_libs (*.jar)
|  +- 03_projects
|  |  +- mystery
|  |  +- [...]
|  +- 04_archives (tous les JARs générés par le projet)

I-E - Tester les exemples

Il est très simple de compiler tout le code en une seule fois :

<chemin_jvm_hardcore>$ ant

Pour supprimer les répertoires 02_build et 03_dist de tous les projets, et le répertoire 04_archives :

<chemin_jvm_hardcore>$ ant clean-achives

Les autres targets sont les suivantes :

- clean : supprime les répertoires 02_build et 03_dist de tous les projets ;

- compile : compile les sources Java de tous les projets ;

- test : lance les tests unitaires de tous les projets ;

- archive : génère un JAR pour tous les projets.

Toutes ces targets sont aussi disponibles pour chacun des projets, comme :

<chemin_du_projet_mystery>$ ant compile

qui compilera les sources du projet mystery uniquement.

Pour exécuter les tests d'une classe ou une méthode, il est nécessaire d'aller à la racine du projet auquel la classe ou méthode appartiennent. Par exemple pour exécuter la méthode de test byteToHex0Test() de la classe org.isk.jvmhardcore.mystery.ByteToHexTest :

<mystery_project_path>$ ant test -DtestClass=org.isk.jvmhardcore.mystery.ByteToHexTest -DtestMethod=byteToHex0Test

I-F - Nombre magique

Le code est disponible sur Github (tag et branche)

L'exemple suivant a pour but d'introduire le dumping d'un fichier .class et sa construction à partir d'un fichier texte contenant des caractères hexadécimaux au format texte (les retours à la ligne sont présents uniquement pour ne pas déformer la page).

CAFEBABE00000034001D0A0006000F09001000110800120A001300140700150700160100063C696
E69743E010003282956010004436F646501000F4C696E654E756D6265725461626C650100046D61
696E010016285B4C6A6176612F6C616E672F537472696E673B295601000A536F7572636546696C6
501000C4D7973746572792E6A6176610C000700080700170C0018001901002248656C6C6F20576F
726C6421204A564D2048617264636F726520726F636B732E2E2E07001A0C001B001C0100074D797
3746572790100106A6176612F6C616E672F4F626A6563740100106A6176612F6C616E672F537973
74656D0100036F75740100154C6A6176612F696F2F5072696E7453747265616D3B0100136A61766
12F696F2F5072696E7453747265616D0100077072696E746C6E010015284C6A6176612F6C616E67
2F537472696E673B2956002100050006000000000002000100070008000100090000001D0001000
1000000052AB70001B100000001000A000000060001000000010009000B000C0001000900000025
0002000100000009B200021203B60004B100000001000A0000000A0002000000030008000400010
00D00000002000E

Source

Pour ceux qui l'ont remarqué, CAFEBABE, n'est pas une blague, il s'agit du « nombre magique » qui apparaît dans tous les fichiers .class, créés hier, aujourd'hui et demain.

Pour construire une classe à partir de la chaîne de caractères présentée ci-dessus, il suffit d'ouvrir un Shell et d'exécuter les commandes suivantes :

<projet_mystery>$ ant execute -Dargs="assemble=01_src/test/resources/Mystery.hex"
<projet_mystery>$ java Mystery
[Message mystère]

Il est aussi possible de créer un fichier .hex à partir d'un fichier .class.

<projet_mystery>$ ant execute -Dargs="dump=Mystery.class"

Notes :

- dans l'exemple ci-dessus, le fichier Mystery.class doit être à la racine du projet ;

- -Dargs est un argument défini dans la target execute de Ant, dont la valeur est passée à la méthode main() de la classe AssembleAndDump ;

- assemble et dump, sont des paramètres de notre mini application. Seul l'un ou l'autre peut être utilisé lors de l'exécution de l'application (pas les deux à la fois). Ils prennent des chemins relatifs par rapport au répertoire courant ;

- les fichiers de résultat (.class ou .hex) sont créés dans le répertoire courant. Ils portent le même nom que le fichier original, seule l'extension change ;

- le paramètre help affiche l'aide.

Il est aussi possible d'exécuter l'application sans passer par Ant. Le jar mystery est disponible dans les répertoires 04archives et 03projects/mystery/03_dist :

<chemin_jvm_hardcore>$ java -jar mystery.<date>.jar assemble="../03_projects/mystery/Mystery.hex"

où le résultat peut avoir la valeur 20130726.123057.

I-F-1 - Implémentation

Le code de cette application n'a rien d'extraordinaire. Mais vous pouvez tout de même le consulter, ainsi que les tests unitaires. Néanmoins, la méthode byteToHex() mérite notre attention.

La méthode byteToHex() est utilisée pour dumper les fichiers .class. Après ouverture du fichier dont le chemin est passé en paramètre - de l'application -, nous récupérons un tableau d'octets que nous passons à la méthode. Chaque élément du tableau est converti en valeur hexadécimale ASCII de deux caractères ajoutés dans un nouveau tableau d'octets. Ce nouveau tableau d'octets est ensuite retourné par la méthode, puis écrit dans un nouveau fichier.

Pour comprendre la méthode byteToHex(), il faut tout d'abord prendre conscience que manipuler un fichier signifie généralement manipuler un tableau d'octets (nous verrons plus tard qu'il y bien d'autres solutions - parfois plus simples -, mais ici l'objectif étant éducatif nous allons souvent recréer la roue).

Pour rappel, un octet (ou un byte) est égal à huit bits ou deux nibbles. En hexadécimal, quatre bits (ou un nibble) sont représentés par un caractère de 0 à F (dans cet exemple nous nous contenterons des lettres en majuscules). Par conséquent, convertir un octet en hexadécimal ASCII de deux caractères est théoriquement extrêmement simple, puisqu'il suffit de découper notre octet en deux parties de quatre bits chacune représentée par un caractère. Cependant, en pratique, il y a quelques pièges à éviter.

En prenant par exemple le nombre 94, nous pouvons écrire un test unitaire de la façon suivante :

1. @Test

2. public void byteToHex0Test() {

3. // 94(10) = 5E(16) = 0101 1110(2)

4. final byte number = 94;

5. final byte[] hex = byteToHex0(number);

7. Assert.assertArrayEquals(new byte[]{5, 14}, hex);

8. }

Source

Dans ce test, nous obtenons deux nombres décimaux. Pour les remplacer par des caractères, il suffit de prendre le tableau suivant :

1. byte[] chars = {'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F'};

Les nombres décimaux sont utilisés comme index du tableau :

1. chars[5] == '5'

2. chars[14] == 'E'

Il nous faut à présent implémenter la méthode

1. byte[] byteToHex0(byte number)

La première question qui nous vient à l'esprit est : « Comment découper un octet en deux nibbles ? »

Pour y répondre, nous devons tout d'abord représenter le nombre décimal au format binaire (0101 1110). Nous souhaitons donc avoir d'un côté « 0101 » et de l'autre «  1110 ». Pour récupérer les quatre premiers bits, le plus simple est de décaler les bits de quatre positions vers la droite :

1. 94 >> 4 // 0101 1110 >> 4 = 0000 0101

quant aux quatre derniers, nous pouvons masquer les quatre premiers :

1. 94 & 0x0f //   0101 1110

2. // & 0000 1111

3. // -----------

4. // = 0000 1110

Un élément important à prendre en compte est qu'avant l'exécution d'une opération de manipulation de bits, les primitifs de type byte, short et char sont promus en int (lors d'une opération de décalage de bits une promotion unaire est effectuée et lors d'une opération logique bit à bit une promotion binaire). De fait, bien que les opérations représentées en commentaire ne comptent que 8 bits, il y en a 32 en réalité. 94 étant positif, cela n'a pas d'importance.

De plus, dans les deux exemples précédents, les deux opérandes de chaque opération étant des valeurs littérales il est possible d'assigner le résultat à une variable de type byte. Néanmoins, si l'un des opérandes est une variable il est obligatoire d'effectuer explicitement un downcast ; et il en est de même dans certains cas d'utilisation de valeurs littérales. La priorité du compilateur est d'éviter - autant que possible - tout overflow ou perte d'information.

Implémentons à présent notre méthode :

1. public byte[] byteToHex0(byte number) {

2. final byte[] bytes = new byte[2];

3. bytes[0] = (byte)(number >> 4);

4. bytes[1] = (byte)(number & 0x0f);

5. return bytes;

6. }

Source

Si vous lancez le test unitaire, il devrait se terminer en succès.

1. $ ant test -DtestClass=org.isk.jvmhardcore.mystery.ByteToHexTest -DtestMethod=byteToHex0Test

Il est temps à présent de se demander si notre test est complet ! Y a-t-il des cas que nous n'avons pas testés ?

Bien évidemment, si je pose la question, la réponse est non. En Java, un byte représente un nombre signé. Il nous faut donc tester une valeur négative.

Il est important de noter qu'en bytecode toutes les valeurs sont positives, or en utilisant la méthode statique byte[] java.nio.Files.readAllBytes() chaque octet est placé dans une variable de type byte. Par conséquent, les valeurs supérieures à 127 sont représentées sous la forme de nombres négatifs (cf. Complément à deux).

Prenons par exemple le nombre -23 et écrivons un nouveau test :

1. @Test

2. public void byteToHex1Test() {

3. // -23(10) = E9(16) = 1110 1001 = 233(10)

4. final byte number = -23;

5. final byte[] hex = byteToHex0(number);

7. Assert.assertArrayEquals(new byte[]{14, 9}, hex);

Source

À présent le test unitaire est en échec, comme le confirme le test suivant (Source) :

$ ant test -DtestClass=org.isk.ByteToHexTest -DtestMethod=byteToHex1Test

Reprenons donc notre méthode byteToHex0(). La méthode fait quatre lignes ; la première et la dernière ne font pas grand-chose. Par conséquent, le problème doit venir de l'une des deux autres, voire les deux.

Commençons par la première :

-23 >> 4 // 1111 1111 1111 1111 1111 1111 1110 1001 >> 4
// = 1111 1111 1111 1111 1111 1111 1110

ce qui n'est absolument pas ce que nous souhaitons.

Note : l'opérateur >> décale de x positions des bits en dupliquant le MSB (Most Significant Bit, le bit le plus à gauche). -23 étant négatif, son MSB est égal à 1, ce qui explique que ce sont des 1 qui ont été ajoutés et non des 0.

En Java, nous avons aussi l'opérateur >>> qui décale de x positions les bits d'un nombre considéré comme non signé.

-23 >>> 4 // 1111 1111 1111 1111 1111 1111 1110 1001 >>> 4
// = 0000 1111 1111 1111 1111 1111 1110

Malheureusement - une fois de plus -, ce n'est pas le résultat escompté.

Il nous faut donc supprimer le signe avant de décaler les bits. Nous allons utiliser à nouveau un masque :

-23 & 0xff //   1111 1111 1111 1111 1111 1111 1110 1001
// & 0000 0000 0000 0000 0000 0000 1111 1111
// -----------------------------------------
// = 0000 0000 0000 0000 0000 0000 1110 1001

À présent en utilisant le nombre non signé (233) et l'opérateur >>> (ou >>) nous obtiendrons le bon résultat.

1. byte[] byteToHex1(byte number) {

2. final int unsignedByte = number & 0xff;

3. final byte[] bytes = new byte[2];

4. bytes[0] = (byte)(unsignedByte >>> 4);

5. bytes[1] = (byte)(unsignedByte & 0x0f);

6. return bytes;

7. }

Source

$ ant test -DtestClass=org.isk.ByteToHexTest -DtestMethod=byteToHex2Test

Ceci conclut le départ de notre fabuleux voyage dans le monde de la JVM. J'espère que vous prendrez autant de plaisir à lire ces parties que moi à les écrire.

Et bien sûr toutes critiques constructives sont les bienvenues.

II - Introduction à la JVM

II-A - Généralités sur la JVM

Avant de nous intéresser au bytecode Java, il est nécessaire de comprendre comment fonctionne dans les grandes lignes la JVM.

Le JRE est composé de l'API Java et de la JVM. Le rôle de la JVM est de lire une application composée de fichiers .class sous différentes formes (zip, jar, war, un simple tableau d'octets, etc.) à l'aide d'un chargeur de classes et de l'exécuter, ainsi que l'API Java.

D'une manière générale, une Machine Virtuelle (VM) est une implémentation logicielle d'une architecture physique ou hypothétique. Il existe deux types de machines virtuelles, les VM système et les VM applicatives. La JVM fait partie de la seconde catégorie. Elle est exécutée comme n'importe quelle application sur un système d'exploitation hôte et est associée à un seul processus. Son but est de fournir un environnement de programmation indépendant de la plate-forme qui fait abstraction du matériel sous-jacent et/ou du système d'exploitation, et permet à un programme de s'exécuter de la même manière sur n'importe quelle plate-forme. La JVM utilise un bytecode, un langage intermédiaire entre Java (le langage utilisateur) et le langage machine (Virtual machine en anglais).

Bien que dans JVM, le « J » signifie Java, il est théoriquement possible d'implémenter un compilateur compilant n'importe quel langage en bytecode pour la JVM. Mais en pratique certains langages sont très difficiles à implémenter de manière efficiente.

Quelques particularités de la JVM

- Machine virtuelle basée sur le modèle de la pile : les architectures d'ordinateurs les plus populaires telles que l'architecture Intel x86 et l'architecture ARM sont basées sur des registres. Cependant la JVM est basée sur le modèle de la pile (LIFO, stack-based). Dalvik, la machine virtuelle d'Android ne suit pas la JVMS, puisqu'elle est basée sur des registres.

- Références symboliques : tous les types (classes et interfaces), à l'exception des primitifs (boolean, int, float, etc.), sont désignés par une référence symbolique et non une référence explicite d'une adresse mémoire.

- Ramasse-miettes : l'instance d'une classe est créée explicitement par le code du développeur et est détruite automatiquement par le ramasse-miettes.

- Garantie de l'indépendance de la plate-forme en définissant clairement les types primitifs : la taille des types primitifs est fixée par la JVMS.

- Ordre des octets du réseau : toujours dans un souci de maintenir l'indépendance de la plate-forme, la représentation des données doit être fixée. L'ordre des octets du réseau a été choisi. Il s'agit en réalité de l'orientation big-endian (l'octet de poids le plus fort se trouve à gauche et est stocké en premier en mémoire).

II-B - Zones de données d'exécution (Runtime Data Areas)

Le code Java est exécuté en suivant le processus ci-dessous :

Pour l'instant, seule l'étude des zones de données d'exécution nous sera utile pour comprendre le format d'un fichier .class.

La JVM définit différentes zones de données d'exécution qui sont utilisées durant l'exécution d'un programme. Certaines de ces zones de données sont créées lorsque la JVM est lancée et sont détruites lorsqu'elle s'arrête. Les autres zones sont propres à chaque fil d'exécution (thread). Les zones de données par fils d'exécution sont créées lorsque le fil d'exécution est créé et sont détruites lorsqu'il se termine.

II-B-1 - Le tas (HEAP)

La JVM a un tas partagé par tous les fils d'exécution. Le tas est une zone de données d'exécution dans laquelle toutes les instances de classes et les tableaux sont stockés. Le tas est créé au démarrage de la JVM. Les objets n'étant pas explicitement désalloués de la mémoire, lorsqu'ils ne sont plus référencés le ramasse-miettes les supprime du tas.

II-B-2 - Zone de méthodes (METHOD AREA)

Lorsque le chargeur de classes charge une classe, il stocke sa structure (le pool de constantes, les données des champs et des méthodes, et le code des méthodes et des constructeurs) dans la Zone de Méthodes. Il s'agit d'un espace mémoire partagé par tous les fils d'exécution et la JVMS n'impose pas qu'il soit libéré par le ramasse-miettes et donc qu'il fasse partie du tas (heap).

II-B-3 - Pool de constantes d'exécution (RUNTIME CONSTANT POOL)

Le pool de constantes est une représentation d'exécution par classe ou par interface du pool de constantes défini dans un fichier .class, sur lequel nous reviendrons dans quelques semaines.

Il contient plusieurs sortes de constantes, des littérales numériques connues lors de la compilation aux références de champs ou de méthodes devant être résolues lors de l'exécution. Le pool de constantes d'exécution est comparable à une table de symboles utilisée par un langage de programmation conventionnel, bien qu'il contienne plus de types de données qu'une table de symboles standard.

Chaque pool de constantes d'exécution est alloué à partir de la zone de méthodes. Le pool de constantes d'exécution pour une classe ou une interface est construit lorsque la classe ou l'interface est créée par la JVM.

II-C - Fils d'exécution (THREADS)

Il existe deux types de fils d'exécution Java :

- les fils d'exécution de type démon ;

- et les fils d'exécution de type non-démon.

Les fils d'exécution de type démon s'arrêtent lorsqu'il n'y a plus de fils d'exécution de type non-démon. Même si une application ne crée pas de fils d'exécution, la JVM en crée plusieurs, dont la plupart sont des fils d'exécution de type démon.

Le fil d'exécution principal d'une application est celui exécutant la méthode main(). Il est le premier et le dernier fil d'exécution de type non-démon à s'exécuter. Lorsque l'on atteint la fin de la méthode main() - et de tous les fils d'exécution de type non-démon lancés lors de son exécution - le fil d'exécution se termine, mettant fin aux fils d'exécution de type démon et par conséquent à l'exécution de la JVM.

À noter qu'un fil d'exécution de type démon peut être créé au sein d'une application.

II-D - Pointeur d'instruction (PROGRAM COUNTER)

La JVM peut supporter l'exécution de plusieurs fils d'exécution en parallèle. Chaque fil d'exécution a son propre pointeur d'instruction (PC Program Counter). À tout moment, chaque fil d'exécution exécute le code d'une seule méthode, la méthode courante pour ce fil d'exécution. Si cette méthode n'est pas native, le pointeur d'instructions contient l'adresse de l'instruction de la JVM en cours d'exécution. Si la méthode en cours d'exécution par le fil d'exécution est native, le pointeur d'instructions est indéfini.

II-E - Piles Java (JAVA VIRTUAL MACHINE STACKS)

Chaque fil d'exécution de la JVM a une pile qui lui est propre, créée en même temps que le fil d'exécution. Une pile stocke des cadres (identifiés par C0, C1, etc. dans l'illustration ci-dessous).

II-F - Piles de méthodes natives (NATIVE METHOD STACKS)

À l'instar des méthodes Java qui sont exécutées dans les piles Java, les méthodes natives (généralement en C/C++) sont exécutées dans les piles de méthodes natives. Les piles de méthodes natives sont généralement allouées par fil d'exécution lorsqu'il est créé.

II-G - Cadres (FRAMES)

Un cadre est utilisé pour stocker des données et des résultats partiels, ainsi que pour effectuer des liaisons dynamiquement, retourner des valeurs de méthodes et transmettre des exceptions.

Un nouveau cadre est créé à chaque fois qu'une méthode est appelée. Un cadre est détruit lorsque l'exécution de la méthode est terminée, que ce soit normalement ou non (si une exception est levée). Les cadres sont alloués dans la pile Java du fil d'exécution créant le cadre. Chaque cadre a son propre tableau de variables locales, sa pile d'opérandes et une référence vers le pool de constantes d'exécution de la classe de la méthode courante.

Seulement un cadre est actif à la fois par fil d'exécution, le cadre de la méthode en cours d'exécution. Ce cadre est appelé le cadre courant, et sa méthode, la méthode courante. La classe dans laquelle la méthode courante est définie est la classe courante.

Un cadre n'est plus courant si sa méthode appelle une autre méthode ou si sa méthode se termine. Quand une méthode est appelée, un nouveau cadre est créé et devient le cadre courant lorsque le contrôle est transféré à la nouvelle méthode. Au retour de la méthode, le cadre courant retransmet le résultat de sa méthode au cadre précédent '- s'il existe -. Le cadre courant est alors supprimé et le cadre précédent redevient le cadre courant.

II-G-1 - Variables locales

Chaque cadre contient un tableau de variables nommé variables locales. La taille du tableau est déterminée lors de la compilation (nous y reviendrons dans une partie ultérieure).

Les variables locales sont adressées par index comme n'importe quel tableau d'un langage de programmation standard. L'index de la première variable locale est zéro et celui de la dernière est égal à la taille du tableau moins un.

La JVM utilise les variables locales pour passer des paramètres à la méthode appelée. Lorsqu'une méthode de classe (statique) est appelée, tous les paramètres sont stockés dans les variables locales de manière consécutive à partir de l'index zéro. Lorsqu'une méthode d'instance est appelée, la variable à l'index zéro est toujours une référence de l'objet (this) sur laquelle la méthode a été appelée. Les paramètres sont quant à eux stockés de manière consécutive à partir de l'index un.

Les variables locales sont aussi utilisées pour stocker des résultats partiels.

II-G-2 - Pile d'opérandes

Chaque cadre contient une pile Last In First Out (LIFO) nommée pile d'opérandes. La taille maximum de la pile est déterminée lors de la compilation (nous y reviendrons aussi dans une partie ultérieure). La pile d'opérandes est vide lorsque le cadre la contenant est créé.

Chaque entrée de la pile peut contenir une valeur de n'importe quel type connu de la JVM.

II-G-3 - Liaison dynamique

Chaque cadre contient une référence pointant vers le pool de constantes d'exécution pour que le type de la méthode courante supporte la liaison dynamique du code de la méthode. En d'autres termes lorsqu'une méthode d'une classe A fait référence à une classe B, dans un fichier .class le lien entre A et B est symbolique. La liaison dynamique traduit cette référence symbolique en une référence concrète, chargeant si nécessaire la classe B et traduisant les différents accès à cette classe (champs, méthodes d'instance, etc.) par des offsets permettant de localiser leur position en mémoire.

Notes :

Dans le cadre correspondant à la méthode main(), la variable à l'index 0 (ra) correspond à une référence au tableau passé en paramètre (nommé « a » ici).

vl0 et vl1 correspondent aux variables locales d'index 0 et 1.

Si certains points vous semblent encore obscurs, normalement tout devrait devenir plus clair dans les prochaines parties. Nous aborderons notamment le cas de la surcharge/redéfinition d'une méthode.

II-H - What's next ?

Dans la prochaine partie, nous nous intéresserons à un outil nommé Plume que nous utiliserons au cours des prochaines parties. Plume est un assembleur/désassembleur de bytecode, qui - comme Jasmin -permet d'écrire un fichier au format texte en utilisant une syntaxe proche de celle décrite dans la spécification de la machine virtuelle Java pour le transformer en un fichier .class. Plume peut aussi être utilisé comme ASM pour créer du bytecode à la volée en Java, le charger à l'aide d'un chargeur de classes et l'exécuter.

Plume ayant un objectif éducatif, pour son implémentation - que nous étudierons - la simplicité du code a été privilégiée face aux performances.

III - Bytecode avec Plume Java Bytecode Assembler (PJBA)

Nous allons maintenant voir comment utiliser Plume Java Bytecode Assembler (PJBA) qui nous permettra d'avoir l'impression d'écrire du bytecode sans passer par des 0 et des 1. Nous l'utiliserons de manière intensive au cours des prochaines semaines. Sans lui, il aurait été nécessaire :

- soit d'utiliser plusieurs outils qui peuvent s'avérer compliqués à prendre en main ;

- soit d'écrire des fichiers binaires à la main, ce qui est, vous me l'accorderez, aussi utile que BrainFuck.

De plus, en ayant notre propre outil, nous allons pouvoir l'étudier en profondeur, puisqu'il a été conçu tout aussi bien pour être simple à utiliser qu'à comprendre.

Par convention, nous utiliserons l'extension .pjb pour identifier les fichiers devant être assemblés par PJBA, mais toutes les extensions sont possibles.

Le code est disponible sur Github (tag et branche).

III-A - Getting Started

Pour commencer, nous allons voir un exemple complet d'une classe avec la méthode statique nommée add() de la partie précédente qui additionne deux entiers.

1. .class org/isk/jvmhardcore/bytecode/parttwo/Adder

3. .method add(II)I

4. iload_0

5. iload_

6. iadd

7. ireturn

8. .methodend

10. .classend

Source

Toutes les lignes commençant par un point (« . ») sont des directives et ce sont les choses qui nous intéresseront dans cette partie.

Pour l'instant, nous nous limiterons au strict minimum nous permettant d'étudier nos premières instructions. Dans quelques semaines, nous recréerons cet assembleur extrêmement simple. Nous pourrons ensuite y ajouter des fonctionnalités au fur et à mesure.

La version équivalente en Java est la suivante :

1. package org.isk.jvmhardcore.bytecode.parttwo;

3. public class Adder {

4. public static int add (int i1, int i2) {

5. return i1 + i2;

6. }

7. }

Pour tester la méthode add() de la version Plume, il nous faut tout d'abord assembler le fichier Adder.pjb en un fichier .class. À partir de là, en ajoutant le fichier .class au classpath, nous pouvons appeler la méthode depuis un test unitaire écrit en Java.

Pour assembler les fichiers .pjb en .class :

ant assemble

Le test unitaire correspondant est le suivant :

1. @Test

2. public void add0() {

3. final int sum = Adder.add(2, 3);

5. Assert.assertEquals(5, sum);

6. }

Source

Pour l'exécuter depuis Ant :

ant test -DtestClass=org.isk.jvmhardcore.bytecode.parttwo.AdderTest -DtestMethod=add0

III-B - Descripteurs

Un descripteur est un moyen d'exprimer un type à l'aide de lettres et de symboles :

- la plupart des types sont représentés par un seul caractère (I pour int, F pour float, ou de manière moins évidente Z pour boolean, J pour long, etc.) ;

- le symbole [ indique un tableau du type indiqué ensuite. Par exemple [I signifie un tableau d'entiers. Il est possible d'avoir plusieurs crochets à la suite pour indiquer des tableaux à plusieurs dimensions ([[Z pour un tableau de tableaux de booléens) ;

- la lettre L signifie un objet du type qui suit (Ljava/lang/String;) ;

- seuls les types d'objets se terminent par un point-virgule.

Tous les descripteurs possibles sont présentés dans le tableau suivant :

Descripteur

Type

Z

boolean

B

byte

S

short

C

char

I

int

J

long

F

float

D

double

V

void

[<type>

tableau de type <type>

L<type>;

Objet de type <type>

Note : tout comme en Java, en bytecode (et de fait dans un fichier .pjb), V (void) ne peut être utilisé qu'en type de retour d'une méthode.

Exemples :

Bytecode

Java

add(II)I

int add(int i1, int i2)

concat(Ljava/lang/String;Ljava/lang/String;)Ljava/lang/String;

String concat(String s1, String s2)

merge([Z[Z)[Z

boolean[] merge(boolean[] a1, boolean[] a2)

III-C - Commentaires

Les commentaires d'une seule ligne sont identifiés soit par :

- un signe croisillon (#) ;

- une arobase (@);

- un point-virgule (;).

Tout ce qui se trouve à droite de ces signes est un commentaire.

Il est aussi possible d'avoir des commentaires de plusieurs lignes (/* … */) :

1. /* Ceci est

2. un commentaire

3. de plusieurs lignes */

III-D - Classes

La première directive que nous allons voir est .class. Elle indique à l'assembleur le nom complètement qualifié de la classe. De plus, ce nom indique le nom des répertoires contenant le fichier et celui du fichier .class généré.

1. .class <nom complètement qualifié de la classe>

2. # contenu de la classe

3. .endclass # Indique la fin d'une classe

Exemple :

1. .class org/isk/jvmhardcore/bytecode/parttwo/Adder

2. # ...

3. .endclass

Équivalent Java :

1. package org.isk.jvmhardcore.bytecode.parttwo;

3. public class Adder {

5. }

Le nom du package et de la classe sont concaténés et les points inclus dans le nom du package sont remplacés par des slashes (/).

Le nom du package suivi de celui de la classe constituent le nom complètement qualifié d'une classe.

Limitations actuelles que nous lèverons ultérieurement :

- une seule directive .class par fichier est autorisée ;

- une classe est obligatoirement publique (public).

III-E - Méthodes

Une méthode est définie de la manière suivante :

1. .method <nom de la méthode>(<descripteur des paramètres>)<descripteur du retour>

2. # Instructions

3. .endmethod

Notons que contrairement à Java, le type de retour est complètement à la fin, comme nous l'avons vu dans le tableau précédent.

Notes :

- pour indiquer plusieurs paramètres, il suffit de les écrire les uns à la suite des autres sans espace ;

- le descripteur de la méthode (paramètres et type de retour) doit être unique. En revanche, contrairement à Java, deux descripteurs peuvent différer uniquement par le type de retour.

Limitations actuelles :

- une méthode est obligatoirement publique et statique (public static).

III-F - Noms

Les noms des packages, classes et méthodes doivent commencer par une lettre ASCII, le caractère underscore « _ » ou dollar « $ », puis des lettres ASCII, des chiffres ou les caractères underscore « _ » ou dollar ‘$'.

Par exemple : helloworld, $hello_world1, _hello$world2, _my/$package/DoSomething1, etc.

III-G - Encodage

Le projet jvm_hardcore doit être en UTF-8.

III-H - Créer un fichier classe en Java

PJBA permet de créer un fichier .class à partir d'un fichier texte comme nous venons de le voir. Mais il est aussi possible d'utiliser des objets Java. Néanmoins en l'état, pour qui ne sait pas de quoi est constitué le format .class, son utilisation est plutôt compliquée.

En reprenant encore une fois notre exemple de méthode add() :

1. @Test

2. public void assembleJava() throws Exception {

3. // ConstantPoolEntries

4. final String className = "org/isk/jvmhardcore/bytecode/parttwo/AdderJava";

5. final String methodName = "add";

6. final String methodDescriptor = "(II)I";

8. // ClassFile

9. final ClassFile classFile = new ClassFile(className);

10. final int classNameIndex = classFile.addConstantUTF8(className);

11. final int thisClassIndex = classFile.addConstantClass(classNameIndex);

12. classFile.setThisClassIndex(thisClassIndex);

14. // Method

15. final int codeAttributeIndex = classFile.addConstantUTF8(Code.ATTRIBUTE_NAME);

16. final int methodIndex = classFile.addConstantUTF8(methodName);

17. final int descriptorIndex = classFile.addConstantUTF8(methodDescriptor);

18. final Method method = new Method(codeAttributeIndex);

19. method.setNameIndex(methodIndex);

20. final int parameterCount = Method.getParameterCount(methodDescriptor);

21. method.setDescriptorIndex(descriptorIndex, parameterCount);

22. classFile.addMethod(method);

24. // Instructions

25. method.addInstruction(Instructions.iload_0());

26. method.addInstruction(Instructions.iload_1());

27. method.addInstruction(Instructions.iadd());

28. method.addInstruction(Instructions.ireturn());

30. this.createFile(classFile);

31. }

Source

Je ne m'attarderai pas sur cet exemple, nous y reviendrons un peu plus tard. De plus, une de nos actions sera de simplifier l'utilisation de PJBA en mode Java puisque même si l'on sait à quoi tout ceci correspond, 30 lignes pour créer une classe et une méthode qui ne fait qu'une addition, cela fait beaucoup.

Pour tester cette classe :

ant assemble
ant test -DtestClass=org.isk.jvmhardcore.bytecode.parttwo.AdderTest -DtestMethod=add1

Source du test

III-I - Utilisation du code source

Pour pouvoir assembler les fichiers .pjb en .class, la structure des projets a dû évoluer :

1. project

2. |  +- 01_src (code source)

3. |  |  +- main

4. |  |  |  +- assembler (Assembleur)

5. |  |  |  +- java

6. |  |  |  +- pjb (Plume Java Bytecode)

7. |  |  +- test

8. |  |  |  +- java

9. |  |  |  +- resources

10. |  +- 02_build (généré)

11. |  |  |  +- assembler

12. |  |  |  |  +- classes (Assembleur compilé)

13. |  |  |  |  +- reports (Rapport d'assemblage)

14. |  |  |  +- classes

15. |  |  |  +- junit-data

16. |  |  |  +- junit-reports

17. |  |  |  +- pjb-classes (.pjb assemblés en .class)

18. |  |  |  +- test-classes

19. |  +- 03_dist (généré)

III-I-1 - Assembleur

Le répertoire 01_src/main/assembler/ contient les classes permettant de générer des fichiers .class à partir d'un fichier .pjb ou du code Java. Par simplicité, le choix a été fait d'utiliser JUnit au lieu d'une méthode main() pour exécuter l'assembleur.

Le répertoire 02_build/assembler/ contient les composants compilés de l'assembleur et les rapports des tests unitaires exécutés pour pouvoir générer des fichiers .class.

La méthode assemblePjb() prend tous les fichiers du répertoire pjb/ et de ses enfants quelle que soit leur extension et appelle le parser PJBA (disponible dans le répertoire 02_libs sous le nom pjba.jar).

Les fichiers générés sont créés dans le répertoire 02_build/pjb-classes. Il doit être par conséquent rajouté au classpath pour que les tests unitaires testant ces classes et méthodes puissent y accéder.

III-I-2 - Scripts de construction Ant

Une target assemble - déjà présentée au cours de cette partie - a été rajoutée.

ant assemble

De plus, pour que les scripts de construction restent simples et qu'il soit possible de compiler/assembler tous les projets à partir du script principal (celui à la racine du projet), toutes les commandes (targets) Ant sont accessibles depuis le répertoire root de n'importe quel projet. Par conséquent, il est possible d'utiliser la target compile sur le projet bytecode/ alors que le répertoire 01_src/main/java n'existe pas. Son exécution se terminera en succès, mais ne fera rien, puisque nous testons si le répertoire 01_src/main/java existe avant de poursuivre l'exécution.

III-J - What's next ?

Au cours de cette partie, nous nous sommes contenté de représenter une classe sous une forme proche de sa représentation en bytecode. Les choses sérieuses commenceront dès la partie suivante. Nous étudierons nos premières instructions.

IV - Constantes

Après trois parties d'introduction, les choses sérieuses vont enfin pouvoir commencer. Pendant plusieurs parties, nous allons étudier les quelque 200 instructions de la JVM, qui comme nous le verrons sont extrêmement simples à comprendre et à utiliser - à l'exception de quelques-unes. À l'issue de cette partie dédiée au bytecode, les différents éléments constituant un fichier .class n'auront plus aucun secret pour nous.

Depuis, la toute première version de Java les modifications de la JVMS ont été minimes. Rien n'a été supprimé, toujours pour des questions de rétrocompatibilité et seulement deux instructions ont été dépréciées.

Pour que le matériel présenté reste simple, nous nous limiterons dans un premier temps à la spécification de la JVM pour Java 1.4. Les ajouts effectués pour Java 5, 6, 7 et 8 feront l'objet d'une (ou plus) partie par version.

Le code est disponible sur Github (taget branche).

IV-A - Vocabulaire lié à la pile

- Stack = Pile = Liste Last In First Out (LIFO).

- Empiler (push) : ajouter un élément en tête de liste.

- Dépiler (pop) : retirer l'élément en tête de liste.

IV-B - Les types de la JVM

La JVM supporte seulement cinq types de données :

- int ;

- long ;

- float ;

- double ;

- reference.

Les quatre premiers types sont identiques aux types Java du même nom. Les types Java boolean, byte, short et char sont tous traités comme des int par la JVM.

En revanche, il est possible d'avoir des tableaux de bytes, short et char comme nous le verrons plus tard.

Les types long et double prennent deux entrées dans la pile, alors que tous les autres n'en prennent qu'une.

Une reference est une référence à un objet Java. Une référence pointe vers un objet présent dans le tas (heap). Contrairement aux types numériques, un objet a des propriétés indépendantes de la référence à l'objet.

Contrairement au C (une référence pouvant être comparée à un pointeur) une fois qu'une référence pointe vers un objet, elle pointe toujours vers le même objet et par conséquent, il n'est pas possible d'effectuer une quelconque opération sur une référence.

IV-C - Convention de nommage des mnémoniques

Une mnémonique est une forme textuelle (simplifiant la lecture/écrire du code pour un être humain) représentant une opération (additionne, charge, stocke, etc.). Chaque mnémonique correspond à un nombre entre 0 et 255 dans un fichier .class. Ce nombre est appelé le code d'opération (opcode).

Les mnémoniques utilisées par PJBA sont celles définies dans la JVMS. Généralement, le premier caractère d'une mnémonique indique le type sur lequel il opère. Par exemple, iadd permet d'ajouter des int et rien d'autre. Néanmoins, il n'existe pas forcément une mnémonique pour chaque type. Certaines opérations sont possibles uniquement sur un nombre réduit de types, par exemple les opérations bit à bit qui ne fonctionnent qu'avec des int ou des long.

Pour rappel 1 byte = 1 octet = 8 bits et 1 word = 2 bytes = 16 bits.

Lettre

Type

Taille (en bit)

b

byte

8

s

short

16

c

char

16

i

int

32

l

long

64

f

float

32

d

double

64

a

référence

32/64 (1)

* l'espace mémoire utilisé pour une référence d'un objet est de 32 bits ou 64 bits en fonction de la JVM utilisée.

Écrire un programme, c'est exécuter deux différentes tâches : définir des structures de données et définir des opérations à effectuer sur ces données. Dans la JVM, l'unité fondamentale d'opération est l'instruction.

En bytecode, tout comme en assembleur, une instruction effectue des opérations atomiques. En d'autres termes, il est généralement nécessaire d'avoir plusieurs instructions pour effectuer une opération prenant une ligne en Java (au tout autre langage de haut niveau).

En bytecode, les instructions sont présentes uniquement dans des méthodes.

Dans cette partie et les suivantes, nous étudierons les quelque 203 instructions de la JVM.

Nous commencerons par voir les instructions permettant de retourner une valeur à une méthode appelante, de manipuler des données des variables locales et de la pile.

IV-D - Arguments et opérandes

Une mnémonique peut avoir des arguments qui le suivent tels que :

1. ldc "Hello World"

Le nombre d'arguments dépend de la mnémonique. Certains n'en prennent aucun et d'autres plusieurs. Ce nombre est fixe pour chaque mnémonique.

En revanche, les opérandes sont récupérés de la pile :

1. iadd

l'opération iadd prend les deux premiers éléments de la pile est les additionne. Les opérandes ne sont donc pas passés en arguments.

IV-E - Représentation de la pile

La JVM étant basée sur le modèle de la pile, il est essentiel de connaître quel est l'impact des instructions. Pour représenter l'état avant/après l'exécution d'une instruction, nous allons reprendre le format utilisé par la JVMS et qui est le suivant :

…, valeur1, valeur2 → …, résultat, où les valeurs le plus à droite sont au sommet de la pile. valeur1 et valeur2 étant les deux valeurs utilisées pour le calcul et résultat le résultat.

Il est important de noter que dans cette représentation les long et le double sont considérés comme une seule valeur. Par conséquent, lorsque nécessaire nous présenterons les différents cas d'utilisation d'une instruction en utilisant plusieurs formes.

IV-F - Retourner une valeur

Quand une méthode a terminé de s'exécuter, elle doit rendre le contrôle à la méthode appelante. L'appelant attend généralement une valeur/référence de la méthode appelée. Après qu'une instruction xreturn (où x est un type) soit exécutée, le contrôle est transféré à l'instruction suivant l'une des instructions invoke (utilisées pour appeler un méthode, nous étudierons les instructions invoke en détail dans une prochaine partie). La valeur au sommet de la pile avant l'exécution d'une instruction xreturn est retournée à l'appelant et est placée au sommet de la pile du cadre contenant la méthode appelante comme nous l'avons vu dans la partie JVM Hardcore - Introduction à la JVM.

La valeur retournée doit être du type indiqué dans le descripteur de la méthode.

Les instructions suivantes retournent la valeur/référence présente au sommet de la pile à l'appelant :

État de la pile avant → après exécution : …, valeur → [vide]

Hex

Mnémonique

Description

0xac

ireturn

Retourne à l'appelant et ajoute un int au sommet de la pile

0xad

lreturn

Retourne à l'appelant et ajoute un long au sommet de la pile

0xae

freturn

Retourne à l'appelant et ajoute un float au sommet de la pile

0xaf

dreturn

Retourne à l'appelant et ajoute un double au sommet de la pile

0xb0

areturn

Retourne à l'appelant et ajoute une reference au sommet de la pile

0xb1

return

Retourne à l'appelant sans changer le sommet de la pile (void)

IV-G - Constantes

Les instructions suivantes ajoutent une constante au sommet de la pile :

État de la pile avant → après exécution : … → …, constante

Hex

Mnémonique

Argument

Description

0x01

aconst_null

Empile une reference de la valeur null

0x02

iconst_m1

Empile la valeur -1 de type int

0x03

iconst_0

Empile la valeur 0 de type int

0x04

iconst_1

Empile la valeur 1 de type int

0x05

iconst_2

Empile la valeur 2 de type int

0x06

iconst_3

Empile la valeur 3 de type int

0x07

Iconst

Empile la valeur 4 de type int

0x08

iconst_5

Empile la valeur 5 de type int

0x09

lconst_0

Empile la valeur 0 de type long

0x0a

lconst_1

Empile la valeur 1 de type long

0x0b

fconst_0

Empile la valeur 0 de type float

0x0c

fconst_1

Empile la valeur 1 de type float

0x0d

fconst_2

Empile la valeur 2 de type float

0x0e

dconst_0

Empile la valeur 0 de type double

0x0f

dconst_1

Empile la valeur 1 de type double

0x10

bipush

n

Empile n, où n appartient à l'intervalle [-128; 127]

0x11

Sipush

n

Empile n, où n appartient à l'intervalle [-32 768; 32 767]

0x12

ldc

n

Empile n, où n peut être de type String, int ou float

0x13

ldc_w

n

Empile n, où n peut être de type String, int ou float

0x14

ldc2_w

n

Empile n, où n peut être de type long ou double

La JVM supporte des constantes de type int, float, long, double et String.

La JVM est optimisée pour utiliser de petites constantes en fournissant des instructions spéciales pour les charger. Cela évite de rajouter des entrées supplémentaires dans le pool de constantes.

Pour les nombres les plus communs, il y a les instructions xconst_n où x est le type et n la valeur à empiler.

Pour ajouter une référence nulle au sommet de la pile, nous pouvons utiliser l'instruction aconstant_null :

1. .class org/isk/jvmhardcore/bytecode/partthree/Aconst_null

2. .method get()Ljava/lang/Object;

3. aconst_null

4. areturn

5. .methodend

6. .classend

Source

Test unitaire :

1. @Test

2. public void aconst_null() {

3. final Object obj = Aconst_null.get();

5. Assert.assertNull(obj);

6. }

Source

La méthode suivante retourne un int ayant pour valeur -1 :

1. .class org/isk/jvmhardcore/bytecode/partthree/Iconst_m1

2. .method get()I

3. iconst_m1

4. ireturn

5. .methodend

6. .classend

Source

Test unitaire :

1. @Test

2. public void iconst_m1() {

3. final int num = Iconst_m1.get();

5. Assert.assertEquals(-1, num);

6. }

Source

La méthode suivante retourne un double ayant pour valeur 1 :

1. .class org/isk/jvmhardcore/bytecode/partthree/Dconst_1

2. .method get()D

3. dconst_1

4. dreturn

5. .methodend

6. .classend

Source

Test unitaire :

1. @Test

2. public void dconst_1() {

3. final double num = Dconst_1.get();

5. Assert.assertEquals(1.0, num);

6. }

Source

Dans les trois exemples précédents, les éléments à prendre en compte sont les suivants :

- le descripteur des méthodes et notamment leur type de retour ;

- les préfixes des instructions.

Essayons de retourner un type différent de ce qui est défini dans le descripteur :

1. class org/isk/jvmhardcore/bytecode/partthree/WrongReturnType

2. .method get()I

3. dconst_1

4. dreturn

5. .methodend

6. .classend

Source

Test unitaire :

1. @Test

2. public void wrongReturnType() {

3. try {

4. WrongReturnType.get();

5. Assert.fail();

6. } catch (VerifyError e) {

7. // Assertion

8. // Message retourné par la JVM:

9. //   (class: org/isk/jvmhardcore/bytecode/partthree/WrongReturnType,

10. //   "method: get signature: ()I) Wrong return type in function

11. }

12. }

Source

Lors de l'étape de vérification de la JVM une exception de type VerifyError est levée, nous indiquant que le type de retour de la méthode get() est incorrect. Il s'agit d'un entier alors que l'on utilise l'instruction dreturn retournant un double.

De même, si l'instruction xreturn ne correspond pas au type de l'élément au sommet de la pile, une exception est levée :

1. .class org/isk/jvmhardcore/bytecode/partthree/WrongTypeReturned

2. .method get()D

3. dconst_1

4. ireturn

5. .methodend

6. .classend

Source

Test unitaire :

1. @Test

2. public void wrongTypeReturned() {

3. try {

4. WrongTypeReturned.get();

5. Assert.fail();

6. } catch (VerifyError e) {

7. // Assertion

8. // Message retourné par la JVM:

9. //   (class: org/isk/jvmhardcore/bytecode/partthree/WrongTypeReturned,

10. //   method: get signature: ()D) Expecting to find integer on stack

11. }

12. }

Source

Nous verrons l'étape de vérification effectuée par la JVM dans quelques parties.

Pour de petits entiers n'étant pas disponibles sous la forme xconst_n, il y a les instructions bipush et sipush. Ces deux instructions prennent les valeurs en arguments comme les instructions ldc. En bytecode bipush et sipush prennent en arguments les valeurs à empiler (sur 1 byte pour bipush et 2 bytes sur sipush) et non des index contrairement aux instructions ldc. Par conséquent, si une constante est incluse dans l'intervalle [-32 768; 32 767] il est préférable de ne pas utiliser l'instruction ldc.

Utilisation de l'instruction bipush :

1. .class org/isk/jvmhardcore/bytecode/partthree/Bipush

2. .method get()B

3. bipush 117

4. ireturn

5. .methodend

6. .classend

Source

Test unitaire :

1. @Test

2. public void bipush() {

3. final byte num = Bipush.get();

5. Assert.assertEquals(117, num);

6. }

Source

Utilisation de l'instruction sipush :

1. .class org/isk/jvmhardcore/bytecode/partthree/Sipush

2. .method get()S

3. sipush 14909

4. ireturn

5. .methodend

6. .classend

Source

Test unitaire :

1. @Test

2. public void sipush() {

3. final short num = Sipush.get();

5. Assert.assertEquals(14909, num);

6. }

Source

Dans les deux exemples précédents, l'instruction de retour utilisée est ireturn et le type de retour des méthodes est respectivement B et S, puisque comme nous l'avons vu, la JVM ne manipule pas ces types. Par conséquent, nous pouvons aussi utiliser I comme type de retour :

1. .class org/isk/jvmhardcore/bytecode/partthree/Bipush_int

2. .method get()I

3. bipush -117

4. ireturn

5. .methodend

6. .classend

Source

Test unitaire :

1. @Test

2. public void bipush_int() {

3. final int num = Bipush_int.get();

5. Assert.assertEquals(-117, num);

6. }

Source

Pour les instructions de type ldc, en PJBA, n représente une valeur littérale alors qu'en bytecode, il s'agit d'un index dans le pool de constantes de la classe (que nous verrons un peu plus tard).

La partie _w des instructions ldc_w et ldc2_w signifie « wide » (large). Concrètement, l'index sur lequel pointent ces instructions prend 2 bytes, au lieu d'un.

Les instructions ldc et ldc_w sont équivalentes, à l'exception que ldc_w pointe sur un index prenant 2 bytes, au lieu d'un pour ldc. PJBA générant le pool de constantes, il choisit l'instruction convenant à la situation. Dans un fichier .pjb, il est possible d'utiliser uniquement l'instruction ldc.

Dans l'instruction ldc2_w, le 2 signifie que la constante prend deux entrées dans la pile.

Voyons quelques exemples.

L'instruction ldc peut prendre toute chaîne de caractères UTF-8 entre guillemets. Pour pouvoir insérer un guillemet au milieu d'une chaîne de caractère, il faut l'échapper (\”).

1. .class org/isk/jvmhardcore/bytecode/partthree/Ldc_String

2. .method getString()Ljava/lang/String;

3. ldc "Привет \\\" мир по-русски"    @ Hello world " en russe

4. areturn    @ Une chaîne de caractères est de type java/lang/String

5. .methodend

6. .classend

Source

Test unitaire :

1. @Test

2. public void ldc_string() {

3. final String result = Ldc_String.getString();

5. Assert.assertEquals("Привет \\\" мир по-русски", result);

6. }

Source

L'instruction ldc avec un int :

1. .class org/isk/jvmhardcore/bytecode/partthree/Ldc_Integer

2. .method getInteger()I

3. ldc 1000

4. ireturn

5. .methodend

6. .classend

Source

Test unitaire :

1. @Test

2. public void ldc_integer() {

3. final int result = Ldc_Integer.getInteger();

5. Assert.assertEquals(1000, result);

6. }

Source

L'instruction ldc avec un float :

1. .class org/isk/jvmhardcore/bytecode/partthree/Ldc_Float

2. .method getFloat()F

3. ldc -15.56e-12

4. freturn

5. .methodend

6. .classend

Source

Test unitaire :

1. @Test

2. public void ldc_float() {

3. final float result = Ldc_Float.getFloat();

5. Assert.assertEquals(-15.56e-12f, result);

6. }

Source

L'instruction ldc2_w avec un long :

1. .class org/isk/jvmhardcore/bytecode/partthree/Ldc_Long

2. .method getLong()J

3. ldc2_w 1324

4. lreturn

5. .methodend

6. .classend

Source

Test unitaire :

1. @Test

2. public void ldc2_w_long() {

3. final long result = Ldc_Long.getLong();

5. Assert.assertEquals(1324l, result);

6. }

Source

L'instruction ldc2_w avec un double :

1. .class org/isk/jvmhardcore/bytecode/partthree/Ldc_Double

2. .method getDouble()D

3. ldc2_w -14.70e-43

4. dreturn

5. .methodend

6. .classend

Source

Test unitaire :

1. @Test

2. public void ldc2_w_double() {

3. final double result = Ldc_Double.getDouble();

5. Assert.assertEquals(-14.70e-43, result);

6. }

Source

IV-H - What's next ?

Dans la partie suivante, nous verrons des instructions permettant de manipuler les variables locales.

V - Manipulation des variables locales

Au cours de cette cinquième partie, nous allons continuer notre voyage dans le monde des instructions bytecode Java.

Chaque cadre (frame) a un tableau de variables locales pouvant accueillir jusqu'à 65 536 entrées. Ceci signifie que la somme du nombre de paramètres et des variables temporaires d'une méthode ne peut excéder 65 536. Sachant que l'utilisation de variables de type long ou double réduit ce nombre. Bien évidemment, pour des raisons de performance, il est préférable d'utiliser des cases contiguës à partir de l'index 0 pour éviter à la JVM de créer des tableaux excessivement grands pour seulement quelques valeurs.

Les instructions load et store permettent de déplacer des valeurs de la pile vers les variables locales et vice versa. Plus précisément, load récupère une valeur des variables locales, puis l'empile, et store stocke la valeur au sommet de la pile dans les variables locales.

Le code est disponible sur Github (tag et branche).

V-A - Représentation de la pile

La JVM étant basée sur le modèle de la pile, il est essentiel de connaître quel est l'impact des instructions. Pour représenter l'état avant/après l'exécution d'une instruction, nous allons reprendre le format utilisé par la JVMS et qui est le suivant :

…, valeur1, valeur2 → …, résultat, où les valeurs le plus à droite sont au sommet de la pile. « valeur1 » et « valeur »2 étant les deux valeurs utilisées pour le calcul et « résultat » le résultat.

Il est important de noter que dans cette représentation le long et le double sont considérés comme une seule valeur. Par conséquent, lorsque nécessaire nous présenterons les différents cas d'utilisation d'une instruction en utilisant plusieurs formes.

V-B - Initialisation des variables locales

Comme nous l'avons vu dans la partie Part II - Introduction à la JVM, la JVM utilise les variables locales pour passer des paramètres à la méthode appelée. Lorsqu'une méthode de classe (statique) est appelée, tous les paramètres sont stockés dans les variables locales de manière consécutive à partir de l'index zéro. Lorsqu'une méthode d'instance est appelée, la variable à l'index zéro est toujours une référence de l'objet (this) sur laquelle la méthode a été appelée. Les paramètres sont quant à eux stockés de manière consécutive à partir de l'index 1.

Néanmoins, les variables locales étant aussi utilisées pour stocker des résultats partiels, les paramètres d'une méthode ou this peuvent être remplacés.

À noter que pour l'instant, PJBA permettant uniquement de générer des méthodes statiques, leurs paramètres sont accessibles à partir de l'index 0 des variables locales.

V-C - Load

Les instructions suivantes permettent de récupérer des valeurs depuis les variables locales. Les valeurs sont ajoutées au sommet de la pile (mais sont toujours disponibles dans les variables locales).

État de la pile avant → après exécution : … → valeur

Hex

Mnémonique

Argument

Description

0x15

iload

n

Empile la valeur de type int à l'index n

0x16

lload

n

Empile la valeur de type long à l'index n

0x17

fload

n

Empile la valeur de type float à l'index n

0x18

dload

n

Empile la valeur de type double à l'index n

0x19

aload

n

Empile la référence à l'index n

0x1a

iload_0

Empile la valeur de type int à l'index 0

0x1b

iload_1

Empile la valeur de type int à l'index 1

0x1c

iload_2

Empile la valeur de type int à l'index 2

0x1d

iload_3

Empile la valeur de type int à l'index 3

0x1e

lload_0

Empile la valeur de type long à l'index 0

0x1f

lload_1

Empile la valeur de type long à l'index 1

0x20

lload_2

Empile la valeur de type long à l'index 2

0x21

lload_3

Empile la valeur de type long à l'index 3

0x22

fload_0

Empile la valeur de type float à l'index 0

0x23

fload_1

Empile la valeur de type float à l'index 1

0x24

fload_2

Empile la valeur de type float à l'index 2

0x25

fload_3

Empile la valeur de type float à l'index 3

0x26

dload_0

Empile la valeur de type double à l'index 0

0x27

dload_1

Empile la valeur de type double à l'index 1

0x28

dload_2

Empile la valeur de type double à l'index 2

0x29

dload_3

Empile la valeur de type double à l'index 3

0x2a

aload_0

Empile la référence à l'index 0

0x2b

aload_1

Empile la référence à l'index 1

0x2c

aload_2

Empile la référence à l'index 2

0x2d

aload_3

Empile la référence à l'index 3

Voyons quelques exemples :

Empile une chaîne de caractères avec aload:

1. .class org/isk/jvmhardcore/bytecode/partfour/Aload

2. .method getThird(BILjava/lang/String;J)Ljava/lang/String;

3. aload 2

4. areturn

5. .methodend

6. .classend

Source

Test unitaire :

1. @Test

2. public void aload() {

3. final String result = Aload.getThird((byte)1, 2, "Hello", 4l);

5. Assert.assertEquals("Hello", result);

6. }

Source

Empile un long avec lload :

1. .class org/isk/jvmhardcore/bytecode/partfour/Lload

2. .method getFourth(BILjava/lang/String;J)J

3. lload 3

4. lreturn

5. .methodend

6. .classend

Source

Test unitaire :

1. @Test

2. public void lload() {

3. final long result = Lload.getFourth((byte)1, 2, "Hello", 4l);

5. Assert.assertEquals(4l, result);

6. }

Source

Empile l'int dans les variables à l'index 0 avec iload_0 :

1. .class org/isk/jvmhardcore/bytecode/partfour/Iload_0

2. .method getFirst(III)I

3. iload_0

4. ireturn

5. .methodend

6. .classend

Source

Test unitaire :

1. @Test

2. public void iload_0() {

3. final int result = Iload_0.getFirst(1, 2, 3);

5. Assert.assertEquals(1, result);

6. }

Source

Empile l'int dans les variables à l'index 0 avec iload_0 et retourne un byte :

1. .class org/isk/jvmhardcore/bytecode/partfour/Iload_0_Byte

2. .method getFirst(BII)B

3. iload_0

4. ireturn

5. .methodend

6. .classend

Source

Test unitaire :

1. @Test

2. public void iload_0_byte() {

3. final byte result = Iload_0_Byte.getFirst((byte) 1, 2, 3);

5. Assert.assertEquals(1, result);

6. }

Source

Empile l'int dans les variables à l'index 0 avec iload_0 et retourne un char :

1. .class org/isk/jvmhardcore/bytecode/partfour/Iload_0_Char

2. .method getFirst(CII)C

3. iload_0

4. ireturn

5. .methodend

6. .classend

Source

Test unitaire :

1. @Test

2. public void iload_0_char() {

3. final char result = Iload_0_Char.getFirst((char) 1, 2, 3);

5. Assert.assertEquals(1, result);

6. }

Source

Empile l'int dans les variables à l'index 0 avec iload_0 et retourne un short :

1. .class org/isk/jvmhardcore/bytecode/partfour/Iload_0_Short

2. .method getFirst(SII)S

3. iload_0

4. ireturn

5. .methodend

6. .classend

Source

Test unitaire :

1. @Test

2. public void iload_0_short() {

3. final short result = Iload_0_Short.getFirst((byte) 1, 2, 3);

5. Assert.assertEquals(1, result);

6. }

Source

Essaie de retourner la valeur à l'index 0 des variables locales.

1. .class org/isk/jvmhardcore/bytecode/partfour/Iload_0_NoArgs

2. .method getFirst()I

3. iload_0

4. ireturn

5. .methodend

6. .classend

Source

Test unitaire :

1. @Test

2. public void iload_0_noargs() {

3. try {

4. Iload_0_NoArgs.getFirst();

5. Assert.fail();

6. } catch (VerifyError e) {

7. // Assertion

8. // Message retourné par la JVM:

9. //   (class: org/isk/jvmhardcore/bytecode/partfour/Iload_0_NoArgs,

10. //   method: getFirst signature: ()I) Accessing value from uninitialized register 0"

11. }

12. }

Source

La méthode n'ayant pas de paramètre et aucune instruction de stockage dans les variables locales n'ayant été effectuée, il n'y a rien à l'index 0. Par conséquent, une exception est levée.

Empile l'int dans les variables à l'index 1 avec iload_1 :

1. .class org/isk/jvmhardcore/bytecode/partfour/Iload_1

2. .method getSecond(III)I

3. iload_1

4. ireturn

5. .methodend

6. .classend

Source

Test unitaire :

1. @Test

2. public void iload_1() {

3. final int result = Iload_1.getSecond(1, 2, 3);

5. Assert.assertEquals(2, result);

6. }

Source

V-D - Store

Les instructions suivantes permettent de stocker la variable au sommet de la pile dans les variables locales. La valeur au sommet de la pile est supprimée.

État de la pile avant → après exécution : …, valeur → …

Hex

Mnémonique

Argument

Description

0x36

istore

n

Stocke la valeur de type int au sommet de la pile à l'index n

0x37

lstore

n

Stocke la valeur de type long au sommet de la pile à l'index n

0x38

fstore

n

Stocke la valeur de type float au sommet de la pile à l'index n

0x39

dstore

n

Stocke la valeur de type double au sommet de la pile à l'index n

0x3a

astore

n

Stocke la référence au sommet de la pile à l'index n

0x3b

istore_0

Stocke la valeur de type int au sommet de la pile à l'index 0

0x3c

istore_1

Stocke la valeur de type int au sommet de la pile à l'index 1

0x3d

istore_2

Stocke la valeur de type int au sommet de la pile à l'index 2

0x3e

istore_3

Stocke la valeur de type int au sommet de la pile à l'index 3

0x3f

lstore_0

Stocke la valeur de type long au sommet de la pile à l'index 0

0x40

lstore_1

Stocke la valeur de type long au sommet de la pile à l'index 1

0x41

lstore_2

Stocke la valeur de type long au sommet de la pile à l'index 2

0x42

lstore_3

Stocke la valeur de type long au sommet de la pile à l'index 3

0x43

fstore_0

Stocke la valeur de type float au sommet de la pile à l'index 0

0x44

fstore_1

Stocke la valeur de type float au sommet de la pile à l'index 1

0x45

fstore_2

Stocke la valeur de type float au sommet de la pile à l'index 2

0x46

fstore_3

Stocke la valeur de type float au sommet de la pile à l'index 3

0x47

dstore_0

Stocke la valeur de type double au sommet de la pile à l'index 0

0x48

dstore_1

Stocke la valeur de type double au sommet de la pile à l'index 1

0x49

dstore_2

Stocke la valeur de type double au sommet de la pile à l'index 2

0x4a

dstore_3

Stocke la valeur de type double au sommet de la pile à l'index 3

0x4b

astore_0

Stocke la référence au sommet de la pile à l'index 0

0x4c

astore_1

Stocke la référence au sommet de la pile à l'index 1

0x4d

astore_2

Stocke la référence au sommet de la pile à l'index 2

0x4e

astore_3

Stocke la référence au sommet de la pile à l'index 3

Contrairement à Java, les variables sont typées dynamiquement. Par conséquent, il est possible de stocker les cinq types connus de la JVM à n'importe quel index des variables locales. Une variable locale peut donc avoir des valeurs différentes à différents moments.

Prenons le code suivant :

1. .class org/isk/jvmhardcore/bytecode/partfour/Reassign

2. .method reassign()D

3. ldc "ma chaîne"

4. astore_0

5. aload_0

6. dconst_1

7. dstore_0

8. dload_0

9. dreturn

10. .methodend

11. .classend

Source

Voyons ce qu'il se passe dans le cadre contenant la méthode reassign() :

Pour finir testons la méthode reassign() :

1. @Test

2. public void reassign() {

3. final double result = Reassign.reassign();

5. Assert.assertEquals(1.0, result, 0.00001);

6. }

Source

Tout comme de nombreuses instructions que nous avons vues dans la partie précédente, load et store sont liées à des types. Ces types sont identifiables - le plus souvent - grâce à la première lettre de la mnémonique de l'instruction. De fait, il est nécessaire de faire attention à utiliser l'instruction correspondant aux types des valeurs présentes dans la pile et qui seront utilisées comme opérandes.

1. ldc  "ma chaîne"

2. istore 0            # Erreur! astore doit être utilisé

Les variables de type long et double prennent deux entrées dans la pile et les variables locales.

1. ldc  "ma chaîne"

2. astore_2

3. ldc2_w 3.14d

4. dstore_1

5. aload_2         # Erreur! Une partie du double a remplacé "ma chaîne"

Pour finir notre tour des points d'attention, il est important de noter qu'une variable locale doit être initialisée avant d'être utilisée.

1. iconst_5    # Empile 5

2. istore_3    # Stocke 5 dans la variable locale à l'index 3

3. iload_3     # Récupère la valeur (5) stockée dans la variable locale à l'index 3

Pour rappel, le tableau des variables locales - d'un cadre - est automatiquement initialisé par la JVM avec les paramètres de la méthode en cours d'exécution, si elle en a.

V-E - What's next ?

Dans la partie suivante, nous verrons des instructions permettant d'effectuer des opérations sur des nombres, mais aussi de changer le type des nombres.

VI - Mathématiques et Conversions

Au cours de cette partie, nous allons nous intéresser aux instructions bytecode dédiées aux opérations sur les nombres. Ces opérations sont divisées en deux catégories :

- les opérations arithmétiques (addition, soustraction, multiplication, division) ;

- les opérations bit à bit (or, xor, not, and, etc.).

En mémoire, les entiers et les nombres à virgules sont représentés différemment. Pour cette raison, comme nous l'avons déjà vu, il y a plusieurs instructions pour une même opération. Les int et les long sont représentés en utilisant le complément à deux. Les float et les double sont quant à eux représentés en utilisant le standard IEEE 754.

Le code est disponible sur GitHub (tag et branche).

VI-A - Représentation de la pile

La JVM étant basée sur le modèle de la pile, il est essentiel de connaître quel est l'impact des instructions. Pour représenter l'état avant/après l'exécution d'une instruction, nous allons reprendre le format utilisé par la JVMS et qui est le suivant :

…, valeur1, valeur2 → …, résultat, où les valeurs les plus à droite sont au sommet de la pile. valeur1 et valeur2 étant les deux valeurs utilisées pour le calcul et résultat, le résultat.

Il est important de noter que dans cette représentation, le long et le double sont considérés comme une seule valeur. Par conséquent, lorsque nécessaire nous présenterons les différents cas d'utilisation d'une instruction en utilisant plusieurs formes.

VI-B - Opérations arithmétiques

VI-B-1 - Addition

Les quatre instructions suivantes permettent d'additionner deux nombres.

Les deux nombres sont dépilés et le résultat est empilé.

Pour une opération du type, où le signe + peut être remplacé par -, *, / ou % (modulo), y est au sommet de la pile et x en dessous. L'addition et la multiplication étant commutatives, cet ordre n'a pas d'importance. En revanche, pour les autres opérations il faut en tenir compte.

État de la pile avant → après exécution : …, v1, v2 → …, résultat.

Hex

Mnémonique

Description

0x60

iadd

v1 + v2, où v1 et v2 doivent être de type int

0x61

ladd

v1 + v2, où v1 et v2 doivent être de type long

0x62

fadd

v1 + v2, où v1 et v2 doivent être de type float

0x63

dadd

v1 + v2, où v1 et v2 doivent être de type double

Note : en Java l'opérateur + permet aussi de concaténer des chaînes de caractères. La JVM n'a pas une telle instruction. En réalité, le compilateur Java remplace toutes les concaténations par des StringBuilder pour les versions de Java supérieures ou égales à Java 5 et des StringBuffer pour les versions inférieures ou égales à Java 1.4. La différence entre les deux est que toutes les opérations d'un StringBuffer sont synchronisées, contrairement à celles d'un StringBuilder.

Pour changer un peu, nous allons voir une addition avec trois termes :

1. .class org/isk/jvmhardcore/bytecode/partfive/Addition

2. .method add(III)I;

3. iload_0  # [empty] -> idx0

4. iload_1  # idx0 -> idx0, idx1

5. iadd     # idx0, idx1 -> résultatPartiel

6. iload_2  # résultatPartiel -> résultatPartiel, idx2

7. iadd     # résultatPartiel, idx2 -> résultat

8. ireturn

9. .methodend

10. .classend

Source

Test unitaire :

1. public void add() {

2. final int result = Addition.add(1, 2, 3);

4. Assert.assertEquals(6, result);

5. }

Source

VI-B-2 - Soustraction

Les quatre instructions suivantes permettent de soustraire deux nombres.

État de la pile avant → après exécution : …, v1, v2 → …, résultat.

Hex

Mnémonique

Description

0x64

isub

v1 - v2, où v1 et v2 doivent être de type int

0x65

lsub

v1 - v2, où v1 et v2 doivent être de type long

0x66

fsub

v1 - v2, où v1 et v2 doivent être de type float

0x67

dsub

v1 - v2, où v1 et v2 doivent être de type double

Exemple :

1. .class org/isk/jvmhardcore/bytecode/partfive/Subtraction

2. .method subtract(DDD)D;

3. dload_0  # [empty] -> idx0

4. dload_2  # idx0 -> idx0, idx2

5. dsub     # idx0, idx2 -> résultatPartiel

6. dload 4  # résultatPartiel -> résultatPartiel, idx4

7. dsub     # résultat

8. dreturn

9. .methodend

10. .classend

Source

Test unitaire :

1. public void subtract() {

2. final double result = Subtraction.subtract(1, 2, 3);

4. Assert.assertEquals(-4d, result, 0.0001);

5. }

Source

VI-B-3 - Multiplication

Les quatre instructions suivantes permettent de multiplier deux nombres.

État de la pile avant → après exécution : …, v1, v2 → …, résultat.

Hex

Mnémonique

Description

0x68

imul

v1 * v2, où v1 et v2 doivent être de type int

0x69

lmul

v1 * v2, où v1 et v2 doivent être de type long

0x6a

fmul

v1 * v2, où v1 et v2 doivent être de type float

0x6b

dmul

v1 * v2, où v1 et v2 doivent être de type double

Exemple :

1. .class org/isk/jvmhardcore/bytecode/partfive/Multiplication

2. .method multiply(FF)F;

3. fload_0  # [empty] -> idx0

4. fload_1  # idx0 -> idx0, idx1

5. fmul     # idx0, idx1 -> résultat

6. freturn

7. .methodend

8. .classend

Source

Test unitaire :

1. public void multiply() {

2. final float result = Multiplication.multiply(3, 2);

4. Assert.assertEquals(6, result, 0.0001);

5. }

Source

VI-B-4 - Division

Les quatre instructions suivantes permettent de diviser deux nombres.

État de la pile avant → après exécution : …, v1, v2 → …, résultat.

Hex

Mnémonique

Description

0x6c

idiv

v1 / v2, où v1 et v2 doivent être de type int

0x6d

ldiv

v1 / v2, où v1 et v2 doivent être de type long

0x6e

fdiv

v1 / v2, où v1 et v2 doivent être de type float

0x6f

ddiv

v1 / v2, où v1 et v2 doivent être de type double

Exemple :

1. .class org/isk/jvmhardcore/bytecode/partfive/Division

2. .method divide(JJ)J

3. lload_0  # [empty] -> idx0

4. lload_2  # idx0 -> idx0, idx2

5. ldiv     # idx0, idx2 -> résultat

6. lreturn

7. .methodend

8. .classend

Source

Test unitaire :

1. public void divide() {

2. final long result = Division.divide(3, 2);

4. Assert.assertEquals(1, result);

5. }

Source

VI-B-5 - Reste

Les quatre instructions suivantes permettent d'obtenir le reste de la division de deux nombres.

État de la pile avant → après exécution : …, v1, v2 → …, résultat.

Hex

Mnémonique

Description

0x70

irem

v1 % v2, où v1 et v2 doivent être de type int

0x71

lrem

v1 % v2, où v1 et v2 doivent être de type long

0x72

frem

v1 % v2, où v1 et v2 doivent être de type float

0x73

drem

v1 % v2, où v1 et v2 doivent être de type double

Exemple :

1. .class org/isk/jvmhardcore/bytecode/partfive/Remainder

2. .method getRemainder(II)I

3. iload_0  # [empty] -> idx0

4. iload_1  # idx0 -> idx0, idx1

5. irem     # idx0, idx1 -> result

6. ireturn

7. .methodend

8. .classend

Source

Test unitaire :

1. public void getRemainder() {

2. final int result = Remainder.getRemainder(40, 7);

4. Assert.assertEquals(5, result);

5. }

Source

VI-B-6 - Négation

Les quatre instructions suivantes permettent de changer le signe du nombre au sommet de la pile.

État de la pile avant → après exécution : …, valeur → …, résultat.

Hex

Mnémonique

Description

0x74

ineg

Inverse le signe d'un int

0x75

lneg

Inverse le signe d'un long

0x76

fneg

Inverse le signe d'un float

0x77

dneg

Inverse le signe d'un double

Exemple :

1. .class org/isk/jvmhardcore/bytecode/partfive/Negation

2. .method negate(I)I

3. iload_0  # [empty] -> idx0

4. ineg     # idx0 -> résultat

5. ireturn

6. .methodend

7. .classend

Source

Test unitaire

1. public void negate() {

2. final int result = Negation.negate(-10);

4. Assert.assertEquals(10, result);

5. }

Source

VI-C - Opérations bit à bit

VI-C-1 - Opérations de décalage de bits

Les instructions suivantes permettent d'effectuer des opérations de décalage de bits.

État de la pile avant → après exécution : …, v1, v2 → …, r.

Hex

Mnémonique

Description

0x78

ishl

v1 << v2, où v1 et v2 doivent être de type int. Seulement les 5 bits les plus faibles de v1 sont pris en compte.

0x79

lshl

v1 << v2, où v1 doit être de type long et v2 de type int. Seulement les 5 bits les plus faibles de v2 sont pris en compte.

0x7a

ishr

v1 >> v2, où v1 et v2 doivent être de type int. Seulement les 5 bits les plus faibles de v1 sont pris en compte.

0x7b

lshr

v1 >> v2, où v1 doit être de type long et v2 de type long. Seulement les 6 bits les plus faibles de v1 sont pris en compte.

0x7c

iushr

v1 >>> v2, où v1 et v2 doivent être de type int. Seulement les 5 bits les plus faibles de v1 sont pris en compte.

0x7b

lushr

v1 >>> v2, v1 doit être de type long et v2 de type long. Seulement les 6 bits les plus faibles de v1 sont pris en compte.

Le fait que seulement 5 ou 6 bits de v2 soient utilisés n'a rien de surprenant, puisque la valeur de v2 correspond au nombre de bits déplacés. Or 5 bits permettent de représenter des nombres de 0 à 31 et 6 bits des nombres de 0 à 63. Au-delà, le résultat serait toujours 0 ou -1 :

// Si x est un int
x << 32 = |x| >>  32 = x >>> 32 = 0
-|x| >> 32 = -1

Si x était un long et le décalage de 64 bits, nous aurions les mêmes résultats.

Il est aussi important de noter que les opérations de décalage de bits, et les opérations bit à bit d'une manière générale, ne s'effectuent que sur des int et des long. La représentation des float et des double en mémoire fait qu'une opération bit à bit n'aurait pas de sens.

Décalage de bits vers la gauche :

1. .class org/isk/jvmhardcore/bytecode/partfive/BitShifting_Left

2. .method shift()I

3. bipush 9  # [empty] -> 9 (1001)

4. iconst_1  # 9 -> 9, 1

5. ishl      # 9, 1 -> 18

6. ireturn

7. .methodend

8. .classend

Source

Test unitaire :

1. public void shiftLeft() {

2. final int result = BitShifting_Left.shift();

3. Assert.assertEquals(18, result);

4. }

Source

Décalage de bits vers la droite :

1. .class org/isk/jvmhardcore/bytecode/partfive/BitShifting_Right

2. .method shift()I

3. bipush 9  # [empty] -> 9 (1001)

4. iconst_1  # 9 -> 9, 1

5. ishr      # 9, 1 -> 4

6. ireturn

7. .methodend

8. .classend

Source

Test unitaire :

1. public void shiftRight() {

2. final int result = BitShifting_Right.shift();

4. Assert.assertEquals(4, result);

5. }

Source

VI-D - Opérations logiques

Les instructions suivantes permettent d'effectuer des opérations logiques.

État de la pile avant → après exécution …, v1, v2 → …, r.

Hex

Mnémonique

Description

0x7e

iand

v1 & v2, où v1 et v2 doivent être de type int

0x7f

land

v1 & v2, où v1 et v2 doivent être de type long

0x80

ior

v1 | v2, où v1 et v2 doivent être de type int

0x81

lor

v1 | v2, où v1 et v2 doivent être de type long

0x82

ixor

v1 ^ v2, où v1 et v2 doivent être de type int

0x83

lxor

v1 ^ v2, où v1 et v2 doivent être de type long

Nous pouvons noter que le signe tilde (~) permettant d'inverser les bits d'un nombre n'a pas d'instruction dédiée. L'opération ~x est convertie par le compilateur de la manière suivante :

1. @ Considérons que la variable x est à l'index 0 des variables locales

2. @ et qu'elle est de type int

3. iload_0

4. iconst_m1

5. ixor        @ x | -1 = ~x

À présent, voyons quelques instructions, en commençant par iand :

1. .class org/isk/jvmhardcore/bytecode/partfive/Iand

2. .method iand()I

3. bipush 10  # [empty] -> 10 (1010)

4. bipush 7   # 10 -> 10, 7 (0111)

5. iand       # 10, 5 -> 2 (0010)

6. ireturn

7. .methodend

8. .classend

Source

Test unitaire :

1. public void iand() {

2. final int result = Iand.iand();

4. Assert.assertEquals(2, result);

5. }

Source

ior :

1. .class org/isk/jvmhardcore/bytecode/partfive/Ior

2. .method ior()I

3. bipush 10  # [empty] -> 10 (1010)

4. bipush 7   # 10 -> 10, 5 (0111)

5. ior        # 10, 5 -> 15 (1111)

6. ireturn

7. .methodend

8. .classend

Source

Test unitaire :

1. public void ior() {

2. final int result = Ior.ior();

4. Assert.assertEquals(15, result);

5. }

Source

ixor :

1. .class org/isk/jvmhardcore/bytecode/partfive/Ixor

2. .method ixor()I

3. bipush 10  # [empty] -> 10 (1010)

4. bipush 7   # 10 -> 10, 5 (0111)

5. ixor       # 10, 5 -> 13 (1101)

6. ireturn

7. .methodend

8. .classend

Source

Test unitaire :

1. public void ixor() {

2. final int result = Ixor.ixor();

4. Assert.assertEquals(13, result);

5. }

Source

VI-E - Conversions

Étant donné que la plupart des opérations que nous venons de voir nécessitent deux opérandes du même type, il faut parfois effectuer des conversions d'un type à un autre.

Les opérations suivantes permettent de changer le type d'un nombre.

État de la pile avant → après exécution : …, valeur → …, résultat.

Hex

Mnémonique

Description

0x85

i2l

Convertit un int en long

0x86

i2f

Convertit un int en float

0x87

i2d

Convertit un int en double

0x88

l2i

Convertit un long en int

0x89

l2f

Convertit un long en float

0x8a

l2d

Convertit un long en double

0x8b

f2i

Convertit un float en int

0x8c

f2l

Convertit un float en long

0x8d

f2d

Convertit un float en double

0x8e

d2i

Convertit un double en int

0x8f

d2l

Convertit un double en long

0x90

d2f

Convertit un double en float

0x91

i2b

Convertit un int en byte

0x92

i2c

Convertit un int en byte

0x93

i2s

Convertit un int en byte

Avant de voir un exemple, il semble nécessaire d'effectuer quelques rappels :

- la JVM interprète les types byte, short et char comme des int. Par conséquent, les variables identifiées par les types B, S et C dans le descripteur d'une méthode doivent être associées à des instructions ayant pour préfixe i ;

- en Java, les littérales numériques sont de type int pour les entiers et double pour les nombres à virgule :

1. int i = 138_009;

2. double d = 354.89;

- en Java, pour pouvoir utiliser des littérales de types long ou float il est nécessaire de les faire suivre respectivement des lettres l et f :

1. long l = 786_987_789_273_456l;

2. float f = 1.32f;

- en Java, lorsque l'on souhaite utiliser des littérales de type byte, short et char il est nécessaire d'effectuer des conversions :

1. addBytes((byte)10, (byte)5)

L'utilisation d'instructions manipulant des valeurs numériques est régie par les règles suivantes :

1 - Une assignation utilisant :

- des littérales - où les littérales sont dans l'intervalle des valeurs possibles pour le type de la variable à laquelle est assignée la valeur ;

- ou des variables de même type.

n'implique aucune conversion :

1. byte a = -128;

2. byte b = a;

2 - Si les deux opérandes sont de même type :

- des littérales - où les littérales sont dans l'intervalle des valeurs possibles pour le type de la variable à laquelle est assignée la valeur ;

- ou des variables de même type.

1. int i = 25, j = 42;

2. int z = i + j;

4. byte a = -128;

5. byte b = 15;

6. int c = a + b;

7. byte d = (byte)(a + b)

3 - Si les opérandes sont de types différents, mais sans perte de précision - ou tout du moins dans les limites de la JVM - les conversions sont implicites (l'opération de conversion est bien présente au niveau bytecode, mais c'est à la charge du compilateur de la rajouter) :

1. long a = 13_342_099l;

2. float b = 3e-17f;

3. float c = a * b;

4 - Toutes les autres conversions doivent être explicitement effectuées.

Un exemple simple de conversion :

1. .class org/isk/jvmhardcore/bytecode/partfive/D2i

2. .method d2i(D)I

3. dload_0

4. d2i

5. ireturn

6. .methodend

7. .classend

Source

Test unitaire :

1. public void d2i() {

2. final int result = D2i.d2i(14.98);

4. Assert.assertEquals(14, result);

5. }

Source

Avant de conclure, notons que les trois dernières instructions (i2b, i2s et i2c) sont utilisées lorsque des conversions explicites sont effectuées entre un int et un byte ou un short ou un char.

VI-F - What's next ?

Dans la partie suivante, nous verrons les instructions permettant de manipuler la pile.

VII - Manipulation de la pile

Dans cette partie, nous allons étudier les instructions permettant de manipuler la pile. Comme nous le verrons, elles sont légèrement plus difficiles à appréhender que les précédentes.

Le code est disponible sur Github (tag et branche).

VII-A - Catégories des types

La correspondance entre les types utilisés par la JVM et les types Java est présentée dans le tableau ci-dessous.

Certaines instructions de la JVM telles que pop et swap opèrent sur la pile sans prendre en compte le type des valeurs manipulées, contrairement à toutes les instructions que nous avons vues jusqu'à présent, telles que iadd, dload ou lshr. Cependant, ces instructions ne peuvent être utilisées que sur des valeurs d'une certaine catégorie.

Il existe deux catégories permettant de distinguer les types nécessitant une entrée dans les variables locales ou la pile, de ceux en nécessitant deux.

Bien qu'une référence puisse être représentée sur 32 ou 64 bits en fonction de la JVM, elle sera toujours de catégorie 1, et par conséquent, prendra toujours une entrée dans les variables locales ou la pile.

Type Java

Type JVM

Catégorie

byte

int

1

short

int

1

char

int

1

int

int

1

float

float

1

référence

référence

1

adresse de retour *

adresse de retour *

1

long

long

2

double

double

2

* utilisée par l'instruction ret.

VII-B - Représentation de la pile

La JVM étant basée sur le modèle de la pile, il est essentiel de connaître quel est l'impact des instructions. Pour représenter l'état avant/après l'exécution d'une instruction, nous allons reprendre le format utilisé par la JVMS et qui est le suivant :

…, valeur1, valeur2 → …, résultat, où les valeurs les plus à droite sont au sommet de la pile. valeur1 et valeur2 étant les deux valeurs utilisées pour le calcul et résultat le résultat.

Il est important de noter que dans cette représentation, le long et le double sont considérés comme une seule valeur. Par conséquent, lorsque nécessaire nous présenterons les différents cas d'utilisation d'une instruction en utilisant plusieurs formes.

VII-C - Opérations sur la pile

Il est parfois utile de manipuler les données au sommet de la pile sans avoir à faire intervenir les variables locales. C'est ce que permettent les instructions suivantes :

Hex

Mnémonique

Description

0x57

pop

Dépile le premier élément.

0x58

pop2

Dépile les deux premiers éléments.

0x59

dup

Duplique le premier élément et l'empile.

0x5a

dup_x1

Duplique le premier élément et l'ajoute sous le deuxième.

0x5b

dup_x2

Duplique le premier élément et l'ajoute sous le troisième.

0x5c

dup2

Duplique les deux premiers éléments et les empile (en gardant l'ordre).

0x5d

dup2_x1

Duplique les deux premiers éléments et les ajoute sous le troisième (en gardant l'ordre)

0x5e

dup2_x2

Duplique les deux premiers éléments et les ajoute sous le quatrième élément (en gardant l'ordre).

0x5f

swap

Échange les deux premiers éléments.

Une chose importante à ne pas oublier est que les long et double prennent deux cases dans la pile et doivent être considérés comme deux éléments.

VII-C-1 - SWAP

L'instruction swap permet d'inverser les deux premiers éléments au sommet de la pile quel que soit leur type à condition qu'il soit de catégorie 1.

Note : elle ne peut pas être utilisée avec des long et des double.

État de la pile avant → après exécution : …, valeur1, valeur2 → …, valeur2, valeur1, où valeur1 et valeur2 sont de catégorie 1.

Code PJB :

1. .class org/isk/jvmhardcore/bytecode/partsix/Swap

2. .method swap()I

3. iconst_1

4. iconst_2

5. swap

6. ireturn

7. .methodend

8. .classend

Source

Test unitaire :

1. public void swap() {

2. final int result = Swap.swap();

4. Assert.assertEquals(1, result);

5. }

Source

VII-C-2 - POP

L'instruction pop dépile l'élément au sommet de la pile.

Note : elle ne peut pas être utilisée avec des long et des double.

État de la pile avant → après exécution : …, valeur1 → …, où valeur1 est de catégorie 1.

Code PJB :

1. .class org/isk/jvmhardcore/bytecode/partsix/Pop

2. .method pop()D

3. dconst_0

4. iconst_1

5. pop

6. dreturn

7. .methodend

8. .classend

Source

Test unitaire :

1. public void pop() {

2. final double result = Pop.pop();

4. Assert.assertEquals(0.0, result, 0.0001);

5. }

Source

VII-C-3 - POP2

L'instruction pop2 dépile les deux premiers éléments au sommet de la pile.

VII-C-3-a - POP2 - Forme 1

État de la pile avant → après exécution : …, valeur1, valeur2 → …, où valeur1 et valeur2 sont de catégorie 1.

Code PJB :

1. .class org/isk/jvmhardcore/bytecode/partsix/Pop2_Form1

2. .method pop2()I

3. iconst_0

4. iconst_1

5. iconst_1

6. pop2

7. ireturn

8. .methodend

9. .classend

Source

Test unitaire :

1. public void pop2_form1() {

2. final int result = Pop2_Form1.pop2();

4. Assert.assertEquals(0, result);

5. }

Source

VII-C-3-b - POP2 - Forme 2

État de la pile avant → après exécution : …, valeur1 → …, où valeur1 est de catégorie 2.

Code PJB :

1. .class org/isk/jvmhardcore/bytecode/partsix/Pop2_Form2

2. .method pop2()I

3. iconst_2

4. dconst_1

5. pop2

6. ireturn

7. .methodend

8. .classend

Source

Test unitaire :

1. Test

2. public void pop2_form2() {

3. final int result = Pop2_Form2.pop2();

5. Assert.assertEquals(2, result);

6. }

Source

VII-C-4 - DUP

L'instruction dup duplique le premier élément et l'empile.

Note : elle ne peut pas être utilisée avec des long et des double.

État de la pile avant → après exécution : …, valeur1 → …, valeur1, valeur1, où valeur1 est de catégorie 1.

Code PJB :

1. .class org/isk/jvmhardcore/bytecode/partsix/Dup

2. .method dup()I

3. iconst_2

4. iconst_1

5. dup

6. pop2

7. ireturn

8. .methodend

9. .classend

Source

Test unitaire :

1. public void dup() {

2. final int result = Dup.dup();

4. Assert.assertEquals(2, result);

5. }

Source

VII-C-5 - DUP_X1

L'instruction dup_x1 duplique le premier élément et l'ajoute sous le deuxième.

Note : elle ne peut pas être utilisée avec des long et des double.

État de la pile avant → après exécution : …, valeur1, valeur2 → …, valeur1, valeur2, valeur1, où valeur1 et valeur2 sont de catégorie 1.

Code PJB :

1. .class org/isk/jvmhardcore/bytecode/partsix/Dup_X1

2. .method dup_x1()I

3. iconst_2

4. iconst_1

5. dup_x1

6. pop2

7. ireturn

8. .methodend

9. .classend

Source

Test unitaire :

1. public void dup_x1() {

2. final int result = Dup_X1.dup_x1();

4. Assert.assertEquals(1, result);

5. }

Source

VII-C-6 - DUP_X2

L'instruction dup_x2 duplique le premier élément et l'ajoute sous le troisième.

Note : elle ne peut pas être utilisée avec des long et des double.

VII-C-6-a - DUP_X2 - Forme 1

État de la pile avant → après exécution : …, valeur1, valeur2, valeur3 → …, valeur3, valeur1, valeur2, valeur3, où valeur1, valeur2 et valeur3 sont de catégorie 1.

Code PJB :

1. .class org/isk/jvmhardcore/bytecode/partsix/Dup_X2_Form1

2. .method dup_x2()I

3. iconst_3

4. iconst_2

5. iconst_1

6. dup_x2

7. pop2

8. pop

9. ireturn

10. .methodend

11. .classend

Source

Test unitaire :

1. public void dup_x2_form1() {

2. final int result = Dup_X2_Form1.dup_x2();

4. Assert.assertEquals(1, result);

5. }

Source

VII-C-6-b - DUP_X2 - Forme 2

État de la pile avant → après exécution : …, valeur1, valeur2 → …, valeur2, valeur1, valeur2, où valeur1 est de catégorie 2 et valeur2 est de catégorie 1.

Code PJB :

1. .class org/isk/jvmhardcore/bytecode/partsix/Dup_X2_Form2

2. .method dup_x2()I

3. dconst_1

4. iconst_2

5. dup_x2

6. pop

7. pop2

8. ireturn

9. .methodend

10. .classend

Source

Test unitaire :

1. public void dup_x2_form2() {

2. final int result = Dup_X2_Form2.dup_x2();

4. Assert.assertEquals(2, result);

5. }

Source

VII-C-7 - DUP2

L'instruction dup2 duplique les deux premiers éléments et les empile (en gardant l'ordre).

VII-C-7-a - DUP2 - Forme 1

État de la pile avant → après exécution : …, valeur1, valeur2 → …, valeur1, valeur2, valeur1, valeur2, où valeur1, valeur2 et valeur3 sont de catégorie 1.

Code PJB :

1. .class org/isk/jvmhardcore/bytecode/partsix/Dup2_Form1

2. .method dup2()I

3. iconst_2  # [empty] -> 2

4. iconst_1  # 2 -> 2, 1

5. dup2      # 2, 1 -> 2, 1, 2, 1

6. @--------- Start packing

7. bipush 8  # 2, 1, 2, 1 -> 2, 1, 2, 1, 8

8. ishl      # 2, 1, 2, 1, 8 -> 2, 1, 2, 1 << 8

9. ior       # 2, 1, 2, 1 << 8 -> 2, 1, 2 | 1 << 8

10. bipush 8  # 2, 1, 2 | 1 << 8 -> 2, 1, 2 | 1 << 8, 8

11. ishl      # 2, 1, 2 | 1 << 8, 8 -> 2, 1, (2 | 1 << 8) << 8

12. ior       # 2, 1, (2 | 1 << 8) << 8 -> 2, 1 | (2 | 1 << 8) << 8

13. bipush 8  # etc.

14. ishl

15. ior

16. ireturn   # 0000 0001 0000 0010 0000 0001 0000 0010

17. .methodend

18. .classend

Source

Nous souhaitons connaître l'état de la pile - les valeurs présentes et leur ordre - après l'exécution des trois premières instructions (celles se trouvant avant le commentaire Start packing) pour vérifier le fonctionnement de l'instruction dup2. Or, avec les instructions que nous avons étudiées jusqu'à présent, la seule solution est d'empaqueter les quatre valeurs présentes dans la pile (2, 1, 2, 1). En prenant le type int, l'empaquetage consistera à découper la valeur retournée en quatre blocs de 8 bits (). Le bloc le plus à gauche contiendra la valeur au sommet de la pile, le suivant la valeur juste au-dessous, et ainsi de suite jusqu'au bas la pile, pour obtenir la valeur 0x1020102. Pour ce faire, nous utilisons les instructions d'opération bit à bit que nous avons vues dans la partie précédente.

Test unitaire :

1. public void dup2_form1() {

2. final int result = Dup2_Form1.dup2();

4. Assert.assertEquals(0x01020102, result);

5. }

Source

VII-C-7-b - DUP2 - Forme 2

État de la pile avant → après exécution : …, valeur1 → …, valeur1, valeur1, où valeur1 est de catégorie 2.

Code PJB :

1. .class org/isk/jvmhardcore/bytecode/partsix/Dup2_Form2

2. .method dup2()D

3. dconst_1  # [empty] -> 1.0

4. dup2      # 1.0 -> 1.0, 1.0

5. dadd      # 1.0, 1.0 -> 2.0

6. dreturn

7. .methodend

8. .classend

Source

Test unitaire :

1. public void dup2_form2() {

2. final double result = Dup2_Form2.dup2();

4. Assert.assertEquals(2.0, result, 0.0001);

5. }

Source

VII-C-8 - DUP2_X1

L'instruction dup2_x1 duplique les deux premiers éléments et les ajoute sous le troisième (en gardant l'ordre).

VII-C-8-a - DUP2_X1 - Forme 1

État de la pile avant → après exécution : …, valeur1, valeur2, valeur3 → …, valeur2, valeur3, valeur1, valeur2, valeur3, où valeur1, valeur2 et valeur3 sont de catégorie 1.

Code PJB :

1. .class org/isk/jvmhardcore/bytecode/partsix/Dup2_X1_Form1

2. .method dup2_x1()I

3. iconst_3  # [empty] -> 3

4. iconst_2  # 3 -> 3, 2

5. iconst_1  # 3, 2 -> 3, 2, 1

6. dup2_x1   # 3, 2, 1 -> 2, 1, 3, 2, 1

7. @--------- Start packing

8. bipush 4

9. ishl

10. ior

11. bipush 4

12. ishl

13. ior

14. bipush 4

15. ishl

16. ior

17. bipush 4

18. ishl

19. ior

20. ireturn  # 0001 0010 0011 0001 0010

21. .methodend

22. .classend

Source

Test unitaire :

1. public void dup2_x1_form1() {

2. final int result = Dup2_X1_Form1.dup2_x1();

4. Assert.assertEquals(0x12312, result);

5. }

Source

VII-C-8-b - DUP2_X1 - Forme 2

État de la pile avant → après exécution : …, valeur1, valeur2 → …, valeur2, valeur1, valeur2, où valeur1 est de catégorie 1 et valeur2 est de catégorie 2.

Code PJB :

1. .class org/isk/jvmhardcore/bytecode/partsix/Dup2_X1_Form2

2. .method dup2_x1()D

3. iconst_3  # [empty] -> 3

4. dconst_1  # 3 -> 3, 1.0

5. dup2_x1   # 3, 1.0 -> 1.0, 3, 1.0

6. pop2      # 1.0, 3, 1.0 -> 1.0, 3

7. pop       # 1.0, 3 -> 1.0

8. dreturn

9. .methodend

10. .classend

Source

Test unitaire :

1. public void dup2_x1_form2() {

2. final double result = Dup2_X1_Form2.dup2_x1();

4. Assert.assertEquals(1.0, result, 0.0001);

5. }

Source

VII-C-9 - DUP2_X2

L'instruction dup2_x2 duplique les deux premiers éléments et les ajoute sous le quatrième élément (en gardant l'ordre).

VII-C-9-a - DUP2_X2 - Forme 1

État de la pile avant → après exécution : …, valeur1, valeur2, valeur3, valeur4 → …, valeur3, valeur4, valeur1, valeur2, valeur3, valeur4, où toutes les valeurs sont de catégorie 1.

Code PJB :

1. .class org/isk/jvmhardcore/bytecode/partsix/Dup2_X2_Form1

2. .method dup2_x2()I

3. iconst_4  # [empty] -> 4

4. iconst_3  # 4 -> 4, 3

5. iconst_2  # 4, 3 -> 4, 3, 2

6. iconst_1  # 4, 3, 2 -> 4, 3, 2, 1

7. dup2_x2   # 3, 2, 1 -> 2, 1, 3, 2, 1

8. @--------- Start packing

9. bipush 4

10. ishl

11. ior

12. bipush 4

13. ishl

14. ior

15. bipush 4

16. ishl

17. ior

18. bipush 4

19. ishl

20. ior

21. bipush 4

22. ishl

23. ior

24. ireturn   # 0001 0010 0011 0100 0001 0010

25. .methodend

26. .classend

Source

Test unitaire :

1. public void dup2_x2_form1() {

2. final int result = Dup2_X2_Form1.dup2_x2();

4. Assert.assertEquals(0x123412, result);

5. }

Source

VII-C-9-b - DUP2_X2 - Forme 2

État de la pile avant → après exécution : …, valeur1, valeur2, valeur3 → …, valeur3, valeur1, valeur2, valeur3, où valeur1 et valeur2 sont de catégorie 1 et valeur3 est de catégorie 2.

Code PJB :

1. .class org/isk/jvmhardcore/bytecode/partsix/Dup2_X2_Form2

2. .method dup2_x2()D

3. iconst_2  # [empty] -> 2

4. iconst_0  # 2 -> 2, 0

5. dconst_1  # 2, 0 -> 2, 0, 1.0

6. dup2_x2   # 2, 0, 1.0 -> 1.0, 2, 0, 1.0

7. pop2      # 1.0, 2, 0, 1.0 -> 1.0, 2, 0

8. pop2      # 1.0, 2, 0 -> 1.0

9. dreturn

10. .methodend

11. .classend

Source

Test unitaire :

1. public void dup2_x2_form2() {

2. final double result = Dup2_X2_Form2.dup2_x2();

4. Assert.assertEquals(1.0, result, 0.0001);

5. }

Source

VII-C-9-c - DUP2_X2 - Forme 3

État de la pile avant → après exécution : …, valeur1, valeur2, valeur3 → …, valeur2, valeur3, valeur1, valeur2, valeur3, où valeur1 est de catégorie 2 et, valeur2 et valeur3 sont de catégorie 1.

Code PJB :

1. .class org/isk/jvmhardcore/bytecode/partsix/Dup2_X2_Form3

2. .method dup2_x2()I

3. dconst_1  # [empty] -> 1.0

4. iconst_1  # 1.0 -> 1.0, 1

5. iconst_2  # 1.0, 1 -> 1.0, 1, 2

6. dup2_x2   # 1.0, 1, 2 -> 1, 2, 1.0, 1, 2

7. pop2      # 1, 2, 1.0, 1, 2 -> 1, 2, 1.0

8. pop2      # 1, 2, 1.0 -> 1, 2

9. @--------- Start packing

10. bipush 4

11. ishl

12. ior

13. ireturn   # 0010 0001

14. .methodend

15. .classend

Source

Test unitaire :

1. public void dup2_x2_form3() {

2. final int result = Dup2_X2_Form3.dup2_x2();

4. Assert.assertEquals(0x21, result);

5. }

Source

VII-C-9-d - DUP2_X2 - Forme 4

État de la pile avant → après exécution : …, valeur1, valeur2 → …, valeur2, valeur1, valeur2, où valeur1 et valeur2 sont de catégorie 2.

Code PJB :

1. .class org/isk/jvmhardcore/bytecode/partsix/Dup2_X2_Form4

2. .method dup2_x2()D

3. dconst_0

4. dconst_1

5. dup2_x2

6. pop2

7. pop2

8. dreturn

9. .methodend

10. .classend

Source

Test unitaire :

1. public void dup2_x2_form4() {

2. final double result = Dup2_X2_Form4.dup2_x2();

4. Assert.assertEquals(1.0, result, 0.0001);

5. }

Source

VII-D - What's next ?

Au cours des trois parties précédentes et de celle-ci, nous avons vu 136 instructions. Néanmoins, l'objectif étant aussi de comprendre le contenu d'un fichier .class, nous allons mettre de côté les 69 restantes pendant quelques parties pour nous concentrer sur l'étude de différents éléments dont la connaissance est nécessaire à la construction d'un assembleur de bytecode.

La prochaine partie sera dédiée à la première partie de la création d'un analyseur syntaxique.

VIII - Mon premier analyseur syntaxique

Pour pouvoir transformer un fichier .pjb en bytecode, il est tout d'abord nécessaire de décomposer la source en objets manipulables en Java (ou tout autre langage). Dans cette partie et les deux suivantes, nous allons partir d'un exemple un peu plus simple permettant de décrire les concepts rudimentaires d'un analyseur syntaxique (parser) et d'un interpréteur. Il s'agira des premiers analyseur et interpréteur de cette série qui à la fin en comptera plusieurs.

L'objectif n'étant pas d'être exhaustif, nous verrons un seul type d'analyseur - un analyseur LL, qui analyse une chaîne de caractères de gauche à droite (Left to right) et construit un arbre syntaxique en commençant par l'élément racine (Leftmost derivation) - que nous allons créer manuellement.

Nous allons donc créer une pseudocalculatrice permettant de résoudre des opérations de ce type :

1.57 + 17) / 15) + 10 * -7 - -8

Le code est disponible sur Github (tag et branche)

VIII-A - Grammaire

Comme pour les langues naturelles, les langages informatiques et les opérations arithmétiques ont besoin d'une grammaire permettant de définir des règles syntaxiques. Ici le sens est sans importance, ce qui compte est de pouvoir extraire des mots (nommés symboles terminaux).

Pour définir une syntaxe, nous pouvons utiliser une spécification informelle en français (ou toute autre langue) ou une spécification formelle dans un format standardisé. La spécification informelle a un problème de taille, elle est libre d'interprétation, et généralement ce n'est pas ce que l'on souhaite. Il est par conséquent nécessaire d'avoir une spécification ne laissant aucune place à l'interprétation. Néanmoins, il est possible - et c'est généralement le cas - de décrire une spécification formelle à l'aide d'un langage naturel, comme c'est le cas de la JLS (Java Language Specification).

Nous allons opter pour une spécification formelle en utilisant un métalangage nommé EBNF (Extended Backus-Naur Form) qui est extrêmement simple à comprendre.

VIII-A-1 - Décomposer une addition

Partons de l'opération ci-dessous :

2+5

En utilisant le format EBNF nous pouvons la traduire de la manière suivante :

1. expression = digit operator digit

2. operator = '+'

3. digit = '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'

expression, operator et digit sont des symboles. expression est un symbole non terminal puisque contenant d'autres symboles. Étant le point d'entrée de la grammaire, il est le symbole de début. operator et digit sont des symboles terminaux puisque contenant des caractères entre apostrophes (') - du texte. Le caractère pipe (|) signifie ou.

Pour utiliser notre grammaire dans un analyseur, il est nécessaire d'attribuer un symbole pour chaque élément de texte et de ne pas les mixer avec d'autres symboles non terminaux (on parle de symboles atomiques) par exemple :

expression = digit '+' digit

En français on obtient : une expression est égale au chiffre un ou deux ou trois … ou huit ou neuf, plus, le chiffre un ou deux ou trois … ou huit ou neuf.

Pour éviter de passer trop de temps sur la théorie, nous allons tout de suite passer à la pratique.

En suivant le principe du TDD, nous souhaitons valider notre analyseur par le test suivant :

1. @Test

2. public void parse0() {

3. final String string = "2+5";

4. final InputStream inputStream = new ByteArrayInputStream(string.getBytes());

5. final MathParser parser = new MathParser(inputStream);

6. final String[] tokens = parser.parse();

8. Assert.assertArrayEquals(new String[] { "2", "+", "5" }, tokens);

9. }

Source

VIII-A-2 - Reader

Le premier composant d'un analyseur syntaxique est un lecteur (reader). Le but d'un lecteur est de lire une chaîne de caractères (dans un fichier, une String, etc.) caractère par caractère, par exemple 2+5.

Nous souhaitons aussi avoir de la flexibilité en pouvant relire le caractère précédent - unread() - ou le dixième précédent - unread(int chars) -. Mais aussi pouvoir marquer une position - mark() - pour y revenir ultérieurement sans avoir à compter les caractères lus - reset(). Et pour finir, un bon analyseur est un analyseur ayant des messages d'erreur clairs indiquant la ligne - getLine() - et la colonne - getColumn() - à laquelle l'erreur se trouve.

1. public interface Reader {

2. int read();

3. int unread();

4. void unread(int chars);

5. void mark();

6. void reset();

7. int getLine();

8. int getColumn();

9. }

Source

La première chose marquante est que les méthodes read() et unread() retournent des entiers et non des caractères. En Java, le type char est en réalité un entier non signé de 16 bits représentant le point de code d'un caractère dans une table de codage. Or comme nous l'avons vu, la JVM manipule par défaut des int. Utiliser des types de taille inférieure, sans une bonne raison (par exemple la lecture d'un fichier sous forme de bytes ou comme nous le verrons la création d'un fichier .class) n'est d'aucune utilité. De plus, pour manipuler des tables de codage telles que l'Unicode, il est nécessaire d'utiliser des types ayant une taille de 32 bits.

Nous ne nous attarderons pas sur l'implémentation de la classe InputStreamReader, ni les tests unitaires associés (InputStreamReaderTest). La seule particularité vient du fait que chaque élément (de type int) de l'InputStream - passé en paramètre du constructeur de la classe InputStreamReader - est ajouté à un tableau de int lors de l'initialisation de la classe à l'aide de la méthode init(). De plus, pour éviter d'avoir à traiter plusieurs types de retour à la ligne, le caractère CR (0x0d) et le groupe CRLF (0x0d et 0x0a) sont remplacés par le caractère unique LF (0x0a).

Mais ce n'est qu'une possibilité. L'architecture de l'analyseur a été conçue de manière à ce que l'on puisse changer les différentes classes d'implémentation très simplement pour essayer d'autres solutions.

Notons que l'interface Reader n'a rien à voir avec la classe abstraite java.io.Reader. Tout comme la classe InputStreamReader et java.io.InputStreamReader.

VIII-A-3 - Tokenizer

Un Tokenizer s'appuie sur un Reader pour extraire les symboles terminaux (comme digit et operator).

La classe abstraite TokenizerReadernull fait le lien avec un Reader et un nom de fichier pouvant être null. Dans le cas où plusieurs fichiers sont analysés et qu'une erreur est constatée, nous souhaitons savoir duquel elle provient :

1. final private String filename;

2. final private Reader reader;

4. public Tokenizer(final String filename, final Reader reader) {

5. this.reader = reader;

6. this.filename = filename;

7. }

Elle possède des méthodes évitant à l'implémentation de faire appel directement au Reader :

1. protected int next() {

2. return this.reader.read();

3. }

5. protected int rewind() {

6. return this.reader.unread();

7. }

9. protected void mark() {

10. this.reader.mark();

11. }

13. protected void reset() {

14. this.reader.reset();

15. }

17. protected int peek() {

18. int character = this.next();

19. this.rewind();

20. return character;

21. }

Et permet d'identifier la fin d'un flux (nommé par convention fin de fichier) :

1. public void checkEndOfFile() {

2. int character = this.next();

4. if (character != Ascii.EOF) {

5. throw new ParserException("Expected: End of file.");

6. }

7. }

La classe Tokenizer possède aussi des méthodes standards :

- consumeUnprintables() : consomme les caractères entre NULL (0x00) et SPACE (0x20) ;

- isDigit(int character) : le caractère en paramètre est-il un chiffre ?

- isAsciiLetter(int character) : le caractère en paramètre est-il une lettre ASCII ([0x41 ; 0x5a] U [0x61 ; 0x7a]) ?

Et pour finir une classe interne nommée ParserException qui standardise les messages d'erreur.

Il nous suffit donc d'hériter de la classe Tokenizer pour avoir toutes les méthodes utilitaires, ainsi que la classe d'exception.

La classe MathTokenizer sera utilisée pour extraire les symboles terminaux d'expressions de type 2+5.

1. public class MathTokenizer extends Tokenizer {

3. public MathTokenizer(String filename, Reader reader) {

4. super(filename, reader);

5. }

7. public int getDigit() {

8. int character = this.next();

10. if (isDigit(character)) {

11. return character;

12. } else {

13. throw new ParserException("Expected: Digit [0-9].");

14. }

15. }

17. public int getOperator() {

18. int character = this.next();

20. if (character == Ascii.PLUS_SIGN) {

21. return character;

22. } else {

23. throw new ParserException("Expected: '+'");

24. }

25. }

26. }

Source

Les méthodes getDigit() et getOperator() seront appelées lorsque l'on s'attendra à lire un chiffre ou un opérateur dans la chaîne de caractères analysée. Si le symbole attendu n'est pas obtenu, une exception (de type ParserException) sera levée indiquant une erreur dans la syntaxe de l'expression.

L'interface ASCII contient tous les caractères ASCII - ayant du sens aujourd'hui - sous la forme de constantes (les noms utilisés sont les noms plus ou moins officiels).

VIII-A-4 - Esquisse du fonctionnement de l'analyseur

En partant du test vu précédemment, nous pouvons résumer le fonctionnement de notre analyseur syntaxique de la manière suivante : à partir d'une chaîne de caractères représentant une expression (2+5 pour garder notre exemple), notre analyseur produit un tableau d'objets de type String (contenant les différents tokens extraits de la chaîne de caractères lors de l'analyse - {« 2 », « + », « 5 »}), en s'appuyant sur un tokenizer possédant des méthodes permettant d'extraire les symboles terminaux, lui-même s'appuyant sur un lecteur permettant de lire une chaîne de caractères, caractère par caractère.

Un élément important à noter est que l'analyseur syntaxique génère un événement à chaque fois qu'il rencontre un symbole terminal. Cet événement sera ensuite utilisé par une méthode parse() pouvant être décrite de la manière suivante :

1. Tant que l'expression n'est pas complètement lue (boucle)

2. 1. récupérer l'événement suivant

3. 2. pour l'événement X, appeler la méthode getX() du tokenizer (qui retourne un token)

4. 3. ajouter le token au tableau de tokens

5. Retourner le tableau de tokens

VIII-A-4-a - Eventtype

À chaque symbole terminal de notre grammaire correspond un événement :

1. public enum EventType {

2. DIGIT,

3. OPERATOR;

4. }

VIII-A-4-b - Symbols

À chaque symbole (terminal et non terminal) de notre grammaire correspond une constante numérique du même nom :

1. public class Symbols {

2. final public static int EXPRESSION = 0;

3. final public static int DIGIT = 1;

4. final public static int OPERATOR = 2;

5. }

VIII-A-4-c - Production

À chaque symbole de notre grammaire correspond ce que l'on appelle une production. Une production est modélisée par un objet Java (que nous verrons plus loin) contenant une seule méthode nommée produce() et retournant un événement de type EventType.

Si une production correspond à un symbole terminal, la méthode produce() retourne l'événement correspondant. Et si une production correspond à un symbole non terminal, elle retourne null.

- La production Digit retourne EventType.DIGIT.

- La production Operator retourne EventType.OPERATOR.

- La production Expression retourne null.

VIII-A-4-d - Table de productions

L'ensemble des symboles de la grammaire est contenu dans un tableau, appelé table de productions. Les trois symboles que nous avons définis précédemment constituent les trois index du tableau. Et à ces index sont associées les productions correspondantes.

1. protected void initProductionTable() {

2. this.table[EXPRESSION] = new Productions.Expression();

3. this.table[DIGIT] = new Productions.Digit();

4. this.table[OPERATOR] = new Productions.Operator();

5. }

La table de productions est propre au tokenizer et ne varie pas au cours de l'exécution.

Les classes Expression, Digit et Operator implémentent l'interface Production :

1. public interface Production<E, T extends Tokenizer> {

2. E produce(T tokenizer,

3. Production<E, T>[] table,

4. Stack<Production<E, T>> productionStack);

5. }

Source

E est un type d'événement et T un tokenizer. En ce qui concerne les paramètres de la méthode produce() :

- tokenizer permet de vérifier les caractères suivants sans les consommer (nous verrons ceci plus en détail dans la partie suivante, puisque nous ne l'utiliserons pas dans celui-ci) ;

- table est la table de productions. Ce paramètre est utile pour les productions empilant des productions ;

- productionStack est la pile sur laquelle seront empilées les productions.

VIII-A-4-e - Pile de productions

À présent, voyons comment, à l'aide de tous les éléments que nous venons de voir, nous pouvons récupérer un événement.

Le cœur de notre analyseur est basé sur une pile. Cette pile contient les productions attendues, ou en d'autres termes les symboles attendus. En reprenant notre exemple, le symbole de début expression correspond à ce que l'on souhaite analyser. Ce symbole est constitué de trois symboles correspondant aux symboles attendus. Nous savons que lorsque nous analysons une expression, nous souhaitons rencontrer un chiffre, puis un opérateur et un autre chiffre.

La pile contenant les productions est nommée simplement pile de productions.

À l'initialisation de l'analyseur, la pile de productions contient uniquement la production représentant le symbole de début : Expression, puisque notre analyseur cherche à analyser une expression. C'est à partir de cette production que notre analyse débute.

L'invocation de la méthode produce() d'une production représentant un symbole non terminal (tel que expression) provoque l'empilement - dans la pile de productions - des productions le définissant (c'est-à-dire pour le symbole expression : Digit, Operator et Digit) et retourne null.

Lors de l'analyse de notre expression d'exemple 2+5 les changements d'état de la pile de productions peuvent être décrits de la manière suivante :

1. L'élément au sommet de la pile de productions (Expression) est dépilé. La méthode produce() de la production est appelée :

1. la production Expression représentant un symbole non terminal, les productions Digit, Operator et Digit sont empilées sur la pile de productions. À présent la pile de productions contient les productions suivantes Digit, Operator et Digit,

2. La méthode produce() retourne null ;

2. L'élément au sommet de la pile de productions (Digit) est dépilé. La méthode produce() de la production est appelée et retourne l'événement EventType.DIGIT;

3. L'élément au sommet de la pile de productions (Operator) est dépilé. La méthode produce() de la production est appelée et retourne l'événement EventType.OPERATOR ;

4. L'élément au sommet de la pile de productions (Digit) est dépilé. La méthode produce() de la production est appelée et retourne l'événement EventType.DIGIT;

5. La pile est vide, nous n'attendons plus aucun caractère, l'analyse syntaxique est dont terminée.

Empiler des productions implique qu'au moment de l'exécution de la méthode produce() aucun token n'est à récupérer par la méthode parse() et donc nous retournons null, ce qui signifie qu'aucun caractère ne sera lu.

VIII-A-4-f - Next Event

Finalement, notre analyseur syntaxique dépend principalement d'une méthode dépilant des productions et les exécutant.

Nous pouvons décrire la méthode getNextEvent() de la manière suivante :

1. Tant que la pile n'est pas vide (boucle)

2. 1. dépiler une production

3. 2. appeler la méthode produce()

4. Si l'événement n'est pas nul

5. On le retourne à la méthode parse(), qui déclenche

6. la lecture de caractères dans la chaîne en cours d'analyse

7. Sinon d'autres productions ont été empilées

8. On poursuit la boucle

9. Lorsque la pile est vide, cela signifie qu'il n'y a plus rien à lire.

10. Nous retournons par conséquent null à la méthode parse()

La méthode produce() effectue l'une des deux actions décrites précédemment :

- retourner un événement ou

- empiler des productions dans la pile.

Voyons à présent l'implémentation de la méthode getNextEvent() :

1. protected E getNextEvent() {

2. while (!this.productionStack.isEmpty()) {

3. // Récupère la production au sommet de la pile

4. final Production production = this.productionStack.pop();

6. // Appelle la méthode produce() de la production récupérée

7. final E event = production.produce(this.tokenizer,

8. this.table,

9. this.productionStack);

11. // Si la production retourne non null

12. // (production représentant un symbole terminal)

13. // on retourne l'événement

14. if (event != null) {

15. return event;

16. }

17. }

19. return null;

20. }

Source

Pour conclure cette présentation de notre analyseur, notons que seulement deux éléments sont variables au cours de son exécution :

- la pile de productions et

- le tableau de tokens retourné par la méthode parse().

VIII-B - Parser

Ce qui nous intéresse dans cette partie est le mécanisme de décomposition analytique. Le principe d'un analyseur LL, nommé aussi analyseur descendant, est de lire chaque caractère de gauche à droite en revenant parfois en arrière sur des caractères déjà analysés, et de savoir plus ou moins à l'avance les symboles qu'il doit rencontrer. En d'autres termes, pour notre grammaire, nous savons que nous devons appeler dans l'ordre les méthodes getDigit(), getOperator() et une deuxième fois getDigit().

Néanmoins, pour que notre analyseur soit évolutif et facilement testable, nous utilisons une table de productions (aussi nommée table d'analyse).

Comme mentionné précédemment, chaque entrée de la table de productions est un symbole de la grammaire, auquel nous faisons aussi référence par le terme de production.

À la table de productions est associée une pile de productions à venir (champ d'instance nommé productionStack) dont les éléments sont dépilés dans la méthode nommée getNextEvent() et empilés dans les méthodes produce() des productions représentant des symboles non terminaux :

1. // A est l'objet racine que crée l'analyseur

2. // E est un type d'événement

3. // T est un tokenizer

4. public abstract class Parser<A, E, T extends Tokenizer> {

5. final public T tokenizer;

6. final public Production<E, T>[] table;

7. final public Stack<Production<E, T>> productionStack;

9. public Parser(final InputStream inputStream, final int productionSize) {

10. this(null, inputStream, productionSize);

11. }

13. public Parser(final String filename,          // Nom du fichier analysé

14. final InputStream inputStream,  // Flux analysé

15. final int productionSize) {     // Nombre de symboles

16. // dans la table de productions

17. this.tokenizer = this.newTokenizer(filename, inputStream);

18. this.table = new Production[productionSize];

19. this.productionStack = new Stack<>();

21. this.initProductionTable();

22. // this.table[0] correspond au symbole de début "expression"

23. this.productionStack.push(this.table[0]);

24. }

26. // ...

28. protected abstract void initProductionTable();

29. }

Source

Voyons à présent les implémentations :

public class Productions {
// expression = digit operator digit
public static class Expression implements Production<EventType, MathTokenizer> {
public EventType produce(MathTokenizer tokenizer,
Production<EventType, MathTokenizer>[] table,
Stack<Production<EventType, MathTokenizer>>
productionStack) {
productionStack.push(table[Symbols.DIGIT]);
productionStack.push(table[Symbols.OPERATOR]);
productionStack.push(table[Symbols.DIGIT]);

return null;
}
}

// digit = '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'
public static class Digit implements Production<EventType, MathTokenizer> {
public EventType produce(MathTokenizer tokenizer,
Production<EventType, MathTokenizer>[] table,
Stack<Production<EventType, MathTokenizer>>
productionStack) {
return EventType.DIGIT;
}
}

// operator = '+'
public static class Operator implements Production<EventType, MathTokenizer> {
public EventType produce(MathTokenizer tokenizer,
Production<EventType, MathTokenizer>[] table,
Stack<Production<EventType, MathTokenizer>>
productionStack) {
return EventType.OPERATOR;
}
}
}

Source

Dans le cas présent, nous avons une production par symbole. La production représentant le symbole non terminal expression ajoute bien les autres productions - comme défini dans la grammaire - dans la pile et les productions représentant les symboles terminaux digit et operator retourne l'événement associé.

Pour finir, nous devons voir comment est appelée la méthode getNextEvent(), qui comme nous l'avons déjà vu, appelle la méthode produce(), le cœur de notre analyseur :

1. public class MathParser extends Parser<String[], EventType, MathTokenizer> {

2. final private LinkedList<Object> postfixExpression;

3. final private Stack operatorStack;

5. public MathParser(final InputStream inputStream) {

6. super(inputStream, Symbols.number());

8. this.postfixExpression = new LinkedList<>();

9. this.operatorStack = new Stack<>();

10. }

12. public String[] parse() {

13. EventType eventType = null;

15. boolean done = false;

16. while (!done) { // Nous verrons plus loin comment done devient true

17. eventType = this.getNextEvent();

19. switch (eventType) {

20. case DIGIT:

21. this.tokens[counter++] =

22. String.valueOf(Character.toChars(this.tokenizer.getDigit()));

23. break;

24. case OPERATOR:

25. this.tokens[counter++] =

26. String.valueOf(Character.toChars(this.tokenizer.getOperator()));

27. break;

28. default:

29. System.err.println("Unexpected event.");

30. break;

31. }

32. }

34. return this.tokens;

35. }

37. protected void initProductionTable() {

38. this.table[EXPRESSION] = new Productions.Expression();

39. this.table[DIGIT] = new Productions.Digit();

40. this.table[OPERATOR] = new Productions.Operator();

41. }

43. // ...

44. }

En reprenant le test unitaire défini au début de cette partie :

1. @Test

2. public void parse() {

3. final String string = "2+5";

4. final InputStream inputStream = new ByteArrayInputStream(string.getBytes());

5. final MathParser parser = new MathParser(inputStream);

6. final String[] tokens = parser.parse();

8. Assert.assertArrayEquals(new String[] { "2", "+", "5" }, tokens);

9. }

La méthode parse() est la méthode faisant/délégant l'action de décomposition analytique. Comme défini dans notre test, elle retourne bien un tableau de String. La méthode parse() récupère des événements en appelant la méthode getNextEvent(), effectue une validation syntaxique en appelant les méthodes getDigit() et getOperator() du tokenizer qui lèvent une exception si la syntaxe est incorrecte et retourne un tableau contenant des tokens sous la forme de chaînes de caractères.

VIII-C - End of file

Nos avons donc presque fini. Il ne reste qu'une interrogation! Quand se termine la boucle de la méthode parse() ?

while(!done) {
// ...
}

Il nous faut une solution pour que la variable done passe un jour à true. Or avec notre table de production actuelle, nous allons appeler indéfiniment la méthode getNextEvent() qui après un certain temps (à partir du quatrième appel) retournera toujours null.

La solution la plus simple est de rajouter un niveau à notre grammaire :

1. stream = expression eof

2. // ...

3. eof = ? fin du flux ?

EBNF : les points d'interrogation permettent de définir dans une langue naturelle un symbole terminal dont l'implémentation n'a pas d'importance, ou dont une simple phrase résume le besoin, exemple : ? tous les caractères UTF-8 ?.

1. public class Productions {

2. // stream = expression eof

3. public static class Stream implements Production<EventType, MathTokenizer> {

4. public EventType produce(MathTokenizer tokenizer,

5. Production<EventType, MathTokenizer>[] table,

6. Stack<Production<EventType, MathTokenizer>>

7. productionStack) {

8. productionStack.push(table[Symbols.EOF]);

9. productionStack.push(table[Symbols.EXPRESSION]);

11. return null;

12. }

13. }

15. // ...

17. // eof = ? fin du flux ?

18. public static class EndOfFile implements Production<EventType, MathTokenizer> {

19. public EventType produce(MathTokenizer tokenizer,

20. Production<EventType, MathTokenizer>[] table,

21. Stack<Production<EventType, MathTokenizer>>

22. productionStack) {

23. return EventType.EOF;

24. }

25. }

26. }

Source

1. public enum EventType {

2. EOF,

3. DIGIT,

4. OPERATOR;

5. }

Source

1. public class Symbols {

2. final public static int STREAM = 0;

3. final public static int EOF = 1;

4. final public static int EXPRESSION = 2;

5. final public static int DIGIT = 3;

6. final public static int OPERATOR = 4;

7. }

Source

Note : le lien ci-dessus pointe vers une classe Symbols légèrement différente. Pour éviter d'avoir à changer la valeur des constantes de classe (EXPRESSION, DIGIT, etc.) à chaque modification de notre grammaire, elles sont initialisées au chargement de la classe. Une fois que l'écriture de l'analyseur sera terminée, nous pourrons les fixer.

1. public class MathParser extends Parser<String[], EventType, MathTokenizer> {

3. // ...

5. protected void initProductionTable() {

6. this.table[STREAM] = new Productions.Stream();

7. this.table[EOF] = new Productions.EndOfFile();

8. this.table[EXPRESSION] = new Productions.Expression();

9. this.table[DIGIT] = new Productions.Digit();

10. this.table[OPERATOR] = new Productions.Operator();

11. }

12. }

Source

Vous constaterez que rajouter un élément à notre grammaire n'impacte que très légèrement notre code. De plus, étant donné que l'on utilise une pile, dans les méthodes produce() les productions sont insérées dans l'ordre inverse de leur définition dans la grammaire :

stream = expression eof

donne :

1. productionStack.push(table[EOF]);

2. productionStack.push(table[EXPRESSION]);

Nous pouvons donc terminer l'implémentation de la méthode parse() :

1. @Override

2. public String[] parse() {

3. EventType eventType = null;

5. boolean done = false;

6. while (!done) {

7. eventType = this.getNextEvent();

9. switch (eventType) {

10. case DIGIT:

11. this.tokens[counter++] =

12. String.valueOf(Character.toChars(this.tokenizer.getDigit()));

13. break;

14. case OPERATOR:

15. this.tokens[counter++] =

16. String.valueOf(Character.toChars(this.tokenizer.getOperator()));

17. break;

18. case EOF:

19. this.tokenizer.checkEndOfFile();

20. done = true;

21. break;

22. default:

23. System.err.println("Unexpected event.");

24. break;

25. }

26. }

28. return this.tokens;

29. }

Source

Pour exécuter le test unitaire (à la racine du projet mathparser) :

1. $ ant

2. $ ant test -DtestClass=org.isk.jvmhardcore.mathparser.MathParserTest -DtestMethod=parse0

VIII-D - What's next ?

Dans cette partie nous avons vu le cœur d'un analyseur syntaxique. Nous allons pouvoir dès la semaine prochaine enrichir notre grammaire en explorant le reste de la syntaxe EBNF. Et pour finir, au lieu de retourner un tableau de chaînes de caractères, la méthode parse() retournera un type d'objet plus adapté à la résolution de notre expression arithmétique.

IX - Mon premier analyseur syntaxique (suite)

IX-A - Évolution de la grammaire

Pour rappel, dans la partie précédente nous nous étions arrêtés à la grammaire suivante (nous laisserons de côté les symboles stream et eof, bien qu'ils soient présents dans le code) :

1. expression = digit operator digit

2. operator = '+'

3. digit = '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'

Au cours de cette partie, nous allons faire évoluer cette grammaire. Par conséquent, il arrivera parfois que certains symboles soient modifiés et d'autres ajoutés. Pour identifier simplement ces différents cas, la définition d'un symbole modifié sera suivie de (* Nouveau *) et celle d'un nouveau symbole de (* Modifié *).

EBNF : le texte entre les caractères (* et *) est un commentaire.

IX-B - Multiples opérateurs

Nous pouvons très simplement ajouter d'autres opérateurs :

1. expression = digit operator digit

2. operator = '+' | '-' | '/' | '*' (* Modifié *)

3. digit = '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'

La modification du code n'a rien de très compliqué.

1. public int getOperator() {

2. int character = this.next();

4. if ( character == Ascii.PLUS_SIGN

5. || character == Ascii.HYPHEN

6. || character == Ascii.ASTERIX

7. || character == Ascii.SLASH

8. ) {

9. return character;

10. } else {

11. throw new ParserException("Expected: '+' or '-' or '*' or '/'.");

12. }

13. }

Source

IX-C - Nombres

Nous permettons ensuite l'utilisation de nombres (positifs pour l'instant) :

1. expression = number operator number

2. number = digit {digit} (* Nouveau *)

3. operator = '+' | '-' | '/' | '*'

4. digit = '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'

EBNF : les caractères { et } indiquent une répétition optionnelle et illimitée. Le nombre peut donc être composé d'un seul chiffre ou de plusieurs.

Lors de la création d'une grammaire, le plus simple est de partir du symbole à modifier (expression dans note cas) et de faire les modifications sans penser à une quelconque factorisation, par exemple :

expression = digit {digit} operator digit {digit}

Un nombre (number) est donc un chiffre (digit) suivi de zéro ou de plusieurs chiffres.

Nous allons autoriser les nombres commençant par plusieurs 0, mais aussi composés uniquement de zéros.

Cette situation est l'exemple typique pour lequel un symbole ne correspond pas à une production. Il est inutile de déclencher un événement par chiffre. Ce qui nous intéresse est d'avoir le nombre complet.

Pour rester cohérents, nous allons renommer la production Digit (de la branche précédente) en Number, le symbole et l'événement DIGIT en NUMBER et pour finir la méthode getDigit() en getNumber().

Il ne nous reste plus qu'à modifier la méthode getNumber() pour répondre à notre nouvelle grammaire :

1. public String getNumber() {

2. int character = Ascii.NULL;

4. while(isDigit(character = this.next())) {

5. generator.appendChar(character);

6. }

8. if (!generator.isEmpty()) {

9. this.rewind();

10. return generator.toString();

11. } else {

12. throw new ParserException("Expected: At least one Digit [0-9].");

13. }

14. }

Trois points importants sont à noter :

- la méthode retourne à présent une chaîne de caractères et non plus un entier (qui correspondait au point de code du chiffre, et non au chiffre lui-même). Les tests unitaires et le code correspondant à l'événement NUMBER ont donc été modifiés en conséquence ;

- nous ajoutons les caractères à un champ generator qui est un StringBuilder ayant des méthodes adaptées à un Tokenizer (cf. StringGenerator) ;

- avant de retourner le nombre analysé, nous faisons appel à la méthode rewind() qui va reculer d'un caractère le Reader (le dernier caractère lu qui n'est pas un chiffre).

IX-D - Nombres à virgule

Pour pouvoir utiliser des nombres à virgule, nous avons plusieurs solutions. La première consiste à différer la connaissance du type du nombre (entier ou nombre à virgule) au moment de la résolution de l'expression :

1. number = repeatingDigit [dot] repeatingDigit

2. repeatingDigit = {digit}

3. dot = '.'

La seconde (celle que nous allons mettre en place) permet de déterminer le type du nombre lors de l'analyse syntaxique.

1. expression = number operator number

2. number = integer | float (* Modifié *)

3. integer = repeatingDigit (* Nouveau *)

4. float = oRepeatingDigit [dot] oRepeatingDigit (* Nouveau *)

5. repeatingDigit = digit repeatingDigit (* Modifié *)

6. oRepeatingDigit = {digit}  (* Nouveau *)

7. operator = '+' | '-' | '/' | '*'

8. digit = '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'

9. dot = '.' (* Nouveau *)

EBNF : les caractères [ et ] indiquent un élément optionnel.

Le o du symbole oRepeatingDigit signifie optionnel.

Les nombres à virgule que nous acceptons peuvent avoir les formes suivantes : 1.1, .567 ou 23. Mais aussi uniquement un point « . » ce qui n'est absolument pas ce que nous souhaitons. Des commentaires ou une spécification informelle sont alors indispensables pour apporter des précisions.

1. (* au moins un chiffre doit être présent à droite ou à gauche du point

2. (ex: 1.1, .567 ou 23.) *)

3. float = oRepeatingDigit [dot] oRepeatingDigit

Nous avons aussi la possibilité de complexifier la grammaire :

1. float = (repeatingDigit [dot] repeatingDigit)

2. | (repeatingDigit [dot])

3. | ([dot] repeatingDigit)

EBNF : Les caractères ( et ) indiquent un groupe. Le symbole number est composé du symbole sign suivi du symbole integer ou float.

Il reviendra à chacun de faire les choix lui semblant les plus appropriés, sachant que dans certains cas, une grammaire trop complexe est beaucoup plus difficile à implémenter qu'une grammaire simple associée à une spécification informelle indiquant les diverses contraintes.

Malgré un impact important dans la grammaire, l'impact sur le code est limité.

Nous n'allons pas rajouter de production, mais uniquement modifier la production Number, ce qui signifie que nous n'ajouterons pas de symboles :

1. public static class Number implements Production<EventType, MathTokenizer> {

2. public EventType produce(MathTokenizer tokenizer,

3. Production<EventType, MathTokenizer>[] table,

4. Stack<Production<EventType, MathTokenizer>> productionStack) {

5. if (tokenizer.isFloat()) {

6. return EventType.FLOAT;

7. } else {

8. return EventType.INTEGER;

9. }

10. }

11. }

Le tokenizer passé en paramètre de la méthode produce(), dont nous n'avions pas l'utilité jusqu'à présent, prend tout son sens dans cette situation. Nous souhaitons déterminer le prochain symbole à analyser par la méthode parse().

La règle est donc simple, une méthode de l'objet tokenizer peut être appelée dans une méthode produce() si elle ne consomme pas de caractères utiles à l'analyse. Nous obtenons donc deux cas :

- la méthode effectue un test, elle appelle la méthode mark() du reader au début et la méthode reset() à la fin ;

- la méthode consomme des caractères inutiles à l'analyse (espaces ou commentaires). Nous verrons ce cas un peu plus loin.

Voyons l'implémentation de la méthode isFloat() :

1. public boolean isFloat() {

2. this.mark();

4. int character = Ascii.NULL;

6. // Nombre de chiffres

7. int counter = 0;

9. // Compte le nombre de chiffres

10. while (isDigit(character = this.next())) {

11. counter++;

12. }

14. // Vérifie si le caractère suivant est un point

15. if (Ascii.PERIOD != character) {

16. this.reset();

17. return false;

18. }

20. // S'il y a des chiffres avant le point, nous n'avons pas besoin de continuer,

21. // il s'agit d'un nombre à virgule

22. if (counter > 0) {

23. this.reset();

24. return true;

25. }

27. // Compte le nombre de chiffres après le point

28. while (isDigit(character = this.next())) {

29. counter++;

30. }

32. // S'il y a des chiffres après le point c'est un nombre à virgule

33. if (counter > 0) {

34. this.reset();

35. return true;

36. }

38. // Il n'y a pas de chiffre avant et après le point

39. this.reset();

40. return false;

41. }

Pour l'instant, que l'événement soit un FLOAT ou un INTEGER n'a pas d'importance puisque nous mettons tout dans un tableau de chaînes de caractères :

1. public String[] parse() {

2. // ...

4. switch (eventType) {

5. case FLOAT:

6. this.tokens[counter++] = this.tokenizer.getFloat();

7. break;

8. case INTEGER:

9. this.tokens[counter++] = this.tokenizer.getInteger();

10. break;

12. // ...

13. }

15. // ...

16. }

Source

La méthode getInteger() est tout simplement la méthode getNumber() de la branche précédente renommée.

Quant à la méthode getFloat(), son implémentation est la suivante :

1. public String getFloat() {

2. int character = Ascii.NULL;

4. while (isDigit(character = this.next())) {

5. generator.appendChar(character);

6. }

8. // getFloat() est appelée après isFloat()

9. // par conséquent nous n'avons pas besoin de vérifier

10. // si le caractère est un point

11. generator.appendChar(character);

13. while (isDigit(character = this.next())) {

14. generator.appendChar(character);

15. }

17. this.rewind();

18. return generator.toString();

19. }

IX-E - Nombres signés

Continuons l'enrichissement de notre grammaire en ajoutant la possibilité d'avoir des nombres signés.

1. expression = number operator number

2. number = sign (integer | float) (* Modifié *)

3. integer = repeatingDigit

4. float = oRepeatingDigit [dot] oRepeatingDigit

5. repeatingDigit = digit repeatingDigit

6. oRepeatingDigit = {digit}

7. sign = '+' | '-' | ''  (* Nouveau *)

8. operator = '+' | '-' | '/' | '*'

9. digit = '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'

10. dot = '.'

Le symbole sign peut être un caractère vide, ce qui évite de le définir en tant que symbole optionnel :

1. number = [sign] (integer | float)

2. sign = '+' | '-'

La modification du code est très simple. Seule la classe MathTokenizer est impactée. Nous devons rajouter quelques lignes aux méthodes suivantes :

isFloat() :

1. int character = this.next();

3. // Ignore le signe

4. if (character != Ascii.PLUS_SIGN && character != Ascii.HYPHEN) {

5. this.rewind();

6. }

getInteger() et getFloat() :

1. int character = this.next();

3. if (character == Ascii.PLUS_SIGN) {

4. // Ignore

5. } else if (character == Ascii.HYPHEN) {

6. generator.appendChar(character);

7. } else {

8. this.rewind();

9. }

IX-F - Espaces

Jusqu'à présent, nous avons imposé la saisie de caractères ayant un sens dans une expression arithmétique. Or, pour plus de clarté et pour que nous puissions saisir l'expression sur plusieurs lignes, nous devons autoriser la saisie de caractères d'espacement, que ce soit le caractère espace (0x20) ou les retours à la ligne (0x0A, 0x0D, etc.)

1. expression = ws number ws operator ws number ws (* Modifié *)

2. number = sign (integer | float)

3. integer = repeatingDigit

4. float = oRepeatingDigit [dot] oRepeatingDigit

5. repeatingDigit = digit repeatingDigit

6. oRepeatingDigit = {digit}

7. sign = '+' | '-' | ''

8. operator = '+' | '-' | '/' | '*'

9. digit = '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'

10. dot = '.'

11. ws = ? caractères d'espacement ? (* Nouveau *)

Pour permettre la saisie de caractères d'espacement, la grammaire n'a été que légèrement modifiée. Il a suffi de rajouter un nouveau symbole terminal (ws) et de le placer entre chaque opérande de l'expression.

L'impact dans le code est lui aussi minime. Nous commençons par ajouter une production pour le nouveau symbole (Whitespaces).

1. public static class Whitespaces implements Production<EventType, MathTokenizer> {

2. public EventType produce(MathTokenizer tokenizer,

3. Production<EventType, MathTokenizer>[] table,

4. Stack<Production<EventType, MathTokenizer>> productionStack) {

5. tokenizer.consumeUnprintables();

6. return null;

7. }

8. }

Le seul objectif de la production Whitespaces est de consommer des caractères d'espacement. Elle n'ajoute rien à la pile de productions et ne retourne aucun événement. Il s'agit en réalité du troisième et dernier mécanisme possible de la méthode produce().

Pour résumer, le comportement de la méthode produce() est le suivant en fonction du symbole que sa production représente :

- si une production représente un symbole terminal, la produce() empile des productions dans la pile de productions et retourne null ;

- si une production représente un symbole terminal, la produce() retourne un événement ;

- si une production représente un symbole terminal, la produce() consomme des caractères et retourne null.

Notons que nous avons aussi utilisé la méthode consumeUnprintables() de la classe Tokenizer qui consomme tous les caractères entre NULL (0x00) et SPACE (0x20) et pas seulement les caractères d'espacement. Ceci n'a vraiment pas d'importance puisque tous ces caractères n'ont aucun intérêt pour nous et qu'il est par conséquent préférable de les ignorer que de lever une exception.

Nous ajoutons ensuite le nouveau symbole WS à notre table de production dans la méthode initProductionTable() de la classe MathParser.

1. @Override

2. protected void initProductionTable() {

3. // ...

4. this.table[Symbols.WS] = new Productions.Whitespaces();

5. }

IX-G - Nombre variable d'opérandes

Nous allons maintenant lever la limite de trois opérandes dans notre expression :

1. expression = ws number orRightExpression ws (* Modifié *)

2. orRightExpression = {ws operator ws number} (* Nouveau *)

3. number = sign (integer | float)

4. integer = repeatingDigit

5. float = oRepeatingDigit [dot] oRepeatingDigit

6. repeatingDigit = digit repeatingDigit

7. oRepeatingDigit = {digit}

8. sign = '+' | '-' | ''

9. operator = '+' | '-' | '/' | '*'

10. digit = '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'

11. dot = '.'

12. ws = ? caractères d'espacement ?

Avec notre grammaire modifiée, nous allons pouvoir écrire des expressions de ce type :

37. + -.2 - 4.3 * 68

mais aussi seulement :

-256

Cette fois, nous avons complètement modifié la manière de représenter une expression. Une expression a au moins un opérande qui est un nombre et optionnellement un ou plusieurs groupes constitués d'un opérateur suivi d'un nombre.

Le préfixe or dans le nom du symbole orRightExpression signifie, optionnel et répétitif.

Avant de continuer, voyons pourquoi nous n'avons pas écrit simplement :

expression = ws number {ws operator ws number} ws

Pour définir une grammaire, ceci est tout à fait correct. Tout comme pour d'autres symboles tels que number que nous avons implémentés précédemment, mais puisque nous n'avions pas besoin de créer une production, ce cas particulier n'a pas été abordé.

Si l'on souhaite pouvoir implémenter la grammaire, sans aucune modification, à l'aide d'un analyseur syntaxique LL, une telle écriture n'est tout simplement pas possible.

Tout d'abord, si un symbole contient une partie optionnelle, elle doit être impérativement assignée à un symbole qui lui est propre, puisque nous avons besoin d'effectuer un test nous permettant de savoir s'il est présent ou non, et donc si nous devons le rajouter dans la pile de productions :

1. public static class OrRightExpression implements Production<EventType, MathTokenizer> {

2. public EventType produce(MathTokenizer tokenizer,

3. Production<EventType, MathTokenizer>[] table,

4. Stack<Production<EventType, MathTokenizer>> productionStack) {

6. tokenizer.consumeWhitespaces();

8. if (tokenizer.isOperator()) {

9. productionStack.push(table[Symbols.OR_RIGHT_EXPRESSION]);

10. productionStack.push(table[Symbols.NUMBER]);

11. productionStack.push(table[Symbols.WS]);

12. productionStack.push(table[Symbols.OPERATOR]);

13. }

15. return null;

16. }

17. }

Source

Nous modifions ensuite la production Expression. Ces productions n'ayant rien de notable, nous ne nous attarderons pas dessus. Tout comme le nouveau symbole OR_RIGHT_EXPRESSION ou la méthode initProductionTable() de la classe MathParser. Notons qu'en raison du fait que nous pouvons avoir des expressions ayant un nombre d'opérandes variable, la méthode parse() ne retourne plus un tableau de chaînes de caractères, mais une java.util.LinkedList de chaînes de caractères.

Il ne nous reste donc plus qu'à voir la méthode isOperator() qui ne mérite pas plus d'explications :

1. public boolean isOperator() {

2. final int character = this.next();

3. this.rewind();

4. return isOperator(character);

5. }

7. public boolean isOperator(int character) {

8. return character == Ascii.PLUS_SIGN

9. || character == Ascii.HYPHEN

10. || character == Ascii.ASTERIX

11. || character == Ascii.SLASH;

12. }

IX-H - Forcer la priorité

Pour terminer, nous allons introduire la possibilité d'utiliser des parenthèses pour changer la priorité de la résolution de notre expression :

1. expression = orLeftParenthesis ws number orRightExpression ws (* Modifié *)

2. orRightExpression = {ws operator rLeftParenthesis number orRightParenthesis ws} (* Modifié *)

3. orLeftParenthesis = {ws leftParenthesis} (* Nouveau *)

4. orRightParenthesis = {ws rightParenthesis} (* Nouveau *)

5. number = sign (integer | float)

6. integer = repeatingDigit

7. float = oRepeatingDigit [dot] oRepeatingDigit

8. repeatingDigit = digit repeatingDigit

9. oRepeatingDigit = {digit}

10. sign = '+' | '-' | ''

11. operator = '+' | '-' | '/' | '*'

12. digit = '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'

13. dot = '.'

14. ws = ? caractères d'espacement ?

15. leftParenthesis = '(' (* Nouveau *)

16. rightParenthesis = ')' (* Nouveau *)

Cette dernière version de notre grammaire n'introduisant aucune nouveauté, nous ne nous attarderons pas dessus. Néanmoins, nous constatons à nouveau que des incohérences peuvent apparaître à cause des parenthèses. La grammaire ne nous interdit aucunement de ne pas avoir autant de parenthèses ouvrantes que de parenthèses fermantes. Il conviendra donc de gérer ce cas au niveau du code, et nous verrons ceci dans la partie suivante.

Le code n'ayant rien de particulier, nous nous contenterons de résumer les modifications :

- ajout des symboles OR_LEFT_PARENTHESIS, OR_RIGHT_PARENTHESIS, LEFT_PARENTHESIS et RIGHT_PARENTHESIS ;

- ajout des événements LEFT_PARENTHESIS et RIGHT_PARENTHESIS ;

- ajout des méthodes getNext(), isLeftParenthesis() et isRightParenthesis() dans la classe MathTokenizer ;

- ajout des productions OrLeftParenthesis, OrRightParenthesis, LeftParenthesis et RightParenthesis ;

- modification des productions Expression et OrRightExpression ;

- modification des méthodes parse() et initProductionTable() de la classe MathParser.

Voyons néanmoins quelques tests unitaires nous permettant de balayer les différents types d'expressions pouvant être analysés par notre analyseur syntaxique.

1. // Construit une liste

2. private LinkedList<String> expected(final String ... strings) {

3. final LinkedList<String> list = new LinkedList<>();

5. for (String s : strings) {

6. list.add(s);

7. }

9. return list;

10. }

12. // À partir d'une expression à analyser,

13. // teste si la liste générée est égale à la liste attendue.

14. private void test(final String expression, final LinkedList<String> expected) {

15. final InputStream inputStream = new ByteArrayInputStream(expression.getBytes());

16. final MathParser parser = new MathParser(inputStream);

17. final LinkedList<String> tokens = parser.parse();

18. Assert.assertEquals(expected, tokens);

19. }

21. @Test

22. public void expressionWithParenthesis5() {

23. this.test("(2 * (2 + 5) - (10 - 8)) + 3",

24. this.expected("(", "2", "*", "(", "2", "+", "5", ")",

25. "-", "(", "10", "-", "8", ")", ")", "+", "3"));

26. }

28. @Test

29. public void expressionWithParenthesis6() {

30. this.test("4 - (2 + 5) - 2",

31. this.expected("4", "-", "(", "2", "+", "5", ")", "-", "2"));

32. }

Source

IX-I - Récapitulatif de la syntaxe EBNF

Terminons par un récapitulatif des différents opérateurs EBNF.

Il est important de noter que, bien qu'il y ait un standard, il n'est jamais complètement respecté, et cette partie ainsi que la précédente ne dérogent pas à la règle. L'essentiel est de définir - avant d'utiliser une grammaire - précisément le sens des différents opérateurs utilisés. Il me semble qu'il n'y a aucun besoin de rajouter de nouveaux opérateurs, en revanche certains n'ont pas de réelle utilité, tels que le point-virgule (;) qui indique la fin de la définition d'un symbole :

expression = number operator number;

ou bien l'opérateur de concaténation (une virgule ,)

expression = number, operator, number

Notation

Description

Exemple

=

définition d'un symbole

expression = number operator number

|

choix

sign = '+' | '-' | ''

[ … ]

option

float = [number] [dot] [number]

{ … }

répétition

number = digit {digit}

( … )

groupe

expression = number (plus | minus) number

' … '

chaîne terminale

dot = '.'

« … »

chaîne terminale

quote = « ' »

(* … *)

commentaire

(* ceci est un commentaire *)

? … ?

séquence spéciale

? Tous les caractères ASCII ?

-

exception

string = '« ' {character - ' »'} '"'

En cours de cette partie et de la précédente, nous avons vu comment fonctionne un analyseur syntaxique LL basé sur des événements, et nous pouvons constater qu'une fois le cœur de l'analyseur en place, adapter le code pour une nouvelle grammaire est plutôt simple.

En réalité, le plus compliqué est de créer la grammaire. Cette complexité peut être amoindrie en utilisant un cycle incrémental :

- ajout d'éléments à une grammaire ;

- implémentation des nouveaux éléments ;

- création des tests unitaires.

Néanmoins, un cas peut poser problème. Si nous souhaitons prendre en compte les retours à la ligne comme en YAML ou Python, il sera nécessaire de connaître l'indentation, par exemple dans le tokenizer, ce qui permet de savoir dans quel bloc on se trouve. Et il faudra aussi prendre en compte les différents types d'indentation. Est-ce qu'une tabulation est identique à plusieurs espaces et si oui, combien ?

Pour conclure, notons qu'avec Java 8 et les lambdas, l'interface Production est une parfaite candidate pour devenir une interface fonctionnelle, c'est-à-dire une interface n'ayant qu'une méthode abstraite n'étant pas héritée de la classe java.lang.Object.

IX-J - What's next

Après deux parties dédiées à la création d'un analyseur syntaxique, nous allons pouvoir finaliser notre calculatrice, qui n'est rien de plus qu'une forme d'interpréteur.

X - Résoudre une expression arithmétique

Depuis deux chapitres nous nous sommes éloignés de la JVM et du bytecode, il est donc grand temps d'y revenir, ou du moins de nous en rapprocher. Aujourd'hui nous allons enfin résoudre les expressions que nous avons découpées en multiples tokens correspondant à des opérandes.

Dans ce chapitre, et sauf mention contraire, le terme opérande aura son sens mathématique pour lequel il désigne un nombre (ou une variable), mais pas un opérateur (contrairement au sens informatique).

Le code est disponible sur Github (tag et branche).

X-A - Notation préfixée, infixée et postfixée

Chacun des tokens est inséré dans une liste selon l'ordre dans lequel il a été analysé. Voyons par exemple l'analyse syntaxique de l'expression suivante :

3 + 4 * 7

Elle a pour résultat la liste suivante (l'élément le plus à gauche étant le premier élément de la liste) :

3, +, 4, *, 7

La notation d'une telle expression est dite infixée, c'est-à-dire que les opérateurs sont placés entre les opérandes utilisés pour effectuer l'opération. Il s'agit de la notation qui nous est la plus familière. Mais ce n'est pas la seule permettant de représenter une expression arithmétique.

La notation préfixée place les opérateurs avant les opérandes utilisés pour effectuer l'opération. Si l'on transforme l'expression infixée précédente nous obtenons l'expression suivante :

+ 3 * 4 7

Le Lisp et les langages qui en sont inspirés, tels que Scheme, utilisent une pseudo notation préfixée. Dans ce cas, on parle de pseudo notation préfixée, puisque pour ces langages, un opérateur est une fonction d'arité indéfinie (c'est-à-dire acceptant un nombre variable de paramètres) alors qu'en arithmétique, quelle que soit la notation, un opérateur n'opère que sur deux opérandes.

La dernière notation que nous allons voir est la notation postfixée. Elle place les opérateurs après les opérandes sur lesquels l'opération est effectuée.

3 4 7 * +

Chaque opérande pouvant être une expression :

1 2 + 3 4 + *
(1 2 +) (3 4 +) *

Les expressions préfixées et postfixées sont non ambiguës : avec ou sans les parenthèses l'interprétation est la même contrairement à une expression infixée, pour laquelle la priorité des opérateurs * et / sur les opérateurs + et - a un impact sur la résolution de l'expression :

(1 + 2) * (3 + 4)

est différent de :

1 + 2 * 3 + 4

X-B - Résolution d'une expression postfixée

La notation postfixée est utilisée par tous les langages basés sur une pile, tels que le Forth, le PostScript, ou - ce qui nous intéresse - le Java.

L'algorithme permettant d'évaluer une expression postfixée en utilisant une pile de nombres est le suivant :

- lire l'expression de gauche à droite, un nombre ou un opérateur à la fois ;

- lorsque l'on rencontre un nombre, on l'empile ;

- lorsque l'on rencontre un opérateur :

- on dépile deux nombres du sommet de la pile,

- on effectue l'opération (en se rappelant que le premier élément dépilé est le second opérande),

- on empile le résultat pour qu'il soit utilisé par l'opération suivante.

Si l'expression est correcte, le résultat est le dernier élément présent dans la pile.

Voyons un exemple. Pour l'expression postfixée ci-dessous :

2 7 5 - * 8 5 - *

Le calcul est le suivant (l'élément le plus à droite est le sommet de la pile) :

Caractère lu : état de la pile avant -> après

2 : [vide] -> 2
7 : 2 -> 2, 7
5 : 2, 7 ->  2, 7, 5
- : 2, 7, 5 - > 2, 2 (7 - 5 = 2)
* : 2, 2 -> 4 (2 * 2 = 4)
8 : 4 -> 4, 8
5 : 4, 8 -> 4, 8, 5
- : 4, 8, 5 -> 4, 3 (8 - 5 = 3)
* : 4, 3 -> 12 (4 * 3 = 12)

Nous pouvons constater simplement que la JVM résout des expressions postfixées en reprenant l'expression précédente :

1. .class org/isk/jvmhardcore/bytecode/partnine/Postfix

2. .method compute()I

3. iconst_2

4. bipush 7

5. iconst_5

6. isub

7. imul

8. bipush 8

9. iconst_5

10. isub

11. imul

12. ireturn

13. .methodend

14. .classend

Source

Le test unitaire nous confirme le résultat que nous avions obtenu en effectuant le calcul à la main :

1. @Test

2. public void compute() {

3. final int result = Postfix.compute();

4. Assert.assertEquals(12, result);

5. }

Source

Voyons à présent comment résoudre une expression postfixée en Java, à partir d'une liste de type java.util.LinkedList contenant des nombres de type java.lang.Number (la superclasse des classes Integer et Double) et des opérateurs de type org.isk.jvmhardcore.math.common.Operator :

1. public enum Operator {

2. PLUS, MINUS, TIMES, DIVIDE;

3. }

Nous allons donc implémenter une méthode prenant en argument une LinkedList représentant une expression postfixée et retournant une valeur de type java.lang.Integer ou java.lang.Double en fonction du type des opérandes de l'expression.

1. public <T>T resolve(LinkedList<Object> postfixExpression) {

3. }

Utiliser un type de retour générique (<T>T) nous permet d'éviter de convertir la valeur en Integer ou en Double.

Si l'on reprend l'algorithme, nous avons besoin d'une pile contenant les nombres.

1. public class MathSolver {

2. private final Stack<Number> processingStack;

4. public MathSolver() {

5. this.processingStack = new Stack<>();

6. }

7. }

L'implémentation de la méthode resolve() est triviale, puisque nous itérons sur les éléments de la liste. Si l'élément est de type Operator nous effectuons un calcul, sinon nous l'empilons. Et pour finir, nous dépilons le dernier élément de la pile (le résultat) pour le retourner.

1. public <T> T resolve(LinkedList<Object> postfixExpression) {

2. this.processingStack.clear();

4. for (Object object : postfixExpression) {

5. if (object instanceof Operator) {

6. this.compute((Operator) object);

7. } else {

8. this.processingStack.push((Number) object);

9. }

10. }

12. return (T) this.processingStack.pop();

13. }

La méthode compute(), quant à elle, dépile deux éléments du sommet de la pile et effectue l'opération en fonction de l'opérateur.

1. private void compute(Operator operator) {

2. final Number right = this.processingStack.pop();

3. final Number left = this.processingStack.pop();

5. switch (operator) {

6. case PLUS:

7. this.add(left, right);

8. break;

10. // case pour chaque opérateur

11. }

12. }

Les trois autres opérateurs fonctionnent sur le même principe.

Les méthodes add(), subtract() et multiply() sont construites sur le même principe :

- nous vérifions le type des opérandes (comme nous l'avons vu dans la partie Mathématiques et Conversions, en Java les opérateurs arithmétiques prennent deux opérandes du même type, en raison du comportement identique des instructions associées) ;

- nous effectuons l'opération ;

- et nous ajoutons le résultat à la pile de nombres (sous la forme d'un Number).

Pour l'exemple, le choix a été fait de distinguer deux types de nombres (Integer et Double), à l'instar de l'analyseur syntaxique. Bien évidemment dans un cas réel, le choix devrait être fait en fonction du besoin.

L'addition, la soustraction et la multiplication retournent une valeur de type Integer si les deux opérandes sont des entiers, sinon une valeur de type Double. La division retourne une valeur de type Integer uniquement si le reste de la division des deux entiers est égal à zéro. Dans tous les autres cas, elle retourne une valeur de type Double.

1. private void add(Number left, Number right) {

2. Number n = null;

4. if (left instanceof Integer && right instanceof Integer) {

5. n = left.intValue() + right.intValue();

6. } else {

7. n = left.doubleValue() + right.doubleValue();

8. }

10. this.processingStack.push(n);

11. }

Ceci fonctionne puisque le résultat d'une addition, d'une soustraction et d'une multiplication est du même type que ses opérandes. En revanche, pour la division ce n'est pas le cas. Si l'on divise deux entiers comme 5 et 2, le résultat (sans perte d'information) sera un nombre à virgule, alors que 4 divisé par 2 aura pour résultat 2. Bien qu'en mathématique 2 soit égal à 2,0, en informatique ce n'est pas le cas puisque, comme nous l'avons déjà vu, un entier n'est pas représenté en mémoire de la même manière qu'un nombre à virgule. Encore une fois, le besoin sera déterminant dans le choix de l'implémentation de la méthode divide().

1. private void divide(Number left, Number right) {

2. Number n = null;

4. if (left instanceof Integer && right instanceof Integer

5. && (left.intValue() % right.intValue()) == 0) {

6. n = left.intValue() / right.intValue();

7. } else {

8. n = left.doubleValue() / right.doubleValue();

9. }

11. this.processingStack.push(n);

12. }

Source

Nous pouvons ensuite effectuer quelques tests unitaires :

1. public class MathSolverTest {

2. private static MathSolver SOLVER;

4. @BeforeClass

5. public static void init() {

6. SOLVER = new MathSolver();

7. }

9. private LinkedList<Object> postfixExpression(final Object ... objects) {

10. final LinkedList<Object> list = new LinkedList<>();

12. for (Object o : objects) {

13. list.add(o);

14. }

16. return list;

17. }

19. private void test(final LinkedList<Object> postfixExpression,

20. final int expectedResult) {

21. final int result = SOLVER.resolve(postfixExpression);

22. Assert.assertEquals(expectedResult, result);

23. }

25. private void test(final LinkedList<Object> postfixExpression,

26. final double expectedResult) {

27. final double result = SOLVER.resolve(postfixExpression);

28. Assert.assertEquals(expectedResult, result, 0.001);

29. }

31. @Test

32. public void resolve21() {

33. // 2 + 5 - 2

34. this.test(this.postfixExpression(2, 5, Operator.PLUS, 2, Operator.MINUS), 5);

35. }

37. @Test

38. public void resolve22() {

39. // ((2 + 5) * 2) - 2

40. this.test(

41. this.postfixExpression(

42. 2, 5, Operator.PLUS, 2, Operator.TIMES, 2, Operator.MINUS),

43. 12);

44. }

45. }

Source

X-C - Typage des symboles terminaux

Nous avons donc d'un côté un analyseur syntaxique créant une liste de chaînes de caractères représentant une expression infixée et, de l'autre, un interpréteur prenant en paramètre une liste de java.lang.Number et de org.isk.jvmhardcore.math.common.Operator représentant une expression postfixée.

Mais avant de transformer notre expression infixée en expression postfixée, nous devons :

- modifier les méthodes getInteger(), getFloat() et getOperator() de la classe MathTokenizer, pour qu'elles retournent respectivement un Integer, un Double et un ParsingOperator ;

- et supprimer la méthode getNext() retournant un caractère sous la forme d'un int, par la méthode getParenthesis() retournant un ParsingOperator.

Le type ParsingOperator nous permet de représenter les quatre opérateurs arithmétiques, mais aussi les parenthèses, sous un seul type pour que la transformation soit simplifiée.

1. enum ParsingOperator {

2. PLUS(0),

3. MINUS(0),

4. TIMES(1),

5. DIVIDE(1),

6. LEFT_PARENTHESIS(100),

7. RIGHT_PARENTHESIS(100);

8. }

Nous verrons dans la partie suivante la signification de ces différentes valeurs.

Cette énumération n'ayant aucun sens à l'extérieur de l'analyseur syntaxique, elle est définie dans la classe MathParser, et n'est accessible qu'à l'intérieur du package org.isk.jvmhardcore.math.parser.

X-D - Transformer une expression infixée en expression postfixée

Maintenant que nous avons typé tous les tokens, nous devons changer la notation utilisée pour représenter les expressions.

La première chose à prendre en compte est que la notation infixée a des règles de précédence :

- une expression entre parenthèses est prioritaire par rapport à tous les opérateurs arithmétiques ou à une expression entre parenthèses englobantes : dans l'expression 2 * ((2 + 7) - 4), l'expression (2 + 7) est prioritaire sur la soustraction, elle-même prioritaire sur la multiplication ;

- la multiplication et la division sont prioritaires par rapport à l'addition et à la soustraction.

Les expressions arithmétiques étant associatives à gauche, si deux opérateurs sont de priorité identique, l'opération la plus à gauche est effectuée en premier.

Ces règles de précédence sont représentées dans l'énumération ParsingOperator par les valeurs 0, 1 et 100. De fait, si l'on compare les opérateurs PLUS, qui a pour valeur 0, et TIMES, qui a pour valeur 1, alors PLUS < TIMES. Néanmoins, les parenthèses n'étant pas des opérateurs, elles devront être traitées d'une manière différente des opérateurs arithmétiques - comme nous allons le voir - et pour cette raison elles ont pour valeur 100.

De plus, pour pouvoir effectuer la transformation il nous faut une pile d'opérateurs et une liste contenant l'expression postfixée.

Ces quelques prérequis pris en considération, voyons l'algorithme :

- lire l'expression de gauche à droite ;

- lorsque l'on rencontre un nombre, on l'ajoute à la liste ;

- lorsque l'on rencontre un opérateur, s'il est de précédence inférieure à l'opérateur au sommet de la pile, on dépile l'opérateur au sommet de la pile, on l'ajoute à la liste et on empile l'opérateur rencontré ;

- lorsque l'on rencontre une parenthèse ouvrante, on l'empile ;

- lorsque l'on rencontre une parenthèse fermante, on dépile tous les opérateurs et on les ajoute à la liste jusqu'à ce que l'on dépile une parenthèse ouvrante. (Les parenthèses seront toutes deux ignorées puisqu'inutiles dans une expression postfixée) ;

- lorsque l'on arrive à la fin de l'expression, on ajoute la totalité des opérateurs de la pile dans la liste, dans l'ordre de dépilage.

Commençons par un exemple simple : 3 * 2. Comme précédemment, pour la pile l'élément le plus à droite est le sommet de la pile. Pour la liste l'élément le plus à gauche est le premier élément de la liste.

Caractère lu : état de la pile avant -> après | état de la liste avant -> après

3: [vide] -> [vide] | [vide] -> 3
*: [vide] -> *      | 3 -> 3
2: *      -> *      | 3 -> 3, 2
fin: *    -> [vide] | 3, 2 -> 3, 2, *

Rajoutons un opérateur de priorité inférieure et un opérande : 3 * 2 + 5

Caractère lu : état de la pile avant -> après | état de la liste avant -> après

3: [vide] -> [vide] | [vide] -> 3
*: [vide] -> *      | 3 -> 3
2: * -> *           | 3 -> 3, 2
+: * -> +           | 3, 2 -> 3, 2, *
5: + -> +           | 3, 2, * -> 3, 2, *, 5
fin: + -> [vide]    | 3, 2, *, 5 -> 3, 2, *, 5, +

Pour terminer, voyons une expression plus complexe : (2 * (2 + 5) - (10 - 8)) + 3. Pour rester concis, hormis pour la première ligne, seul l'état de la pile « après » est indiqué (l'état « avant » étant l'état « après » de la ligne précédente).

Caractère lu : état de la pile -> après | état de la liste -> après

(:      [vide] -> (         | [vide] -> [vide]
2:      -> (                | [vide] -> 2
*:      -> (, *             | -> 2
(:      -> (, *, (          | -> 2
2:      -> (, *, (          | -> 2, 2
+:      -> (, *, (, +       | -> 2, 2
5:      -> (, *, (, +       | -> 2, 2, 5
):      -> (, *             | -> 2, 2, 5, +
-:      -> (, -             | -> 2, 2, 5, +, *
(:      -> (, -, (          | -> 2, 2, 5, +, *
10:     -> (, -, (          | -> 2, 2, 5, +, *, 10
-:      -> (, -, (, -       | -> 2, 2, 5, +, *, 10
8:      -> (, -, (, -       | -> 2, 2, 5, +, *, 10, 8
):      -> (, -,            | -> 2, 2, 5, +, *, 10, 8, -
):      -> [vide]           | -> 2, 2, 5, +, *, 10, 8, -, -
+:      -> +                | -> 2, 2, 5, +, *, 10, 8, -, -
3:      -> +                | -> 2, 2, 5, +, *, 10, 8, -, -, 3
fin:    -> [vide]           | -> 2, 2, 5, +, *, 10, 8, -, -, 3, +

Cet exemple peut être validé par le test unitaire suivant :

1. public class MathParserTest {

3. private LinkedList<Object> expected(final Object ... objects) {

4. final LinkedList<Object> list = new LinkedList<>();

6. for (Object o : objects) {

7. list.add(o);

8. }

10. return list;

11. }

13. private void test(final String expression, final LinkedList<Object> expected) {

14. final InputStream inputStream =

15. new ByteArrayInputStream(expression.getBytes());

16. final MathParser parser = new MathParser(inputStream);

17. final LinkedList<Object> tokens = parser.parse();

18. Assert.assertEquals(expected, tokens);

19. }

21. @Test

22. public void expressionWithParenthesis5() {

23. this.test("(2 * (2 + 5) - (10 - 8)) + 3",

24. this.expected(

25. 2, 2, 5, Operator.PLUS, Operator.TIMES,

26. 10, 8, Operator.MINUS, Operator.MINUS, 3, Operator.PLUS));

27. }

28. }

Source

En l'état le test est en erreur, puisque nous n'avons pas encore effectué les modifications dans la classe MathParser.

Pour commencer, nous renommons le champ tokens de type LinkedList en postfixExpression, contenant à présent des objets de type java.lang.Object, puis nous rajoutons une pile d'opérateurs :

1. final private LinkedList<Object> postfixExpression;

2. final private Stack<ParsingOperator> operatorStack;

4. public MathParser(final InputStream inputStream) {

5. super(inputStream, Symbols.number());

7. this.postfixExpression = new LinkedList<>();

8. this.operatorStack = new Stack<>();

9. }

Nous modifions ensuite le switch/case de la méthode parse() :

1. switch (eventType) {

2. case FLOAT:

3. this.postfixExpression.add(this.tokenizer.getFloat());

4. break;

5. case INTEGER:

6. this.postfixExpression.add(this.tokenizer.getInteger());

7. break;

8. case OPERATOR:

9. this.processOperator(this.tokenizer.getOperator());

10. break;

11. case LEFT_PARENTHESIS:

12. this.operatorStack.push(this.tokenizer.getParenthesis());

13. break;

14. case RIGHT_PARENTHESIS:

15. this.processRightParenthesis(this.tokenizer.getParenthesis());

16. break;

17. case EOF:

18. this.tokenizer.checkEndOfFile();

19. this.processEndOfFile();

20. done = true;

21. break;

En reprenant l'algorithme, nous ajoutons les nombres à la liste (postfixExpression) et ajoutons les parenthèses ouvrantes à la liste des opérateurs (operatorStack). Le traitement des autres événements est déporté dans des méthodes dédiées.

Commençons par la méthode processOperator().

1. private void processOperator(ParsingOperator parsingOperator) {

2. if (!this.operatorStack.isEmpty()

3. && parsingOperator.le(this.operatorStack.peek())) {

4. this.postfixExpression.add(ParsingOperator.getClean(this.operatorStack.pop()));

5. }

7. this.operatorStack.push(parsingOperator);

8. }

Nous testons si l'opérateur au sommet de la pile est de priorité supérieure à l'opérateur courant. Si c'est le cas, il est dépilé, converti en Operator (ParsingOperator.getClean()) et ajouté à la liste. Dans tous les cas, l'opérateur courant est ajouté à la pile d'opérateurs.

La méthode le() de l'énumération ParsingOperator exclut les parenthèses des règles de précédence, puisqu'il ne s'agit pas d'un opérateur et que c'est l'ensemble de l'expression entre parenthèses qui est prioritaire.

1. public boolean le(ParsingOperator po) {

2. return po.value != 100 && this.value <= po.value;

3. }

Si l'opérateur est une parenthèse ouvrante (les parenthèses fermantes n'étant jamais ajoutées à la pile d'opérateurs), elle ne doit pas être dépilée. Une expression entre parenthèses étant une sous-expression, quel que soit le premier opérateur de cette sous-expression, nous devons considérer que la pile d'opérateurs est vide.

Seul le traitement d'une parenthèse fermante (processRightParenthesis()) impliquera le dépilage d'une parenthèse ouvrante.

1. private void processRightParenthesis(ParsingOperator rightParenthsesis) {

2. while (!this.operatorStack.isEmpty()

3. && this.operatorStack.peek() != ParsingOperator.LEFT_PARENTHESIS) {

4. this.postfixExpression.add(ParsingOperator.getClean(this.operatorStack.pop()));

5. }

7. if (this.operatorStack.isEmpty()

8. || this.operatorStack.pop() != ParsingOperator.LEFT_PARENTHESIS) {

9. throw new MathException("Missing left parenthesis.");

10. }

11. }

Si l'on rencontre une parenthèse fermante, tous les opérateurs sont dépilés un par un, convertis en Operator et ajoutés à la liste, et ceci jusqu'à ce qu'une parenthèse ouvrante soit rencontrée (ou pour parer aux erreurs, jusqu'à ce que la pile soit vide).

Finalement, nous vérifions que la boucle s'est bien arrêtée parce qu'une parenthèse ouvrante a été rencontrée, et non parce que la pile était vide (cas d'une expression avec une parenthèse fermante sans parenthèse ouvrante).

Notez que nous dépilons la parenthèse, puisqu'elle ne nous est plus utile.

Lorsque l'analyse de l'expression est terminée, comme pour le traitement d'une parenthèse fermante, nous dépilons tous les opérateurs de la pile un par un, les convertissons en Operator et les ajoutons à la liste.

1. private void processEndOfFile() {

2. while (!this.operatorStack.isEmpty()) {

3. this.postfixExpression.add(ParsingOperator.getClean(this.operatorStack.pop()));

4. }

5. }

Si dans la pile est présente une parenthèse ouvrante (l'expression a une parenthèse ouvrante qui n'a pas de parenthèse fermante), la méthode ParsingOperator.getClean() lève une exception.

Les deux exceptions (liées à une asymétrie entre les parenthèses ouvrantes et fermantes) levées dans la classe MathParser, n'utilisent pas l'exception ParserException, mais MathException. De ce fait, nous n'avons ni le numéro de ligne, ni le numéro de colonne. Dans le cas de l'exception levée dans la méthode processRightParenthesis() nous pourrions trouver le moyen d'utiliser l'exception ParserException, en revanche pour celle de la méthode ParsingOperator.getClean(), cela n'apporterait aucune information de plus à l'utilisateur, puisque nous devons analyser toute l'expression pour nous rendre compte qu'il manque une parenthèse fermante. Une solution serait d'associer à un token une ligne et une colonne. Néanmoins, dans le cas présent ce serait ajouter une complexité inutile.

Ceci conclut notre série consacrée aux analyseurs syntaxiques et à l'implémentation d'un interpréteur plutôt simple. Le matériel traité dans ces trois articles nous sera utile prochainement lorsque nous créerons un assembleur permettant de générer du bytecode à partir d'un fichier .pjb, et plus tard encore lorsque nous créerons des compilateurs.

X-E - What's next ?

Dans le chapitre suivant, nous achèverons notre excursion hors de l'univers du bytecode en nous intéressant à l'Unicode et à son intégration dans le monde Java.

XI - L'unicode et Java

XI-A - Principes fondamentaux et vocabulaire

Comme vous le savez déjà, un ordinateur ne comprend que le binaire. Des 0 et des 1, représentant des nombres (entiers ou à virgule).

Le codage (binaire) des caractères (charset encoding) est la relation entre un nombre entier (point de code) et un caractère. Par exemple, le nombre 0100 0001 en base 2, ou 65 en base 10, correspond à la lettre A dans la plupart des jeux de caractères.

Un jeu de caractères rassemble un ensemble fini de caractères, dont chaque caractère est codé sur un nombre de bits, défini par l'encodage.

Le terme « binaire » est ajouté à l'expression « codage des caractères », car il est possible de coder des caractères sous une autre forme, telle que le braille ou le morse.

XI-B - Avant l'Unicode

Tout a commencé au cours du XIXe siècle avec le Code Baudot, mais il nous est inutile de remonter si loin. En prenant quelques raccourcis, disons que pour le monde informatique les premiers jeux de caractères furent l'EBCDIC (prononcez /ˈɛbsɨdɪk/) et l'ASCII qui doit vous être plus familier. Chaque caractère ASCII est codé sur 7 bits, permettant d'avoir 128 caractères basés sur l'alphabet anglais (ASCII signifiant American Standard Code for Information Interchange).

Or, pour tous les systèmes d'écriture utilisant d'autres caractères, il a fallu créer d'autres jeux de caractères comme les différents ISO-xxxx, KOI8, JIS-yyyy, Windows-zzzz, etc., dont la plupart codent chaque caractère sur un octet.

Mais ce n'était pas une solution idéale. Chaque application internationalisée devait gérer plusieurs jeux de caractères. Finalement, à la fin des années 80 un nouveau standard, l'Unicode, a été inventé pour pouvoir coder tous les systèmes d'écriture modernes.

XI-C - L'Unicode

À l'origine (dans le document nommé Unicode 88), Joe Becker (l'un des créateurs de l'Unicode avec Lee Collins et Mark Davis) considérait que 16 bits seraient amplement suffisants pour représenter tous les systèmes d'écriture modernes, et que l'Unicode n'avait pas pour but de représenter des systèmes rares et/ou obsolètes.

Or en 1996, un mécanisme de caractères de remplacement a été introduit en Unicode 2. De fait, l'Unicode n'était plus limité à 16 bits. Ceci a eu pour effet d'augmenter le répertoire Unicode (codespace - nombre de caractères qu'il est possible de représenter) à plus d'un million, permettant le codage de nombreux systèmes d'écriture anciens, tel que les hiéroglyphes égyptiens et des milliers de caractères obsolètes ou rarement utilisés, considérés originellement non nécessaires. Parmi lesquels nous retrouvons les caractères chinois et les Kanji rarement utilisés puisqu'ils sont des composants de noms propres ou de lieux.

La dernière version d'Unicode (6.2) contient un peu plus de 100 000 caractères de plus de 100 systèmes d'écriture.

Le standard est maintenu par le Consortium Unicode.

L'Unicode est utilisé pour représenter les chaînes de caractères dans la plupart des langages modernes : Java, .Net (C#, VB.Net), Go, Python3, Dart, etc.

XI-C-1 - Les concepts

L'Unicode permet de définir 1 114 112 points de code de 0x0000 à 0x10FFFF. Généralement un point de code est noté U+xxxx où xxxx est en hexadécimal, et comporte de 4 à 6 chiffres. Par exemple, U+0041 correspond à la lettre A.

Le répertoire Unicode est divisé en 17 plans, numérotés de 0 à 16. Le premier plan (plan 0) est nommé Plan Multilingue de Base (BMP). Il contient les points de code de U+0000 à U+FFFF représentant la plupart des systèmes d'écriture modernes. Les autres plans sont nommés plans supplémentaires.

Dans chaque plan, les caractères sont alloués à des blocs - nommés - de caractères liés, par exemple Basic Latin, Latin-1 Supplement, etc. Chaque bloc est de taille variable, mais cette taille est toujours un multiple de 16. Certains systèmes d'écriture sont répartis dans plusieurs blocs.

Prenons par exemple la chaîne de caractères « Bonjour ». Elle est codée en points de code Unicode de la manière suivante :

U+0042 U+006F U+006E U+006A U+006F U+0075 U+0072.

Mais attention. L'Unicode définit un jeu de caractères, mais ne spécifie en rien l'apparence d'un caractère (police de caractères), ni comment les points de code sont stockés en mémoire (codage des caractères).

À noter que les 256 premiers points de code sont identiques à ceux du jeu de caractères ISO-8859-1 rendant la conversion des textes utilisant des caractères occidentaux presque triviale.

XI-C-2 - Zone d'indirection

Les points de code de U+D800 à U+DBFF (1024 points de code) sont connus sous le nom de point de code de la zone haute d'indirection (lead surrogate).

Les points de code de U+DC00 à U+DFFF (1024 points de code) sont connus sous le nom de point de code de la zone basse d'indirection (trail surrogate).

Un point de code de la zone haute d'indirection suivi d'un point de code de la zone basse d'indirection constituent une paire de substitution (zone d'indirection/surrogate pair) utilisée pour représenter en UFT‑16 1 048 576 points de code n'appartenant pas au BMP (plan 0). Nous y reviendrons un peu plus loin dans cet article, lorsque nous verrons l'UTF‑16.

Les zones haute et basse d'indirection ne sont pas valides lorsqu'elles sont isolées. Ainsi, les points de code pouvant être utilisés en tant que caractères vont de U+0000 à U+D7FF et de U+E000 à U+10FFFF (soit 1 112 064 points de code).

XI-C-3 - Les non-caractères

Un « non-caractère » est un point de code qui est réservé de manière permanente dans le standard Unicode pour un usage interne.

Il y a soixante-six non-caractères :

- les points de code entre les deux zones d'indirection : U+FDD0 à U+FDEF (32 caractères) ;

- Tous les points de code finissant par FFFE ou FFFF (les deux derniers caractères de chaque plan), comme U+FFFE, U+FFFF, U+1FFFE, U+1FFFF, U+2FFFE, U+2FFFF…, U+10FFFE, U+10FFFF (34 caractères).

L'ensemble des non-caractères est stable, et aucun nouveau non-caractère ne sera défini.

XI-C-4 - Caractères à usage privé

Les caractères à usage privé sont des points de code dont l'interprétation n'est pas spécifiée par une norme de codage de caractères et dont l'utilisation et l'interprétation peuvent être déterminées par un accord privé entre les utilisateurs/applications.

Il y a trois zones de caractères à usage privé :

- zone à usage privé (Private Use Area) : U+E000 à U+F8FF (6400 caractères) ;

- zone à usage privé supplémentaire A (Supplementary Private Use Area-A) : U+F0000 à U+FFFFD (65 534 caractères) ;

- zone à usage privé supplémentaire B (Supplementary Private Use Area-B) : U+100000 à U+10FFFD (65 534 caractères).

XI-C-5 - Points de code réservés

Les points de code réservés sont des points de code actuellement non attribués, mais réservés pour une normalisation future. (Roadmaps to Unicode).

XI-C-6 - Glyphes et graphème

Un glyphe est une représentation graphique d'un caractère :

Un graphème est une unité distinctive minimale de l'écriture dans le cadre d'un système d'écriture donné. Par exemple, b et m sont des graphèmes distincts dans le système d'écriture latin, puisque par exemple en français, ils constituent des mots différents, comme bal ou mal. En revanche, a (en gras) et a (en italique) ne sont pas des graphèmes distincts, car aucun mot ne se distingue sur la base de ces deux formes différentes. Le terme graphème est souvent défini comme un caractère perçu par l'utilisateur (user-perceived character). J'imagine que certains doivent se demander où je veux en venir et quelle est l'utilité d'entrer autant dans les détails. La réponse est très simple, il s'agit d'une introduction à l'un des cauchemars de l'Unicode, et d'une manière générale de n'importe quel jeu de caractères.

À un point de code correspond un caractère, mais un caractère ne correspond pas toujours à un caractère perçu par l'utilisateur. De plus, il y a aussi des duplications.

XI-C-6-a - Un graphème et plusieurs points de code

Le graphème é a pour point de code U+00E9 ou la combinaison de U+0065 (e) et U+0301 ( _ ́ _ ), un accent. Il en va de même pour tous les graphèmes contenant des signes diacritiques, définis dans le bloc Unicode nommé Combining Diacritical Marks. La première forme composée d'un seul point de code est nommée forme précomposée et la seconde forme combinée. Tous les caractères français ont une forme précomposée, mais ce n'est pas le cas pour tous les systèmes d'écriture, sachant qu'un graphème peut être composé de plus de deux caractères.

XI-C-6-b - Duplication des graphèmes

Pour des questions de rétrocompatibilité avec d'anciens jeux de caractères, ainsi que pour garder une certaine indépendance des blocs, des graphèmes ont été dupliqués.

Le graphème μ est présent dans les blocs Greek sous le nom GREEK SMALL LETTER MU - et a pour point de code U+03BC - et Latin-1 Supplement sous le nom MICRO SIGN avec pour point de code U+00B5.

Mais ce n'est qu'un exemple, il y a de nombreux autres cas.

Que ce soit la duplication des graphèmes, la possibilité de représenter un même graphème en un ou plusieurs points de code, il y a un véritable impact dans :

- l'égalité de deux caractères et donc de deux chaînes de caractères ;

- le tri de plusieurs caractères et donc de plusieurs chaînes de caractères ;

- le comptage du nombre de caractères dans une chaîne de caractères.

XI-C-6-c - Ligatures

Contrairement à ce que l'on pourrait penser, le cas suivant ne pose aucun problème. Dans le mot cœur, œ est un graphème (résultat de la ligature des lettres o et e) et son point de code est U+0153.

Les ligatures, tout comme les diagraphes n'étant que des représentations particulières de deux glyphes, ils ne sont pas - toujours - assignés à un point de code (les ligatures et diagraphes assignés à un point de code, l'ont été pour des raisons de rétrocompatibilité). La tâche de les afficher correctement revient aux polices de caractères.

XI-D - Codage des caractères

L'Unicode définit deux méthodes de codage des caractères : l'UTF (Unicode Transformation Format) et l'UCS (Universal Character Set). Le nombre suivant l'acronyme correspondant, pour l'UTF au nombre de bits par unité de code et pour l'UCS au nombre d'octets par unité de code. L'unité de code est la combinaison minimale de bits pouvant représenter une unité de texte codé pour un traitement ou un échange. Le standard Unicode utilise des unités de code de 8 bits pour l'UTF-8, 16 pour l'UTF-16 et 32 pour UTF-32. L'UTF-8 et l'UTF-16 sont probablement les formes de codage des caractères les plus utilisées. L'UCS-2 est un sous-ensemble de l'UTF-16 aujourd'hui obsolète, et l'UCS-4 et l'UTF-32 sont fonctionnellement équivalents.

XI-D-1 - UTF-32

En UTF-32 (et UCS-4), une unité de code de 32 bits permet de représenter sans aucune transformation un point de code (même si le boutisme, qui varie selon les différentes plates-formes, affecte la façon dont la valeur de code se manifeste dans une séquence d'octets). Dans les autres codages, chaque point de code peut être représenté par un nombre variable d'unités de code. UTF-32 est principalement utilisé comme représentation interne du texte dans les programmes (par opposition au texte stocké ou transmis), notamment des éditeurs de texte.

XI-D-2 - UTF-16

En UTF-16 (et UCS-2) les points de codes du BMP sont codés sur 2 octets, sans aucune transformation.

En revanche, pour les plans supplémentaires l'UCS-2 n'est pas adapté. L'UTF-16, quant à lui, code les points de codes par paires d'unités de code de 16 bits, appelées paires de substitution codées sur 4 octets. Le codage est effectué de la manière suivante :

1. On soustrait 0x10000 au point de code. Le résultat est un nombre de 20 bits, compris entre 0 et 0xFFFFF (résultat de la soustraction 0x10FFFF - 0x10000) ;

2. On ajoute 0xD800 aux dix bits supérieurs (un nombre compris entre 0 et 0x3FF). Le résultat constitue la première unité de code (comprise entre 0xD800 et 0xDBFF), appelée aussi zone haute d'indirection ;

3. On ajoute 0xDC00 aux dix bits inférieurs (un nombre compris entre 0 et 0x3FF). Le résultat constitue la seconde unité de code (comprise entre 0xDC00 et 0xDFFF), appelée aussi zone basse d'indirection.

Pour rappel, les zones haute et basse d'indirection ne sont pas valides lorsqu'elles sont isolées. Par conséquent, il ne peut y avoir d'erreur d'interprétation entre un point de code codé sur 2 octets et un autre codé sur 4 octets.

Exemple avec le point de code U+64321.

1. Commençons par soustraire 0x10000 au point de code 0x64321 - 0x10000 = 0x54321 = 0101 0100 0011 0010 0001

2. Passons ensuite à la première unité de code : 0x54321 >> 10 = 01 0101 0000 = 0x0150

0x0150 + 0xD800 = 0xD950

3. Et terminons par la seconde unité de code 0x54321 & 0x3FF = 11 0010 0001 = 0x0321

0x0321 + 0xDC00 = 0xDF21

U+64321 appartenant à un plan supplémentaire (puisque supérieur à U+FFFF), en mémoire il est codé sur les 4 octets suivants : D9 50 DF 21.

XI-D-3 - UTF-8

En UTF-8, un point de code est codé sur un, deux, trois ou quatre octets.

Le codage est effectué de la manière suivante :

Interval

Octet 1

Octet 2

Octet 3

Octet 4

U+0000 - U+007F

0xxxxxxx

U+0080 - U+07FF

110xxxxx

10xxxxxx

U+0800 - U+FFFF

1110xxxx

10xxxxxx

10xxxxxx

U+10000 - U+1FFFFF

11110xxx

10xxxxxx

10xxxxxx

10xxxxxx

Les principales caractéristiques de cette conception sont les suivantes :

- les points de code ASCII 0 à 127 sont codés sur un octet. Dans ce cas, le code UTF-8 a la même valeur que le code ASCII. Le bit de poids fort est toujours 0 ;

- les points de code supérieurs à 127 sont représentés par des séquences de plusieurs octets. Le premier octet commence par deux, trois ou quatre « 1 » suivi par un 0. Les octets suivants commencent tous par « 10 » ;

- le nombre de 1 au début du premier octet d'une séquence de plusieurs octets indique le nombre d'octets dans la séquence, de sorte que la longueur de la séquence peut être déterminée sans examiner les octets suivants ;

- les bits restants (indiqués par des x dans le tableau ci-dessus) sont utilisés par le point de code en cours de codage, potentiellement précédé par des 0 si nécessaire ;

- les codes composés d'un seul octet, les premiers octets d'une séquence et les octets de continuation (octets suivants le premier octet d'une séquence de plusieurs octets) ne peuvent pas être confondus. En utilisant différents patterns de reconnaissance, il est donc possible d'identifier le type d'un octet, ce qui permet notamment d'identifier des chaînes incorrectes et d'ignorer les erreurs (si le flux provient du réseau par exemple), d'avancer ou reculer d'un caractère Unicode à la fois sans itérer sur chaque octet, etc.

Si l'on prend par exemple le caractère œ (U+0153) :

1. Le point de code étant compris entre U+0080 et U+07FF il sera codé sur deux octets, dont 11 bits sont réservés au point de code ;

2. 0x153 correspond en binaire à 0001 0101 0011, les 6 derniers bits (01 0011) composeront le second octet, et les bits 2 à 6 (001 01) composeront le premier. Le premier bit (0) est quant à lui ignoré ;

3. En partant du modèle 110xxxxx 10xxxxxx, nous remplaçons les x par les valeurs calculées dans le point 2 ce qui donne 1100 0101 1001 0011 ou 0x12 0x05 0x09 0x03.

La spécification du standard est disponible à l'adresse suivante : http://www.ietf.org/rfc/rfc3629.txt

XI-D-3-a - Codage trop long

La norme précise que le codage correct d'un point de code, doit utiliser uniquement le nombre minimum d'octets nécessaires pour contenir les bits significatifs du point de code. Cette règle permet de garder une correspondance un à un entre les points de code et de leur codage, de sorte qu'il existe un codage valable unique pour chaque point de code. Permettre plusieurs codages rendrait les tests d'égalité entre les chaînes de caractères plus compliqués à définir.

XI-D-4 - UTF-8 modifié

Les différences entre l'UTF-8 et l'UTF-8 modifié sont les suivantes :

- le caractère NULL est codé en utilisant le format sur 2 octets, de fait les chaînes de caractères ne contiennent jamais le caractère NULL, ce qui leur permet d'être traitées par des fonctions traditionnelles pour lesquelles le caractère NULL est un marqueur de fin de chaîne ;

- seulement les formats sur 1, 2 et 3 octets sont utilisés ;

- les caractères supplémentaires sont codés en codant séparément les unités de code de leur représentation UTF-16. Chaque demi-zone d'indirection (unité de code) est représentée sur 3 octets, et donc un caractère supplémentaire est codé sur 6 octets.

Le codage d'un caractère supplémentaire a pour modèle :

1. // Unité de code 1

2. 1110aaaa 10bbxxxx 10xxxxxx

4. // Unité de code 2

5. 1110aaaa 10ccxxxx 10xxxxxx

7. où aaaa = 1101 = 0xD

8. bb = 10 puisque correspondant à une valeur entre Ox8 et 0xB

9. cc = 11 puisque correspondant à une valeur entre OxC et 0xF

Pour rappel, la zone d'indirection haute est comprise entre 0xD800 et 0xDBFF et la zone d'indirection basse entre 0xDC00 et 0xDFFF.

XI-D-5 - BOM

Le BOM ou Byte Order Mark (indicateur de l'ordre des octets) est un caractère Unicode utilisé pour signaler le boutisme (ordre des octets) d'un fichier texte ou un flux. Il a pour point de code U+FEFF. L'utilisation du BOM étant facultative, s'il est utilisé, il doit être présent au début du flux. Au-delà de son utilisation spécifique comme un indicateur d'ordre des octets, le BOM permet aussi d'indiquer, la transformation Unicode utilisée.

XI-D-5-a - UTF-8

L'UTF-8 peut contenir un BOM, cependant, il n'est ni requis de l'utiliser, ni recommandé. En UTF-8 les caractères étant interprétés comme une séquence d'octets, le boutisme n'a aucun impact. Le BOM est utilisé comme une signature, indiquant qu'un fichier est codé en UTF-8.

XI-D-5-b - UTF-16 et UTF-32

En UTF-16 (et UTF-32), le BOM peut être placé au début d'un flux pour indiquer le boutisme de toutes les unités de code de 16 bits (32 pour l'UTF-32) du flux.

- Si les unités de 16 bits sont représentées dans l'ordre big-endian, le caractère BOM apparaîtra dans la séquence d'octets 0xFE suivie par 0xFF.

- Si les unités de 16 bits sont représentées dans l'ordre little-endian, la séquence d'octets sera 0xFF suivis par 0xFE.

En résumé

Codage

Représentation

UTF-8

EF BB BF

UTF-16 Big Endian

FE FF

UTF-16 Little Endian

FF FE

UTF-32 Big Endian

00 00 FE FF

UTF-32 Little Endian

FF FE 00 00

XI-E - Longueur d'une chaîne de caractères

Calculer la longueur d'une chaîne de caractères Unicode ou trouver la position d'un caractère peut s'avérer un peu compliqué, car il existe quatre approches différentes auxquelles s'ajoute le risque de confusion causé par la combinaison des caractères. Le choix de la méthode de comptage à utiliser dépendra donc de ce qui doit être compté et de l'utilisation du résultat.

Chacune des quatre approches est illustrée à l'aide de la chaîne de caractères suivante : U+0061 U+0928U+093F U+4E9C U+10083 . Cette chaîne de caractères se compose :

- de la lettre minuscule latine a (U+0061) ;

- suivie par la syllabe Devanagari « ni » (qui est représenté par la syllabe « na » et la combinaison caractère voyelle « i ») (U+0928, U+093F) ;

- suivie d'un idéogramme commun Han (U+4E9) ;

- et enfin d'un idéogramme en linéaire B signifiant un « équidé » (U+10083) :

Nous pouvons compter les choses suivantes :

1. Des octets ;

2. Des unités de code ;

3. Des points de code ;

4. Des graphèmes.

1. Connaître le nombre d'octets d'une chaîne de caractères peut être nécessaire si l'on souhaite savoir la taille qu'elle prend en mémoire.

Voyons le détail pour les codages UTF-8, UTF-16 et UTF-32 :

Codage

Nombre d'octets

Séquence d'octets

UTF-8

14

61 E0 A4 A8 E0 A4 BF E4 BA 9C F0 90 82 83

UTF-16

12

00 61 09 28 09 3F 4E 9C D8 00 DC 83

UTF-32

20

00 00 00 61 00 00 09 28 00 00 09 3F 00 00 4E 9C 00 01 00 83

2. Connaître le nombre d'unités de code d'une chaîne de caractères peut être nécessaire lorsque l'on indique la taille d'un tableau de caractères ou l'on souhaite avoir la position d'un caractère. En considérant que la taille du type du caractère est égale à la taille d'une unité de code.

Voyons le détail pour les codages UTF-8, UTF-16 et UTF-32 :

Codage

Nombre d'unités de code

Séquence d'octets

UTF-8

14

61 E0 A4 A8 E0 A4 BF E4 BA 9C F0 90 82 83

UFT-16

6

0061 0928 093F 4E9C D800 DC83

UTF-32

5

00000061 00000928 0000093F 00004E9C 00010083

3. Il peut être parfois utile de connaître le nombre de points de code quel que soit l'encodage. À noter qu'en UTF-32 le comptage du nombre de points de code dans une chaîne de caractères est identique à celui du nombre d'unités de code.

L'exemple contient 5 points de code, U+0061, U+0928, U+093F, U+4E9C et U+10083.

4. La dernière chose que l'on puisse compter est le nombre de graphèmes (caractères perçus par l'utilisateur). Dans notre exemple, la syllabe Devanagari « ni » doit être composé en utilisant un caractère de base « na » (न), suivi par une voyelle combinant le son « i » (ि), bien que les utilisateurs finals voient et pensent de la combinaison des deux (नि) comme une seule unité de texte. En ce sens, la chaîne d'exemple peut être considérée comme contenant 4 « caractères ».

XI-F - Manipulation de chaînes de caractères en Java

En Java, la façon la plus commune d'assigner une chaîne de caractères à une variable s'effectue de la manière suivante :

1. final String s1 = "abcdefghij";

Mais il est aussi possible d'instancier la classe String :

1. final String s2 = new String("abcdefghij");

Néanmoins, lors de la compilation en bytecode, le premier cas sera traduit par une simple instruction ldc (ou ldc_wen fonction du contexte), alors que le second nécessitera l'utilisation d'instructions relatives à l'instanciation de classes (instructions que nous verrons prochainement).

Vérifions que les deux chaînes sont bien égales :

1. @Test

2. public void stringEquality0() {

3. final String s1 = "abcdefghij";

4. final String s2 = new String("abcdefghij");

6. Assert.assertEquals(s1, s2);

7. }

Source

Nous pouvons aussi préciser le codage de la chaîne de caractères :

1. final String s2 = new String("abcdefghij".getBytes(), "UTF-8");

Une fois de plus, un test unitaire nous confirme l'égalité de deux chaînes :

1. @Test

2. public void stringEquality1() throws UnsupportedEncodingException {

3. final String s1 = "abcdefghij";

4. final String s2 = new String("abcdefghij".getBytes(), "UTF-8");

6. Assert.assertEquals(s1, s2);

7. }

Source

Mais attention. Instancier une chaîne de caractères en précisant un codage, ne va pas convertir la chaîne dans le codage indiqué :

1. @Test

2. public void stringEquality2() throws UnsupportedEncodingException {

3. final String s1 = "abcdefghij";

4. final String s2 = new String("abcdefghij".getBytes(), "UTF-16");

6. Assert.assertFalse(s1.equals(s2));

7. }

Source

À présent, s1 et s2 ne sont plus égaux. Essayons de voir pourquoi, en affichant chaque caractère de chacune des chaînes :

1. @Test

2. public void stringEquality3() throws UnsupportedEncodingException {

3. final String s1 = "abcdefghij";

4. final String s2 = new String("abcdefghij".getBytes(), "UTF-16");

6. System.out.println("---- s1 ----");

8. for(char c : s1.toCharArray()) {

9. System.out.print(c + " ");

10. }

12. System.out.println("\n---- s2 ----");

14. for(char c : s2.toCharArray()) {

15. System.out.print(c + " ");

16. }

17. }

Source

Le test précédent affiche :

---- s1 ----
a b c d e f g h i j
---- s2 ----
慢 捤 敦 杨 楪

Note : s2 peut être représenté de manière différente en fonction de l'environnement d'exécution.

Les caractères de s1 sont donc bien affichés, contrairement à ceux de s2. Mais ceci ne démontre pas grand-chose. Pour prouver que s2, n'a pas été converti en UTF-16, nous devons récupérer le point de code de chaque caractère :

1. @Test

2. public void stringEquality4() throws UnsupportedEncodingException {

3. final String s1 = "abcdefghij";

4. final String s2 = new String("abcdefghij".getBytes(), "UTF-16");

6. System.out.println("---- s1 ----");

8. for(int i = 0; i < s1.length(); i++) {

9. final int codePoint = s1.codePointAt(i);

10. System.out.print(codePoint + " ");

11. }

13. System.out.println("\n---- s2 ----");

15. for(int i = 0; i < s2.length(); i++) {

16. final int codePoint = s2.codePointAt(i);

17. System.out.print(codePoint + " ");

18. }

19. }

Source

Le résultat du test est le suivant :

---- s1 ----
97 98 99 100 101 102 103 104 105 106
---- s2 ----
24930 25444 25958 26472 26986

Sans surprise, les points de code de la chaîne s1 sont corrects et ceux de s2 ne le sont pas.

Pourquoi ? Avant de rentrer dans les détails, faisons un dernier test. Il serait intéressant de savoir ce que retourne la méthode getBytes().

1. @Test

2. public void stringEquality5() throws UnsupportedEncodingException {

3. final String s1 = "abcdefghij";

4. final String s2 = new String("abcdefghij".getBytes(), "UTF-16");

6. System.out.println("---- s1 ----");

8. for(byte b : s1.getBytes()) {

9. System.out.print(this.byteToHex(b) + " ");

10. }

12. System.out.println("\n---- s2 ----");

14. for(byte b : s2.getBytes()) {

15. System.out.print(this.byteToHex(b) + " ");

16. }

17. }

Source

Le test affiche :

---- s1 ----
61 62 63 64 65 66 67 68 69 6A
---- s2 ----
E6 85 A2 E6 8D A4 E6 95 A6 E6 9D A8 E6 A5 AA

où s2 peut avoir une forme différente en fonctionnement de l'environnement d'exécution. Si s2 avait été converti en UTF-16, nous aurions eu :

00 61 00 62 00 63 00 64 00 65 00 66 00 67 00 68 00 69 00 6A

Finalement, qu'avons-nous démontré ? La réponse ne peut être plus simple. Nous n'avons absolument rien démontré, nous n'avons fait qu'accumuler les erreurs, et ceci, depuis le second exemple. Preuve qu'un mauvais test peut laisser à penser que du code est correct alors que l'on se trompe complètement.

Reprenons tout depuis le début en mettant le code de côté et en nous focalisant sur le compilateur, la JVM et la plate-forme.

Tout fichier texte est codé dans un système de codage. Les fichiers source Java n'échappent pas à cette règle. De fait, il est impératif de préciser au compilateur le codage des fichiers .java. Il va sans dire que toutes les sources (fichiers .java) d'une même application (ou bibliothèque) doivent avoir le même codage.

En utilisant javac, nous avons à notre disposition l'option -encoding (tous les outils de construction permettent aussi d'indiquer le codage qui sera utilisé par le compilateur, comme cela a été fait dans le fichier macros.xml que nous utilisons) :

1. javac -encoding UTF-8 MyFile.java

Note : la casse n'a pas d'importance et le tiret de séparation entre un système de codage et le nombre qui le suit est optionnel. Les valeurs UTF8, utf-8 et utf8 sont aussi valides.

Vous trouverez tous les codages supportés par Java sur le site d'Oracle.

En indiquant un type de codage des fichiers source, le compilateur est à même de convertir toutes les chaînes de caractères en UTF-8 modifié. Puisqu'il faut garder à l'esprit que d'une manière générale, déterminer le type de codage d'un fichier sans aucune information est quasiment impossible, surtout lorsque l'on peut en utiliser plusieurs. Concernant javac, si l'option -encoding n'est pas précisée, il utilise le codage du système d'exploitation sur lequel il est exécuté, c'est-à-dire UTF-8 pour la plupart des OS Linux récents et FreeBSD, CP-1252 pour les versions occidentales de Windows, etc.

De fait, laisser le compilateur choisir le codage des fichiers sources est plus que déconseillé.

Le fait que toutes les chaînes de caractères d'un fichier .class soient codées en UTF-8 modifié, permet d'avoir un fichier de taille réduite, ce qui à l'origine de Java était une nécessité. En effet, comme nous l'avons vu dans le premier article de la série (Part 0 - Sneak Peek) l'un des intérêts de Java était de pouvoir exécuter des fichiers compilés envoyés au travers du réseau - comme c'est le cas des Applets - or à la fin des années 90, les connexions Internet étant lentes, il fallait minimiser la taille d'une application au minimum.

De plus, le fait de n'avoir qu'un seul type de codage permet à la JVM, de ne pas se poser de questions lorsqu'elle charge des fichiers .class. Comme mentionné dans l'introduction, les chaînes de caractères codées en UTF-8 modifié dans un fichier .class sont converties à UTF-16 par la JVM. Nous y reviendrons. Mais avant, repartons du second exemple.

La chaîne de caractères "abcdefghij" est égale à new String("abcdefghij".getBytes(), "UTF-8") :

- puisque tous les fichiers de notre projet sont en UTF-8. Si nous utilisions un autre codage, le test serait en erreur ;

- mais aussi, car nous utilisons des caractères dont le point de code est inférieur à 8 bits. Or presque tous les systèmes de codage (ne les connaissant pas tous et dans le doute, nous considérerons que cette règle ne s'applique pas à tous les systèmes de codage) ont les mêmes 128 premiers caractères. De plus, hormis l'UTF-16 et l'UTF-32, les types de codage pour la majorité des systèmes d'écriture occidentaux codent les caractères sur 1 octet. De fait, sous Windows, pour la chaîne la méthode "abcdefghij", la méthode getBytes() retourne un tableau de bytes ayant les mêmes valeurs que sous Linux, et ceci, bien que Windows et Linux n'utilisent pas le même codage par défaut. Mais pourquoi est-il question du codage du système d'exploitation ? La réponse se trouve dans la javadoc de la méthode getBytes() : « Code cette String en une séquence d'octets en utilisant le codage par défaut de la plate-forme, en stockage le résultat dans un nouveau tableau de bytes ». Tout comme l'option -encoding du compilateur, il est judicieux de passer en paramètre de la méthode getBytes() le type de codage dans lequel nous souhaitons que la chaîne de caractères soit convertie : getBytes(« UTF-8 »).

Si nous résumons, notre chaîne de caractères est codée en UTF-8 modifié dans le fichier .class, puis convertie en UTF-16 par la JVM. Lorsque nous appelons la méthode getBytes("UTF-8"), elle est encodée en UTF-8 puis transformée en tableau de bytes. Tout ceci nous permet d'instancier une classe String en utilisant le tableau de bytes et le codage « UTF-8 ».

Avec nos nouvelles connaissances, nous pouvons donc réécrire la méthode stringEquality2() :

1. @Test

2. public void stringEquality6() throws UnsupportedEncodingException {

3. final String s1 = "abcdefghij";

4. final String s2 = new String("abcdefghij".getBytes("UTF-16"), "UTF-16");

6. Assert.assertTrue(s1.equals(s2));

7. }

Source

Passons rapidement en revue les autres exemples.

Lorsque l'on exécute la méthode stringEquality3(), les caractères de s2 correspondent aux caractères ayant pour point de code les valeurs affichées par la méthode stringEquality4(). Le tableau de bytes ayant été utilisé pour créer s2 étant considéré comme étant codé en UTF-16, chaque paire i et i+1 est considérée comme un caractère. Par exemple :

1. 0x61 << 8 | 0x62 = 24930

Et pour finir, si la méthode stringEquality5() n'affiche pas les bonnes valeurs hexadécimales, c'est que nous appelons getBytes() (sous Windows, dont le codage par défaut est CP-1252) sur une chaîne s2 qui est - mal - codée en UTF-16.

1. @Test

2. public void stringEquality7() throws UnsupportedEncodingException {

3. final String s1 = "abcdefghij";

4. final String s2 = new String("abcdefghij".getBytes("UTF-8"), "UTF-16");

6. System.out.println("---- s1 ----");

8. for (byte b : s1.getBytes("UTF-8")) {

9. System.out.print(this.byteToHex(b) + " ");

10. }

12. System.out.println("\n---- s2 ----");

14. for (byte b : s2.getBytes("UTF-16")) {

15. System.out.print(this.byteToHex(b) + " ");

16. }

17. }

Source

Le test affiche :

---- s1 ----
61 62 63 64 65 66 67 68 69 6A
---- s2 ----
FE FF 61 62 63 64 65 66 67 68 69 6A

Avant de conclure, revenons sur le fait que la JVM manipule des chaînes en UTF-16.

Mentionnons tout d'abord que c'est pour cette raison que le type char a une taille de 2 octets.

1. char c = '\u03F4';

Note : la notation \uXXXX permet d'écrire en Java, un caractère ou une chaîne de caractères sous forme d'une séquence de points de code.

Si vous vous souvenez de ce que l'on a vu précédemment concernant les caractères codés en UTF-16, ils tiennent sur 2 ou 4 octets. C'est dans ces moments qu'on se rend compte que les bons/mauvais choix ne se jouent qu'à un fil. Java a été créé en 1991 et la version première publique date de 1995. Un an plus tard, la version 2 d'Unicode sort et les caractères ne sont plus limités à 16 bits (2 octets). Ceci a en réalité très peu d'impact pour la majorité des cas, puisqu'il est assez rare d'utiliser des caractères n'appartenant pas au Plan Multilingue de Base. Mais il est tout de même bon de savoir :

- qu'il n'est pas possible d'écrire char c = '\u10083'; ou tout point de code supérieur à 0xffff ;

- et que "\u10083".length() retourne 2 et non 1.

Néanmoins, la classe Character permet de manipuler - plus ou moins simplement - les caractères des plans supplémentaires.

XI-G - What's next ?

Si vous souhaitez en savoir plus sur l'Unicode, la spécification et la FAQ sont les points d'entrée à consulter en priorité.

Concernant Java, il y a encore beaucoup à dire. Mais le principe est le suivant :

- toutes les constantes de type chaînes de caractères ne doivent pas être instanciées en utilisant les constructeurs String(…), à moins d'avoir une très bonne raison ;

- ne jamais utiliser le codage de la plate-forme sous peine d'avoir de gros soucis ;

- la conversion d'une chaîne de caractères ou l'indication du type de codage d'un flux d'octets, ne doivent être faites que dans deux situations : (1) à la réception d'un flux et (2) à l'envoi d'un flux (réception et envoi, s'appliquent à un fichier, des données venant du réseau, etc.), en d'autres termes, un flux externe à l'application. À noter que pour le XML et le JSON, il n'y a pas à se soucier du type de codage, les nombreuses bibliothèques existantes (permettant de convertir un flux en objet Java) s'en chargent pour vous.

Mais nous aurons l'occasion d'y revenir dans de prochains articles de la série.

XII - ClassFile

Après plusieurs chapitres de détours, nous allons enfin reprendre notre périple dans l'univers du bytecode. Si l'ensemble des articles précédents ont bien été compris, créer un assembleur de bytecode ne sera qu'une simple formalité. Aujourd'hui, nous allons nous intéresser au format d'un fichier .class ce qui nous permettra de créer un assembleur simplifié (tel que celui que nous avons utilisé jusqu'à présent). Bien que simplifié, pour implémenter un tel assembleur nous avons besoin de comprendre 70 % (au doigt mouillé) du format d'un fichier .class décrit dans la JVMS et c'est à quoi nous allons nous atteler au cours de cet article.

Le code est disponible sur Github (tag et branche).

XII-A - ClassFile

La JVMS définit un format binaire appelé le fichier class, qui représente une classe en tant qu'un flux d'octets. Mais le terme fichier class est trompeur puisqu'il n'y a pas d'obligation à ce que les données au format fichier class soient stockées dans un fichier. Elles peuvent être stockées dans une base de données, en mémoire, etc.

Un fichier .class peut être représenté par la classe Java suivante :

public class ClassFile {
int magic;
short minorVersion;
short majorVersion;
short constantPoolCount;
ConstantPoolEntry[] constantPool;
short accessFlags;
short thisClass;
short superClass;
short interfacesCount;
short[] interfaces;
short fieldsCount;
Field[] fields;
short methodsCount;
Method[] methods;
short attributesCount;
Attribute[] attributes;
}

Source (À noter que toutes les sources de cet article sont légèrement différentes de manière à suivre les principes de base de la programmation objet.)

où les types byte, short et int doivent être considérés comme des nombres non signés. Dans la JVMS ces trois types sont représentés respectivement sous les types u1, u2 et u4, où u signifie unsigned (non signé) et le chiffre indique le nombre d'octets.

Dans cet article nous allons faire l'impasse sur les champs suivants :

short[] interfaces;
Field[] fields;
Attribute[] attributes;

On considérera que leur champ associé - indiquant la taille des tableaux - aura pour valeur 0.

short interfacesCount;
short fieldsCount;
short attributesCount;

De plus, les types ConstantPoolEntry et Method ne seront étudiés que partiellement. Nous compléterons le détail d'un fichier .class au fil des articles suivants.

Avant de commencer à décrire l'utilité et l'utilisation des champs, il est important de noter que la génération d'un fichier .class consiste à ajouter tous les champs de la classe ClassFile et de toutes les classes du graphe d'objets, dans l'ordre, sous la forme d'octets, d'où le nom bytecode. Dans l'API Java, ce format est supporté par les interfaces java.io.DataInput et java.io.DataOutput, et des classes telles que java.io.DataInputStream et java.io.DataOutputStream.

En nous limitant aux quatre premiers champs, nous pouvons générer un fichier .class de la manière suivante :

DataOutputStream dos = new DataOutputStream(/*...*/);
dos.writeInt(this.magic);
dos.writeShort(this.minorVersion);
dos.writeShort(this.majorVersion);
dos.writeShort(this.constantPoolCount);

XII-A-1 - magic

Le champ magic permet d'identifier un fichier comme étant un fichier .class. Il a toujours pour valeur 0xCAFEBABE. Nous pouvons donc écrire :

final int magic = 0xCAFEBABE;

XII-A-2 - minorVersion et majorVersion

Les champs minorVersion et majorVersion indiquent le numéro de version du fichier .class. La JDK 1.0.2 supporte les versions comprises dans l'intervalle [45.0; 45.3], la JDK 1.1.* dans l'intervalle [45.0; 45.65536] et les JDK 1.k supportent les versions dans l'intervalle [45.0; 44+k.0] où k >= 2.

Par exemple, la JDK7 supporte les versions de fichiers .class comprises dans l'intervalle [45.0; 51.0].

Or comme mentionné dans la partie 3 (Part 3 - Bytecode - Constantes), nous allons nous concentrer sur Java 1.4 (version 48.0), nous pouvons rassembler les deux champs par un seul (version) :

// 48 = 0x00 (version mineure) | 0x30 (version majeure)
final private short version = 0x30;

0x30 étant une valeur littérale inférieure à 32 767 nous n'avons pas besoin de la caster pour l'assigner à un short. Néanmoins, comme nous l'avons déjà vu, la JVM préfère manipuler des int. Par conséquent, rien ne nous empêche d'écrire :

final private int version = 0x30;

Il suffira de ne pas oublier, lors de la génération du fichier classe, d'appeler la méthode writeShort() de la classe DataOutputStream, et non writeInt().

XII-A-3 - constantPoolCount et constantPool

La partie suivante est assez particulière. Elle représente un pool de constantes et n'a aucun équivalent en Java. Elle a pour but de rassembler toutes les constantes présentes dans le code, comme le nom d'une classe ou d'une méthode, des littérales et des valeurs de constantes définies dans le code.

Le tableau constantPool est indexé de 1 à constantPoolCount - 1. L'index 0 est réservé pour l'utilisation de la JVM.

Chaque classe peut avoir jusqu'à 65 535 entrées dans son pool de constantes.

La classe ConstantPoolEntry a le format suivant :

ConstantPoolEntry {
byte tag;
byte[] info;
}

Le champ tag correspond au type de constante. Pour la JDK 1.4, il existe 11 tags différents, numérotés de 1 à 12 (2 n'étant pas utilisé).

Type de constante

Valeur

ConstantUtf8

1

ConstantInteger

3

ConstantFloat

4

ConstantLong

5

ConstantDouble

6

ConstantClass

7

ConstantString

8

ConstantFieldref

9

ConstantMethodref

10

ConstantInterfaceMethodref

11

ConstantNameAndType

12

Ces tags peuvent être représentés en Java sous la forme d'une énumération :

public static enum ConstantPoolTag {
UTF8(1),
INTEGER(3),
FLOAT(4),
LONG(5),
DOUBLE(6),
CLASS(7),
STRING(8),
FIELDREF(9),
METHODREF(10),
INTERFACE_METHODREF(11),
NAME_AND_TYPE(12);

private int value;

private ConstantPoolTag(int value) {
this.value = value;
}

public int getValue() {
return this.value;
}
}

Source

Le contenu du tableau d'octets info varie en fonction du type de tag. Nous allons donc créer une classe par type de constantes, avec une classe parente contenant le tag.

public static abstract class ConstantPoolEntry {
final private int tag;

public ConstantPoolEntry(ConstantPoolTag tag) {
this.tag = tag.getValue();
}
}

Source

XII-A-3-a - ConstantUtf8

Le type de constante le plus commun est le type UTF-8. La classe ConstantUtf8 est utilisée pour stocker le nom des packages, des classes, des champs, des méthodes et les littérales, mais aussi du texte ajouté lors de la génération des fichiers .class et utilisé par la JVM.

Les deux premiers octets correspondent à la taille de la chaîne de caractères (le nombre d'octets en UTF-8 modifié), les autres, la chaîne de caractères codée en UTF-8.

public class ConstantUTF8 {
int tag = 0x01;
int length;
byte[] string;
}

La méthode writeUTF() de la classe DataOutputStream permet de transformer des chaînes de caractères codées en UTF-16 en UTF-8 modifié, en la faisant précéder par la taille de la chaîne.

Nous pouvons donc modifier la classe ConstantUTF8 de la manière suivante :

public static class UTF8 extends ConstantPoolEntry {
final private java.lang.String value;

public UTF8(final java.lang.String value) {
super(ConstantPoolTag.UTF8);
this.value = value;
}
}

Source

XII-A-3-b - ConstantInt et ConstantFloat

Les classes ConstantInt et ConstantFloat permettent de stocker des constantes de types int et float.

public class ConstantInt {
int tag = 0x03;
int value;
}

public class ConstantFloat {
int tag = 0x04;
int value;
}

En suivant notre modélisation, les classes sont définies de la manière suivante :

public static class Integer extends ConstantPoolEntry {
final private int integer;

public Integer(int integer) {
super(ConstantPoolTag.INTEGER);
this.integer = integer;
}
}

public static class Float extends ConstantPoolEntry {
final private float floatValue;

public Float(float floatValue) {
super(ConstantPoolTag.FLOAT);
this.floatValue = floatValue;
}
}

Source

XII-A-3-c - ConstantLong et ConstantDouble

Les classes ConstantLong et ConstantDouble permettent de stocker des constantes de types long et double.

public class ConstantLong {
int tag = 0x05;
long value;
}

public class ConstantDouble {
int tag = 0x06;
long value;
}

Toutes les constantes dont les valeurs ont pour taille 8 octets prennent deux entrées du tableau constantPool d'un fichier .class. Si les constantes ConstantLong ou ConstantDouble sont présentes dans le tableau constantPool à l'index n, alors le prochain élément utilisable se trouve à l'index n+2. L'index n+1 est considéré comme inutilisable.

public static class Long extends ConstantPoolEntry {
final private long longValue;

public Long(long longValue) {
super(ConstantPoolTag.LONG);
this.longValue = longValue;
}
}

public static class Double extends ConstantPoolEntry {
final private double doubleValue;

public Double(double doubleValue) {
super(ConstantPoolTag.DOUBLE);
this.doubleValue = doubleValue;
}
}

Source

XII-A-3-d - ConstantString

La classe ConstantString permet d'indiquer qu'une chaîne de caractères est une constante. Elle contient l'index d'un objet de type ConstantUTF8 dans le tableau de ConstantPoolEntry.

Il ne faut donc pas confondre la classe ConstantString qui pointe vers une instance de la classe ConstantUTF8, avec la classe ConstantUTF8 qui contient la chaîne de caractères.

Sans rentrer dans le détail, lorsque nous utilisons l'instruction ldc suivie d'une chaîne de caractères :

ldc "Hello World"

nous procédons de la manière suivante :

- nous créons un objet de type ConstantUTF8 contenant la valeur "Hello World" ;

- nous ajoutons cet objet au tableau de type ConstantPoolEntry et récupérons l'index associé ;

- nous créons un objet de type ConstantString contenant l'index l'objet de type ConstantUTF8 précédemment créé ;

- nous ajoutons cet objet au tableau de type ConstantPoolEntry et récupérons l'index associé ;

- nous associons l'instruction ldc à l'index précédent.

La structure de la classe ConstantString est la suivante :

public class ConstantString {
int tag = 0x08;
short utf8Index;
}

ou selon notre modèle :

public static class String extends ConstantPoolEntry {
final private int utf8Index;

public String(int stringIndex) {
super(ConstantPoolTag.STRING);
this.utf8Index = stringIndex;
}
}

Source

XII-A-3-e - ConstantClass

La classe ConstantClass s'utilise de la même manière que la classe ConstantString. Elle stocke l'index d'un objet de type

ConstantUTF8

dans le tableau de ConstantPoolEntry qui lui contient le nom complètement qualifié d'une classe, tel que java/lang/Object, ou puisqu'un tableau est un objet la valeur [[I.

La structure de la classe est la suivante :

public class ConstantClass {
int tag = 0x07;
short utf8Index;
}

ou selon notre modèle :

public static class Class extends ConstantPoolEntry {
final private int nameIndex;

public Class(final int nameIndex) {
super(ConstantPoolTag.CLASS);
this.nameIndex = nameIndex;
}
}

Source

XII-A-3-f - Les quatre derniers tags

Pour l'instant nous n'avons pas besoin de nous soucier des quatre autres tags. Nous les étudierons le moment venu.

XII-A-4 - accessFlags

Le champ accessFlags permet d'indiquer l'ensemble des modificateurs d'une classe à l'aide de masques. En d'autres termes chaque bit correspond à un type de modificateur sachant que plusieurs peuvent être utilisés en même temps, mais que certaines combinaisons sont impossibles.

Nom du flag

Valeur

Mot clé Java

ACC_PUBLIC

0x0001

public

ACC_FINAL

0x0010

final

ACC_SUPER

0x0020

-

ACC_INTERFACE

0x0200

interface

ACC_ABSTRACT

0x0400

abstract

La représentation sur 2 octets est la suivante :

0000 a0b0 00cd 000e

où :

a = 0x0400 = 0000 1000 0000 0000 (ACC_ABSTRACT)
b = 0x0200 = 0000 0010 0000 0000 (ACC_INTERFACE)
c = 0x0020 = 0000 0000 0010 0000 (ACC_SUPER)
d = 0x0010 = 0000 0000 0001 0000 (ACC_FINAL)
e = 0x0001 = 0000 0000 0000 0001 (ACC_PUBLIC)

Quelques règles :

- une interface est distinguée d'une classe à l'aide du flag ACC_INTERFACE ;

- si le flag ACC_INTERFACE est à 1, il doit obligatoirement être accompagné des flags ACC_PUBLIC et ACC_ABSTRACT et les autres ne doivent pas être renseignés ;

- si le flag ACC_INTERFACE est à 0, tous les autres peuvent être utilisés. Néanmoins, les flags ACC_ABSTRACT et ACC_FINAL ne peuvent pas être utilisés en même temps ;

- le flag ACC_SUPER est un artefact du passé lié à l'instruction invokespecial. Tous les nouveaux compilateurs/assembleurs doivent le renseigner.

Dans la version de pjba que nous utilisons actuellement, il est impossible de préciser les modificateurs d'une classe. Le champ accessFlags a pour valeur 0x0021 :

0x0001 | 0x0020 // public super

XII-A-5 - thisClass

Le champ thisClass contient l'index de l'objet de type ConstantClass dans le tableau de PoolConstantEntry pointant (par un index dans le tableau de PoolConstantEntry) vers l'objet de type ConstantUtf8 contenant le nom complètement qualifié de la classe.

XII-A-6 - superClass

Le champ superClass contient l'index de l'objet de type ConstantClass dans le tableau de PoolConstantEntry pointant (par un index dans le tableau de PoolConstantEntry) vers l'objet de type ConstantUtf8 contenant le nom complètement qualifié de la classe parente de la classe courante.

En Java, une classe n'héritant pas explicitement (à l'aide du mot clé extends) d'une autre, hérite implicitement de la classe java.lang.Object. Dans un fichier .class tout étant indiqué explicitement, nous aurons toujours une super classe. La seule classe pouvant avoir le champ superClass égal à zéro est la classe Object.

XII-A-7 - methodsCount et methods

Le champ methodsCount indique le nombre de méthodes définies dans le fichier .class (tout simplement la taille du tableau methods) et le champ methods est un tableau de méthodes de type Method dont la structure peut être représentée de la manière suivante :

public class Method {
short accessFlags;
short nameIndex;
short descriptorIndex;
short attributesCount;
Attribute[] attributes;
}

Source

XII-B - Method

XII-B-1 - accessFlags

Tout comme le champ accessFlags dans la classe ClassFile, celui-ci permet d'indiquer les modificateurs d'une méthode à l'aide de masques.

Nom du flag

Valeur

Mot clé Java

ACC_PUBLIC

0x0001

public

ACC_PRIVATE

0x0002

private

ACC_PROTECTED

0x0004

protected

ACC_STATIC

0x0008

static

ACC_FINAL

0x0010

final

ACC_SYNCHRONIZED

0x0020

synchronized

ACC_NATIVE

0x0100

native

ACC_ABSTRACT

0x0400

abstract

ACC_STRICT

0x0800

strictfp

Quelques règles :

- une méthode ne peut avoir que l'un des flags suivants à 1 à la fois : ACC_PRIVATE, ACC_PROTECTED ou ACC_PUBLIC ;

- une méthode ayant le flag ACC_ABSTRACT à 1, ne peut avoir aucun des flags suivants : ACC_FINAL, ACC_NATIVE, ACC_PRIVATE, ACC_STATIC, ACC_STRICT, ou ACC_SYNCHRONIZED ;

- une méthode d'interface doit uniquement avoir les flags suivants à 1 : ACC_ABSTRACT et ACC_PUBLIC.

XII-B-2 - nameIndex

Le champ nameIndex contient l'index de l'objet de type ConstantUtf8 dans le tableau ConstantPoolEntry contenant le nom de la méthode. Par exemple add.

XII-B-3 - descriptorIndex

Le champ descriptorIndex contient l'index de l'objet de type ConstantUtf8 dans le tableau ConstantPoolEntry contenant le nom du descripteur de la méthode. Par exemple (I[[Lorg/isk/pjb/Test;Z)V.

XII-B-4 - attributesCount et attributes

Le champ attributesCount indique la taille du tableau attributes et le champ attributes est un tableau de type Attribute dont la structure peut être représentée de la manière suivante :

public class Attribute {
short nameIndex;
int attributeLength;
byte[] info;
}

Source (Dans le code, la classe Attribute est abstraite et n'a pas de champ info.)

XII-C - Attribute

Nous retrouvons la structure Attribute dans de nombreuses autres :

- ClassFile ;

- Field ;

- Method ;

- Code .

Tout comme les ConstantXxx, il existe de nombreux attributs (9 pour la JDK 1.4), mais tous ne peuvent pas se retrouver dans les quatre structures mentionnées précédemment :

- SourceFile : permet d'indiquer le nom du fichier source ;

- ConstantValue : permet de définir la valeur d'une constante ;

- Code : permet d'indiquer l'ensemble des instructions d'une méthode ;

- Exceptions : permet de définir l'ensemble des exceptions - vérifiées - potentiellement levées par une méthode ;

- InnerClasses : permet de définir une classe interne ;

- Synthetic : permet d'indiquer qu'une classe, un champ ou une méthode, n'existant pas dans le fichier source, a été rajouté par le compilateur ;

- LineNumberTable : permet d'indiquer à quelle ligne du fichier source correspondent un ensemble d'instructions ;

- LocalVariableTable : permet d'attribuer un nom à la valeur présente à un index donné des variables locales ;

- Deprecated : permet d'indiquer qu'une classe, un champ ou une méthode est déprécié.

Aujourd'hui, nous nous intéresserons uniquement à l'attribut Code.

XII-C-1 - Code

L'attribut Code ne peut être présent que dans la structure Method.

L'attribut Code est probablement l'élément le plus important d'un fichier .class puisqu'il contient tous les détails d'implémentation d'une méthode.

Si une méthode est native ou abstraite, l'attribut Code ne doit pas être présent.

public class Code {
short attributeNameIndex;
int attributeLength;
short maxStack;
short maxLocals;
int codeLength;
byte[] code;
short exceptionsCount;
Exception[] exceptions;
short attributesCount;
Attribute[] attributes;
}

Source (Dans le code, la classe Code hérite de la classe Attribute.)

Les champs suivants ne seront pas décrits dans cet article :

short exceptionsCount;
Exception[] exceptions;
short attributesCount;
Attribute[] attributes;

On considérera que leur champ associé - indiquant la taille des tableaux - aura pour valeur 0.

short exceptionsCount;
short attributesCount;

XII-C-1-a - attributeNameIndex

Le champ attributeNameIndex contient l'index de l'objet de type ConstantUtf8 dans le tableau ConstantPoolEntry contenant le nom du type de l'attribut. Pour l'attribut Code, le nom est « Code ».

XII-C-1-b - attributeLength

Le champ attributeLength indique le nombre d'octets constituant l'attribut, moins les six premiers octets.

Nous pouvons calculer cette valeur de la manière suivante :

2 + 2 + 4 + code.length + 2 + 8 * exceptions.length + 2 + attributes.length

Note : La structure Exception prend 8 octets.

XII-C-1-c - maxStack

Le champ maxStack a pour valeur la taille maximum de la pile du cadre (frame) de la méthode (pour plus d'informations cf. Part 1 - Introduction à la JVM). Nous pourrions utiliser la valeur maximale pouvant être contenue dans un short non signé (0xFFFFFFFF), mais nous ne souhaitons pas consommer de la mémoire inutilement. Par conséquent, il est nécessaire de calculer précisément l'impact de chaque instruction sur la pile. Nous verrons comment faire dans l'article suivant.

XII-C-1-d - maxLocals

Le champ maxLocals a pour valeur la taille maximum des variables locales du cadre de la méthode. Nous verrons aussi comment la calculer dans l'article suivant.

XII-C-1-e - codeLength et code

Le champ codeLength indique la taille du tableau code et le champ code est un tableau de bytes contenant les instructions et leurs arguments si elles en ont.

Chaque opcode d'une instruction tient sur un octet. La taille et le nombre des arguments - des instructions qui en possèdent - sont variables. Sur les 200 instructions, seulement un quart ont des arguments (nous en avons déjà vu une dizaine ldc, bipush, xload, xstore, etc.)

XII-D - What's next

Nous avons à présent un ensemble de classes permettant de modéliser le format d'un fichier .class. Dans l'article suivant, nous verrons comment générer un fichier .class et survolerons l'implémentation d'un analyseur syntaxique de fichiers .pjb.

XIII - Assembleur de bytecode

Voilà quelques chapitres que notre périple dans les tréfonds de la JVM a commencé. Nous avons abordé de nombreux sujets, plus ou moins liés à la JVM. Dans cet article nous allons recréer la bibliothèque PJBA - que nous utilisions jusqu'à présent - nous permettant de générer des fichiers .class à partir d'un fichier texte. Dans l'article suivant, il sera question d'étudier une solution permettant de traverser un arbre syntaxique simplement, et dans celui d'après nous enrichirons la bibliothèque PJBA. Nous pourrons ensuite reprendre notre étude - que nous avions mise de côté - des instructions et des éléments constituant un fichier .class.

Dans la suite de cet article, et sauf mention contraire, le terme variables locales correspondra au tableau des variables locales d'un cadre (frame).

Le code est disponible sur Github (tag et branche).

XIII-A - Tableaux

Dans l'article précédent, nous avons créé un graphe d'objets, tel qu'il est décrit dans la JVMS. Tous les éléments devant être présents dans un fichier .class ont été indiqués. Néanmoins, l'utilisation de tableaux est loin d'être souple ; en les gardant, nous risquons d'avoir plus de problèmes que de solutions. Par conséquent, nous allons supprimer tous les attributs count et length, et remplacer les tableaux par des java.util.LinkedList, ou plus précisément par une classe héritant de LinkedList. Vous en comprendrez la raison avant la fin de l'article.

public class PjbaLinkedList<E> extends LinkedList<E> {

}

Source

À noter que nous ne toucherons pas au champ int[] interfaces de la classe ClassFile, et le champ byte[] code de la classe Code sera modifié un peu plus loin.

XIII-B - Attribute

Dans l'article précédent, nous avons vu que le type Attribute était présent dans la classe ClassFile, Method et Code. Or, tous les attributs ne peuvent pas être utilisés partout. De fait, nous allons créer trois interfaces qui auront pour seul objectif de contraindre le contenu des listes.

public interface ClassAttribute {

}

Source

public interface MethodAttribute {

}

Source

public interface CodeAttribute {

}

Source

Le seul attribut que nous avons vu pour l'instant est Code, qui ne peut être présent que dans une méthode. Modifions la classe en conséquence :

public class Code extends Attribute implements MethodAttribute {

}

Source

XIII-C - Enrichissement des classes

Actuellement, toutes nos classes ont des champs privés et utilisent toutes le constructeur par défaut (un constructeur sans paramètre). À présent, il nous faut pouvoir fixer la valeur de ces champs simplement, sans pour autant transformer nos classes en builder. Cette tâche fera partie du prochain article. Nous allons donc passer en revue tous les champs un par un. Cela peut paraître rébarbatif et répétitif, mais c'est une tâche indispensable pour bien comprendre comment former un fichier .class. Pour une explication détaillée : Format d'un fichier class.

XIII-C-1 - ClassFile

Commençons par tous les champs ayant des valeurs constantes.

final private int magicNumber = 0xcafebabe;
final private int version = 0x30; // 48.0
final private int accessFlags = 0x0001 | 0x0020; // public super

Note : Nous lèverons les limitations de la version et des modificateurs d'une classe très prochainement.

XIII-C-1-a - contantPool

Pour ajouter des constantes dans le pool de constantes, nous allons ajouter une méthode par constante qui prendra les mêmes paramètres que le constructeur de la constante et qui retournera l'index de la constante dans le pool de constantes.

Par exemple pour la constante ConstantUTF8 :

public int getCurrentCPIndex() {
return this.constantPool.size() - 1;
}

public int addConstantUTF8(final String value) {
final Constant.UTF8 constant = new Constant.UTF8(value);
this.constantPool.add(constant);
return this.getCurrentCPIndex();
}

Néanmoins, arrêtons-nous quelques secondes. Si l'on écrit et exécute le test unitaire ci-dessous, nous constatons qu'il est correct :

@Test
public void stringEquality() {
final String s1 = "Bonjour";
final String s2 = "Bonjour";

Assert.assertEquals(s1, s2);
Assert.assertTrue(s1 == s2);
}

Les deux assignations peuvent être traduites en PJB de la manière suivante :

ldc "Bonjour"
astore_0
ldc "Bonjour"
astore_1

Dans un fichier .class, les instructions ldc pointent vers l'index d'une constante de type ConstantString, elle-même pointant vers une constante de type ConstantUTF8. Dans le cas présent, les deux instructions pointeront vers la même constante.

Mais new String("Bonjour") != new String("Bonjour"). Et ceci est aussi valable pour les types numériques :

5 == 5

et

Integer i1 = 5;
Integer i2 = 5;
i1 == i2;

mais

Integer i1 = 5_000;
Integer i2 = 5_000;
i1 != i2;

et

new Integer(5) != new Integer(5)

Nous le savions, Java aime faire les choses simplement et sans surprise…

Pour les types primitifs, nous comparons des valeurs, par conséquent elles sont égales. Jusque-là, rien de très surprenant. En revanche pour les objets les choses sont bien différentes.

Commençons par les objets de type String. Toutes les littérales de type String - dont la chaîne de caractères est identique - ont toujours la même référence quel que soit l'endroit de leur déclaration.

Les littérales numériques sont quant à elles autoboxées. C'est-à-dire que l'assignation Integer i = 5 est compilée en Integer i = Integer.valueOf(5). Or, comme indiqué dans la javadoc, la méthode valueOf() a un cache initialisé au chargement de la classe, contenant des objets de type Integer pour toutes les valeurs comprises entre -128 et 127 (oublions la fin de la phrase « et peut mettre en cache d'autres valeurs hors de cet intervalle »). Ceci explique pourquoi dans le premier cas (pour la valeur 5) deux primitifs autoboxés en Integer sont égaux et dans le second (pour la valeur 5000) ne le sont pas.

Pour le type Long, bien que le système de mise en cache ne soit pas requis, il est bien présent.

En revanche, il n'y a aucun mécanisme similaire pour les types Float et Double.

Néanmoins, il est déconseillé de se reposer sur l'autoboxing/unboxing pour effectuer une comparaison, il est préférable de faire des comparaisons uniquement sur des types primitifs.

Note : les tests présentés ci-dessus peuvent être retrouvés dans la classe suivante : EqualityTest

Nous en venons à la conclusion que dans le pool de constantes d'un fichier .class, chaque constante peut être unique, sans que cela ne pose de problèmes. Il nous faut donc adapter les méthodes addConstantXYZ() en conséquence.

Prenons quelques exemples :

private int addConstant(final ConstantPoolEntry constant) {
final int index = this.constantPool.indexOf(constant);

if (index == -1) {
this.constantPool.add(constant);
return this.getCurrentCPIndex();
} else {
return index;
}
}

public int addConstantUTF8(final String value) {
final Constant.UTF8 constant = new Constant.UTF8(value);
return this.addConstant(constant);
}

public int addConstantString(final int utf8Index) {
final Constant.String constant = new Constant.String(utf8Index);
return this.addConstant(constant);
}

public int addConstantLong(final long value) {
final Constant.Long constant = new Constant.Long(value);
final int index = this.addConstant(constant);
this.constantPool.add(null);
return index;
}

public int addConstantDouble(final double value) {
final Constant.Double constant = new Constant.Double(value);
final int index = this.addConstant(constant);
this.constantPool.add(null);
return index;
}

Comme mentionné dans l'article précédent, les constantes ConstantLong et ConstantDouble prennent deux index dans le pool de constantes (n et n+1). Dans le fichier .class généré, l'index n+1 n'est en réalité pas utilisé. Imaginons que nous ajoutons une constante ConstantInt à l'index 11, puis une constante ConstantLong à l'index 12, la prochaine constante sera à l'index 14.

De plus, nous devons surcharger dans toutes les classes de constantes, les méthode hashCode() et equals().

Tests Unitaires

XIII-C-1-b - thisClass et superClass

Les champs thisClass et superClass ont pour valeur l'index d'une classe de type ConstantClass dans le pool de constantes. Dans cette version de PJBA, toute classe aura pour parent java.lang.Object. Nous allons donc pouvoir valoriser le champ dans le constructeur. Quant au champ thisClass, plusieurs solutions s'offrent à nous. Ajouter un paramètre de type String au constructeur prenant le nom complètement qualifié de la classe ou ajouter un setter, ce qui nécessitera en amont de créer une constante ConstantUTF8, puis une constante ConstantClass et de passer au setter l'index de cette dernière. Bien évidemment, nous pouvons mettre en place les deux solutions, néanmoins la première semble convenir à la majorité des situations.

public ClassFile(final String fullyQualifiedName) {
//...

// This
final int classNameIndex = this.addConstantUTF8(fullyQualifiedName);
this.thisClass  = this.addConstantClass(classNameIndex);

// Parent - Codé en dur pour l'instant
final String superName = "java/lang/Object";
final int superNameIndex = this.addConstantUTF8(superName);
this.superClass = this.addConstantClass(superNameIndex);

//...
}

Avant de continuer, ajoutons deux champs qui nous seront utiles lors de la génération de nos fichiers .class, le répertoire dans lequel devra être généré le fichier (le package en terme Java) et le nom de la classe. Nous avons ces deux informations dans le nom complètement qualifié d'une classe (le paramètre du constructeur). Il nous faut donc le découper en deux parties, sachant qu'une classe n'est pas obligatoirement dans un package.

private String className;
private String directories;

private void parseName(final String fullyQualifiedName) {
int index = fullyQualifiedName.lastIndexOf(Ascii.SLASH);

if (index >= 0) {
this.directories = fullyQualifiedName.substring(0, ++index);
this.className = fullyQualifiedName.substring(index);
} else {
this.className = fullyQualifiedName;
}
}

La méthode parseName() sera appelée au début du constructeur.

À noter que nous n'effectuons absolument aucune vérification quant à la validité des données. De fait, la génération se fera sans aucune erreur, en revanche si des données sont incorrectes, quelle qu'en soit la raison, les erreurs seront remontées par la JVM.

XIII-C-1-c - Tableau et liste

Le tableau et les listes sont aussi initialisés dans le constructeur :

public ClassFile(final String fullyQualifiedName) {
//...

this.interfaces = new int[0];
this.fields = new PjbaLinkedList<>();
this.methods = new PjbaLinkedList<>();
this.attributes = new PjbaLinkedList<>();

//...
}

Pour l'instant, nous nous intéresserons uniquement à la liste d'objets de type Method, qui seront ajoutés très simplement à l'aide d'une méthode addMethod() :

public void addMethod(final Method method) {
this.methods.add(method);
}

Source

XIII-C-2 - Method

Tout comme la classe ClassFile, la classe Method définit les modificateurs d'une méthode qui sont, pour l'instant, définis sous la forme d'une constante :

final private int accessFlags = 0x0001 | 0x0008; // public static

Les champs nameIndex et descriptorIndex ont pour valeur l'index de deux constantes ConstantUTF8 :

public void setNameIndex(int utf8NameIndex) {
this.nameIndex = utf8NameIndex;
}

public void setDescriptorIndex(int utf8DescriptorIndex) {
this.descriptorIndex = utf8DescriptorIndex;
}

Terminons par la liste attributes d'objets de type MethodAttribute :

public Method() {
super();

this.attributes = new PjbaLinkedList<>();
}

public void addAttibute(final MethodAttribute attribute) {
this.attributes.add(attribute);
}

Source

XIII-C-3 - Code

Comme mentionné dans la partie précédente (Format d'un fichier class), les instructions sont définies dans un tableau de byte de la classe Code. Or, définir des instructions ayant des arguments en utilisant des bytes n'est pas simple et surtout, ce n'est pas une conception orientée objets. Nous allons donc créer une classe Instruction :

public class Instruction {
final private int opcode;

public Instruction(final int opcode) {
super();
this.opcode = opcode;
}
}

puis remplacer le tableau de byte de la classe Code par une liste d'Instruction.

Pour pouvoir tester notre assembleur, définissons quelques instructions :

public class Instructions {
final public static int ILOAD_0_OPCODE = 0x1a;
final public static int ILOAD_1_OPCODE = 0x1b;
final public static int IADD_OPCODE = 0x60;
final public static int IRETURN_OPCODE = 0xac;
}

Comme nous l'avons vu dans l'article précédent, la classe Code a trois champs. Nous allons à présent détailler comment leur valeur est fixée.

private int maxStack;
private int maxLocals;
private int codeLength;

Chaque instruction a une taille, 1 octet auquel s'ajoute la taille de ses arguments si elle en a. De plus, nous pouvons déduire l'impact de l'exécution d'une instruction sur les variables locales et la pile d'opérandes.

Par exemple :

Instruction

Variables locales

Pile d'opérandes

Description

iload 6

7

+1

Prend la valeur (de catégorie 1) à l'index 6 des variables locales et l'empile (+1)

lload_2

3

+2

Prend la valeur (de catégorie 2) à l'index 2 des variables locales et l'empile (+2)

fstore_2

3

-1

Dépile une valeur de catégorie 1 (-1) et l'ajoute dans les variables locales à l'index 2

dstore 3

5

-2

Dépile une valeur de catégorie 2 (-2) et l'ajoute dans les variables locales à l'index 3

ldc

0

+1

Empile une référence (catégorie 1, +1)

iadd

0

-1

Dépile deux valeurs de catégorie 1 (-2), les additionne et empile le résultat (+1)

ladd

0

-2

Dépile deux valeurs de catégorie 2 (-4), les additionne et empile le résultat (+2)

La colonne Variables locales correspond à la taille minimum que doivent avoir les variables suite à l'exécution de l'instruction. Par exemple dans l'instruction dstore 3, le 3 indique que le tableau doit avoir une taille au moins égale à 4 et le ‘d‘ que l'élément prend aussi la case à l'index suivant. D'où 4 + 1 = 5. La colonne Pile d'opérandes correspond à la taille des valeurs empilées et dépilées suite à l'exécution de l'instruction.

Les instructions load et store sont un peu particulières. Prenons un cas simple :

public int locals(int i1, int i2) {
int t1 = i1 + 2;
int t2 = i2 + 3;
int t3 = t1 * t2;
int t4 = t2 / t1;
return t4 - t3;
}

Le code ci-dessus peut être écrit en bytecode, sans aucune transformation, de la manière suivante :

// int t1 = i1 + 2;
iload_1   // i1
iconst_2  // 2
iadd      // i1 + 2
istore_0  // t1

// int t2 = i2 + 3;
iload_2   // i2
iconst_3  // 3
iadd      // i2 + 3
istore_1  // t2

// int t3 = t1 * t2;
iload_0   // t1
iload_1   // t2
imul      // t1 * t2
istore_2  // t3

// int t4 = t2 / t1;
iload_1   // t1
iload_0   // t2
idiv      // t1 / t2
istore_3  // t4

// return t4 - t3;
iload_3   // t4
iload_4   // t3
isub      // t4 - t3
ireturn   // return

Nous avons donc sept variables :

- this puisque nous sommes dans le cas d'une méthode d'instance ;

- les deux paramètres de la méthode ;

- et quatre variables temporaires

et nous utilisons seulement les quatre premiers index des variables locales. Néanmoins, une autre solution - bien plus simple - qui est utilisée par javac est de considérer qu'une variable a une place fixe dans les variables locales et de laisser le compilateur JIT effectuer les optimisations.

Ceci se traduit par :

- la modification de la classe Instruction et de la gestion des instructions ;

- l'ajout de méthodes dans la classe Code.

Voyons le détail :

public class Instruction {
final private int opcode;
final private int stack;
final private int locals;
final private int length;

public Instruction(int opcode, int stack, int locals, int length) {
this.opcode = opcode;
this.stack = stack;
this.locals = locals;
this.length = length;
}
}

Source

public class NoArgInstruction extends Instruction {

public NoArgInstruction(int opcode, int stack, int locals) {
super(opcode, stack, locals, 1);
}
}

Source

public class Instructions {
final public static int ILOAD_0_OPCODE = 0x1a;
final public static int ILOAD_1_OPCODE = 0x1b;
final public static int IADD_OPCODE = 0x60;
final public static int IRETURN_OPCODE = 0xac;

final public static Instruction ILOAD_0 = new NoArgInstruction(ILOAD_0_OPCODE, 1, 1);
final public static Instruction ILOAD_1 = new NoArgInstruction(ILOAD_1_OPCODE, 1, 2);
final public static Instruction IADD = new NoArgInstruction(IADD_OPCODE, -1, 0);
final public static Instruction IRETURN = new NoArgInstruction(IRETURN_OPCODE, 0, 0);

public static Instruction iload_0() {
return ILOAD_0;
}

public static Instruction iload_1() {
return ILOAD_1;
}

public static Instruction iadd() {
return IADD;
}

public static Instruction ireturn() {
return IRETURN;
}
}

La classe Instructions doit être considérée comme une méthode utilitaire, nous permettant de rajouter simplement des instructions. De plus, le fait d'utiliser des méthodes en plus des constantes a pour but d'homogénéiser l'instanciation d'une instruction lorsque nous utiliserons des instructions ayant des arguments. Les ILOAD_0, IADD, etc. étant publiques, rien ne nous empêche de les utiliser.

Source

La base de la classe Code est la suivante :

public class Code extends Attribute implements MethodAttribute {
public final static String ATTRIBUTE_NAME = "Code";

private int maxStack;
private int maxLocals;
private int codeLength;

private PjbaLinkedList<Instruction> instructions;
private PjbaLinkedList<Exception> exceptions;
private PjbaLinkedList<CodeAttribute> attributes;

public Code(final int attributeNameIndex) {
super(attributeNameIndex);

this.instructions = new PjbaLinkedList<>();
this.exceptions = new PjbaLinkedList<>();
this.attributes = new PjbaLinkedList<>();
}
}

À chaque fois que l'on ajoute une instruction, nous mettons à jour les champs maxStack, maxLocals et length et nous ajoutons l'instruction à la liste d'instructions.

public void addInstruction(final Instruction instruction) {
this.addStack(instruction.getStack());
this.addLocals(instruction.getLocals());
this.addLength(instruction.getLength());
this.instructions.add(instruction);
}

Le champ length est extrêmement simple à valoriser puisque nous prenons la taille de chaque instruction et nous les additionnons. En revanche, nous verrons que dans certains cas, il est difficile - mais pas impossible - de connaître la taille d'une instruction.

private void addLength(int length) {
this.codeLength += length;
}

Pour calculer la taille maximum de la pile d'opérandes, nous avons rajouté un champ (currentStack) nous permettant de garder la taille courante de la pile suite à l'ajout d'instructions. Nous pouvons très bien avoir une suite d'instructions qui vont augmenter la taille de la pile, suivie par des instructions la faisant diminuer. De fait, nous modifions la variable maxStack uniquement si la variable currentStack est supérieure à la valeur actuelle de maxStack.

private int currentStack;

private void addStack(int stack) {
this.currentStack += stack;

if (this.maxStack < this.currentStack) {
this.maxStack = this.currentStack;
}
}

Comme nous l'avons vu, pour fixer la valeur du champ maxLocals, nous nous intéressons uniquement à la valeur la plus élevée, qui correspond soit à l'index + 1 puisque le tableau est indexé à partir de 0 pour les types de catégorie 1, soit à l'index + 2 pour les types de catégorie 2.

private void addLocals(int locals) {
if (this.maxLocals < locals) {
this.maxLocals = locals;
}
}

Pour terminer, nous devons ajouter une méthode nous permettant d'indiquer le nombre de cases que prennent les paramètres dans le tableau des variables locales. Hormis les types long et double prenant deux cases, tous les autres en prennent une. La méthode setParameterCount() est indispensable puisqu'une méthode peut avoir plusieurs paramètres, mais aucune variable locale (au sens Java).

public void setParameterCount(int parameterCount) {
this.addLocals(parameterCount);
}

Source

XIII-C-4 - Créer une classe

Nous avons ajouté des méthodes pour valoriser tous les champs de nos classes, voyons à présent comment les utiliser, en reprenant notre exemple habituel d'une méthode statique additionnant deux entiers et retournant un entier.

Puisque nous connaissons maintenant parfaitement comment est constitué un fichier .class, le code suivant est très simple à comprendre.

// ConstantPoolEntries
final String className = "org/isk/jvmhardcore/pjba/MyFirstClass";
final String methodName = "add";
final String methodDescriptor = "(II)I";

// ClassFile
final ClassFile classFile = new ClassFile(className);

// Method
final int methodIndex = classFile.addConstantUTF8(methodName);
final int descriptorIndex = classFile.addConstantUTF8(methodDescriptor);
final Method method = new Method();
method.setNameIndex(methodIndex);
method.setDescriptorIndex(descriptorIndex);
classFile.addMethod(method);

// Code
final int codeAttributeIndex = classFile.addConstantUTF8(Code.ATTRIBUTE_NAME);
final Code code = new Code(codeAttributeIndex);
final int parameterCount = method.countParameters(methodDescriptor);
code.setParameterCount(parameterCount);

// Instructions
code.addInstruction(Instructions.iload_0());
code.addInstruction(Instructions.iload_1());
code.addInstruction(Instructions.iadd());
code.addInstruction(Instructions.ireturn());
method.addAttibute(code);

Pour tester ce code, nous allons utiliser la même technique que pour le projet bytecode, en utilisant un test unitaire pour générer nos fichiers .class.

La Classe à assembler, l'Assembleur et le test unitaire de la classe.

XIII-C-4-a - Compter le nombre de paramètres d'un descripteur

Dans le code ci-dessus, une méthode demande une explication, puisque nous ne l'avions pas vue jusqu'à présent. La méthode countParameters() compte le nombre de paramètres d'une méthode en analysant son descripteur. Pour un être humain, cette méthode n'est pas forcément utile, puisque nous pouvons indiquer directement le nombre de paramètres de la méthode que nous sommes en train de créer. Néanmoins, il n'en va pas de même pour l'analyseur syntaxique que nous créerons prochainement.

Pour rappel, un descripteur peut avoir la forme suivante :

([[[Ljava.lang.Object;[[LObject;)V

ce qui donnerait en Java :

void nomDeLaMethode(java.lang.Object[][][], Object[][])

En repartant d'une situation plus simple, les types primitifs sont assez simples à analyser. Les types long et double prennent deux cases dans les variables locales, les autres une seule et void zéro.

Pour les classes, nous savons qu'elles commencent par la lettre « L » et se terminent par un point-virgule « ; ».

En revanche, les tableaux sont représentés par un crochet ouvrant « [ » suivi du type du tableau, et pour les tableaux à plusieurs dimensions les crochets se suivent mais comptent toujours pour un seul paramètre. Le cas extrême est celui illustré ci-dessus, un tableau à plusieurs dimensions d'objets.

La tâche étant légèrement complexe, le code de la méthode l'est aussi. Sachant que pour l'occasion, l'optimisation du code a été mise en avant.

L'idée est de parcourir la chaîne en analysant chaque caractère, d'incrémenter le nombre de paramètres si le caractère est une lettre représentant un type ou s'il s'agit du premier crochet rencontré et d'ignorer tous les autres caractères.

En ignorant le cas des tableaux, le code de la méthode est le suivant (Le détail de chaque étape est en commentaire) :

private static final String ENCODING = "UTF-8";

public int countParameters(final String methodDescriptor) {
try {
// Nous transformons la chaîne de caractères en tableau de bytes
final byte[] descriptor = methodDescriptor.getBytes(ENCODING);

// Le premier caractère est une parenthèse ouvrante
int index = 1;
// Représente le nombre de paramètres du descripteur
int locals = 0;
// Permet de savoir si le compte a changé entre les différentes itérations
int previousLocals = locals;

for (;;) {
byte character = descriptor[index++];

switch (character) {
case Ascii.UPPERCASE_B: // byte
case Ascii.UPPERCASE_C: // char
case Ascii.UPPERCASE_F: // float
case Ascii.UPPERCASE_I: // int
case Ascii.UPPERCASE_S: // short
case Ascii.UPPERCASE_Z: // boolean
locals++;
break;
case Ascii.UPPERCASE_J: // long
case Ascii.UPPERCASE_D: // double
locals += 2;
break;
// Nous ignorons tous les caractères jusqu'au point-virgule
case Ascii.UPPERCASE_L: // reference
locals++;
while (index < descriptor.length
&& (character = descriptor[index++]) != Ascii.SEMICOLON);
break;
}

// Nous avons rencontré un crochet fermant ou un V
// Il n'y a plus rien à compter
if (locals == previousLocals) {
break;
}

previousLocals = locals;
}

return locals;
} catch (UnsupportedEncodingException e) {
throw new RuntimeException("Should never happen", e);
}
}

En introduisant les tableaux, le code ci-dessus a besoin d'être modifié. Si nous rencontrons un crochet, nous ajoutons 1 à la variable locals, puis nous devons ignorer les crochets suivants ainsi qu'un type qui peut être représenté par un ou plusieurs caractères. Pour ce faire, nous devons utiliser une méthode récursive qui contiendra le switch. Le problème est que nous mettons à jour deux variables, index et locals. Utiliser un objet est généralement la solution la plus simple. Néanmoins, dans un tel cas, utiliser un objet mutable rend le code difficile à lire et à maintenir. Nous allons donc choisir une autre solution, la méthode de packing/unpacking (rassembler plusieurs valeurs dans une même variable) que nous avons déjà vue dans la partie Manipulation de la pile. Nous savons que les variables locales ne peuvent pas excéder 65 535 éléments (soit un short non signé) et qu'un tableau en Java ne peut avoir plus de 2 147 483 647 éléments (soit un int), or à moins d'être complètement dérangé, et dans ce cas il est conseillé d'aller consulter, le descripteur d'une méthode ne fera pas plus de deux milliards de caractères. De fait, un long conviendra parfaitement. Les 32 premiers bits seront utilisés pour l'index et les 32 derniers pour le nombre de paramètres.

La méthode précédente est à présent découpée en deux méthodes :

public int countParameters(final String methodDescriptor) {
try {
final byte[] descriptor = methodDescriptor.getBytes(ENCODING);

int index = 1; // Step over the first element: Left parenthesis
int locals = 0;
int previousLocals = locals;

for (;;) {
final long pack = countOneParameter(descriptor, index, locals);
locals = (int) (pack & 0xffff);
index = (int) (pack >>> 32);

// We encountered a right bracket or a void
if (locals == previousLocals) {
break;
}

previousLocals = locals;
}

return locals;
} catch (UnsupportedEncodingException e) {
throw new RuntimeException("Should never happen", e);
}
}

private long countOneParameter(byte[] descriptor, int index, int locals) {
byte character = descriptor[index++];

switch (character) {
case Ascii.UPPERCASE_B: // byte
case Ascii.UPPERCASE_C: // char
case Ascii.UPPERCASE_F: // float
case Ascii.UPPERCASE_I: // int
case Ascii.UPPERCASE_S: // short
case Ascii.UPPERCASE_Z: // boolean
locals++;
break;
case Ascii.UPPERCASE_J: // long
case Ascii.UPPERCASE_D: // double
locals += 2;
break;
case Ascii.LEFT_BRACKET: // array
locals++;
final long pack = this.countOneParameter(descriptor, index, 0)
index = (int) (pack >>> 32);
break;
case Ascii.UPPERCASE_L: // reference
locals++;
while (index < descriptor.length &&
(character = descriptor[index++]) != Ascii.SEMICOLON)
;
break;
}

// Locals maximum value = 65,535
// Arrays maximum size in Java = 2,147,483,647
return (((long) index) << 32) | locals;
}

Source

Si l'on fait l'impasse sur le packing/unpacking qui n'a rien de particulier en soi, le seul changement est l'ajout d'un case dans le switch :

case Ascii.LEFT_BRACKET: // Array
locals++;
final long pack = this.countOneParameter(descriptor, index, 0);
index = (int) (pack >>> 32);
break;

Nous prenons bien en compte le premier crochet, puis appelons la méthode countOneParameter() récursivement en ignorant le paramètre locals. Nous avons les cas suivants :

- si l'élément suivant est un type primitif, l'index est incrémenté de 1 ou 2 ;

- s'il s'agit d'un objet, l'index est incrémenté d'autant de caractères le constituant ;

- s'il s'agit à nouveau d'un ou plusieurs crochets ouvrants, nous aurons des appels récursifs successifs.

Tests unitaires

XIII-C-5 - Génération d'un fichier .class

Pour générer un fichier .class, nous avons à notre disposition la classe java.io.DataOutputStream que nous pouvons utiliser de la manière suivante :

final ClassFile classFile = new ClassFile();
// ...Création de la classe...

final String directoryStr = classFile.getDirectories();

// Création des répertoires contenant le fichier .class, s'ils n'existent pas.
final File directory = new File(directoryStr);
if (!directory.exists()) {
directory.mkdirs();
}

// Création d'un fichier .class
final String filename = directoryStr + classFile.getClassName() + ".class";
final FileOutputStream file = new FileOutputStream(filename);

// Génération du contenu du fichier
final DataOutput bytecode = new DataOutputStream(file);
classFile.toBytecode(bytecode);
file.close();

En définitive, la seule chose qu'il nous manque est la méthode toBytecode() de la classe ClassFile. Pour éviter d'avoir une méthode extrêmement longue, nous allons déléguer à chaque élément sa construction en bytecode. Pour ce faire, nous ajouterons dans toutes les classes une méthode toBytecode(). Et pour être sûr que toutes les classes nécessitant la méthode toBytecode() l'implémentent, la meilleure solution est de créer une interface BytecodeEnabled.

public interface BytecodeEnabled {
void toBytecode(final DataOutput dataOutput) throws IOException;
}

Source

Prenons par exemple la classe ClassFile (toutes les autres classes présentes dans le package org.isk.jvmhardcore.jpba.struture sont basées sur le même modèle) :

public class ClassFile implements BytecodeEnabled {
@Override
public void toBytecode(DataOutput dataOutput) throws IOException {
dataOutput.writeInt(this.magicNumber);
dataOutput.writeInt(this.version);
dataOutput.writeShort(this.constantPool.size());
this.constantPool.toBytecode(dataOutput);
dataOutput.writeShort(this.accessFlags);
dataOutput.writeShort(this.thisClass);
dataOutput.writeShort(this.superClass);
dataOutput.writeShort(this.interfaces.length);
// short interfaces[interfacesCount];
dataOutput.writeShort(this.fields.size());
this.fields.toBytecode(dataOutput);
dataOutput.writeShort(this.methods.size());
this.methods.toBytecode(dataOutput);
dataOutput.writeShort(this.attributes.size());
this.attributes.toBytecode(dataOutput);
}
}

Source

XIII-D - What's next?

Ce fut long, mais nous avons pu voir notre assembleur en détail. Nous sommes à présent capables de faire les modifications permettant de lever toutes les limitations que nous avons fixées. Avec une telle conception, nous constaterons que l'ajout des instructions à notre assembleur est trivial.

Dans l'article suivant, nous allons voir comment traverser un graphe d'objets simplement, tout comme nous l'avons fait avec la méthode toBytecode(), mais en offrant de la souplesse et c'est bien là tout l'enjeu d'un code réutilisable.

XIV - Remerciements

Cette partie a été publiée avec l'aimable autorisation de SOAT, société d'expertise et de conseil en informatique.

Nous tenons à remercier Claude Leloup, f-leb, FRANOUCH et lejimi pour la relecture orthographique, puis Malick SECK, zoom61, Winjerome et Laethy pour la mise au gabarit.

(1)L'espace mémoire utilisé pour une référence d'un objet est de 32 bits ou 64 bits en fonction de la JVM utilisée.