JVM Hardcore – Part 19 – Bytecode – Comparaisons et contrôle – 3/3

academic_duke
Au cours des parties 1/3 et 2/3, nous avons étudié en détail le fonctionnement de 25 instructions de comparaisons et de contrôle. Aujourd’hui, nous allons nous intéresser à leur implémentation dans PJBA tout aussi bien au niveau des builders, des dumpers ou de l’analyseur syntaxique.

Le code est disponible sur Github (tag et branche)

Tous les articles déjà publiés de la série portent le tag jvmhardcore.

Instructions.java

La première étape est d’ajouter les 25 instructions que nous avons vues dans les deux premières parties dans la classe Instructions.

  • Les instructions de type cmp ne prenant aucun argument, nous pouvons utiliser la classe NoArgInstruction.
  • Les instructions de type if, if_icmp, if_acmp, ifnull, ifnonnull et goto prenant un argument de deux octets nous pouvons utiliser la classe ShortArgInstruction.
  • L’instruction goto_w prenant un argument de quatre octets, nous allons créer une classe IntArgInstruction.
  • Les instructions tableswitch et lookupswitch prenant des arguments de taille variable, nous allons créer deux classes dédiées, TableswitchInstruction et LookupswitchInstruction.

Voyons ceci en détail pour une instruction de chaque groupe :

// -4 (2 long) + 1 (int) = -3
final public static Instruction LCMP = new NoArgInstruction(0x94, -3, 0);

public static Instruction lcmp() {
  return LCMP;
}

public static Instruction ifeq(short branch) {
  return new ShortArgInstruction(0x99, -1, 0, branch);
}

public static Instruction if_icmpeq(short branch) {
  return new ShortArgInstruction(0x9f, -2, 0, branch);
}

public static Instruction if_acmpeq(short branch) {
  return new ShortArgInstruction(0xa5, -2, 0, branch);
}

public static Instruction goto_(short branch) {
  return new ShortArgInstruction(0xa7, 0, 0, branch);
}

public static Instruction tableswitch(int padding, int defaultOffset,
                                      int lowValue, int highValue,
                                      int[] jumpOffsets) {
  return new TableswitchInstruction(0xaa, -1, 0, padding, defaultOffset,
                                    lowValue, highValue, jumpOffsets);
}

public static Instruction lookupswitch(int padding,  int defaultOffset,
                                       int nbPairs,
                                       int[] keys, int[] offsets) {
  return new LookupswitchInstruction(0xab, -1, 0, padding, defaultOffset,
                                     nbPairs, keys, offsets);
}

public static Instruction ifnull(short branch) {
  return new ShortArgInstruction(0xc6, -2, 0, branch);
}

public static Instruction goto_w(int branch) {
  return new IntArgInstruction(0xc8, 0, 0, branch);
}

Source

Nous n’avons pas vu pour l’instant l’implémentation des classes IntArgInstruction, TableswitchInstruction et LookupswitchInstruction, mais les paramètres de leur constructeur n’ont rien de surprenant. Les trois premiers sont respectivement l’opcode de l’instruction, les modifications dans les variables locales et dans la pile après exécution de l’instruction. Les paramètres suivants sont les arguments de l’instruction.

public class IntArgInstruction extends Instruction {

  private int arg;

  public IntArgInstruction(int opcode, int stack, int locals, int arg) {
    super(opcode, stack, locals, 5);
    this.arg = arg;
  }

  @Override
  public void accept(Visitor visitor) {
    super.accept(visitor);
    visitor.visitInstructionInt(this.arg);
  }
}

Source

public class TableswitchInstruction extends Instruction {
  private int padding;
  private int defaultOffset;
  final private int lowValue;
  final private int highValue;
  final private int[] jumpOffsets;

  public TableswitchInstruction(int opcode, int stack, int locals,
                                int padding, int defaultOffset,
                                int lowValue, int highValue, int[] jumpOffsets) {
    super(opcode, stack, locals, getLength(padding, jumpOffsets.length));
    this.padding = padding;
    this.defaultOffset = defaultOffset;
    this.lowValue = lowValue;
    this.highValue = highValue;
    this.jumpOffsets = jumpOffsets;
  }

  public static int getLength(int padding, int offsets) {
    // 1 + padding + 4 + 4 + 4 + 4 * jumpOffsets.length
    return 13 + padding + 4 * offsets;
  }

  @Override
  public void accept(Visitor visitor) {
    super.accept(visitor);
    visitor.visitInstructionTableSwitch(this.padding,
                                        this.defaultOffset,
                                        this.lowValue,
                                        this.highValue,
                                        this.jumpOffsets);
  }
}

Source

public class LookupswitchInstruction extends Instruction {
  private int padding;
  private int defaultOffset;
  final private int nbPairs;
  final private int[] keys;
  final private int[] jumpOffsets;

  public LookupswitchInstruction(int opcode, int stack, int locals, int padding,
                                 int defaultOffset, int nbPairs,
                                 int[] keys, int[] jumpOffsets) {
    super(opcode, stack, locals, getLength(padding, keys.length));
    this.padding = padding;
    this.defaultOffset = defaultOffset;
    this.nbPairs = nbPairs;
    this.keys = keys;
    this.jumpOffsets = jumpOffsets;
  }

  public static int getLength(int padding, int keys) {
    // 1 + padding + 4 + 4 + 4 * keys.length + 4 * offsets.length)
    // où keys.length == offsets.length
    return 9 + padding + 8 * keys;
  }

