/*

  * Licensed to the Apache Software Foundation (ASF) under one or more

  * contributor license agreements.  See the NOTICE file distributed with

  * this work for additional information regarding copyright ownership.

  * The ASF licenses this file to You under the Apache License, Version 2.0

  * (the "License"); you may not use this file except in compliance with

  * the License.  You may obtain a copy of the License at

  *

  *      http://www.apache.org/licenses/LICENSE-2.0

  *

  * Unless required by applicable law or agreed to in writing, software

  * distributed under the License is distributed on an "AS IS" BASIS,

  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.

  * See the License for the specific language governing permissions and

  * limitations under the License.

  */

 package org.apache.commons.nabla.forward.analysis;

 import java.util.ArrayList;

 import java.util.HashSet;

 import java.util.IdentityHashMap;

 import java.util.Iterator;

 import java.util.List;

 import java.util.ListIterator;

 import java.util.Map;

 import java.util.Set;

 import org.apache.commons.math3.analysis.differentiation.DerivativeStructure;

 import org.apache.commons.nabla.DifferentiationException;

 import org.apache.commons.nabla.NablaMessages;

 import org.apache.commons.nabla.forward.arithmetic.DAddTransformer;

 import org.apache.commons.nabla.forward.arithmetic.DDivTransformer;

 import org.apache.commons.nabla.forward.arithmetic.DMulTransformer;

 import org.apache.commons.nabla.forward.arithmetic.DNegTransformer;

 import org.apache.commons.nabla.forward.arithmetic.DRemTransformer;

 import org.apache.commons.nabla.forward.arithmetic.DSubTransformer;

 import org.apache.commons.nabla.forward.instructions.DLoadTransformer;

 import org.apache.commons.nabla.forward.instructions.DReturnTransformer;

 import org.apache.commons.nabla.forward.instructions.DStoreTransformer;

 import org.apache.commons.nabla.forward.instructions.DcmpTransformer;

 import org.apache.commons.nabla.forward.instructions.Dup2Transformer;

 import org.apache.commons.nabla.forward.instructions.Dup2X1Transformer;

 import org.apache.commons.nabla.forward.instructions.Dup2X2Transformer;

 import org.apache.commons.nabla.forward.instructions.InvokeStaticTransformer;

 import org.apache.commons.nabla.forward.instructions.NarrowingTransformer;

 import org.apache.commons.nabla.forward.instructions.Pop2Transformer;

 import org.apache.commons.nabla.forward.instructions.WideningTransformer;

 import org.apache.commons.nabla.forward.trimming.DLoadPop2Trimmer;

 import org.apache.commons.nabla.forward.trimming.SwappedDloadTrimmer;

 import org.apache.commons.nabla.forward.trimming.SwappedDstoreTrimmer;

 import org.objectweb.asm.Opcodes;

 import org.objectweb.asm.Type;

 import org.objectweb.asm.tree.AbstractInsnNode;

 import org.objectweb.asm.tree.FieldInsnNode;

 import org.objectweb.asm.tree.IincInsnNode;

 import org.objectweb.asm.tree.InsnList;

 import org.objectweb.asm.tree.InsnNode;

 import org.objectweb.asm.tree.LdcInsnNode;

 import org.objectweb.asm.tree.MethodInsnNode;

 import org.objectweb.asm.tree.MethodNode;

 import org.objectweb.asm.tree.TypeInsnNode;

 import org.objectweb.asm.tree.VarInsnNode;

 import org.objectweb.asm.tree.analysis.Analyzer;

 import org.objectweb.asm.tree.analysis.AnalyzerException;

 import org.objectweb.asm.tree.analysis.Frame;

 import org.objectweb.asm.tree.analysis.Interpreter;

 /** Class transforming a method computing a value to a method

  * computing both a value and its differential.

  * @version $Id$

  */

 public class MethodDifferentiator {

     /** Maximal number of temporary size 2 variables. */

     private static final int MAX_TEMP = 5;

     /** Math implementation classes. */

     private final Set<String> mathClasses;

     /** Name of the derived class. */

     private final String derivedName;

     /** Used locals variables array. */

     private boolean[] usedLocals;

     /** Set of converted values. */

     private final Set<TrackingValue> converted;

     /** Frames for the original method. */

     private final Map<AbstractInsnNode, Frame<TrackingValue>> frames;

     /** Instructions successors array. */

     private final Map<AbstractInsnNode, Set<AbstractInsnNode>> successors;

     /** Build a differentiator for a method.

      * @param mathClasses math implementation classes

      * @param derivedName name of the derived class

      */

     public MethodDifferentiator(final Set<String> mathClasses, final String derivedName) {

         this.usedLocals   = null;

         this.mathClasses  = mathClasses;

         this.derivedName  = derivedName;

         this.converted    = new HashSet<TrackingValue>();

         this.frames       = new IdentityHashMap<AbstractInsnNode, Frame<TrackingValue>>();

         this.successors   = new IdentityHashMap<AbstractInsnNode, Set<AbstractInsnNode>>();

     }

     /** Get the index of the input {@link DerivativeStructure derivative structure} variable.

      * @return index of the input {@link DerivativeStructure derivative structure} variable

      */

     public int getInputDSIndex() {

         // TODO: this should be improved in the general case,

         // as we are not sure the variable will always remain at index 1

         return 1;

     }

     /**

      * Differentiate a method.

      * @param primitiveName primitive class name

      * @param method method to differentiate (<em>will</em> be modified)

      * @exception DifferentiationException if method cannot be differentiated

      */

     public void differentiate(final String primitiveName, final MethodNode method)

         throws DifferentiationException {

         try {

             // at start, "this" and one DerivativeStructure are already used

             method.maxLocals  = 2 * (method.maxLocals + MAX_TEMP) - 1;

             usedLocals = new boolean[method.maxLocals];

             useLocal(0, 1);

             useLocal(1, 4);

             final Type dsType = Type.getType(DerivativeStructure.class);

             // add spare cells to hold new variables if needed

             addSpareLocalVariables(method.instructions);

             // analyze the original code, tracing values production/consumption

             final FlowAnalyzer analyzer =

                 new FlowAnalyzer(new TrackingInterpreter(), method.instructions);

             final Frame<TrackingValue>[] array = analyzer.analyze(primitiveName, method);

             // convert the array into a map, since code changes will shift all indices

             for (int i = 0; i < array.length; ++i) {

                 frames.put(method.instructions.get(i), array[i]);

             }

             // identify the needed changes

             final Set<AbstractInsnNode> changes = identifyChanges(method.instructions);

             if (changes.isEmpty()) {

                 // TODO: merge this case with the general case: DRETURN must always be

                 // changed when the function signature changes, and the change is either

                 // converting DRETURN to ARETURN, possibly with a prepended call to

                 // convertDoubleToDerivativeStructure before the ARETURN when stack0converted

                 // is false

                 // the method does not depend on the parameter at all!

                 // we replace all "return d;" by "return new DerivativeStructure(parameters, order, d);"

                 for (final Iterator<AbstractInsnNode> i = method.instructions.iterator(); i.hasNext();) {

                     final AbstractInsnNode insn = i.next();

                     if (insn.getOpcode() == Opcodes.DRETURN) {

                         final InsnList list = new DReturnTransformer(false).getReplacement(insn, this);

                         method.instructions.insert(insn, list);

                         method.instructions.remove(insn);

                     }

                 }

             } else {

                 // perform the code changes

                 for (final AbstractInsnNode insn : changes) {

                     method.instructions.insert(insn, getReplacement(insn));

                     method.instructions.remove(insn);

                 }

                 // trim generated instructions list

                 new SwappedDloadTrimmer().trim(method.instructions);

                 new SwappedDstoreTrimmer().trim(method.instructions);

                 new DLoadPop2Trimmer().trim(method.instructions);

             }

             // remove the local variables added at the beginning and not used

             removeUnusedSpareLocalVariables(method.instructions);

             // set the method properties

             method.desc       = Type.getMethodDescriptor(dsType, dsType);

             method.access    |= Opcodes.ACC_SYNTHETIC;

             method.maxLocals  = maxVariables();

         } catch (AnalyzerException ae) {

             ae.printStackTrace(System.err);

             if ((ae.getCause() != null) && ae.getCause() instanceof DifferentiationException) {

                 throw (DifferentiationException) ae.getCause();

             } else {

                 throw new DifferentiationException(NablaMessages.UNABLE_TO_ANALYZE_METHOD,

                                                    primitiveName, method.name, ae.getMessage());

             }

         }

     }

     /** Add spare cells for new local variables.

      * <p>In order to ease conversion from double values to derivative structures,

      * we start by reserving one spare cell between each original local variables.

      * So we have to modify the indices in all instructions referencing local

      * variables in the original code, to take into account the renumbering

      * introduced by these spare cells. The spare cells by themselves will

      * be referenced by the converted instructions in the following passes.</p>

      * <p>The spare cells that will not be used will be reclaimed after

      * conversion, to avoid wasting memory.</p>

      * @param instructions instructions of the method

      * @exception DifferentiationException if local variables array has not been

      * expanded appropriately beforehand

      * @see #removeUnusedSpareLocalVariables()

      */

     private void addSpareLocalVariables(final InsnList instructions)

         throws DifferentiationException {

         for (final Iterator<AbstractInsnNode> i = instructions.iterator(); i.hasNext();) {

             final AbstractInsnNode insn = i.next();

             if (insn.getType() == AbstractInsnNode.VAR_INSN) {

                 final VarInsnNode varInsn = (VarInsnNode) insn;

                 if (varInsn.var > 2) {

                     varInsn.var = 2 * varInsn.var - 1;

                     final int opcode = varInsn.getOpcode();

                     if ((opcode == Opcodes.ILOAD)  || (opcode == Opcodes.FLOAD)  ||

                         (opcode == Opcodes.ALOAD)  || (opcode == Opcodes.ISTORE) ||

                         (opcode == Opcodes.FSTORE) || (opcode == Opcodes.ASTORE)) {

                         useLocal(varInsn.var, 1);

                     } else {

                         useLocal(varInsn.var, 2);

                     }

                 }

             } else if (insn.getOpcode() == Opcodes.IINC) {

                 final IincInsnNode iincInsn = (IincInsnNode) insn;

                 if (iincInsn.var > 2) {

                     iincInsn.var = 2 * iincInsn.var - 1;

                     useLocal(iincInsn.var, 1);

                 }

             }

         }

     }

     /** Remove the unused spare cells introduced at conversion start.

      * @param instructions instructions of the method

      * @see #addSpareLocalVariables()

      */

     private void removeUnusedSpareLocalVariables(final InsnList instructions) {

         for (final Iterator<AbstractInsnNode> i = instructions.iterator(); i.hasNext();) {

             final AbstractInsnNode insn = i.next();

             if (insn.getType() == AbstractInsnNode.VAR_INSN) {

                 shiftVariable((VarInsnNode) insn);

             }

         }

     }

     /** Identify the instructions that must be changed.

      * <p>Identification is based on data flow analysis. We start by changing

      * the local variables in the initial frame to match the parameters of

      * the derivative method, and propagate these variables following the

      * instructions path, updating stack cells and local variables as needed.

      * Instructions that must be changed are the ones that consume changed

      * variables or stack cells.</p>

      * @param instructions instructions of the method

      * @return set containing all the instructions that must be changed

      */

     private Set<AbstractInsnNode> identifyChanges(final InsnList instructions) {

         // the pending set contains the values (local variables or stack cells)

         // that have been changed, they will trigger changes on the instructions

         // that consume them

         final Set<TrackingValue> pending = new HashSet<TrackingValue>();

         // the changes set contains the instructions that must be changed

         final Set<AbstractInsnNode> changes = new HashSet<AbstractInsnNode>();

         // start by converting the parameter of the method,

         // which is kept in local variable 1 of the initial frame

         final TrackingValue dpParameter = frames.get(instructions.get(0)).getLocal(1);

         pending.add(dpParameter);

         // propagate the values conversions throughout the method

         while (!pending.isEmpty()) {

             // pop one element from the set of changed values

             final Iterator<TrackingValue> iterator = pending.iterator();

             final TrackingValue value = iterator.next();

             iterator.remove();

             // this value is converted

             converted.add(value);

             // check the consumers instructions for this value

             for (final AbstractInsnNode consumer : value.getConsumers()) {

                 // an instruction consuming a converted value and producing

                 // a double must be changed to produce a derivative structure,

                 // get the double values produced and add them to the changed set

                 pending.addAll(getProducedAndNotConvertedDoubleValues(consumer));

                 // as a consumer of a converted value, the instruction must be changed

                 changes.add(consumer);

             }

             // check the producers instructions for this value

             for (final AbstractInsnNode producer : value.getProducers()) {

                 // an instruction producing a converted value must be changed

                 changes.add(producer);

             }

         }

         // the various GETFIELD/PUTFIELD instructions must also be changed

         // to retrieve the field from the outer class

         final ListIterator<AbstractInsnNode> iterator = instructions.iterator();

         while (iterator.hasNext()) {

             final AbstractInsnNode ins = iterator.next();

             if ((ins.getOpcode() == Opcodes.GETFIELD) || (ins.getOpcode() == Opcodes.PUTFIELD)) {

                 changes.add(ins);

             }

         }

         return changes;

     }

     /** Get the list of double values produced by an instruction and not yet converted.

      * @param instruction instruction producing the values

      * @return list of double values produced

      */

     private List<TrackingValue> getProducedAndNotConvertedDoubleValues(final AbstractInsnNode instruction) {

         final List<TrackingValue> values = new ArrayList<TrackingValue>();

         // get the frame before instruction execution

         final Frame<TrackingValue> before = frames.get(instruction);

         final int beforeStackSize = before.getStackSize();

         final int locals = before.getLocals();

         // check the frames produced by this instruction

         // (they correspond to the input frames of its successors)

         final Set<AbstractInsnNode> set = successors.get(instruction);

         if (set != null) {

             // loop over the successors of this instruction

             for (final AbstractInsnNode successor : set) {

                 final Frame<TrackingValue> produced = frames.get(successor);

                 // check the stack cells

                 for (int i = 0; i < produced.getStackSize(); ++i) {

                     final TrackingValue value = produced.getStack(i);

                     if (((i >= beforeStackSize) || (value != before.getStack(i))) &&

                         value.getType().equals(Type.DOUBLE_TYPE) &&

                         !converted.contains(value)) {

                         values.add(value);

                     }

                 }

                 // check the local variables

                 for (int i = 0; i < locals; ++i) {

                     final TrackingValue value = (TrackingValue) produced.getLocal(i);

                     if ((value != before.getLocal(i)) &&

                         value.getType().equals(Type.DOUBLE_TYPE) &&

                         !converted.contains(value)) {

                         values.add(value);

                     }

                 }

             }

         }

         return values;

     }

     /** Get the replacement list for an instruction.

      * @param insn instruction to replace

      * @return replacement instructions list

      * @exception DifferentiationException if some instruction cannot be handled

      * or if no temporary variable can be reserved

      */

     private InsnList getReplacement(final AbstractInsnNode insn)

         throws DifferentiationException {

         // get the frame at the start of the instruction

         final Frame<TrackingValue> frame = frames.get(insn);

         final int size = frame.getStackSize();

         final boolean stack1Converted = (size > 0) && converted.contains(frame.getStack(size - 2));

         final boolean stack0Converted = (size > 1) && converted.contains(frame.getStack(size - 1));

         switch(insn.getOpcode()) {

             case Opcodes.DLOAD :

                 useLocal(((VarInsnNode) insn).var, 4);

                 return new DLoadTransformer().getReplacement(insn, this);

             case Opcodes.DALOAD :

                 // TODO: add support for DALOAD differentiation

                 throw new RuntimeException("DALOAD not handled yet");

             case Opcodes.DSTORE :

                 useLocal(((VarInsnNode) insn).var, 4);

                 return new DStoreTransformer().getReplacement(insn, this);

             case Opcodes.DASTORE :

                 // TODO: add support for DASTORE differentiation

                 throw new RuntimeException("DASTORE not handled yet");

             case Opcodes.DUP2 :

                 return new Dup2Transformer().getReplacement(insn, this);

             case Opcodes.POP2 :

                 return new Pop2Transformer().getReplacement(insn, this);

             case Opcodes.DUP2_X1 :

                 return new Dup2X1Transformer().getReplacement(insn, this);

             case Opcodes.DUP2_X2 :

                 return new Dup2X2Transformer(stack0Converted, stack1Converted).getReplacement(insn, this);

             case Opcodes.DADD :

                 return new DAddTransformer(stack0Converted, stack1Converted).getReplacement(insn, this);

             case Opcodes.DSUB :

                 return new DSubTransformer(stack0Converted, stack1Converted).getReplacement(insn, this);

             case Opcodes.DMUL :

                 return new DMulTransformer(stack0Converted, stack1Converted).getReplacement(insn, this);

             case Opcodes.DDIV :

                 return new DDivTransformer(stack0Converted, stack1Converted).getReplacement(insn, this);

             case Opcodes.DREM :

                 return new DRemTransformer(stack0Converted, stack1Converted).getReplacement(insn, this);

             case Opcodes.DNEG :

                 return new DNegTransformer().getReplacement(insn, this);

             case Opcodes.DCONST_0 :

             case Opcodes.DCONST_1 :

             case Opcodes.LDC :

             case Opcodes.I2D :

             case Opcodes.L2D :

             case Opcodes.F2D :

                 return new WideningTransformer().getReplacement(insn, this);

             case Opcodes.D2I :

             case Opcodes.D2L :

             case Opcodes.D2F :

                 return new NarrowingTransformer().getReplacement(insn, this);

             case Opcodes.DCMPL :

             case Opcodes.DCMPG :

                 return new DcmpTransformer(stack0Converted, stack1Converted).getReplacement(insn, this);

             case Opcodes.DRETURN :

                 // TODO: the constructor parameter forced to true seems strange...

                 return new DReturnTransformer(true).getReplacement(insn, this);

             case Opcodes.GETSTATIC :

                 // TODO: add support for GETSTATIC differentiation

                 throw new RuntimeException("GETSTATIC not handled yet");

             case Opcodes.PUTSTATIC :

                 // TODO: add support for PUTSTATIC differentiation

                 throw new RuntimeException("PUTSTATIC not handled yet");

             case Opcodes.GETFIELD :

                 return replaceGetField((FieldInsnNode) insn);

             case Opcodes.PUTFIELD :

                 // TODO: add support for PUTFIELD differentiation

                 throw new RuntimeException("PUTFIELD not handled yet");

             case Opcodes.INVOKEVIRTUAL :

                 // TODO: add support for INVOKEVIRTUAL differentiation

                 throw new RuntimeException("INVOKEVIRTUAL not handled yet");

             case Opcodes.INVOKESPECIAL :

                 // TODO: add support for INVOKESPECIAL differentiation

                 throw new RuntimeException("INVOKESPECIAL not handled yet");

             case Opcodes.INVOKESTATIC :

                 return new InvokeStaticTransformer(stack0Converted, stack1Converted).getReplacement(insn, this);

             case Opcodes.INVOKEINTERFACE :

                 // TODO: add support for INVOKEINTERFACE differentiation

                 throw new RuntimeException("INVOKEINTERFACE not handled yet");

             case Opcodes.INVOKEDYNAMIC :

                 // TODO: add support for INVOKEDYNAMIC differentiation

                 throw new RuntimeException("INVOKEDYNAMIC not handled yet");

             case Opcodes.NEWARRAY :

                 // TODO: add support for NEWARRAY differentiation

                 throw new RuntimeException("NEWARRAY not handled yet");

             case Opcodes.ANEWARRAY :

                 // TODO: add support for ANEWARRAY differentiation

                 throw new RuntimeException("ANEWARRAY not handled yet");

             case Opcodes.MULTIANEWARRAY :

                 // TODO: add support for MULTIANEWARRAY differentiation

                 throw new RuntimeException("MULTIANEWARRAY not handled yet");

             default:

                 throw new DifferentiationException(NablaMessages.UNABLE_TO_HANDLE_INSTRUCTION, insn.getOpcode());

         }

     }

     /** Replace a GETFIELD instruction.

      * @param fieldInsn field instruction

      * @return replacement instructions list

      * @exception DifferentiationException if instruction cannot be replaced

      */

     private InsnList replaceGetField(final FieldInsnNode fieldInsn) throws DifferentiationException {

         final InsnList list = new InsnList();

         // get the field as an object

         list.add(new LdcInsnNode(fieldInsn.name));

         list.add(new MethodInsnNode(Opcodes.INVOKESPECIAL, derivedName, "getPrimitiveField",

                                     Type.getMethodDescriptor(Type.getType(Object.class),

                                                              Type.getType(String.class))));

         // convert it to the expected type

         final Type type = Type.getType(fieldInsn.desc);

         final Type boxedType;

         final String valueMethodName;

         switch (type.getSort()) {

             case Type.VOID:

                 throw new DifferentiationException(NablaMessages.CANNOT_GET_VOID_FIELD, fieldInsn.name);

             case Type.BOOLEAN:

                 valueMethodName = "booleanValue";

                 boxedType       = Type.getType(Boolean.class);

                 break;

             case Type.CHAR:

                 valueMethodName = "charValue";

                 boxedType       = Type.getType(Character.class);

                 break;

             case Type.BYTE:

                 valueMethodName = "byteValue";

                 boxedType       = Type.getType(Byte.class);

                 break;

             case Type.SHORT:

                 valueMethodName = "shortValue";

                 boxedType       = Type.getType(Short.class);

                 break;

             case Type.INT:

                 valueMethodName = "intValue";

                 boxedType       = Type.getType(Integer.class);

                 break;

             case Type.FLOAT:

                 valueMethodName = "floatValue";

                 boxedType       = Type.getType(Float.class);

                 break;

             case Type.LONG:

                 valueMethodName = "longValue";

                 boxedType       = Type.getType(Long.class);

                 break;

             case Type.DOUBLE:

                 valueMethodName = "doubleValue";

                 boxedType       = Type.getType(Double.class);

                 break;

             default :

                 // do nothing for Type.ARRAY and Type.OBJECT

                 valueMethodName = null;

                 boxedType       = null;

         }

         if (boxedType != null) {

             list.add(new TypeInsnNode(Opcodes.CHECKCAST, boxedType.getInternalName()));

         }

         if (valueMethodName != null) {

             list.add(new MethodInsnNode(Opcodes.INVOKEVIRTUAL, boxedType.getInternalName(),

                                         valueMethodName,

                                         Type.getMethodDescriptor(type, new Type[0])));

         }

         return list;

     }

     /** Test if a class is a math implementation class.

      * @param name name of the class to test

      * @return true if the named class is a math implementation class

      */

     public boolean isMathImplementationClass(final String name) {

         return mathClasses.contains(name);

     }

     /** Create instructions to convert a double on top of stack to a {@link DerivativeStructure}.

      * @return list of conversion instructions

      */

     public InsnList doubleToDerivativeStructureConversion() {

         final InsnList list = new InsnList();

         // operand stack initial state: d

         list.add(new TypeInsnNode(Opcodes.NEW,

                                   Type.getInternalName(DerivativeStructure.class))); // => d y_ds

         list.add(new InsnNode(Opcodes.DUP_X2));                                      // => y_ds d y_ds

         list.add(new InsnNode(Opcodes.DUP_X2));                                      // => y_ds y_ds d y_ds

         list.add(new InsnNode(Opcodes.POP));                                         // => y_ds y_ds d

         list.add(new VarInsnNode(Opcodes.ALOAD, getInputDSIndex()));                 // => y_ds y_ds d x_ds

         list.add(new MethodInsnNode(Opcodes.INVOKEVIRTUAL,

                                     Type.getInternalName(DerivativeStructure.class),

                                     "getFreeParameters",

                                     Type.getMethodDescriptor(Type.INT_TYPE)));       // => y_ds y_ds d params

         list.add(new VarInsnNode(Opcodes.ALOAD, 1));                                 // => y_ds y_ds d params x_ds

         list.add(new MethodInsnNode(Opcodes.INVOKEVIRTUAL,

                                     Type.getInternalName(DerivativeStructure.class),

                                     "getOrder",

                                     Type.getMethodDescriptor(Type.INT_TYPE)));       // => y_ds y_ds d params order

         list.add(new InsnNode(Opcodes.DUP2_X2));                                     // => y_ds y_ds params order d params order

         list.add(new InsnNode(Opcodes.POP2));                                        // => y_ds y_ds params order d

         list.add(new MethodInsnNode(Opcodes.INVOKESPECIAL,

                                     Type.getInternalName(DerivativeStructure.class),

                                     "<init>",

                                     Type.getMethodDescriptor(Type.VOID_TYPE,

                                                              Type.INT_TYPE,

                                                              Type.INT_TYPE,

                                                              Type.DOUBLE_TYPE)));    // => y_ds

         return list;

     }

     /** Set a local variable as used by the modified code.

      * @param index index of the variable

      * @param size size of the variable (1 or 2 for standard variables,

      * 4 for special expanded derivative structures)

      * @exception DifferentiationException if the number of the

      * temporary variable lies outside of the allowed range

      */

     public void useLocal(final int index, final int size)

         throws DifferentiationException {

         if ((index < 0) || ((index + size) > usedLocals.length)) {

             throw new DifferentiationException(NablaMessages.INDEX_OF_LOCAL_VARIABLE_OUT_OF_RANGE,

                                                size, index, 1, MAX_TEMP);

         }

         for (int i = index; i < index + size; ++i) {

             usedLocals[i] = true;

         }

     }

     /** Get index of a size 2 temporary variable.

      * <p>Temporary variables can be used for very short duration

      * storage of size 2 values (i.e one double, or one long or two

      * integers). These variables are reused in many replacement

      * instructions sequences, so their content may be overridden

      * at any time: they should be considered to have a scope

      * limited to one replacement sequence only. This means that

      * one should <em>not</em> store a value in a variable in one

      * replacement sequence and retrieve it later in another

      * replacement sequence as it may have been overridden in

      * between.</p>

      * <p>At most 5 temporary variables may be used.</p>

      * @param number number of the temporary variable (must be

      * between 1 and the maximal number of available temporary

      * variables)

      * @return index of the variable within the local variables

      * array

      * @exception DifferentiationException if the number of the

      * temporary variable lies outside of the allowed range

      */

     public int getTmp(final int number) throws DifferentiationException {

         if ((number < 0) || (number > MAX_TEMP)) {

             throw new DifferentiationException(NablaMessages.NUMBER_OF_TEMPORARY_VARIABLES_OUT_OF_RANGE,

                                                number, 1, MAX_TEMP);

         }

         final int index = usedLocals.length - 2 * number;

         useLocal(index, 2);

         return index;

     }

     /** Shifted the index of a variable instruction.

      * @param insn variable instruction

      */

     private void shiftVariable(final VarInsnNode insn) {

         int shifted = 0;

         for (int i = 0; i < insn.var; ++i) {

             if (usedLocals[i]) {

                 ++shifted;

             }

         }

         insn.var = shifted;

     }

     /** Compute the maximal number of used local variables.

      * @return maximal number of used local variables

      */

     private int maxVariables() {

         int max = 0;

         for (final boolean isUsed : usedLocals) {

             if (isUsed) {

                 ++max;

             }

         }

         return max;

     }

     /** Analyzer preserving instructions successors information. */

     private class FlowAnalyzer extends Analyzer<TrackingValue> {

         /** Instructions of the method. */

         private final InsnList instructions;

         /** Simple constructor.

          * @param interpreter associated interpreter

          * @param instructions instructions of the method

          */

         public FlowAnalyzer(final Interpreter<TrackingValue> interpreter,

                             final InsnList instructions) {

             super(interpreter);

             this.instructions = instructions;

         }

         /** Store a new edge.

          * @param insn current instruction

          * @param successor successor instruction

          */

         protected void newControlFlowEdge(final int insn, final int successor) {

             // store the successor information

             final AbstractInsnNode node = instructions.get(insn);

             Set<AbstractInsnNode> set = successors.get(node);

             if (set == null) {

                 set = new HashSet<AbstractInsnNode>();

                 successors.put(node, set);

             }

             set.add(instructions.get(successor));

         }

     }

 }