1 17 package org.apache.bcel.verifier.structurals; 18 19 import java.util.ArrayList ; 20 import java.util.HashSet ; 21 import java.util.Hashtable ; 22 import java.util.Iterator ; 23 import java.util.Set ; 24 import org.apache.bcel.generic.ASTORE; 25 import org.apache.bcel.generic.ATHROW; 26 import org.apache.bcel.generic.BranchInstruction; 27 import org.apache.bcel.generic.CodeExceptionGen; 28 import org.apache.bcel.generic.GotoInstruction; 29 import org.apache.bcel.generic.IndexedInstruction; 30 import org.apache.bcel.generic.Instruction; 31 import org.apache.bcel.generic.InstructionHandle; 32 import org.apache.bcel.generic.JsrInstruction; 33 import org.apache.bcel.generic.LocalVariableInstruction; 34 import org.apache.bcel.generic.MethodGen; 35 import org.apache.bcel.generic.RET; 36 import org.apache.bcel.generic.ReturnInstruction; 37 import org.apache.bcel.generic.Select; 38 import org.apache.bcel.verifier.exc.AssertionViolatedException; 39 import org.apache.bcel.verifier.exc.StructuralCodeConstraintException; 40 41 65 public class Subroutines{ 66 69 private class SubroutineImpl implements Subroutine{ 70 75 private static final int UNSET = -1; 76 77 83 private int localVariable = UNSET; 84 85 86 private Set instructions = new HashSet (); 88 91 public boolean contains(InstructionHandle inst){ 92 return instructions.contains(inst); 93 } 94 95 99 private Set theJSRs = new HashSet (); 100 101 104 private InstructionHandle theRET; 105 106 113 public String toString(){ 114 String ret = "Subroutine: Local variable is '"+localVariable+"', JSRs are '"+theJSRs+"', RET is '"+theRET+"', Instructions: '"+instructions.toString()+"'."; 115 116 ret += " Accessed local variable slots: '"; 117 int[] alv = getAccessedLocalsIndices(); 118 for (int i=0; i<alv.length; i++){ 119 ret += alv[i]+" "; 120 } 121 ret+="'."; 122 123 ret += " Recursively (via subsub...routines) accessed local variable slots: '"; 124 alv = getRecursivelyAccessedLocalsIndices(); 125 for (int i=0; i<alv.length; i++){ 126 ret += alv[i]+" "; 127 } 128 ret+="'."; 129 130 return ret; 131 } 132 133 137 void setLeavingRET(){ 138 if (localVariable == UNSET){ 139 throw new AssertionViolatedException("setLeavingRET() called for top-level 'subroutine' or forgot to set local variable first."); 140 } 141 Iterator iter = instructions.iterator(); 142 InstructionHandle ret = null; 143 while(iter.hasNext()){ 144 InstructionHandle actual = (InstructionHandle) iter.next(); 145 if (actual.getInstruction() instanceof RET){ 146 if (ret != null){ 147 throw new StructuralCodeConstraintException("Subroutine with more then one RET detected: '"+ret+"' and '"+actual+"'."); 148 } 149 else{ 150 ret = actual; 151 } 152 } 153 } 154 if (ret == null){ 155 throw new StructuralCodeConstraintException("Subroutine without a RET detected."); 156 } 157 if (((RET) ret.getInstruction()).getIndex() != localVariable){ 158 throw new StructuralCodeConstraintException("Subroutine uses '"+ret+"' which does not match the correct local variable '"+localVariable+"'."); 159 } 160 theRET = ret; 161 } 162 163 166 public InstructionHandle[] getEnteringJsrInstructions(){ 167 if (this == TOPLEVEL) { 168 throw new AssertionViolatedException("getLeavingRET() called on top level pseudo-subroutine."); 169 } 170 InstructionHandle[] jsrs = new InstructionHandle[theJSRs.size()]; 171 return (InstructionHandle[]) (theJSRs.toArray(jsrs)); 172 } 173 174 177 public void addEnteringJsrInstruction(InstructionHandle jsrInst){ 178 if ( (jsrInst == null) || (! (jsrInst.getInstruction() instanceof JsrInstruction))){ 179 throw new AssertionViolatedException("Expecting JsrInstruction InstructionHandle."); 180 } 181 if (localVariable == UNSET){ 182 throw new AssertionViolatedException("Set the localVariable first!"); 183 } 184 else{ 185 if (localVariable != ((ASTORE) (((JsrInstruction) jsrInst.getInstruction()).getTarget().getInstruction())).getIndex()){ 189 throw new AssertionViolatedException("Setting a wrong JsrInstruction."); 190 } 191 } 192 theJSRs.add(jsrInst); 193 } 194 195 198 public InstructionHandle getLeavingRET(){ 199 if (this == TOPLEVEL) { 200 throw new AssertionViolatedException("getLeavingRET() called on top level pseudo-subroutine."); 201 } 202 return theRET; 203 } 204 205 208 public InstructionHandle[] getInstructions(){ 209 InstructionHandle[] ret = new InstructionHandle[instructions.size()]; 210 return (InstructionHandle[]) instructions.toArray(ret); 211 } 212 213 218 void addInstruction(InstructionHandle ih){ 219 if (theRET != null){ 220 throw new AssertionViolatedException("All instructions must have been added before invoking setLeavingRET()."); 221 } 222 instructions.add(ih); 223 } 224 225 226 public int[] getRecursivelyAccessedLocalsIndices(){ 227 Set s = new HashSet (); 228 int[] lvs = getAccessedLocalsIndices(); 229 for (int j=0; j<lvs.length; j++){ 230 s.add(new Integer (lvs[j])); 231 } 232 _getRecursivelyAccessedLocalsIndicesHelper(s, this.subSubs()); 233 int[] ret = new int[s.size()]; 234 Iterator i = s.iterator(); 235 int j=-1; 236 while (i.hasNext()){ 237 j++; 238 ret[j] = ((Integer ) i.next()).intValue(); 239 } 240 return ret; 241 } 242 243 247 private void _getRecursivelyAccessedLocalsIndicesHelper(Set s, Subroutine[] subs){ 248 for (int i=0; i<subs.length; i++){ 249 int[] lvs = subs[i].getAccessedLocalsIndices(); 250 for (int j=0; j<lvs.length; j++){ 251 s.add(new Integer (lvs[j])); 252 } 253 if(subs[i].subSubs().length != 0){ 254 _getRecursivelyAccessedLocalsIndicesHelper(s, subs[i].subSubs()); 255 } 256 } 257 } 258 259 262 public int[] getAccessedLocalsIndices(){ 263 Set acc = new HashSet (); 265 if (theRET == null && this != TOPLEVEL){ 266 throw new AssertionViolatedException("This subroutine object must be built up completely before calculating accessed locals."); 267 } 268 Iterator i = instructions.iterator(); 269 while (i.hasNext()){ 270 InstructionHandle ih = (InstructionHandle) i.next(); 271 if (ih.getInstruction() instanceof LocalVariableInstruction || ih.getInstruction() instanceof RET){ 273 int idx = ((IndexedInstruction) (ih.getInstruction())).getIndex(); 274 acc.add(new Integer (idx)); 275 try{ 277 if (ih.getInstruction() instanceof LocalVariableInstruction){ 280 int s = ((LocalVariableInstruction) ih.getInstruction()).getType(null).getSize(); 281 if (s==2) { 282 acc.add(new Integer (idx+1)); 283 } 284 } 285 } 286 catch(RuntimeException re){ 287 throw new AssertionViolatedException("Oops. BCEL did not like NULL as a ConstantPoolGen object."); 288 } 289 } 290 } 291 292 int[] ret = new int[acc.size()]; 293 i = acc.iterator(); 294 int j=-1; 295 while (i.hasNext()){ 296 j++; 297 ret[j] = ((Integer ) i.next()).intValue(); 298 } 299 return ret; 300 } 301 302 305 public Subroutine[] subSubs(){ 306 Set h = new HashSet (); 307 308 Iterator i = instructions.iterator(); 309 while (i.hasNext()){ 310 Instruction inst = ((InstructionHandle) i.next()).getInstruction(); 311 if (inst instanceof JsrInstruction){ 312 InstructionHandle targ = ((JsrInstruction) inst).getTarget(); 313 h.add(getSubroutine(targ)); 314 } 315 } 316 Subroutine[] ret = new Subroutine[h.size()]; 317 return (Subroutine[]) h.toArray(ret); 318 } 319 320 326 void setLocalVariable(int i){ 327 if (localVariable != UNSET){ 328 throw new AssertionViolatedException("localVariable set twice."); 329 } 330 else{ 331 localVariable = i; 332 } 333 } 334 335 338 public SubroutineImpl(){ 339 } 340 341 } 343 private static final Integer WHITE = new Integer (0); 345 private static final Integer GRAY = new Integer (1); 346 private static final Integer BLACK = new Integer (2); 347 348 353 private Hashtable subroutines = new Hashtable (); 354 355 361 public final Subroutine TOPLEVEL; 362 363 368 public Subroutines(MethodGen mg){ 369 370 InstructionHandle[] all = mg.getInstructionList().getInstructionHandles(); 371 CodeExceptionGen[] handlers = mg.getExceptionHandlers(); 372 373 TOPLEVEL = new SubroutineImpl(); 375 376 Set sub_leaders = new HashSet (); for (int i=0; i<all.length; i++){ 379 Instruction inst = all[i].getInstruction(); 380 if (inst instanceof JsrInstruction){ 381 sub_leaders.add(((JsrInstruction) inst).getTarget()); 382 } 383 } 384 385 Iterator iter = sub_leaders.iterator(); 387 while (iter.hasNext()){ 388 SubroutineImpl sr = new SubroutineImpl(); 389 InstructionHandle astore = (InstructionHandle) (iter.next()); 390 sr.setLocalVariable( ((ASTORE) (astore.getInstruction())).getIndex() ); 391 subroutines.put(astore, sr); 392 } 393 394 subroutines.put(all[0], TOPLEVEL); 396 sub_leaders.add(all[0]); 397 398 for (int i=0; i<all.length; i++){ 404 Instruction inst = all[i].getInstruction(); 405 if (inst instanceof JsrInstruction){ 406 InstructionHandle leader = ((JsrInstruction) inst).getTarget(); 407 ((SubroutineImpl) getSubroutine(leader)).addEnteringJsrInstruction(all[i]); 408 } 409 } 410 411 Set instructions_assigned = new HashSet (); 415 Hashtable colors = new Hashtable (); 417 iter = sub_leaders.iterator(); 418 while (iter.hasNext()){ 419 InstructionHandle actual = (InstructionHandle) (iter.next()); 421 for (int i=0; i<all.length; i++){ 423 colors.put(all[i], WHITE); 424 } 425 colors.put(actual, GRAY); 426 ArrayList Q = new ArrayList (); 428 Q.add(actual); 430 431 if (actual == all[0]){ 432 for (int j=0; j<handlers.length; j++){ 433 colors.put(handlers[j].getHandlerPC(), GRAY); 434 Q.add(handlers[j].getHandlerPC()); 435 } 436 } 437 438 439 while (Q.size() != 0){ 441 InstructionHandle u = (InstructionHandle) Q.remove(0); 442 InstructionHandle[] successors = getSuccessors(u); 443 for (int i=0; i<successors.length; i++){ 444 if (((Integer ) colors.get(successors[i])) == WHITE){ 445 colors.put(successors[i], GRAY); 446 Q.add(successors[i]); 447 } 448 } 449 colors.put(u, BLACK); 450 } 451 for (int i=0; i<all.length; i++){ 453 if (colors.get(all[i]) == BLACK){ 454 ((SubroutineImpl) (actual==all[0]?getTopLevel():getSubroutine(actual))).addInstruction(all[i]); 455 if (instructions_assigned.contains(all[i])){ 456 throw new StructuralCodeConstraintException("Instruction '"+all[i]+"' is part of more than one subroutine (or of the top level and a subroutine)."); 457 } 458 else{ 459 instructions_assigned.add(all[i]); 460 } 461 } 462 } 463 if (actual != all[0]){ ((SubroutineImpl) getSubroutine(actual)).setLeavingRET(); 465 } 466 } 467 468 for (int i=0; i<handlers.length; i++){ 471 InstructionHandle _protected = handlers[i].getStartPC(); 472 while (_protected != handlers[i].getEndPC().getNext()){ Iterator subs = subroutines.values().iterator(); 474 while (subs.hasNext()){ 475 Subroutine sub = (Subroutine) subs.next(); 476 if (sub != subroutines.get(all[0])){ if (sub.contains(_protected)){ 478 throw new StructuralCodeConstraintException("Subroutine instruction '"+_protected+"' is protected by an exception handler, '"+handlers[i]+"'. This is forbidden by the JustIce verifier due to its clear definition of subroutines."); 479 } 480 } 481 } 482 _protected = _protected.getNext(); 483 } 484 } 485 486 noRecursiveCalls(getTopLevel(), new HashSet ()); 493 494 } 495 496 507 private void noRecursiveCalls(Subroutine sub, Set set){ 508 Subroutine[] subs = sub.subSubs(); 509 510 for (int i=0; i<subs.length; i++){ 511 int index = ((RET) (subs[i].getLeavingRET().getInstruction())).getIndex(); 512 513 if (!set.add(new Integer (index))){ 514 SubroutineImpl si = (SubroutineImpl) subs[i]; 516 throw new StructuralCodeConstraintException("Subroutine with local variable '"+si.localVariable+"', JSRs '"+si.theJSRs+"', RET '"+si.theRET+"' is called by a subroutine which uses the same local variable index as itself; maybe even a recursive call? JustIce's clean definition of a subroutine forbids both."); 517 } 518 519 noRecursiveCalls(subs[i], set); 520 521 set.remove(new Integer (index)); 522 } 523 } 524 525 533 public Subroutine getSubroutine(InstructionHandle leader){ 534 Subroutine ret = (Subroutine) subroutines.get(leader); 535 536 if (ret == null){ 537 throw new AssertionViolatedException("Subroutine requested for an InstructionHandle that is not a leader of a subroutine."); 538 } 539 540 if (ret == TOPLEVEL){ 541 throw new AssertionViolatedException("TOPLEVEL special subroutine requested; use getTopLevel()."); 542 } 543 544 return ret; 545 } 546 547 558 public Subroutine subroutineOf(InstructionHandle any){ 559 Iterator i = subroutines.values().iterator(); 560 while (i.hasNext()){ 561 Subroutine s = (Subroutine) i.next(); 562 if (s.contains(any)) { 563 return s; 564 } 565 } 566 System.err.println("DEBUG: Please verify '"+any+"' lies in dead code."); 567 return null; 568 } 570 571 581 public Subroutine getTopLevel(){ 582 return TOPLEVEL; 583 } 584 590 private static InstructionHandle[] getSuccessors(InstructionHandle instruction){ 591 final InstructionHandle[] empty = new InstructionHandle[0]; 592 final InstructionHandle[] single = new InstructionHandle[1]; 593 final InstructionHandle[] pair = new InstructionHandle[2]; 594 595 Instruction inst = instruction.getInstruction(); 596 597 if (inst instanceof RET){ 598 return empty; 599 } 600 601 if (inst instanceof ReturnInstruction){ 603 return empty; 604 } 605 606 if (inst instanceof ATHROW){ 609 return empty; 610 } 611 612 if (inst instanceof JsrInstruction){ 614 single[0] = instruction.getNext(); 615 return single; 616 } 617 618 if (inst instanceof GotoInstruction){ 619 single[0] = ((GotoInstruction) inst).getTarget(); 620 return single; 621 } 622 623 if (inst instanceof BranchInstruction){ 624 if (inst instanceof Select){ 625 InstructionHandle[] matchTargets = ((Select) inst).getTargets(); 628 InstructionHandle[] ret = new InstructionHandle[matchTargets.length+1]; 629 ret[0] = ((Select) inst).getTarget(); 630 System.arraycopy(matchTargets, 0, ret, 1, matchTargets.length); 631 return ret; 632 } 633 else{ 634 pair[0] = instruction.getNext(); 635 pair[1] = ((BranchInstruction) inst).getTarget(); 636 return pair; 637 } 638 } 639 640 single[0] = instruction.getNext(); 642 return single; 643 } 644 645 648 public String toString(){ 649 return "---\n"+subroutines.toString()+"\n---\n"; 650 } 651 } 652 | Popular Tags |