  @Override
  public void accept(Visitor visitor) {
    super.accept(visitor);
    visitor.visitInstructionLookupSwitch(this.padding,
                                         this.defaultOffset,
                                         this.nbPairs,
                                         this.keys,
                                         this.jumpOffsets);
  }
}

Source

Visitor.java

En ajoutant trois nouveaux types d’instructions, nous avons ajouté trois nouvelles méthodes dans l’interface Visitor.

public interface Visitor {
  // ...
  void visitInstructionInt(int arg);
  // ...
  void visitInstructionTableSwitch(int padding, int defaultOffset,
                                   int lowValue, int highValue,
                                   int[] jumpOffsets);
  void visitInstructionLookupSwitch(int padding, int defaultOffset,
                                    int nbPairs,
                                    int[] keys, int[] jumpOffsets);
}

Source

Une fois encore, avoir des méthodes visitXxx() avec de nombreux paramètres n’est pas en complet accord avec le patron de conception visiteur, mais cela nous sera d’une aide précieuse lors de l’implémentation des classes XxxDumper.

Assembler.java

La classe Assembler implémentant l’interface Visitor, il nous est nécessaire d’ajouter les trois nouvelles méthodes. La première – visitInstructionInt() – est tout ce qu’il y a de plus classique :

@Override
public void visitInstructionInt(int arg) {
  this.writeInt(arg);
}

Source

En revanche, les méthodes visitInstructionTableSwitch() et visitInstructionLookupSwitch() sont peu conventionnelles.

Pour rappel, le paramètre padding correspond au nombre de zéros – représentés sur un octet – à ajouter.

De plus, sans surprise, chaque élément des tableaux doit être ajouté au fichier .class. Néanmoins, notons – pour la méthode visitInstructionLookupSwitch() – que les tableaux keys et jumpOffsets doivent être lus en “parallèle” pour pouvoir être ajoutés au fichier .class :

keys[0]
jumpOffsets[0]
...
keys[i]
jumpOffsets[i]
keys[i + 1]
jumpOffsets[i + 1]
...
keys[keys.length - 1]
jumpOffsets[jumpOffsets.length - 1]

Les éléments importants ayant été soulevés l’implémentation reste tout de même assez simple.

@Override
public void visitInstructionTableSwitch(int padding, int defaultOffset,
                                        int lowValue, int highValue,
                                        int[] jumpOffsets) {
  for (int i = padding; i > 0; i--) {
    this.writeByte(0);
  }

  this.writeInt(defaultOffset);
  this.writeInt(lowValue);
  this.writeInt(highValue);

  for (int i : jumpOffsets) {
    this.writeInt(i);
  }
}

@Override
public void visitInstructionLookupSwitch(int padding, int defaultOffset,
                                         int nbPairs,
                                         int[] keys, int[] jumpOffsets) {
  for (int i = padding; i > 0; i--) {
    this.writeByte(0);
  }

  this.writeInt(defaultOffset);
  this.writeInt(nbPairs);

  for (int i = 0; i < keys.length; i++) {
    this.writeInt(keys[i]);
    this.writeInt(jumpOffsets[i]);
  }
}

Source

ClassFileBuilder.java et MethodBuilder.java

Jusqu’à présent les modifications nécessaires ont été extrêmement simples. Malheureusement ceci va changer en raison de (1) l’introduction des labels et de (2) l’utilisation des instructions goto et goto_w dont le choix entre les deux ne fait être fait qu’après avoir connaissance de la totalité des instructions d’une méthode.

Étant donné que le point 2 (ajout différé des instructions à l’objet de type Code de la méthode) a un coût non négligeable en terme de performance, nous allons donc opter pour deux stratégies que nous nommerons (1) eager et (2) lazy.

Le choix entre ces deux stratégies se fera lors de l’appel à la méthode newMethod(). Nous garderons tout de même la méthode sans ce paramètre, ce qui revient à choisir le mode eager par défaut.

public class ClassFileBuilder {
  // ...

  private MethodBuilder methodBuilder;

   public MethodBuilder newMethod(final int methodModifiers,
                                  final String methodName,
                                  final String methodDescriptor,
                                  final boolean eagerConstruction) {
    if (this.methodBuilder != null) {
      this.methodBuilder.buildMethod();
    }

    // ...

    this.methodBuilder = new MethodBuilder(this, method,
                                           parametersCount,
                                           eagerConstruction);

    return this.methodBuilder;
  }

  public MethodBuilder newMethod(final int methodModifiers,
                                 final String methodName,
                                 final String methodDescriptor) {
    return this.newMethod(methodModifiers, methodName,
                          methodDescriptor, true);
  }

  public ClassFile build() {
    this.methodBuilder.buildMethod();
    return this.classFile;
  }

  // ...
}

Source

Pour pouvoir construire la méthode “en cours” en mode lazy, nous devons ajouter la méthode buildMethod() dans la classe MethodBuilder.

void buildMethod() {
  if (!this.eagerConstruction) {
    this.checkGotoInstructions();
    this.setPositions();
    this.setOffsets();
    this.addInstructions();
  }
}

Source

Nous verrons un peu plus loin l’implémentation des quatre méthodes appelées dans la méthode buildMethod(). Pour l’instant, nous allons nous intéresser au mode eager, en commençant par déplacer la gestion des instructions dans une seule méthode instruction(Instruction instruction). Pour chaque méthode correspondant à une instruction nous allons appeler la méthode instruction() au lieu d’appeler this.code.addInstruction(/* instruction */).

