/*

  * 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.javaflow.bytecode.transformation.bcel.analyser;

 import java.util.ArrayList;

 import java.util.HashMap;

 import java.util.Hashtable;

 import org.apache.bcel.generic.ATHROW;

 import org.apache.bcel.generic.BranchInstruction;

 import org.apache.bcel.generic.GotoInstruction;

 import org.apache.bcel.generic.Instruction;

 import org.apache.bcel.generic.InstructionHandle;

 import org.apache.bcel.generic.JsrInstruction;

 import org.apache.bcel.generic.MethodGen;

 import org.apache.bcel.generic.RET;

 import org.apache.bcel.generic.ReturnInstruction;

 import org.apache.bcel.generic.Select;

 import org.apache.bcel.verifier.exc.AssertionViolatedException;

 import org.apache.bcel.verifier.exc.StructuralCodeConstraintException;

 /**

  * This class represents a control flow graph of a method.

  * 

  * WARNING! These classes are a fork of the bcel verifier. 

  *

  * @version $Id: ControlFlowGraph.java 480487 2006-11-29 08:54:42Z bayard $

  * @author <A HREF="http://www.inf.fu-berlin.de/~ehaase"/>Enver Haase</A>

  */

 public class ControlFlowGraph{

         /**

          * Objects of this class represent a node in a ControlFlowGraph.

          * These nodes are instructions, not basic blocks.

          */

         private class InstructionContextImpl implements InstructionContext{

                 /**

                  * The InstructionHandle this InstructionContext is wrapped around.

                  */

                 private InstructionHandle instruction;

                 /**

                  * The 'incoming' execution Frames.

                  */

                 private HashMap inFrames;        // key: the last-executed JSR

                 /**

                  * The 'outgoing' execution Frames.

                  */

                 private HashMap outFrames; // key: the last-executed JSR 

                 /**

                  * The 'execution predecessors' - a list of {@link InstructionContext}

                  * of those instances that have been execute()d before in that order.

                  */

                 private ExecutionPath executionPredecessors = null; // Type: InstructionContext

                 /**

                  * Creates an InstructionHandleImpl object from an InstructionHandle.

                  * Creation of one per InstructionHandle suffices. Don't create more.

                  */

                 public InstructionContextImpl(InstructionHandle inst){

                         if (inst == null) throw new AssertionViolatedException("Cannot instantiate InstructionContextImpl from NULL.");

                         instruction = inst;

                         inFrames = new java.util.HashMap();

                         outFrames = new java.util.HashMap();

                 }

                 /**

                  * Returns the exception handlers of this instruction.

                  */

                 public ExceptionHandler[] getExceptionHandlers(){

                         return exceptionhandlers.getExceptionHandlers(getInstruction());

                 }

                 /**

                  * Returns a clone of the "outgoing" frame situation with respect to the given ExecutionChain.

                  */        

                 public Frame getOutFrame(ExecutionPath execChain){

                         executionPredecessors = execChain;

                         Frame org;

                         InstructionContext jsr = lastExecutionJSR();

                         org = (Frame) outFrames.get(jsr);

                         if (org == null){

                                 throw new AssertionViolatedException("outFrame not set! This:\n"+this+"\nExecutionChain: "+getExecutionChain()+"\nOutFrames: '"+outFrames+"'.");

                         }

                         return org.getClone();

                 }

     public Frame getInFrame() {

                   Frame org;

                         InstructionContext jsr = lastExecutionJSR();

                         org = (Frame) inFrames.get(jsr);

                         if (org == null){

                             throw new AssertionViolatedException("inFrame not set! This:\n"+this+"\nInFrames: '"+inFrames+"'.");

       }

       return org.getClone();

     }

                 /**

                  * "Merges in" (vmspec2, page 146) the "incoming" frame situation;

                  * executes the instructions symbolically

                  * and therefore calculates the "outgoing" frame situation.

                  * Returns: True iff the "incoming" frame situation changed after

                  * merging with "inFrame".

                  * The execPreds contain the InstructionContext

                  * objects executed so far in the correct order. This is just

                  * one execution path [out of many]. This is needed to correctly

                  * "merge" in the special case of a RET's successor.

                  * <B>The InstConstraintVisitor and ExecutionVisitor instances

                  * must be set up correctly.</B>

                  * @return true - if and only if the "outgoing" frame situation

                  * changed from the one before execute()ing.

                  */

                 public boolean execute(Frame inFrame, ExecutionPath execPreds, ExecutionVisitor ev){

             // When merge failed, this is useful to see what are two passes

             ExecutionPath oldExecPreds = executionPredecessors;

             executionPredecessors = execPreds;

                         //sanity check

                         if ( (lastExecutionJSR() == null) && (subroutines.subroutineOf(getInstruction()) != subroutines.getTopLevel() ) ){

                                 //throw new AssertionViolatedException("Huh?! Am I '"+this+"' part of a subroutine or not?");

                                 return false;

                         }

                         if ( (lastExecutionJSR() != null) && (subroutines.subroutineOf(getInstruction()) == subroutines.getTopLevel() ) ){

                                 //throw new AssertionViolatedException("Huh?! Am I '"+this+"' part of a subroutine or not?");

                                 return false;

                         }

                         Frame inF = (Frame) inFrames.get(lastExecutionJSR());

                         if (inF == null){// no incoming frame was set, so set it.

                                 inFrames.put(lastExecutionJSR(), inFrame);

                                 inF = inFrame;

                         }

                         else{// if there was an "old" inFrame

                                 if (inF.equals(inFrame)){ //shortcut: no need to merge equal frames.

                                         return false;

                                 }

                                 if (! mergeInFrames(inFrame)){

                                         return false;

                                 }

                         }

                         // Now we're sure the inFrame has changed!

                         // new inFrame is already merged in, see above.                

                         Frame workingFrame = inF.getClone();

                         // This executes the Instruction.

                         // Therefore the workingFrame object is modified.

 //ExecutionVisitor ev = ExecutionVisitor.getInstance(VerifierFactory.getVerifier(method_gen.getClassName()));

                         ev.setFrame(workingFrame);

                         getInstruction().accept(ev);

                         //getInstruction().accept(ExecutionVisitor.withFrame(workingFrame));

                         outFrames.put(lastExecutionJSR(), workingFrame);

                         return true;        // new inFrame was different from old inFrame so merging them

                                                                                 // yielded a different this.inFrame.

                 }

                 /**

                  * Returns a simple String representation of this InstructionContext.

                  */

                 public String toString(){

                 //TODO: Put information in the brackets, e.g.

                 //      Is this an ExceptionHandler? Is this a RET? Is this the start of

                 //      a subroutine?

                         String ret = getInstruction().toString(false)+"\t[InstructionContext]";

                         return ret;

                 }

                 /**

                  * Does the actual merging (vmspec2, page 146).

                  * Returns true IFF this.inFrame was changed in course of merging with inFrame.

                  */

                 private boolean mergeInFrames(Frame inFrame){

                         // TODO: Can be performance-improved.

                         Frame inF = (Frame) inFrames.get(lastExecutionJSR());

                         OperandStack oldstack = inF.getStack().getClone();

                         LocalVariables oldlocals = inF.getLocals().getClone();

                         try{

                                 inF.getStack().merge(inFrame.getStack());

                                 inF.getLocals().merge(inFrame.getLocals());

                         }

                         catch (StructuralCodeConstraintException sce){

                                 extendMessageWithFlow(sce);

                                 throw sce;

                         }

                         if (        oldstack.equals(inF.getStack()) &&

                                                 oldlocals.equals(inF.getLocals()) ){

                                 return false;

                         }

                         else{

                                 return true;

                         }

                 }

                 /**

                  * Returns the control flow execution chain. This is built

                  * while {@link #execute(Frame, ExecutionPath, ExecutionVisitor) executing} the code represented

                  * by the surrounding ControlFlowGraph.

                  */

                 private String getExecutionChain(){

             return executionPredecessors.toString()+"\n"+this.toString();

                 }

                 /**

                  * Extends the StructuralCodeConstraintException ("e") object with an at-the-end-extended message.

                  * This extended message will then reflect the execution flow needed to get to the constraint

                  * violation that triggered the throwing of the "e" object.

                  */

                 private void extendMessageWithFlow(StructuralCodeConstraintException e){

                         String s = "Execution flow:\n";

                         e.extendMessage("", s+getExecutionChain());

                 }

                 /*

                  * Fulfils the contract of InstructionContext.getInstruction().

                  */

                 public InstructionHandle getInstruction(){

                         return instruction;

                 }

                 private InstructionContext lastExecutionJSR(){

             return executionPredecessors.lastExecutionJSR();

                 }

                 /* Satisfies InstructionContext.getSuccessors(). */

                 public InstructionContext[] getSuccessors(){

                         return contextsOf(_getSuccessors());

                 }

                 /**

                  * A utility method that calculates the successors of a given InstructionHandle

                  * That means, a RET does have successors as defined here.

                  * A JsrInstruction has its target as its successor

                  * (opposed to its physical successor) as defined here.

                  */

 // TODO: implement caching!

                 private InstructionHandle[] _getSuccessors(){

                         final InstructionHandle[] empty = new InstructionHandle[0];

                         final InstructionHandle[] single = new InstructionHandle[1];

                         final InstructionHandle[] pair = new InstructionHandle[2];

                         Instruction inst = getInstruction().getInstruction();

                         if (inst instanceof RET){

                                 Subroutine s = subroutines.subroutineOf(getInstruction());

                                 if (s==null){ //return empty; // RET in dead code. "empty" would be the correct answer, but we know something about the surrounding project...

                                         throw new AssertionViolatedException("Asking for successors of a RET in dead code?!");

                                 }

 //TODO: remove

 throw new AssertionViolatedException("DID YOU REALLY WANT TO ASK FOR RET'S SUCCS?");

 /*

                                 InstructionHandle[] jsrs = s.getEnteringJsrInstructions();

                                 InstructionHandle[] ret = new InstructionHandle[jsrs.length];

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

                                         ret[i] = jsrs[i].getNext();

                                 }

                                 return ret;

 */

                         }

                         // Terminates method normally.

                         if (inst instanceof ReturnInstruction){

                                 return empty;

                         }

                         // Terminates method abnormally, because JustIce mandates

                         // subroutines not to be protected by exception handlers.

                         if (inst instanceof ATHROW){

                                 return empty;

                         }

                         // See method comment.

                         if (inst instanceof JsrInstruction){

                                 single[0] = ((JsrInstruction) inst).getTarget();

                                 return single;

                         }

                         if (inst instanceof GotoInstruction){

                                 single[0] = ((GotoInstruction) inst).getTarget();

                                 return single;

                         }

                         if (inst instanceof BranchInstruction){

                                 if (inst instanceof Select){

                                         // BCEL's getTargets() returns only the non-default targets,

                                         // thanks to Eli Tilevich for reporting.

                                         InstructionHandle[] matchTargets = ((Select) inst).getTargets();

                                         InstructionHandle[] ret = new InstructionHandle[matchTargets.length+1];

                                         ret[0] = ((Select) inst).getTarget();

                                         System.arraycopy(matchTargets, 0, ret, 1, matchTargets.length);

                                         return ret;

                                 }

                                 else{

                                         pair[0] = getInstruction().getNext();

                                         pair[1] = ((BranchInstruction) inst).getTarget();

                                         return pair;

                                 }

                         }

                         // default case: Fall through.                

                         single[0] = getInstruction().getNext();

                         return single;

                 }

         } // End Inner InstructionContextImpl Class.

         /** The Subroutines object for the method whose control flow is represented by this ControlFlowGraph. */

         private final Subroutines subroutines;

         /** The ExceptionHandlers object for the method whose control flow is represented by this ControlFlowGraph. */

         private final ExceptionHandlers exceptionhandlers;

         /** All InstructionContext instances of this ControlFlowGraph. */

         private Hashtable instructionContexts = new Hashtable(); //keys: InstructionHandle, values: InstructionContextImpl

         /** 

          * A Control Flow Graph.

          */

         public ControlFlowGraph(MethodGen method_gen){

                 subroutines = new Subroutines(method_gen);

                 exceptionhandlers = new ExceptionHandlers(method_gen);

                 InstructionHandle[] instructionhandles = method_gen.getInstructionList().getInstructionHandles();

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

                         instructionContexts.put(instructionhandles[i], new InstructionContextImpl(instructionhandles[i]));

                 }

         }

         /**

          * Returns the InstructionContext of a given instruction.

          */

         public InstructionContext contextOf(InstructionHandle inst){

                 InstructionContext ic = (InstructionContext) instructionContexts.get(inst);

                 if (ic == null){

                         throw new AssertionViolatedException("InstructionContext requested for an InstructionHandle that's not known!");

                 }

                 return ic;

         }

         /**

          * Returns the InstructionContext[] of a given InstructionHandle[],

          * in a naturally ordered manner.

          */

         public InstructionContext[] contextsOf(InstructionHandle[] insts){

                 InstructionContext[] ret = new InstructionContext[insts.length];

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

                         ret[i] = contextOf(insts[i]);

                 }

                 return ret;

         }

         /**

          * Returns an InstructionContext[] with all the InstructionContext instances

          * for the method whose control flow is represented by this ControlFlowGraph

          * <B>(NOT ORDERED!)</B>.

          */

         public InstructionContext[] getInstructionContexts(){

                 InstructionContext[] ret = new InstructionContext[instructionContexts.values().size()];

                 return (InstructionContext[]) instructionContexts.values().toArray(ret);

         }

         /**

          * Returns true, if and only if the said instruction is not reachable; that means,

          * if it is not part of this ControlFlowGraph.

          */

         public boolean isDead(InstructionHandle i){

         return subroutines.subroutineOf(i) == null;

         }         

 }