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

This page was automatically generated by Maven