public MethodBuilder nop() {
  this.instruction(Instructions.NOP);
  return this;
}

// ...

public MethodBuilder sipush(short value) {
  this.instruction(Instructions.sipush(value));
  return this;
}

// ...

public MethodBuilder iload_0() {
  this.instruction(Instructions.ILOAD_0);
  return this;
}

Source

Ensuite pour les instructions ayant en argument un offset, les méthodes correspondantes auront en paramètre un label. Il va donc nous falloir ajouter une méthode instruction() possédant un paramètre supplémentaire pour le label. Mais c’est ici que commencent les problèmes. Jusqu’à présent nous pouvions ajouter directement l’instruction à l’objet de type Code puisque nous possédions toutes les informations nécessaires à l’instanciation des instructions. Or en utilisant un label, nous n’avons pas connaissance de l’offset, qui est un argument de la majorité des instructions que nous avons ajoutées dans la partie précédente. Pour résoudre ce problème nous avons donc deux possibilités :

  • différer l’instanciation de l’instruction et ajouter une instruction fictive à l’objet de type Code, pour la remplacer lorsque nous aurons l’information attendue ou
  • créer l’instruction sans offset et ajouter l’offset lorsque nous l’aurons.

La première solution pose de nombreux problèmes (notamment le fait que l’ordre des labels n’est pas imposé) dont la complexité n’apporte aucun gain, bien au contraire.

Puisque nous utilisons des objets et donc des références, la deuxième solution est la plus adaptée. Néanmoins, elle nécessite une contrepartie. Les instructions possédant des arguments de type offset ne pourront plus être immuables, puisque nous allons avoir besoin de rajouter un setter pour l’argument.

Nous utilisons la valeur zéro pour l’offset en attendant d’avoir la valeur réelle.

public MethodBuilder ifeq(String label) {
  final Instruction instruction = Instructions.ifeq(SHORT_ZERO);
  this.instruction(instruction, label);

  return this;
}

Source

Nous verrons ce qu’il en est pour les instructions goto, tableswitch et lookupswitch un peu plus loin.

Comme à notre habitude nous avons repoussé les problèmes au maximum pour les regrouper en un seul point (en réalité deux ici).

Vu de l’extérieur, lorsque l’on utilise la classe MethodBuilder, les appels des méthodes permettant d’ajouter des instructions ou des labels à une méthode sont/doivent être strictement identiques. De fait, nous avons d’un côté la méthode permettant d’ajouter des instructions avec des labels – instruction(Instruction instruction, String label) – et de l’autre une méthode permettant d’ajouter des labels – label(String label).

Principe du mode eager

Dans le cas du mode eager, nous souhaitons conserver le mécanisme que nous avions jusqu’à présent. L’instruction doit être directement ajoutée à la méthode (plus précisément à l’objet de type Code).

  • Si la la méthode instruction(Instruction instruction) est appelée, nous ajoutons l’instruction à l’objet de type Code
  • Si la la méthode instruction(Instruction instruction, String label) est appelée, nous devons déterminer
    • (1) si le label a déjà été déclaré (label_1:) et dans ce cas nous pouvons calculer la valeur de l’offset, ou dans le cas contraire
    • (2) conserver l’instruction, le label associé et la position de l’instruction dans un type que nous nommerons LabelWrapper.
    • dans tous les cas nous rajoutons l’instruction à la méthode
  • Si la méthode label(String label) est appelée, à l’inverse du point précédent, nous devons déterminer
    • si au moins une instruction – ayant un label identique a celui passé en argument – a déjà été ajoutée, dans ce cas nous pouvons calculer la valeur de l’offset
    • dans tous les cas, nous conservons le label avec sa position (en réalité la position de l’instruction suivante) pour qu’il puisse être utilisé par des instructions qui n’ont pas encore été ajoutées à la méthode.

Principe du mode lazy

Il est important de noter que la position en mode lazy est la position “considérée comme la meilleure” et non la position optimale et ceci en raison des instructions goto et goto_w. Lorsque nous utiliserons la méthode goto() – que nous n’avons toujours pas ajouté à la classe MethodBuilder -, nous ajouterons l’instruction Instructions.goto_w(/* label */) – ayant une taille de 5 octets – à une liste d’instructions (d’où le concept de lazy), et nous la transformerons en Instructions.goto(/* label */) – ayant une taille de 3 octets – si nécessaire. De fait, lorsque la taille d’un offset se rapprochera de 32767 octets, il est possible que nous utilisions l’instruction goto_w, en raison de deux octets en trop, au lieu de l’instruction goto.

  • Si la méthode instruction(Instruction instruction) est appelée, nous ajoutons l’instruction associé à sa position à la liste d’instructions.
  • Si la méthode instruction(Instruction instruction, String label) est appelée nous conservons l’instruction, le label associé et la position de l’instruction toujours dans le type LabelWrapper.
  • Si la méthode label(String label) est appelée,
    • pour chaque instruction déjà ajoutée à la liste d’instruction nous fixons la valeur de la position du label (attention, la position du label ne doit pas impacter la position de l’instruction)
    • et dans tous les cas, (1) nous créons une instruction de type LabelInstruction et l’ajoutons à la liste, ce qui nous permettra de toujours connaître la position du label (dans tous les objets l’ayant en référence) lors des recalculs, (2) nous conservons à part le label de manière à avoir une collection de tous les labels utilisés dans la méthode en cours de création.

