001/* 002 * Licensed to the Apache Software Foundation (ASF) under one or more 003 * contributor license agreements. See the NOTICE file distributed with 004 * this work for additional information regarding copyright ownership. 005 * The ASF licenses this file to You under the Apache License, Version 2.0 006 * (the "License"); you may not use this file except in compliance with 007 * the License. You may obtain a copy of the License at 008 * 009 * http://www.apache.org/licenses/LICENSE-2.0 010 * 011 * Unless required by applicable law or agreed to in writing, software 012 * distributed under the License is distributed on an "AS IS" BASIS, 013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 014 * See the License for the specific language governing permissions and 015 * limitations under the License. 016 * 017 */ 018package org.apache.bcel.verifier.structurals; 019 020 021import java.util.ArrayList; 022import java.util.HashMap; 023import java.util.List; 024import java.util.Map; 025 026import org.apache.bcel.generic.ATHROW; 027import org.apache.bcel.generic.BranchInstruction; 028import org.apache.bcel.generic.GotoInstruction; 029import org.apache.bcel.generic.Instruction; 030import org.apache.bcel.generic.InstructionHandle; 031import org.apache.bcel.generic.JsrInstruction; 032import org.apache.bcel.generic.MethodGen; 033import org.apache.bcel.generic.RET; 034import org.apache.bcel.generic.ReturnInstruction; 035import org.apache.bcel.generic.Select; 036import org.apache.bcel.verifier.exc.AssertionViolatedException; 037import org.apache.bcel.verifier.exc.StructuralCodeConstraintException; 038 039/** 040 * This class represents a control flow graph of a method. 041 * 042 */ 043public class ControlFlowGraph{ 044 045 /** 046 * Objects of this class represent a node in a ControlFlowGraph. 047 * These nodes are instructions, not basic blocks. 048 */ 049 private class InstructionContextImpl implements InstructionContext{ 050 051 /** 052 * The TAG field is here for external temporary flagging, such 053 * as graph colouring. 054 * 055 * @see #getTag() 056 * @see #setTag(int) 057 */ 058 private int TAG; 059 060 /** 061 * The InstructionHandle this InstructionContext is wrapped around. 062 */ 063 private final InstructionHandle instruction; 064 065 /** 066 * The 'incoming' execution Frames. 067 */ 068 private final Map<InstructionContext, Frame> inFrames; // key: the last-executed JSR 069 070 /** 071 * The 'outgoing' execution Frames. 072 */ 073 private final Map<InstructionContext, Frame> outFrames; // key: the last-executed JSR 074 075 /** 076 * The 'execution predecessors' - a list of type InstructionContext 077 * of those instances that have been execute()d before in that order. 078 */ 079 private List<InstructionContext> executionPredecessors = null; // Type: InstructionContext 080 081 /** 082 * Creates an InstructionHandleImpl object from an InstructionHandle. 083 * Creation of one per InstructionHandle suffices. Don't create more. 084 */ 085 public InstructionContextImpl(final InstructionHandle inst) { 086 if (inst == null) { 087 throw new AssertionViolatedException("Cannot instantiate InstructionContextImpl from NULL."); 088 } 089 090 instruction = inst; 091 inFrames = new HashMap<>(); 092 outFrames = new HashMap<>(); 093 } 094 095 /* Satisfies InstructionContext.getTag(). */ 096 @Override 097 public int getTag() { 098 return TAG; 099 } 100 101 /* Satisfies InstructionContext.setTag(int). */ 102 @Override 103 public void setTag(final int tag) { // part of InstructionContext interface 104 TAG = tag; 105 } 106 107 /** 108 * Returns the exception handlers of this instruction. 109 */ 110 @Override 111 public ExceptionHandler[] getExceptionHandlers() { 112 return exceptionhandlers.getExceptionHandlers(getInstruction()); 113 } 114 115 /** 116 * Returns a clone of the "outgoing" frame situation with respect to the given ExecutionChain. 117 */ 118 @Override 119 public Frame getOutFrame(final ArrayList<InstructionContext> execChain) { 120 executionPredecessors = execChain; 121 122 Frame org; 123 124 final InstructionContext jsr = lastExecutionJSR(); 125 126 org = outFrames.get(jsr); 127 128 if (org == null) { 129 throw new AssertionViolatedException( 130 "outFrame not set! This:\n"+this+"\nExecutionChain: "+getExecutionChain()+"\nOutFrames: '"+outFrames+"'."); 131 } 132 return org.getClone(); 133 } 134 135 @Override 136 public Frame getInFrame() { 137 Frame org; 138 139 final InstructionContext jsr = lastExecutionJSR(); 140 141 org = inFrames.get(jsr); 142 143 if (org == null) { 144 throw new AssertionViolatedException("inFrame not set! This:\n"+this+"\nInFrames: '"+inFrames+"'."); 145 } 146 return org.getClone(); 147 } 148 149 /** 150 * "Merges in" (vmspec2, page 146) the "incoming" frame situation; 151 * executes the instructions symbolically 152 * and therefore calculates the "outgoing" frame situation. 153 * Returns: True iff the "incoming" frame situation changed after 154 * merging with "inFrame". 155 * The execPreds ArrayList must contain the InstructionContext 156 * objects executed so far in the correct order. This is just 157 * one execution path [out of many]. This is needed to correctly 158 * "merge" in the special case of a RET's successor. 159 * <B>The InstConstraintVisitor and ExecutionVisitor instances 160 * must be set up correctly.</B> 161 * @return true - if and only if the "outgoing" frame situation 162 * changed from the one before execute()ing. 163 */ 164 @Override 165 public boolean execute(final Frame inFrame, final ArrayList<InstructionContext> execPreds, final InstConstraintVisitor icv, final ExecutionVisitor ev) { 166 167 @SuppressWarnings("unchecked") // OK because execPreds is compatible type 168 final List<InstructionContext> clone = (List<InstructionContext>) execPreds.clone(); 169 executionPredecessors = clone; 170 171 //sanity check 172 if ( (lastExecutionJSR() == null) && (subroutines.subroutineOf(getInstruction()) != subroutines.getTopLevel() ) ) { 173 throw new AssertionViolatedException("Huh?! Am I '"+this+"' part of a subroutine or not?"); 174 } 175 if ( (lastExecutionJSR() != null) && (subroutines.subroutineOf(getInstruction()) == subroutines.getTopLevel() ) ) { 176 throw new AssertionViolatedException("Huh?! Am I '"+this+"' part of a subroutine or not?"); 177 } 178 179 Frame inF = inFrames.get(lastExecutionJSR()); 180 if (inF == null) {// no incoming frame was set, so set it. 181 inFrames.put(lastExecutionJSR(), inFrame); 182 inF = inFrame; 183 } 184 else{// if there was an "old" inFrame 185 if (inF.equals(inFrame)) { //shortcut: no need to merge equal frames. 186 return false; 187 } 188 if (! mergeInFrames(inFrame)) { 189 return false; 190 } 191 } 192 193 // Now we're sure the inFrame has changed! 194 195 // new inFrame is already merged in, see above. 196 final Frame workingFrame = inF.getClone(); 197 198 try{ 199 // This verifies the InstructionConstraint for the current 200 // instruction, but does not modify the workingFrame object. 201//InstConstraintVisitor icv = InstConstraintVisitor.getInstance(VerifierFactory.getVerifier(method_gen.getClassName())); 202 icv.setFrame(workingFrame); 203 getInstruction().accept(icv); 204 } 205 catch(final StructuralCodeConstraintException ce) { 206 ce.extendMessage("","\nInstructionHandle: "+getInstruction()+"\n"); 207 ce.extendMessage("","\nExecution Frame:\n"+workingFrame); 208 extendMessageWithFlow(ce); 209 throw ce; 210 } 211 212 // This executes the Instruction. 213 // Therefore the workingFrame object is modified. 214//ExecutionVisitor ev = ExecutionVisitor.getInstance(VerifierFactory.getVerifier(method_gen.getClassName())); 215 ev.setFrame(workingFrame); 216 getInstruction().accept(ev); 217 //getInstruction().accept(ExecutionVisitor.withFrame(workingFrame)); 218 outFrames.put(lastExecutionJSR(), workingFrame); 219 220 return true; // new inFrame was different from old inFrame so merging them 221 // yielded a different this.inFrame. 222 } 223 224 /** 225 * Returns a simple String representation of this InstructionContext. 226 */ 227 @Override 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 final 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(final Frame inFrame) { 241 // TODO: Can be performance-improved. 242 final Frame inF = inFrames.get(lastExecutionJSR()); 243 final OperandStack oldstack = inF.getStack().getClone(); 244 final LocalVariables oldlocals = inF.getLocals().getClone(); 245 try { 246 inF.getStack().merge(inFrame.getStack()); 247 inF.getLocals().merge(inFrame.getLocals()); 248 } catch (final StructuralCodeConstraintException sce) { 249 extendMessageWithFlow(sce); 250 throw sce; 251 } 252 return !(oldstack.equals(inF.getStack()) && oldlocals.equals(inF.getLocals())); 253 } 254 255 /** 256 * Returns the control flow execution chain. This is built 257 * while execute(Frame, ArrayList)-ing the code represented 258 * by the surrounding ControlFlowGraph. 259 */ 260 private String getExecutionChain() { 261 String s = this.toString(); 262 for (int i=executionPredecessors.size()-1; i>=0; i--) { 263 s = executionPredecessors.get(i)+"\n" + s; 264 } 265 return s; 266 } 267 268 269 /** 270 * Extends the StructuralCodeConstraintException ("e") object with an at-the-end-extended message. 271 * This extended message will then reflect the execution flow needed to get to the constraint 272 * violation that triggered the throwing of the "e" object. 273 */ 274 private void extendMessageWithFlow(final StructuralCodeConstraintException e) { 275 final String s = "Execution flow:\n"; 276 e.extendMessage("", s+getExecutionChain()); 277 } 278 279 /* 280 * Fulfils the contract of InstructionContext.getInstruction(). 281 */ 282 @Override 283 public InstructionHandle getInstruction() { 284 return instruction; 285 } 286 287 /** 288 * Returns the InstructionContextImpl with an JSR/JSR_W 289 * that was last in the ExecutionChain, without 290 * a corresponding RET, i.e. 291 * we were called by this one. 292 * Returns null if we were called from the top level. 293 */ 294 private InstructionContextImpl lastExecutionJSR() { 295 296 final int size = executionPredecessors.size(); 297 int retcount = 0; 298 299 for (int i=size-1; i>=0; i--) { 300 final InstructionContextImpl current = (InstructionContextImpl) (executionPredecessors.get(i)); 301 final Instruction currentlast = current.getInstruction().getInstruction(); 302 if (currentlast instanceof RET) { 303 retcount++; 304 } 305 if (currentlast instanceof JsrInstruction) { 306 retcount--; 307 if (retcount == -1) { 308 return current; 309 } 310 } 311 } 312 return null; 313 } 314 315 /* Satisfies InstructionContext.getSuccessors(). */ 316 @Override 317 public InstructionContext[] getSuccessors() { 318 return contextsOf(_getSuccessors()); 319 } 320 321 /** 322 * A utility method that calculates the successors of a given InstructionHandle 323 * That means, a RET does have successors as defined here. 324 * A JsrInstruction has its target as its successor 325 * (opposed to its physical successor) as defined here. 326 */ 327// TODO: implement caching! 328 private InstructionHandle[] _getSuccessors() { 329 final InstructionHandle[] empty = new InstructionHandle[0]; 330 final InstructionHandle[] single = new InstructionHandle[1]; 331 332 final Instruction inst = getInstruction().getInstruction(); 333 334 if (inst instanceof RET) { 335 final Subroutine s = subroutines.subroutineOf(getInstruction()); 336 if (s==null) { //return empty; 337 // RET in dead code. "empty" would be the correct answer, but we know something about the surrounding project... 338 throw new AssertionViolatedException("Asking for successors of a RET in dead code?!"); 339 } 340 341//TODO: remove. Only JustIce must not use it, but foreign users of the ControlFlowGraph 342// will want it. Thanks Johannes Wust. 343//throw new AssertionViolatedException("DID YOU REALLY WANT TO ASK FOR RET'S SUCCS?"); 344 345 final InstructionHandle[] jsrs = s.getEnteringJsrInstructions(); 346 final InstructionHandle[] ret = new InstructionHandle[jsrs.length]; 347 for (int i=0; i<jsrs.length; i++) { 348 ret[i] = jsrs[i].getNext(); 349 } 350 return ret; 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 final InstructionHandle[] matchTargets = ((Select) inst).getTargets(); 380 final 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 final InstructionHandle[] pair = new InstructionHandle[2]; 386 pair[0] = getInstruction().getNext(); 387 pair[1] = ((BranchInstruction) inst).getTarget(); 388 return pair; 389 } 390 391 // default case: Fall through. 392 single[0] = getInstruction().getNext(); 393 return single; 394 } 395 396 } // End Inner InstructionContextImpl Class. 397 398 ///** The MethodGen object we're working on. */ 399 //private final MethodGen method_gen; 400 401 /** The Subroutines object for the method whose control flow is represented by this ControlFlowGraph. */ 402 private final Subroutines subroutines; 403 404 /** The ExceptionHandlers object for the method whose control flow is represented by this ControlFlowGraph. */ 405 private final ExceptionHandlers exceptionhandlers; 406 407 /** All InstructionContext instances of this ControlFlowGraph. */ 408 private final Map<InstructionHandle, InstructionContext> instructionContexts = new HashMap<>(); 409 410 /** 411 * A Control Flow Graph; with additional JustIce checks 412 * @param method_gen the method generator instance 413 */ 414 public ControlFlowGraph(final MethodGen method_gen) { 415 this(method_gen, true); 416 } 417 418 /** 419 * A Control Flow Graph. 420 * @param method_gen the method generator instance 421 * @param enableJustIceCheck if true, additional JustIce checks are performed 422 * @since 6.0 423 */ 424 public ControlFlowGraph(final MethodGen method_gen, final boolean enableJustIceCheck) { 425 subroutines = new Subroutines(method_gen, enableJustIceCheck); 426 exceptionhandlers = new ExceptionHandlers(method_gen); 427 428 final InstructionHandle[] instructionhandles = method_gen.getInstructionList().getInstructionHandles(); 429 for (final InstructionHandle instructionhandle : instructionhandles) { 430 instructionContexts.put(instructionhandle, new InstructionContextImpl(instructionhandle)); 431 } 432 433 //this.method_gen = method_gen; 434 } 435 436 /** 437 * Returns the InstructionContext of a given instruction. 438 */ 439 public InstructionContext contextOf(final InstructionHandle inst) { 440 final InstructionContext ic = instructionContexts.get(inst); 441 if (ic == null) { 442 throw new AssertionViolatedException("InstructionContext requested for an InstructionHandle that's not known!"); 443 } 444 return ic; 445 } 446 447 /** 448 * Returns the InstructionContext[] of a given InstructionHandle[], 449 * in a naturally ordered manner. 450 */ 451 public InstructionContext[] contextsOf(final InstructionHandle[] insts) { 452 final InstructionContext[] ret = new InstructionContext[insts.length]; 453 for (int i=0; i<insts.length; i++) { 454 ret[i] = contextOf(insts[i]); 455 } 456 return ret; 457 } 458 459 /** 460 * Returns an InstructionContext[] with all the InstructionContext instances 461 * for the method whose control flow is represented by this ControlFlowGraph 462 * <B>(NOT ORDERED!)</B>. 463 */ 464 public InstructionContext[] getInstructionContexts() { 465 final InstructionContext[] ret = new InstructionContext[instructionContexts.values().size()]; 466 return instructionContexts.values().toArray(ret); 467 } 468 469 /** 470 * Returns true, if and only if the said instruction is not reachable; that means, 471 * if it is not part of this ControlFlowGraph. 472 */ 473 public boolean isDead(final InstructionHandle i) { 474 return subroutines.subroutineOf(i) == null; 475 } 476}