/*
    * 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));
         }
 
     }
 
 }