Une fois que nous avons fini de construire la méthode, la méthode buildMethod() est appelée. Cette méthode effectue plusieurs actions :

  1. checkGotoInstructions() : Les instruction goto_w sont remplacées par des instructions goto si nécessaire
  2. setPositions() : Les positions de toutes les instructions sont recalculés
  3. setOffsets() : Les arguments de toutes les instructions étant des offsets sont recalculés
  4. addInstructions() : Toutes les instructions sont ajoutées à l’objet de type Code

Implémentation

Nous n’allons pas détailler l’implémentation, mais nous nous contenterons de présenter l’utilité de chaque méthode :

Notons que pour faciliter les traitements, nous pouvons rajouter deux interfaces.

L’interface LabeledInstruction devant être implémentée par toutes les classes ayant en paramètre un offset telles que ShortArgInstructionIntArgInstructionTableswitchInstruction et LookupswitchInstruction.

public interface LabeledInstruction {
  void setOffset(String label, int offset);
}

Source

L’interface SwitchInstruction sera implémentée par les classes TableswitchInstruction et LookupswitchInstruction ce qui nous permettra de fixer le nombre d’octets de remplissage en mode lazy.

public interface SwitchInstruction {
  void setPadding(int padding);
}

Source

Maintenant que nous avons survolé les mécanismes des deux modes, nous pouvons introduire la méthode goto_() (goto étant un mot réservé en Java, nous choisissons de postfixer le nom de la méthode d’un underscore, comme nous l’avons fait pour la méthode return_()) :

public MethodBuilder goto_(String label) {
  this.instructionGoto(label);

  return this;
}

private void instructionGoto(String label) {
  if (this.eagerConstruction) {
    this.eagerGoto(label);
  } else {
    this.lazyGoto(label);
  }
}

private void eagerGoto(String label) {
  final InstructionWrapper labelInstructionWrapper = this.labelsAsMap.get(label);

  // Le label a déjà été déclaré, nous pouvons calculer son adresse
  if (labelInstructionWrapper != null) {
    final int offset = labelInstructionWrapper.position - this.currentMethodLength;

    if (offset >= Short.MIN_VALUE && offset <= Short.MAX_VALUE) {
      this.instruction(Instructions.goto_((short) offset));
    } else {
      this.instruction(Instructions.goto_w(offset));
    }
    return;
  }

  // Label non declaré
  // En mode eager nous n'utilisons jamais goto_w
  final Instruction instruction = Instructions.goto_(SHORT_ZERO);
  this.instruction(instruction, label);
}

private void lazyGoto(String label) {
  final Instruction instruction = Instructions.goto_w(0);
  final InstructionWrapper instructionWrapper =
    new InstructionWrapper(label, instruction, this.currentMethodLength);
  this.instruction(instructionWrapper, label);
  this.gotos.add(instructionWrapper);
}

Source

La méthode lazyGoto() est similaire aux méthodes représentant des instructions utilisant des labels. Néanmoins, nous utilisons le constructeur de la classe InstructionWrapper prenant un label et nous ajoutons l’instruction à une liste d’instructions goto_w, qui sera ensuite utilisée par la méthode checkGotoInstructions() que nous avons déjà détaillée.

Switch

Les méthodes tableswitch() et lookupswitch() nécessitent plus de code que les autres puisque les instructions qu’elles représentent ont plus d’arguments. En revanche, elles ne sont pas plus compliquées. Voyons la méthode tableswitch() (la méthode lookupswitch() étant similaire dans le principe) :

public TableswitchBuilder tableswitch(String defaultLabel,
                                      int lowValue,
                                      int highValue) {
  final int positionBeforeInstruction = this.code.getCodeLength();
  final int padding = 3 - positionBeforeInstruction % 4;
  final int nbOffsets = highValue - lowValue + 1;

  final TableswitchInstruction instruction = (TableswitchInstruction)
      Instructions.tableswitch(padding, 0,
                               lowValue, highValue,
                               new int[nbOffsets]);

  instruction.setDefaultLabel(defaultLabel);
  final InstructionWrapper instructionWrapper =
    new InstructionWrapper(instruction, this.currentMethodLength);
  this.instruction(instructionWrapper, defaultLabel);

  return new TableswitchBuilder(instruction, instructionWrapper, this);
}

Source

Tout d’abord, notons que l’utilisation de :

final int positionBeforeInstruction = this.code.getCodeLength();

ou

final int positionBeforeInstruction = this.currentMethodLength;

est strictement identique puisqu’en mode eager

this.code.getCodeLength() == this.currentMethodLength;

et en mode lazy le nombre d’octets de remplissage est recalculé dans la méthode setPositions().

Ensuite, rappelons que le nombre d’octets de remplissage est égal à 0, 1, 2 ou 3 de manière à ce que l’adresse du premier argument des instructions xswitch (la valeur de l’offset du default) soit un multiple de 4. Pour savoir si un nombre, que nous nommerons x, est un multiple de 4 il suffit d’utiliser l’opérateur modulo (%) où x % 4 == 0 signifie que x est un multiple de 4.

Si x n’est pas un multiple de 4 nous souhaitons connaître le nombre d’octets de remplissage, c’est à dire la valeur (y) à ajouter à x pour que (x + y) % 4 == 0. Pour avoir la valeur de y, il suffit de modifier l’expression précédente de la manière suivante : y = (4 - x) % 4.

