View Javadoc
1 /*** 2 * ControlFlowGraph 3 * 4 * This is a class which represents a ControlFlowGraph. 5 * 6 * It subclasses the Graph from org/apache/commons/graph 7 * and stores things such as the MethodGen object. 8 */ 9 10 package junit.quilt.cover.generic; 11 12 import junit.quilt.exception.QuiltException; 13 14 import org.apache.bcel.*; 15 import org.apache.bcel.generic.*; 16 import org.apache.bcel.classfile.*; 17 18 import org.apache.commons.graph.*; 19 import org.apache.commons.graph.algorithm.search.*; 20 import org.apache.commons.graph.domain.basic.*; 21 22 import java.util.*; 23 24 public class ControlFlowGraph 25 extends DirectedGraphImpl 26 implements DirectedGraph 27 { 28 private ClassGen clazz = null; 29 private MethodGen method = null; 30 private Method oldMethod = null; 31 private ConstantPoolGen pool = null; 32 private BlockVertex start = null; 33 private BlockVertex end = null; 34 35 private Map jsrEdges = new HashMap(); // JSR Edge/Edge 36 37 /*** 38 * This constructs an empty ControlFlowGraph 39 * for the current class. 40 * 41 * You need to call "initialize()" before the 42 * graph is valid. 43 */ 44 public ControlFlowGraph(InstContext context, 45 MethodGen method) 46 { 47 super( ); 48 this.clazz = context.getClassGen(); 49 this.method = method; 50 this.oldMethod = method.getMethod(); 51 this.pool = context.getConstantPoolGen(); 52 } 53 54 public void initialize( EdgeFactory factory ) { 55 SortedMap blocks = findBlocks( factory, method, pool ); // Position X Block Vertex 56 57 // Simple Setup 58 LocalVariableTable lvt = // Local Variable definitions. 59 method.getLocalVariableTable( pool ); 60 61 setStartVertex( factory.makeStartVertex() ); 62 setEndVertex( factory.makeEndVertex() ); 63 64 // This is to make sure our vertex is attached to 65 // the right entry point. 66 67 BlockVertex first = (BlockVertex) blocks.get( blocks.firstKey() ); 68 69 addEdge( factory.makeNormalEdge( getStartVertex(), 70 first ), 71 getStartVertex(), 72 first); 73 74 75 // Now, we iterate over all of the blocks, and set up their 76 // edges. . . 77 78 Iterator allBlocks = blocks.values().iterator(); 79 while (allBlocks.hasNext()) { 80 BlockVertex vertex = (BlockVertex) allBlocks.next(); 81 InstructionHandle last = vertex.getLastInst(); 82 InstructionHandle next = last.getNext(); 83 84 if (last.getInstruction() instanceof ReturnInstruction) { 85 FlowControlEdge rEdge = factory.makeReturnEdge( vertex ); 86 addEdge( rEdge, vertex, getEndVertex() ); 87 88 } else if (last.getInstruction() instanceof RET) { 89 // RET - End of the line for a Subroutine. 90 // We do nothing to handle this. 91 } else if (last.getInstruction() instanceof Select) { 92 handleSelect( factory, next, last, vertex, blocks, lvt ); 93 } else if (last.getInstruction() instanceof IfInstruction) { 94 handleIf( factory, next, last, vertex, blocks, lvt ); 95 } else if (last.getInstruction() instanceof GotoInstruction) { 96 handleGoto( factory, next, last, vertex, blocks, lvt ); 97 } else if (last.getInstruction() instanceof JsrInstruction) { 98 handleJSR( factory, next, last, vertex, blocks, lvt ); 99 } else if (last.getInstruction() instanceof ExceptionThrower) { 100 handleExceptionThrower( factory, next, last, 101 vertex, blocks, lvt ); 102 } else { 103 handleNormal( factory, next, last, vertex, blocks, lvt ); 104 } 105 } 106 107 Iterator jsrs = jsrEdges.keySet().iterator(); 108 while (jsrs.hasNext()) { 109 FlowControlEdge jEdge = // JSR Edge 110 (FlowControlEdge) jsrs.next(); 111 FlowControlEdge nEdge = // "Normal" Edge 112 (FlowControlEdge) jsrEdges.get( jEdge ); 113 114 BlockVertex jsrInst = // This is where we enter. 115 (BlockVertex) getSource( jEdge ); 116 BlockVertex start = // Where we start inlining 117 (BlockVertex) getTarget( jEdge ); 118 BlockVertex target = // When we find a RET, where to direct it to. 119 (BlockVertex) getTarget( nEdge ); 120 121 JSRInliner inliner = new JSRInliner( factory, target ); 122 123 DFS dfs = new DFS(); 124 dfs.visit( this, start, inliner ); // A miracle occours 125 126 // At this point, the Subroutine has been copied 127 // 128 // The RET instructions in the copied routine have been 129 // changed to NormalEdges pointing to the target of 130 // the normal edge which will disappear real soon. 131 // 132 // getRoot() of the inliner, will return the copy of 133 // the JSR Target we started the graph with. 134 // 135 136 removeEdge( jEdge ); 137 removeEdge( nEdge ); 138 addEdge( factory.makeNormalEdge( jsrInst, inliner.getRoot() ), 139 jsrInst, inliner.getRoot()); 140 if (jsrInst.getLastInst().getInstruction() instanceof RET) { 141 jsrInst.chomp(); 142 } 143 } 144 } 145 146 /*** 147 * Returns a map between the Position 148 * of an Instruction, and the BlockVertex 149 * which contains it. 150 * 151 * It uses the method and pool to initialize 152 * everything. 153 * 154 * @param method The method the graph is representing. 155 * @param pool The constant pool. 156 */ 157 158 private SortedMap findBlocks( EdgeFactory factory, 159 MethodGen method, 160 ConstantPoolGen pool ) 161 { 162 InstructionList iList = method.getInstructionList(); 163 LineNumberTable lines = method.getLineNumberTable( pool ); 164 165 InstructionHandle inst[] = iList.getInstructionHandles(); 166 SortedMap RC = new TreeMap(); 167 168 BlockVertex block = null; 169 170 boolean startNewBlock = true; 171 172 int lastStart = 0; 173 int i = 0; 174 while (i < inst.length) { 175 // If the block is targeted by anything other than 176 // the previous instruction, we need to put it on 177 // a new block. 178 179 if (hasInbound( inst[i] )) { 180 startNewBlock = true; 181 } 182 183 if (startNewBlock) { 184 lastStart = i; 185 startNewBlock = false; 186 187 if (block != null) { 188 addVertex( block ); 189 RC.put( new Integer( block.getPCStart() ), block ); 190 } 191 192 block = factory.makeBlockVertex( lines ); 193 } 194 195 block.addInstruction( inst[i] ); 196 197 if (hasOutbound( inst[i] )) { 198 startNewBlock = true; 199 } 200 i++; 201 } 202 if (block.length() > 0) { 203 addVertex( block ); 204 RC.put( new Integer( block.getPCStart() ), block ); 205 } 206 207 return RC; 208 } 209 210 /*** 211 * Given an InstructionHandle, it builds up a String 212 * representing what comprises the top element 213 * of the stack. 214 * 215 * It works, by looking at the stack backwards 216 * 217 * @param handle is the handle we want to find the 218 * stack value for. 219 * 220 * @param locals is a LocalVariableTable which is 221 * used for looking up the name of a variable. 222 */ 223 public String getStackContents( InstructionHandle handle, 224 LocalVariableTable locals ) 225 { 226 Instruction inst = handle.getInstruction(); 227 228 if (hasInbound( handle )) { 229 return "???"; 230 } 231 232 if (inst instanceof LoadInstruction) { 233 int index = ((LoadInstruction) inst).getIndex(); 234 return locals.getLocalVariable(index).getName(); 235 } 236 237 return "???"; 238 } 239 240 private BlockVertex lookup( Map vertices, int position ) 241 { 242 if (!vertices.containsKey( new Integer( position ))) 243 System.err.println("WARNING! Tried to get non existant block!"); 244 245 return (BlockVertex) vertices.get( new Integer( position ) ); 246 } 247 248 private BlockVertex lookup( Map vertices, InstructionHandle ih ) 249 { 250 if (!vertices.containsKey( new Integer( ih.getPosition() ))) 251 System.err.println("WARNING! Tried to get non existant block!"); 252 253 return (BlockVertex) vertices.get( new Integer( ih.getPosition() )); 254 } 255 256 private boolean isCatchCompatible( Class exception, ObjectType catchType ) 257 { 258 return true; 259 260 // TODO: Fix this in BCEL!!!!! 261 262 // NULL means ALL. 263 // if (catchType == null) return true; 264 265 // ObjectType excepType = 266 // new ObjectType( exception.getName() ); 267 268 // if (excepType.getSignature().equals( catchType.getSignature() )) 269 // return true; 270 // return catchType.subclassOf( excepType ); 271 } 272 273 public BlockVertex getStartVertex() { 274 return this.start; 275 } 276 277 public BlockVertex getEndVertex() { 278 return this.end; 279 } 280 281 public void setStartVertex(BlockVertex start) { 282 this.start = start; 283 addVertex( start ); 284 } 285 286 public void setEndVertex(BlockVertex end) { 287 this.end = end; 288 addVertex( end ); 289 } 290 291 public int makeNewLocal(String name, Type type) { 292 LocalVariableGen lvg = 293 method.addLocalVariable( name, type, 294 method.getInstructionList().getStart(), 295 method.getInstructionList().getEnd()); 296 297 return lvg.getIndex(); 298 } 299 300 public Method getMethod() { 301 BytecodeLayout layout = new BytecodeLayout( method ); 302 DFS dfs = new DFS(); 303 dfs.visit( this, getStartVertex(), layout ); 304 305 // layout.visit( this, getStartVertex() ); 306 307 try { 308 return layout.getMethod(); 309 } catch (QuiltException e) { 310 System.err.println("Warning: Instrumentation Failed."); 311 e.printStackTrace(); 312 return oldMethod; 313 } 314 } 315 316 public boolean doesHandle( InstructionHandle ih, 317 CodeExceptionGen handler ) 318 { 319 InstructionHandle curr = handler.getStartPC(); 320 321 if (handler.getEndPC() == ih) return true; 322 323 while ( curr != handler.getEndPC() ) { 324 if (ih == curr) return true; 325 curr = curr.getNext(); 326 } 327 328 return false; 329 } 330 331 public String getMethodName() { 332 return method.getName(); 333 } 334 335 public void updateEdge( FlowControlEdge edge ) { 336 if ( getEdges().contains( edge )) { 337 removeEdge( edge ); 338 } 339 addEdge( edge ); 340 } 341 342 public void addEdge( FlowControlEdge edge ) { 343 BlockVertex source = edge.getSource(); 344 BlockVertex target = edge.getTarget(); 345 346 if (source == null) { 347 source = getStartVertex(); 348 } 349 350 if (target == null) { 351 target = getEndVertex(); 352 } 353 354 addEdge( edge, source, target ); 355 } 356 357 private void handleNormal( EdgeFactory factory, 358 InstructionHandle next, 359 InstructionHandle last, 360 BlockVertex vertex, 361 Map blocks, 362 LocalVariableTable lvt) { 363 BlockVertex target = lookup( blocks, next ); 364 if (target == null) System.err.println("Wrong Lookup in handleNormal"); 365 FlowControlEdge nEdge = 366 factory.makeNormalEdge( vertex, target ); 367 368 addEdge( nEdge ); 369 } 370 371 private void handleSelect( EdgeFactory factory, 372 InstructionHandle next, 373 InstructionHandle last, 374 BlockVertex vertex, 375 Map blocks, 376 LocalVariableTable lvt) { 377 378 Select instruction = (Select) last.getInstruction(); 379 String expr = getStackContents( last, lvt ); 380 InstructionHandle targets[] = 381 instruction.getTargets(); 382 int match[] = 383 instruction.getMatchs(); 384 385 BlockVertex target; 386 FlowControlEdge sEdge; 387 388 // CASE . . . 389 for (int i = 0; i < targets.length; i++) { 390 target = lookup( blocks, targets[i] ); 391 if (target == null) System.err.println("Wrong Lookup in handleSelect(1)"); 392 sEdge = factory.makeSelectEdge( vertex, target, 393 expr, match[i] ); 394 395 addEdge( sEdge, vertex, target ); 396 } 397 398 // DEFAULT 399 target = lookup( blocks, instruction.getTarget() ); 400 if (target == null) System.err.println("Wrong Lookup in handleSelect(2)"); 401 402 sEdge = factory.makeSelectEdge( vertex, target, expr ); 403 404 addEdge( sEdge, vertex, target ); 405 } 406 407 private void handleIf( EdgeFactory factory, 408 InstructionHandle next, 409 InstructionHandle last, 410 BlockVertex vertex, 411 Map blocks, 412 LocalVariableTable lvt) { 413 414 BlockVertex target; 415 FlowControlEdge bEdge; 416 String expr = getStackContents( last, lvt ); 417 IfInstruction ifInst = 418 (IfInstruction) last.getInstruction(); 419 420 // THEN 421 target = lookup( blocks, ifInst.getTarget() ); 422 if (target == null) System.err.println("Wrong Lookup in handleIf(1)"); 423 424 bEdge = factory.makeBranchEdge( vertex, target, expr, true ); 425 426 addEdge( bEdge, vertex, target ); 427 428 // ELSE 429 target = lookup( blocks, next ); 430 if (target == null) System.err.println("Wrong Lookup in handleIf(2)"); 431 432 bEdge = factory.makeBranchEdge( vertex, target, expr, false ); 433 434 addEdge( bEdge, vertex, target ); 435 } 436 437 private void handleGoto( EdgeFactory factory, 438 InstructionHandle next, 439 InstructionHandle last, 440 BlockVertex vertex, 441 Map blocks, 442 LocalVariableTable lvt) { 443 444 // Unconditional Jump 445 GotoInstruction goI = (GotoInstruction) last.getInstruction(); 446 BlockVertex target = lookup( blocks, goI.getTarget() ); 447 if (target == null) System.err.println("Wrong Lookup in handleGoto"); 448 449 FlowControlEdge nEdge = 450 factory.makeNormalEdge( vertex, target ); 451 452 addEdge( nEdge, vertex, target ); 453 } 454 455 private void handleJSR( EdgeFactory factory, 456 InstructionHandle next, 457 InstructionHandle last, 458 BlockVertex vertex, 459 Map blocks, 460 LocalVariableTable lvt) { 461 // SUBROUTINE. . . Don't forget about the RET. 462 JsrInstruction jsrI = (JsrInstruction) last.getInstruction(); 463 464 BlockVertex jsrTarget = lookup( blocks, jsrI.getTarget() ); 465 BlockVertex nTarget = lookup( blocks, last.getNext() ); 466 467 FlowControlEdge jEdge = 468 factory.makeJSREdge( vertex, jsrTarget ); 469 FlowControlEdge nEdge = 470 factory.makeNormalEdge( vertex, nTarget ); 471 472 addEdge( jEdge, vertex, jsrTarget ); 473 addEdge( nEdge, vertex, nTarget ); 474 475 jsrEdges.put( jEdge, nEdge ); 476 } 477 478 private void handleExceptionThrower( EdgeFactory factory, 479 InstructionHandle next, 480 InstructionHandle last, 481 BlockVertex vertex, 482 Map blocks, 483 LocalVariableTable lvt) { 484 485 BlockVertex target = null; 486 if (last.getInstruction() instanceof InvokeInstruction) { 487 target = lookup( blocks, next ); 488 if (target == null) System.err.println("Wrong Lookup in handleExceptionThrower(1) -- next: " + next); 489 490 FlowControlEdge nEdge = factory.makeNormalEdge( vertex, 491 target ); 492 addEdge( nEdge, vertex, target ); 493 494 CodeExceptionGen handlers[] = 495 method.getExceptionHandlers(); 496 497 for (int j = 0; j < handlers.length; j++) { 498 if (doesHandle( last, handlers[j] )) { 499 target = lookup( blocks, handlers[j].getHandlerPC() ); 500 if (target == null) System.err.println("Wrong Lookup in handleExceptionThrower(2) -- handler: " + handlers[j].getHandlerPC() ); 501 502 FlowControlEdge xEdge = 503 factory.makeExceptionEdge( vertex, 504 target, 505 handlers[j].getCatchType()); 506 addEdge( xEdge, vertex, 507 lookup( blocks, 508 handlers[j].getHandlerPC() ) ); 509 } 510 } 511 } 512 // ATHROW always throws an Exception. So, don't 513 // create a Normal Edge for it. 514 if (!(last.getInstruction() instanceof ATHROW)) { 515 target = lookup( blocks, next ); 516 if (target == null) System.err.println("Wrong Lookup in handleExceptionThrower(3) -- next: " + next ); 517 518 FlowControlEdge nEdge = factory.makeNormalEdge( vertex, 519 target ); 520 521 addEdge(nEdge, vertex, target); 522 } 523 524 ExceptionThrower inst = 525 (ExceptionThrower) last.getInstruction(); 526 527 Class exceptions[] = inst.getExceptions(); 528 CodeExceptionGen handlers[] = 529 method.getExceptionHandlers(); 530 531 for (int i = 0; i < exceptions.length; i++) { 532 int numHandlers = 0; 533 for (int j = 0; j < handlers.length; j++) { 534 if (handlers[j].containsTarget( last )) { 535 if (isCatchCompatible( exceptions[i], 536 handlers[j].getCatchType())) { 537 numHandlers ++; 538 FlowControlEdge xEdge = 539 factory.makeExceptionEdge( vertex, 540 lookup( blocks, 541 handlers[j].getHandlerPC() ), 542 exceptions[i] ); 543 target = lookup( blocks, handlers[j].getHandlerPC() ); 544 if (target == null) System.err.println("Wrong Lookup in handleExceptionHandlers(4) -- handler: " + handlers[j].getHandlerPC() ); 545 addEdge( xEdge, vertex, target); 546 } 547 } 548 } 549 550 // if (numHandlers == 0) { 551 // FlowControlEdge xEdge = 552 // factory.makeExceptionEdge( vertex, 553 // exceptions[i]); 554 // addEdge( xEdge, vertex, getEndVertex() ); 555 // } 556 } 557 } 558 559 public boolean hasInbound( InstructionHandle instructionHandle ) { 560 if (instructionHandle.hasTargeters()) { 561 InstructionTargeter targeters[] = instructionHandle.getTargeters(); 562 for (int j = 0; j < targeters.length; j++) { 563 if (targeters[j] instanceof BranchInstruction) 564 return true; 565 if (targeters[j] instanceof CodeExceptionGen) 566 return true; 567 } 568 } 569 570 return false; 571 } 572 573 public boolean hasOutbound( InstructionHandle instructionHandle ) { 574 Instruction inst = instructionHandle.getInstruction(); 575 576 if (inst instanceof BranchInstruction) 577 return true; 578 if (inst instanceof ExceptionThrower) 579 return true; 580 return false; 581 } 582 583 584 } 585 586

This page was automatically generated by Maven