ControlFlowGraph xref

View Javadoc

    1   /*
    2    * Copyright  2000-2004 The Apache Software Foundation
    3    *
    4    *  Licensed under the Apache License, Version 2.0 (the "License");
    5    *  you may not use this file except in compliance with the License.
    6    *  You may obtain a copy of the License at
    7    *
    8    *      http://www.apache.org/licenses/LICENSE-2.0
    9    *
    10   *  Unless required by applicable law or agreed to in writing, software
    11   *  distributed under the License is distributed on an "AS IS" BASIS,
    12   *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    13   *  See the License for the specific language governing permissions and
    14   *  limitations under the License.
    15   *
    16   */
    17  package org.apache.bcel.verifier.structurals;
    18
    19
    20  import java.util.ArrayList;
    21  import java.util.Hashtable;
    22  import java.util.Map;
    23  import org.apache.bcel.generic.ATHROW;
    24  import org.apache.bcel.generic.BranchInstruction;
    25  import org.apache.bcel.generic.GotoInstruction;
    26  import org.apache.bcel.generic.Instruction;
    27  import org.apache.bcel.generic.InstructionHandle;
    28  import org.apache.bcel.generic.JsrInstruction;
    29  import org.apache.bcel.generic.MethodGen;
    30  import org.apache.bcel.generic.RET;
    31  import org.apache.bcel.generic.ReturnInstruction;
    32  import org.apache.bcel.generic.Select;
    33  import org.apache.bcel.verifier.exc.AssertionViolatedException;
    34  import org.apache.bcel.verifier.exc.StructuralCodeConstraintException;
    35
    36  /***
    37   * This class represents a control flow graph of a method.
    38   *
    39   * @version $Id: ControlFlowGraph.java 386056 2006-03-15 11:31:56Z tcurdt $
    40   * @author Enver Haase
    41   */
    42  public class ControlFlowGraph{
    43
    44  	/***
    45  	 * Objects of this class represent a node in a ControlFlowGraph.
    46  	 * These nodes are instructions, not basic blocks.
    47  	 */
    48  	private class InstructionContextImpl implements InstructionContext{
    49
    50  		/***
    51  		 * The TAG field is here for external temporary flagging, such
    52  		 * as graph colouring.
    53  		 *
    54  		 * @see #getTag()
    55  		 * @see #setTag(int)
    56  		 */
    57  		private int TAG;
    58
    59  		/***
    60  		 * The InstructionHandle this InstructionContext is wrapped around.
    61  		 */
    62  		private InstructionHandle instruction;
    63
    64  		/***
    65  		 * The 'incoming' execution Frames.
    66  		 */
    67  		private Map inFrames;	// key: the last-executed JSR
    68
    69  		/***
    70  		 * The 'outgoing' execution Frames.
    71  		 */
    72  		private Map outFrames; // key: the last-executed JSR
    73
    74  		/***
    75  		 * The 'execution predecessors' - a list of type InstructionContext
    76  		 * of those instances that have been execute()d before in that order.
    77  		 */
    78  		private ArrayList executionPredecessors = null; // Type: InstructionContext
    79
    80  		/***
    81  		 * Creates an InstructionHandleImpl object from an InstructionHandle.
    82  		 * Creation of one per InstructionHandle suffices. Don't create more.
    83  		 */
    84  		public InstructionContextImpl(InstructionHandle inst){
    85  			if (inst == null) {
    86                  throw new AssertionViolatedException("Cannot instantiate InstructionContextImpl from NULL.");
    87              }
    88
    89  			instruction = inst;
    90  			inFrames = new java.util.HashMap();
    91  			outFrames = new java.util.HashMap();
    92  		}
    93
    94  		/* Satisfies InstructionContext.getTag(). */
    95  		public int getTag(){
    96  			return TAG;
    97  		}
    98
    99  		/* Satisfies InstructionContext.setTag(int). */
    100 		public void setTag(int tag){
    101 			TAG = tag;
    102 		}
    103
    104 		/***
    105 		 * Returns the exception handlers of this instruction.
    106 		 */
    107 		public ExceptionHandler[] getExceptionHandlers(){
    108 			return exceptionhandlers.getExceptionHandlers(getInstruction());
    109 		}
    110
    111 		/***
    112 		 * Returns a clone of the "outgoing" frame situation with respect to the given ExecutionChain.
    113 		 */
    114 		public Frame getOutFrame(ArrayList execChain){
    115 			executionPredecessors = execChain;
    116
    117 			Frame org;
    118
    119 			InstructionContext jsr = lastExecutionJSR();
    120
    121 			org = (Frame) outFrames.get(jsr);
    122
    123 			if (org == null){
    124 				throw new AssertionViolatedException("outFrame not set! This:\n"+this+"\nExecutionChain: "+getExecutionChain()+"\nOutFrames: '"+outFrames+"'.");
    125 			}
    126 			return org.getClone();
    127 		}
    128
    129     public Frame getInFrame() {
    130 		  Frame org;
    131
    132 			InstructionContext jsr = lastExecutionJSR();
    133
    134 			org = (Frame) inFrames.get(jsr);
    135
    136 			if (org == null){
    137 			    throw new AssertionViolatedException("inFrame not set! This:\n"+this+"\nInFrames: '"+inFrames+"'.");
    138       }
    139       return org.getClone();
    140     }
    141
    142 		/***
    143 		 * "Merges in" (vmspec2, page 146) the "incoming" frame situation;
    144 		 * executes the instructions symbolically
    145 		 * and therefore calculates the "outgoing" frame situation.
    146 		 * Returns: True iff the "incoming" frame situation changed after
    147 		 * merging with "inFrame".
    148 		 * The execPreds ArrayList must contain the InstructionContext
    149 		 * objects executed so far in the correct order. This is just
    150 		 * one execution path [out of many]. This is needed to correctly
    151 		 * "merge" in the special case of a RET's successor.
    152 		 * <B>The InstConstraintVisitor and ExecutionVisitor instances
    153 		 * must be set up correctly.</B>
    154 		 * @return true - if and only if the "outgoing" frame situation
    155 		 * changed from the one before execute()ing.
    156 		 */
    157 		public boolean execute(Frame inFrame, ArrayList execPreds, InstConstraintVisitor icv, ExecutionVisitor ev){
    158
    159 			executionPredecessors = (ArrayList) execPreds.clone();
    160
    161 			//sanity check
    162 			if ( (lastExecutionJSR() == null) && (subroutines.subroutineOf(getInstruction()) != subroutines.getTopLevel() ) ){
    163 				throw new AssertionViolatedException("Huh?! Am I '"+this+"' part of a subroutine or not?");
    164 			}
    165 			if ( (lastExecutionJSR() != null) && (subroutines.subroutineOf(getInstruction()) == subroutines.getTopLevel() ) ){
    166 				throw new AssertionViolatedException("Huh?! Am I '"+this+"' part of a subroutine or not?");
    167 			}
    168
    169 			Frame inF = (Frame) inFrames.get(lastExecutionJSR());
    170 			if (inF == null){// no incoming frame was set, so set it.
    171 				inFrames.put(lastExecutionJSR(), inFrame);
    172 				inF = inFrame;
    173 			}
    174 			else{// if there was an "old" inFrame
    175 				if (inF.equals(inFrame)){ //shortcut: no need to merge equal frames.
    176 					return false;
    177 				}
    178 				if (! mergeInFrames(inFrame)){
    179 					return false;
    180 				}
    181 			}
    182
    183 			// Now we're sure the inFrame has changed!
    184
    185 			// new inFrame is already merged in, see above.
    186 			Frame workingFrame = inF.getClone();
    187
    188 			try{
    189 				// This verifies the InstructionConstraint for the current
    190 				// instruction, but does not modify the workingFrame object.
    191 //InstConstraintVisitor icv = InstConstraintVisitor.getInstance(VerifierFactory.getVerifier(method_gen.getClassName()));
    192 				icv.setFrame(workingFrame);
    193 				getInstruction().accept(icv);
    194 			}
    195 			catch(StructuralCodeConstraintException ce){
    196 				ce.extendMessage("","\nInstructionHandle: "+getInstruction()+"\n");
    197 				ce.extendMessage("","\nExecution Frame:\n"+workingFrame);
    198 				extendMessageWithFlow(ce);
    199 				throw ce;
    200 			}
    201
    202 			// This executes the Instruction.
    203 			// Therefore the workingFrame object is modified.
    204 //ExecutionVisitor ev = ExecutionVisitor.getInstance(VerifierFactory.getVerifier(method_gen.getClassName()));
    205 			ev.setFrame(workingFrame);
    206 			getInstruction().accept(ev);
    207 			//getInstruction().accept(ExecutionVisitor.withFrame(workingFrame));
    208 			outFrames.put(lastExecutionJSR(), workingFrame);
    209
    210 			return true;	// new inFrame was different from old inFrame so merging them
    211 										// yielded a different this.inFrame.
    212 		}
    213
    214 		/***
    215 		 * Returns a simple String representation of this InstructionContext.
    216 		 */
    217 		public String toString(){
    218 		//TODO: Put information in the brackets, e.g.
    219 		//      Is this an ExceptionHandler? Is this a RET? Is this the start of
    220 		//      a subroutine?
    221 			String ret = getInstruction().toString(false)+"\t[InstructionContext]";
    222 			return ret;
    223 		}
    224
    225 		/***
    226 		 * Does the actual merging (vmspec2, page 146).
    227 		 * Returns true IFF this.inFrame was changed in course of merging with inFrame.
    228 		 */
    229 		private boolean mergeInFrames(Frame inFrame){
    230 			// TODO: Can be performance-improved.
    231 			Frame inF = (Frame) inFrames.get(lastExecutionJSR());
    232 			OperandStack oldstack = inF.getStack().getClone();
    233 			LocalVariables oldlocals = inF.getLocals().getClone();
    234 			try{
    235 				inF.getStack().merge(inFrame.getStack());
    236 				inF.getLocals().merge(inFrame.getLocals());
    237 			}
    238 			catch (StructuralCodeConstraintException sce){
    239 				extendMessageWithFlow(sce);
    240 				throw sce;
    241 			}
    242 			if (	oldstack.equals(inF.getStack()) &&
    243 						oldlocals.equals(inF.getLocals()) ){
    244 				return false;
    245 			}
    246 			else{
    247 				return true;
    248 			}
    249 		}
    250
    251 		/***
    252 		 * Returns the control flow execution chain. This is built
    253 		 * while execute(Frame, ArrayList)-ing the code represented
    254 		 * by the surrounding ControlFlowGraph.
    255 		 */
    256 		private String getExecutionChain(){
    257 			String s = this.toString();
    258 			for (int i=executionPredecessors.size()-1; i>=0; i--){
    259 				s = executionPredecessors.get(i)+"\n" + s;
    260 			}
    261 			return s;
    262 		}
    263
    264
    265 		/***
    266 		 * Extends the StructuralCodeConstraintException ("e") object with an at-the-end-extended message.
    267 		 * This extended message will then reflect the execution flow needed to get to the constraint
    268 		 * violation that triggered the throwing of the "e" object.
    269 		 */
    270 		private void extendMessageWithFlow(StructuralCodeConstraintException e){
    271 			String s = "Execution flow:\n";
    272 			e.extendMessage("", s+getExecutionChain());
    273 		}
    274
    275 		/*
    276 		 * Fulfils the contract of InstructionContext.getInstruction().
    277 		 */
    278 		public InstructionHandle getInstruction(){
    279 			return instruction;
    280 		}
    281
    282 		/***
    283 		 * Returns the InstructionContextImpl with an JSR/JSR_W
    284 		 * that was last in the ExecutionChain, without
    285 		 * a corresponding RET, i.e.
    286 		 * we were called by this one.
    287 		 * Returns null if we were called from the top level.
    288 		 */
    289 		private InstructionContextImpl lastExecutionJSR(){
    290
    291 			int size = executionPredecessors.size();
    292 			int retcount = 0;
    293
    294 			for (int i=size-1; i>=0; i--){
    295 				InstructionContextImpl current = (InstructionContextImpl) (executionPredecessors.get(i));
    296 				Instruction currentlast = current.getInstruction().getInstruction();
    297 				if (currentlast instanceof RET) {
    298                     retcount++;
    299                 }
    300 				if (currentlast instanceof JsrInstruction){
    301 					retcount--;
    302 					if (retcount == -1) {
    303                         return current;
    304                     }
    305 				}
    306 			}
    307 			return null;
    308 		}
    309
    310 		/* Satisfies InstructionContext.getSuccessors(). */
    311 		public InstructionContext[] getSuccessors(){
    312 			return contextsOf(_getSuccessors());
    313 		}
    314
    315 		/***
    316 		 * A utility method that calculates the successors of a given InstructionHandle
    317 		 * That means, a RET does have successors as defined here.
    318 		 * A JsrInstruction has its target as its successor
    319 		 * (opposed to its physical successor) as defined here.
    320 		 */
    321 // TODO: implement caching!
    322 		private InstructionHandle[] _getSuccessors(){
    323 			final InstructionHandle[] empty = new InstructionHandle[0];
    324 			final InstructionHandle[] single = new InstructionHandle[1];
    325 			final InstructionHandle[] pair = new InstructionHandle[2];
    326
    327 			Instruction inst = getInstruction().getInstruction();
    328
    329 			if (inst instanceof RET){
    330 				Subroutine s = subroutines.subroutineOf(getInstruction());
    331 				if (s==null){ //return empty; // RET in dead code. "empty" would be the correct answer, but we know something about the surrounding project...
    332 					throw new AssertionViolatedException("Asking for successors of a RET in dead code?!");
    333 				}
    334
    335 //TODO: remove. Only JustIce must not use it, but foreign users of the ControlFlowGraph
    336 //      will want it. Thanks Johannes Wust.
    337 //throw new AssertionViolatedException("DID YOU REALLY WANT TO ASK FOR RET'S SUCCS?");
    338
    339 				InstructionHandle[] jsrs = s.getEnteringJsrInstructions();
    340 				InstructionHandle[] ret = new InstructionHandle[jsrs.length];
    341 				for (int i=0; i<jsrs.length; i++){
    342 					ret[i] = jsrs[i].getNext();
    343 				}
    344 				return ret;
    345 			}
    346
    347 			// Terminates method normally.
    348 			if (inst instanceof ReturnInstruction){
    349 				return empty;
    350 			}
    351
    352 			// Terminates method abnormally, because JustIce mandates
    353 			// subroutines not to be protected by exception handlers.
    354 			if (inst instanceof ATHROW){
    355 				return empty;
    356 			}
    357
    358 			// See method comment.
    359 			if (inst instanceof JsrInstruction){
    360 				single[0] = ((JsrInstruction) inst).getTarget();
    361 				return single;
    362 			}
    363
    364 			if (inst instanceof GotoInstruction){
    365 				single[0] = ((GotoInstruction) inst).getTarget();
    366 				return single;
    367 			}
    368
    369 			if (inst instanceof BranchInstruction){
    370 				if (inst instanceof Select){
    371 					// BCEL's getTargets() returns only the non-default targets,
    372 					// thanks to Eli Tilevich for reporting.
    373 					InstructionHandle[] matchTargets = ((Select) inst).getTargets();
    374 					InstructionHandle[] ret = new InstructionHandle[matchTargets.length+1];
    375 					ret[0] = ((Select) inst).getTarget();
    376 					System.arraycopy(matchTargets, 0, ret, 1, matchTargets.length);
    377 					return ret;
    378 				}
    379 				else{
    380 					pair[0] = getInstruction().getNext();
    381 					pair[1] = ((BranchInstruction) inst).getTarget();
    382 					return pair;
    383 				}
    384 			}
    385
    386 			// default case: Fall through.
    387 			single[0] = getInstruction().getNext();
    388 			return single;
    389 		}
    390
    391 	} // End Inner InstructionContextImpl Class.
    392
    393 	/*** The MethodGen object we're working on. */
    394 	private final MethodGen method_gen;
    395
    396 	/*** The Subroutines object for the method whose control flow is represented by this ControlFlowGraph. */
    397 	private final Subroutines subroutines;
    398
    399 	/*** The ExceptionHandlers object for the method whose control flow is represented by this ControlFlowGraph. */
    400 	private final ExceptionHandlers exceptionhandlers;
    401
    402 	/*** All InstructionContext instances of this ControlFlowGraph. */
    403 	private Hashtable instructionContexts = new Hashtable(); //keys: InstructionHandle, values: InstructionContextImpl
    404
    405 	/***
    406 	 * A Control Flow Graph.
    407 	 */
    408 	public ControlFlowGraph(MethodGen method_gen){
    409 		subroutines = new Subroutines(method_gen);
    410 		exceptionhandlers = new ExceptionHandlers(method_gen);
    411
    412 		InstructionHandle[] instructionhandles = method_gen.getInstructionList().getInstructionHandles();
    413 		for (int i=0; i<instructionhandles.length; i++){
    414 			instructionContexts.put(instructionhandles[i], new InstructionContextImpl(instructionhandles[i]));
    415 		}
    416
    417 		this.method_gen = method_gen;
    418 	}
    419
    420 	/***
    421 	 * Returns the InstructionContext of a given instruction.
    422 	 */
    423 	public InstructionContext contextOf(InstructionHandle inst){
    424 		InstructionContext ic = (InstructionContext) instructionContexts.get(inst);
    425 		if (ic == null){
    426 			throw new AssertionViolatedException("InstructionContext requested for an InstructionHandle that's not known!");
    427 		}
    428 		return ic;
    429 	}
    430
    431 	/***
    432 	 * Returns the InstructionContext[] of a given InstructionHandle[],
    433 	 * in a naturally ordered manner.
    434 	 */
    435 	public InstructionContext[] contextsOf(InstructionHandle[] insts){
    436 		InstructionContext[] ret = new InstructionContext[insts.length];
    437 		for (int i=0; i<insts.length; i++){
    438 			ret[i] = contextOf(insts[i]);
    439 		}
    440 		return ret;
    441 	}
    442
    443 	/***
    444 	 * Returns an InstructionContext[] with all the InstructionContext instances
    445 	 * for the method whose control flow is represented by this ControlFlowGraph
    446 	 * <B>(NOT ORDERED!)</B>.
    447 	 */
    448 	public InstructionContext[] getInstructionContexts(){
    449 		InstructionContext[] ret = new InstructionContext[instructionContexts.values().size()];
    450 		return (InstructionContext[]) instructionContexts.values().toArray(ret);
    451 	}
    452
    453 	/***
    454 	 * Returns true, if and only if the said instruction is not reachable; that means,
    455 	 * if it is not part of this ControlFlowGraph.
    456 	 */
    457 	public boolean isDead(InstructionHandle i){
    458         return subroutines.subroutineOf(i) == null;
    459 	}
    460 }