Néanmoins, lorsque les méthodes tableswitch() ou lookswitch() sont appelées leur opcode n’a pas encore été ajouté (à la méthode en cours de construction). De fait, nous devons ajouter 1 à la variable positionBeforeInstruction (x) pour prendre en compte l’opcode. Or (4 - x + 1) % 4 == (3 - x) % 4, d’où :

final int padding = 3 - positionBeforeInstruction % 4;

Pour terminer, nous constatons que nous avons dû rajouter un builder (TableswitchBuilder) pour pouvoir ajouter des cases d’une manière plus souple (Pour la méthode lookupswitch() nous avons aussi rajouté une classe LookupswitchBuilder).

public class TableswitchBuilder {

  final private TableswitchInstruction instruction;
  final private InstructionWrapper instructionWrapper;
  final private MethodBuilder methodBuilder;

  public TableswitchBuilder(TableswitchInstruction instruction,
                            InstructionWrapper instructionWrapper,
                            MethodBuilder methodBuilder) {
    this.instruction = instruction;
    this.instructionWrapper = instructionWrapper;
    this.methodBuilder = methodBuilder;
  }

  public TableswitchBuilder offset(String label) {
    this.instruction.addOffsetLabel(label);
    this.methodBuilder.addLabel(this.instructionWrapper, label);
    return this;
  }

  public MethodBuilder end() {
    return this.methodBuilder;
  }
}

Source

Le partie du code la plus importante étant la méthode offset() qui délègue à l’instruction TableswitchInstruction la gestion de ses labels et donc de ses offsets, mais aussi appelle la méthode addLabel() (que nous avons décrit précédemment), qui entre autre, ajoute le label à la liste des labels.

public class TableswitchInstruction
        extends Instruction
        implements LabeledInstruction, SwitchInstruction {
  final private List<Label> labels;
  private Label defaultLabel;
  // ...
  private int defaultOffset;
  final private int[] jumpOffsets;

  // ...

  public void setDefaultLabel(String defaultLabel) {
    this.defaultLabel = new Label(defaultLabel);
  }

  public void addOffsetLabel(String label) {
    this.labels.add(new Label(label));
  }

  @Override
  public void setOffset(String label, int offset) {
    if (this.defaultLabel != null && this.defaultLabel.equals(new Label(label))) {
      this.defaultOffset = offset;
      this.defaultLabel.complete = true;
      return;
    }

    final int index = this.labels.indexOf(new Label(label));

    if (index == -1) {
      throw new RuntimeException("Unknow label: " + label);
    } else {
      final Label labelObj = this.labels.get(index);
      labelObj.complete = true;
      this.jumpOffsets[index] = offset;
    }
  }

  // ...

  private class Label {
    final public String label;
    private boolean complete;

    public Label(String label) {
      super();
      this.label = label;
    }

    // ...
  }
}

Source

La méthode setOffset() héritée par l’interface SwitchInstruction, appelée par les méthodes addLabel(), eagerLabel() et setOffsets(), permet de fixer l’offset d’un label donné. Pour pouvoir gérer l’utilisation d’un même label plusieurs fois (que ce soit dans plusieurs case et/ou par le default), la classe interne Label possède un champ complete utilisé par la méthode equals() (non montrée ici) de cette classe. Et c’est pour cette raison que nous utilisons une classe Label et non un simple type String.

La classe LookupswitchInstruction suit le même principe, à la différence qu’elle doit gérer des paires clé/valeur.

Pour conclure, mentionnons que la valeur du champ maxStack de la classe Code est correcte uniquement dans une situation “parfaite”, c’est-à-dire que lorsque les blocs (définis par les débranchements ifxxx, xxxswitch et goto) laissent la pile comme ils l’ont trouvée. Ceci est dû au fait que nous calculons la taille de la pile en déroulant les instructions séquentiellement sans prendre en compte les débranchements. Si nous souhaitions prendre en compte les autres cas, il serait nécessaire de cartographier l’ensemble des débranchements.

En partant d’un exemple simple, n’ayant pas vraiment de sens, voyons ce qu’il en est (En commentaire le calcul de la taille maximale de la pile).

bipush 20   @ +1 = 1
iload_0     @ +1 = 2
iload_1     @ +1 = 3
ifeq ok     @ -1 = 2
pop2        @ -2 = 0
iconst_0    @ +1 = 1
goto end    @  0 = 1
ok:
iload_0     @ +1 = 2
iload_1     @ +1 = 3
iadd        @ -2 + 1 = 2
end:
ireturn     @ -1 = 1

En suivant le mécanisme de calcul que nous utilisons actuellement nous considérons que la taille maximale de la pile lors de l’exécution de ce bout de code est 3.

Avec cet exemple nous pouvons identifier deux chemins différents :

1.
bipush 20   @ +1 = 1
iload_0     @ +1 = 2
iload_1     @ +1 = 3
pop         @ ifeq ok / -1 = 2
pop2        @ -2 = 0
iconst_0    @ +1 = 1
ireturn     @ -1 = 0

2.
bipush 20   @ +1 = 1
iload_0     @ +1 = 2
iload_1     @ +1 = 3
pop         @ ifeq ok / -1 = 2
iload_0     @ +1 = 3
iload_1     @ +1 = 4
iadd        @ -1 = 3
ireturn     @ -1 = 2

