1 package com.sun.org.apache.bcel.internal.verifier.structurals; 2 3 56 57 import com.sun.org.apache.bcel.internal.generic.*; 58 import com.sun.org.apache.bcel.internal.verifier.VerifierFactory; 59 import com.sun.org.apache.bcel.internal.verifier.exc.*; 60 import java.util.*; 61 62 68 public class ControlFlowGraph{ 69 70 74 private class InstructionContextImpl implements InstructionContext{ 75 76 83 private int TAG; 84 85 88 private InstructionHandle instruction; 89 90 93 private HashMap inFrames; 95 98 private HashMap outFrames; 100 104 private ArrayList executionPredecessors = null; 106 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 119 public int getTag(){ 120 return TAG; 121 } 122 123 124 public void setTag(int tag){ 125 TAG = tag; 126 } 127 128 131 public ExceptionHandler[] getExceptionHandlers(){ 132 return exceptionhandlers.getExceptionHandlers(getInstruction()); 133 } 134 135 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 168 public boolean execute(Frame inFrame, ArrayList execPreds, InstConstraintVisitor icv, ExecutionVisitor ev){ 169 170 executionPredecessors = (ArrayList) execPreds.clone(); 171 172 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){ inFrames.put(lastExecutionJSR(), inFrame); 183 inF = inFrame; 184 } 185 else{ if (inF.equals(inFrame)){ return false; 188 } 189 if (! mergeInFrames(inFrame)){ 190 return false; 191 } 192 } 193 194 196 Frame workingFrame = inF.getClone(); 198 199 try{ 200 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 ev.setFrame(workingFrame); 217 getInstruction().accept(ev); 218 outFrames.put(lastExecutionJSR(), workingFrame); 220 221 return true; } 224 225 228 public String toString(){ 229 String ret = getInstruction().toString(false)+"\t[InstructionContext]"; 233 return ret; 234 } 235 236 240 private boolean mergeInFrames(Frame inFrame){ 241 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 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 281 private void extendMessageWithFlow(StructuralCodeConstraintException e){ 282 String s = "Execution flow:\n"; 283 e.extendMessage("", s+getExecutionChain()); 284 } 285 286 289 public InstructionHandle getInstruction(){ 290 return instruction; 291 } 292 293 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 318 public InstructionContext[] getSuccessors(){ 319 return contextsOf(_getSuccessors()); 320 } 321 322 328 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){ throw new AssertionViolatedException("Asking for successors of a RET in dead code?!"); 340 } 341 throw new AssertionViolatedException("DID YOU REALLY WANT TO ASK FOR RET'S SUCCS?"); 343 351 } 352 353 if (inst instanceof ReturnInstruction){ 355 return empty; 356 } 357 358 if (inst instanceof ATHROW){ 361 return empty; 362 } 363 364 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 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 single[0] = getInstruction().getNext(); 394 return single; 395 } 396 397 } 399 400 private final MethodGen method_gen; 401 402 403 private final Subroutines subroutines; 404 405 406 private final ExceptionHandlers exceptionhandlers; 407 408 409 private Hashtable instructionContexts = new Hashtable(); 411 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 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 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 454 public InstructionContext[] getInstructionContexts(){ 455 InstructionContext[] ret = new InstructionContext[instructionContexts.values().size()]; 456 return (InstructionContext[]) instructionContexts.values().toArray(ret); 457 } 458 459 463 public boolean isDead(InstructionHandle i){ 464 return instructionContexts.containsKey(i); 465 } 466 } 467 | Popular Tags |