Nous nous rendons compte que pour le chemin 2 la taille maximale de la pile est de 4 soit une valeur supérieure à ce que nous avons calculé précédemment. De fait, si nous utilisions notre MethodBuilder sur le code que nous venons de voir, le fichier .class généré provoquerait une exception au niveau de la JVM, puisque la taille maximale indiquée dans le fichier ne correspond pas à la taille maximale réelle.

Notons aussi, qu’en considérant qu’un bloc ne laisse pas la pile dans l’état où il l’a trouvé, il nous serait impossible de déterminer la taille maximale de la pile lorsqu’une boucle entre en jeu (le label est défini avant l’instruction), et notamment lorsque l’arrêt de la boucle est conditionné par la valeur d’une variable (fournie en paramètre de la méthode ou calculée dans la méthode) connue uniquement lors de l’exécution. Dans ce cas précis, nous n’avons pas d’autres choix que d’utiliser la valeur maximale autorisée pour une pile d’un cadre, c’est-à-dire 65536.

Nous verrons tout ceci plus en détail dans un prochain article.

MetaInstructions.java

Avant de pouvoir ajouter les nouvelles instructions à la classe MetaInstructions, il nous faut tout d’abord créer trois nouvelles fabriques : IntArgInstructionFactory, TableswitchInstructionFactory et LookupswitchInstructionFactory, mais aussi trois nouvelles MetaInstruction : IntArgMetaInstruction, TableswitchMetaInstruction et LookupswitchMetaInstruction, toutes similaires à celles que nous avons vu précédemment. De plus, il nous faut ajouter de nouvelles valeurs à l’énumération ArgTypes :

public static enum ArgsType {
  // ...
  LABEL, // => 1 short (unsigned)
  GOTO, // => 1 short (signed)
  GOTO_W, // => 1 int (signed)
  TABLE_SWITCH,
  LOOKUP_SWITCH;
}

Source

Ajouter les instructions à la classe MetaInstructions n’est à présent qu’une formalité.

list.add(new NoArgMetaInstruction("lcmp", ArgsType.NONE, Instructions.LCMP));

list.add(new ShortArgMetaInstruction("ifeq", ArgsType.LABEL,
  new ShortArgInstructionFactory() {
    public Instruction buildInstruction(short branch) {
      return Instructions.ifeq(branch);
    }
  }
));

list.add(new TableswitchMetaInstruction("tableswitch", ArgsType.TABLE_SWITCH,
  new TableswitchInstructionFactory() {
    public Instruction buildInstruction(int padding,
                                        int defaultOffset,
                                        int lowValue, int highValue,
                                        int[] jumpOffsets) {
      return Instructions.tableswitch(padding,
                                      defaultOffset,
                                      lowValue, highValue,
                                      jumpOffsets);
    }
  }
));

list.add(new IntArgMetaInstruction("goto_w", "goto", ArgsType.GOTO_W,
  new IntArgInstructionFactory() {
    public Instruction buildInstruction(int branch) {
      return Instructions.goto_w(branch);
    }
  }
));

Source

Disassembler.java

La seule modification dans la classe Disassembler consiste à prendre en compte les trois nouvelles MetaInstruction.

La gestion de la MetaInstruction IntArgMetaInstruction est similaire aux MetaInstruction ByteArgMetaInstruction et ShortArgMetaInstruction

else if (metaInstruction instanceof IntArgMetaInstruction) {
  bytesProceed += 4;
  final int i = this.readInt();
  instruction = ((IntArgMetaInstruction) metaInstruction).buildInstruction(i);
}

Source

En revanche, pour les MetaInstruction TableswitchMetaInstruction et LookupswitchMetaInstruction le code est plus étoffé puisqu’il faut lire tous les arguments des instructions liées.

Le premier argument est le nombre d’octets de remplissage dépendant des instructions précédentes :

final int padding = this.readSwitchPadding(bytesProceed - 1);

private int readSwitchPadding(int bytesProceed) {
  final int padding = 3 - bytesProceed % 4;

  if (padding == 1) {
    this.readByte();
  } else if (padding == 2) {
    this.readShort();
  } else if (padding == 3) {
    this.readByte();
    this.readShort();
  }
  return padding;
}

Le reste des arguments est simple à lire à condition de ne pas faire d’erreur pour les offsets et paires valeur/offset :

else if (metaInstruction instanceof TableswitchMetaInstruction) {
  final int padding = this.readSwitchPadding(bytesProceed - 1);
  final int defaultOffset = this.readInt();
  final int lowValue = this.readInt();
  final int highValue = this.readInt();
  final int[] jumpOffsets = new int[highValue - lowValue + 1];

  for (int i = 0; i < jumpOffsets.length; i++) {
    jumpOffsets[i] = this.readInt();
  }

  bytesProceed += TableswitchInstruction
    .getLength(padding, jumpOffsets.length) - 1;

  instruction = ((TableswitchMetaInstruction) metaInstruction)
    .buildInstruction(padding, defaultOffset, lowValue, highValue, jumpOffsets);
} else if (metaInstruction instanceof LookupswitchMetaInstruction) {
  final int padding = this.readSwitchPadding(bytesProceed - 1);
  final int defaultOffset = this.readInt();
  final int nbPairs = this.readInt();
  final int[] keys = new int[nbPairs];
  final int[] offsets = new int[nbPairs];

  for (int i = 0; i < keys.length; i++) {
    keys[i] = this.readInt();
    offsets[i] = this.readInt();
  }

  bytesProceed += LookupswitchInstruction
    .getLength(padding, keys.length) - 1;

  instruction = ((LookupswitchMetaInstruction) metaInstruction)
    .buildInstruction(padding, defaultOffset, nbPairs, keys, offsets);
}

Source

HexDumper.java

Les modifications de la classe HexDumper sont aussi extrêmement triviales :

Dans la méthode visitOpcode(), nous devons rajouter l’adresse de l’instruction en octet au format décimal, ce qui implique de connaître l’adresse actuelle, ce que nous avons grâce à la variable currentMethodLength qui est incrémentée dans la méthode visitOpcode() et toutes les méthodes visitInstructionXxx() :

@Override
public void visitOpcode(int opcode) {
  // ...
  this.pjb.append(this.getHexAndAddByte()).append("\t");
  this.pjb.append("      ").append(this.getDecPadded(this.currentMethodLength))
          .append("  ").append(this.metaInstruction.getMnemonic());

  // ...

  this.currentMethodLength += 1;
}

// Ajouter des espaces devant la valeur si nécessaire
private String getDecPadded(int value) {
  final String s = String.valueOf(value);
  return this.pad(s, this.methodCounterMax, " ");
}

// Calcul de la valeur de la variable methodCounterMax
public void visitCodeLength(int codeLength) {
  this.methodCounterMax = String.valueOf(codeLength).length();
  // ...
}

Source

Nous devons ensuite afficher les arguments des nouvelles instructions, qui sont soit identifiées par un nouveau type d’argument (MetaInstruction.ArgsType) :

@Override
public void visitInstructionShort(int value) {
  final ArgsType type = this.metaInstruction.getArgsType();
  switch (type) {
    // ...
    case LABEL:
    case GOTO:
      this.pjb.append(" <").append(value).append(">\n");
      break;
    // ...
  }

  this.currentMethodLength += 2;
  this.getHexAndAdd(2);
}

Source

soit par une nouvelle méthode :

@Override
public void visitInstructionTableSwitch(int padding, int defaultOffset,
                                        int lowValue, int highValue,
                                        int[] jumpOffsets) {
  this.pjb.append(" ").append(padding)
          .append(" <").append(BytecodeUtils.unsign(defaultOffset)).append("> ")
          .append(lowValue).append(" ").append(highValue).append("\n");

  for (int jumpOffset : jumpOffsets) {
    this.pjb.append("                     <")
            .append(BytecodeUtils.unsign(jumpOffset)).append(">\n");
  }

  final int length = TableswitchInstruction
    .getLength(padding, jumpOffsets.length) - 1;
  this.currentMethodLength += length;
  this.getHexAndAdd(length);
}

Source

PjbDumper.java

La classe PjbDumper nécessite que l’on prenne en compte les labels en les générant et les plaçant au bon endroit. Néanmoins, ceci est moins complexe que pour la classe MethodBuilder.

Tout comme pour la classe HexDumper nous allons avoir besoin d’une variable (currentMethodLength) nous permettant de connaître l’adresse de chaque instruction. Ensuite, et c’est le changement le plus important dans cette classe, nous allons devoir adopter un mode lazy, qui consistera à stocker chaque instruction dans une liste pour qu’à la fin de la visite de toutes les instructions d’une méthode nous puissions ajouter les labels.

Tout d’abord, nous devons créer un StringBuilder intermédiaire contenant l’instruction courante :

@Override
public void visitOpcode(int opcode) {
  if (this.currentInstruction == null) {
    this.currentInstruction = new StringBuilder();
  }

  // ...
}

Source

Toutes les références à la variable pjb dans les méthodes visitOpcode() et visitInstructionXxx() devant être remplacées par la variable currentInstruction.

Ensuite, à la fin de chaque méthode visitInstructionXxx() nous faisons appel à la méthode writeInstruction() pour rajouter l’instruction sous la forme d’une chaîne de caractères et son adresse dans la liste des instructions.

private void writeInstruction() {
  final InstructionWrapper iw = new InstructionWrapper(
                                    this.currentInstruction.toString(),
                                    this.currentMethodLength);
  this.instructions.add();
  this.currentInstruction = new StringBuilder();
}

Source

L’étape suivante consiste à gérer les labels.

private String getLabel(int offset) {
  String printableValue;

  final int expectedPosition = this.currentMethodLength + offset;
  final String label = this.getLabelAtExpectedPosition(expectedPosition);

  if (label != null) {
    printableValue = label;
  } else {
    printableValue = "label" + this.labelCount++;
    this.labels.add(new LabelWrapper(printableValue.toString(), expectedPosition));
  }

  return printableValue;
}

private String getLabelAtExpectedPosition(int expectedPosition) {
  for (LabelWrapper lw : this.labels) {
    if (lw.expectedPosition == expectedPosition) {
      return lw.label;
    }
  }
  return null;
}

Source

A l’aide de la méthode getLabelAtExpectedPosition() nous vérifions si nous avons déjà un label à cette position. Si oui, la méthode getLabel() le retourne, sinon elle en génère un nouveau et crée un objet de type LabelWrapper contenant le label et l’adresse à laquelle il doit être affiché. Cet objet est ensuite ajouté à une liste nommée labels.

Appeler la méthode getLabel() permet à la fois de gérer les différents labels mais aussi de générer les instructions au format chaîne de caractères :

@Override
public void visitInstructionShort(int value) {
  Object printableValue = null;

  final ArgsType type = this.metaInstruction.getArgsType();
  switch (type) {
    // ...
    case LABEL:
    case GOTO:
      printableValue = this.getLabel(value);
      break;
    // ...
  }

  this.currentInstruction.append(" ").append(printableValue).append("\n");
  this.writeInstruction();
  this.currentMethodLength += 3;
}

Source

@Override
public void visitInstructionTableSwitch(int padding, int defaultOffset,
                                        int lowValue, int highValue,
                                        int[] jumpOffsets) {
  final String defaultLabel = this.getLabel(defaultOffset);

  this.currentInstruction.append(" ")
                         .append(defaultLabel)
                         .append(" ")
                         .append(lowValue).append(" ").append(highValue)
                         .append("\n");

  for (int jumpOffset : jumpOffsets) {
    final String label = this.getLabel(jumpOffset);
    this.currentInstruction.append("      ").append(label).append("\n");
  }

  this.writeInstruction();
  this.currentMethodLength += TableswitchInstruction.
    getLength(padding, jumpOffsets.length);
}

Source

Il ne nous reste plus qu’à ajouter les instructions et les labels au StringBuilder pjb

private void finalizeMethod() {
  for (LabelWrapper label : this.labels) {
    final int index = this.getInstructionIndex(label.expectedPosition);
    this.instructions.add(index,
        new InstructionWrapper("    " + label.label + ":\n", 0));
  }

  for (InstructionWrapper instruction : this.instructions) {
    this.pjb.append(instruction.instruction);
  }
}

private int getInstructionIndex(int expectedPosition) {
  for (int i = 0; i < this.instructions.size(); i++) {
    final InstructionWrapper instruction = this.instructions.get(i);
    if (instruction.position == expectedPosition) {
      return i;
    }
  }

  throw new RuntimeException("Instruction not found starting at: "
                             + expectedPosition);
}

Source

La première boucle de la méthode finalizeMethod() ajoute tous les labels à la liste des instructions et la seconde ajoute chacun des labels et des instructions au champ pjb.

PjbParser.java

Pour terminer cette longue revue des modifications de PJBA permettant de prendre en compte les nouvelles instructions, nous allons nous intéresser à son analyseur syntaxique. Tout d’abord, nous devons faire évoluer la grammaire pour pouvoir gérer les labels (le symbole label ayant été défini dans un article précédent).

methodContent = {ws instruction | label ws}
label = labelAsArg labelEnd
labelAsArg = {labelCharacter}
labelEnd = ':'
labelCharacter = ?[a-zA-Z]? | ?[0-9]? | '_'

Ce qui implique la création d’une nouvelle production nommée Label, de nouveaux symbole et événement, la modification de la production MethodContent et, de fait, la création de nouvelles méthodes dans la classe PjbTokenizer :

  • isLabel() : les caractères suivants à lire constituent-ils un label ?
  • getLabel() : lit un label, vérifie qu’il est suivi par un deux-points et le retourne sans le deux-points.
  • getLabelAsArg() : idem que précédemment sans la lecture et la vérification de la présence du deux-points final.

Ensuite la méthode parse() de la classe PjbParser a besoin de prendre en compte le nouvel événement LABEL et la méthode processInstruction() les nouveaux types d’argument nommés LABEL, GOTO, TABLE_SWITCH et LOOKUP_SWITCH

case LABEL:
  this.tokenizer.consumeWhitespaces();
  final String label = this.tokenizer.getLabelAsArg();
  final Instruction ifInstruction =
    ((ShortArgMetaInstruction) metaInstruction).
        buildInstruction((byte)0);
  this.methodBuilder.instruction(ifInstruction, label);
  break;
case GOTO:
  this.tokenizer.consumeWhitespaces();
  final String gLabel = this.tokenizer.getLabelAsArg();
  this.methodBuilder.goto_(gLabel);
  break;
case TABLE_SWITCH:
  this.tokenizer.consumeWhitespaces();
  final String tDefaultLabel = this.tokenizer.getLabelAsArg();
  this.tokenizer.consumeWhitespaces();
  final int lowValue = this.tokenizer.getIntValue();
  this.tokenizer.consumeWhitespaces();
  final int highValue = this.tokenizer.getIntValue();
  this.tokenizer.consumeWhitespaces();
  final TableswitchBuilder tsb = this.methodBuilder.
            tableswitch(tDefaultLabel, lowValue, highValue);

  final int nbOffsets = highValue - lowValue + 1;

  for (int i = 0; i < nbOffsets; i++) {
    this.tokenizer.consumeWhitespaces();
    final String tLabel = this.tokenizer.getLabelAsArg();
    tsb.offset(tLabel);
  }

  tsb.end();

  break;

Source

Note : Le code du case LOOKUP_SWITCH étant proche du case TABLE_SWITCH il n’est pas montré ici.

Pour conclure, il nous faut générer les méthodes à tester dans la classe Classes et les tests dans les classes AllInstructionsWithoutDummiesInCPTest et AllInstructionsWithDummiesInCPTest.

What’s next ?

Dans l’article suivant nous verrons comment appeler des méthodes statiques, mais aussi comment récupérer et fixer la valeur de champs statiques.

Nombre de vue : 27

AJOUTER UN COMMENTAIRE