1 19 20 package edu.umd.cs.findbugs.detect; 21 22 import java.util.BitSet ; 23 import java.util.Iterator ; 24 25 import org.apache.bcel.Constants; 26 import org.apache.bcel.classfile.JavaClass; 27 import org.apache.bcel.classfile.Method; 28 import org.apache.bcel.generic.ConstantPoolGen; 29 import org.apache.bcel.generic.Instruction; 30 import org.apache.bcel.generic.InstructionHandle; 31 import org.apache.bcel.generic.InvokeInstruction; 32 import org.apache.bcel.generic.ObjectType; 33 import org.apache.bcel.generic.Type; 34 35 import edu.umd.cs.findbugs.BugInstance; 36 import edu.umd.cs.findbugs.BugReporter; 37 import edu.umd.cs.findbugs.Detector; 38 import edu.umd.cs.findbugs.SystemProperties; 39 import edu.umd.cs.findbugs.ba.BasicBlock; 40 import edu.umd.cs.findbugs.ba.CFG; 41 import edu.umd.cs.findbugs.ba.CFGBuilderException; 42 import edu.umd.cs.findbugs.ba.ClassContext; 43 import edu.umd.cs.findbugs.ba.DataflowAnalysisException; 44 import edu.umd.cs.findbugs.ba.PostDominatorsAnalysis; 45 import edu.umd.cs.findbugs.ba.SignatureConverter; 46 import edu.umd.cs.findbugs.ba.SignatureParser; 47 import edu.umd.cs.findbugs.ba.heap.FieldSet; 48 import edu.umd.cs.findbugs.ba.heap.LoadDataflow; 49 import edu.umd.cs.findbugs.ba.heap.StoreDataflow; 50 import edu.umd.cs.findbugs.ba.type.TypeFrame; 51 import edu.umd.cs.findbugs.ba.vna.ValueNumber; 52 import edu.umd.cs.findbugs.ba.vna.ValueNumberDataflow; 53 import edu.umd.cs.findbugs.ba.vna.ValueNumberFrame; 54 55 67 public @Deprecated class InfiniteRecursiveLoop2 implements Detector { 68 private static final boolean DEBUG = SystemProperties.getBoolean("irl.debug"); 69 private static final String IRL_METHOD = SystemProperties.getProperty("irl.method"); 70 71 private BugReporter bugReporter; 72 73 public InfiniteRecursiveLoop2(BugReporter bugReporter) { 74 this.bugReporter = bugReporter; 75 } 76 77 80 public void visitClassContext(ClassContext classContext) { 81 Method[] methodList = classContext.getJavaClass().getMethods(); 82 for (Method method : methodList) { 83 if (method.getCode() == null) 84 continue; 85 86 if (IRL_METHOD != null && !method.getName().equals(IRL_METHOD)) 87 continue; 88 89 try { 90 if (DEBUG) { 91 System.out.println("Checking method " + 92 SignatureConverter.convertMethodSignature(classContext.getJavaClass(), method)); 93 } 94 analyzeMethod(classContext, method); 95 } catch (CFGBuilderException e) { 96 bugReporter.logError("Error checking for infinite recursive loop in " + 97 SignatureConverter.convertMethodSignature(classContext.getJavaClass(), method), e); 98 } catch (DataflowAnalysisException e) { 99 bugReporter.logError("Error checking for infinite recursive loop in " + 100 SignatureConverter.convertMethodSignature(classContext.getJavaClass(), method), e); 101 } 102 } 103 } 104 105 private void analyzeMethod(ClassContext classContext, Method method) throws CFGBuilderException, DataflowAnalysisException { 106 CFG cfg = classContext.getCFG(method); 107 108 for (Iterator <BasicBlock> i = cfg.blockIterator(); i.hasNext(); ) { 112 BasicBlock basicBlock = i.next(); 113 114 if (!basicBlock.isExceptionThrower()) 116 continue; 117 InstructionHandle thrower = basicBlock.getExceptionThrower(); 118 Instruction ins = thrower.getInstruction(); 119 if (!(ins instanceof InvokeInstruction)) 120 continue; 121 122 if (isRecursiveCall((InvokeInstruction) ins, classContext, method)) { 124 checkRecursiveCall(classContext, method, cfg, basicBlock, thrower, (InvokeInstruction) ins); 125 } 126 127 if (isCallToAdd((InvokeInstruction) ins, classContext.getConstantPoolGen())) { 129 if (DEBUG) { System.out.println("Checking call to add..."); } 130 checkCallToAdd(classContext, method, basicBlock, thrower); 131 } 132 } 133 } 134 135 private boolean isRecursiveCall(InvokeInstruction instruction, ClassContext classContext, Method method) { 136 if ((instruction.getOpcode() == Constants.INVOKESTATIC) != method.isStatic()) 137 return false; 138 139 ConstantPoolGen cpg = classContext.getConstantPoolGen(); 140 if (!instruction.getClassName(cpg).equals(classContext.getJavaClass().getClassName()) 141 || !instruction.getName(cpg).equals(method.getName()) 142 || !instruction.getSignature(cpg).equals(method.getSignature())) 143 return false; 144 145 return true; 146 } 147 148 private void checkRecursiveCall( 149 ClassContext classContext, 150 Method method, 151 CFG cfg, 152 BasicBlock basicBlock, 153 InstructionHandle thrower, 154 InvokeInstruction ins) throws DataflowAnalysisException, CFGBuilderException { 155 156 if (DEBUG) { 157 System.out.println("Checking recursive call in " + 158 SignatureConverter.convertMethodSignature(classContext.getJavaClass(), method)); 159 } 160 161 PostDominatorsAnalysis postDominators = 162 classContext.getNonImplicitExceptionDominatorsAnalysis(method); 163 164 ValueNumberDataflow vnaDataflow = classContext.getValueNumberDataflow(method); 165 ValueNumberFrame vnaFrameAtEntry = vnaDataflow.getStartFact(cfg.getEntry()); 166 167 BitSet entryPostDominators = postDominators.getAllDominatorsOf(cfg.getEntry()); 169 170 int numArgsToCheck = new SignatureParser(method.getSignature()).getNumParameters(); 173 if (!method.isStatic()) 174 ++numArgsToCheck; 175 176 boolean report = false; 177 178 report = entryPostDominators.get(basicBlock.getId()) 181 && targetMethodKnownExactly(classContext, method, basicBlock, ins); 182 183 if (!report) { 184 report = allParamsPassedAsArgs(classContext, vnaDataflow, vnaFrameAtEntry, numArgsToCheck, basicBlock, ins) 189 && !checkedStateHasBeenModified(classContext, method, basicBlock); 190 } 191 192 if (report) { 193 JavaClass javaClass = classContext.getJavaClass(); 194 String sourceFile = javaClass.getSourceFileName(); 195 BugInstance warning = new BugInstance("IL_INFINITE_RECURSIVE_LOOP", HIGH_PRIORITY) 196 .addClassAndMethod(javaClass, method) 197 .addSourceLine(classContext, classContext.getMethodGen(method), sourceFile, thrower); 198 bugReporter.reportBug(warning); 199 } 200 } 201 202 private boolean targetMethodKnownExactly(ClassContext classContext, Method method, BasicBlock basicBlock, InvokeInstruction ins) 203 throws DataflowAnalysisException, CFGBuilderException { 204 205 214 if (ins.getOpcode() == Constants.INVOKESTATIC || ins.getOpcode() == Constants.INVOKESPECIAL) 215 return true; 216 217 if (method.isPrivate()) 218 return true; 219 220 if (method.isFinal() || classContext.getJavaClass().isFinal()) 221 return true; 222 223 ValueNumberDataflow vnaDataflow = classContext.getValueNumberDataflow(method); 227 ValueNumber caller = vnaDataflow.getAnalysis().getThisValue(); 228 ValueNumberFrame frameAtCall = vnaDataflow.getStartFact(basicBlock); 229 ValueNumber callee = frameAtCall.getInstance(ins, classContext.getConstantPoolGen()); 230 if (caller.equals(callee)) { 231 return true; 232 } 233 234 TypeFrame typeFrame = classContext.getTypeDataflow(method).getStartFact(basicBlock); 235 int receiverStackSlot = typeFrame.getInstanceSlot(ins, classContext.getConstantPoolGen()); 236 237 if (!typeFrame.isExact(receiverStackSlot)) 238 return false; 239 240 Type receiverType = typeFrame.getValue(receiverStackSlot); 241 if (!(receiverType instanceof ObjectType)) 242 return false; 243 244 return (((ObjectType) receiverType).getClassName().equals( 245 classContext.getJavaClass().getClassName())); 246 } 247 248 private boolean allParamsPassedAsArgs( 249 ClassContext classContext, 250 ValueNumberDataflow vnaDataflow, 251 ValueNumberFrame vnaFrameAtEntry, 252 int numArgsToCheck, 253 BasicBlock basicBlock, 254 InvokeInstruction ins) throws DataflowAnalysisException { 255 256 boolean allParamsPassedAsArgs = false; 257 258 ValueNumberFrame vnaFrame = vnaDataflow.getStartFact(basicBlock); 259 if (vnaFrame.isValid() && vnaFrame.getStackDepth() >= numArgsToCheck) { 260 allParamsPassedAsArgs = true; 261 262 checkArgsLoop: 263 for (int arg = 0; arg < numArgsToCheck; ++arg) { 264 ValueNumber paramVal = vnaFrameAtEntry.getValue(arg); 265 ValueNumber argVal = vnaFrame.getOperand(ins, classContext.getConstantPoolGen(), arg); 266 267 if (DEBUG) { 268 System.out.println("param="+paramVal.getNumber()+", arg=" + argVal.getNumber()); 269 } 270 271 if (!paramVal.equals(argVal)) { 272 allParamsPassedAsArgs = false; 273 break checkArgsLoop; 274 } 275 } 276 } 277 278 return allParamsPassedAsArgs; 279 } 280 281 private boolean checkedStateHasBeenModified(ClassContext classContext, Method method, BasicBlock basicBlock) 282 throws CFGBuilderException, DataflowAnalysisException { 283 284 LoadDataflow loadDataflow = classContext.getLoadDataflow(method); 285 FieldSet loadSet = loadDataflow.getStartFact(basicBlock); 286 287 StoreDataflow storeDataflow = classContext.getStoreDataflow(method); 288 FieldSet storeSet = storeDataflow.getStartFact(basicBlock); 289 290 if (DEBUG) { 291 System.out.println("Checking state: loads=" + loadSet + ", stores=" + storeSet); 292 } 293 294 if (loadSet.isEmpty() || storeSet.isEmpty()) 295 return false; 296 297 if (loadSet.isBottom() || storeSet.isBottom()) 299 return true; 300 301 if (loadSet.isTop() || storeSet.isTop()) 303 return true; 304 305 return loadSet.isIntersectionNonEmpty(storeSet); 306 } 307 308 private boolean isCallToAdd(InvokeInstruction ins, ConstantPoolGen cpg) { 309 return ins.getOpcode() != Constants.INVOKESTATIC 310 && ins.getName(cpg).equals("add") 311 && ins.getSignature(cpg).equals("(Ljava/lang/Object;)Z"); 312 } 313 314 private void checkCallToAdd( 315 ClassContext classContext, 316 Method method, 317 BasicBlock basicBlock, 318 InstructionHandle thrower) throws DataflowAnalysisException, CFGBuilderException { 319 ValueNumberDataflow vnaDataflow = classContext.getValueNumberDataflow(method); 320 ValueNumberFrame vnaFrame = vnaDataflow.getStartFact(basicBlock); 321 322 if (vnaFrame.isValid() && vnaFrame.getStackDepth() >= 2) { 323 ValueNumber top = vnaFrame.getStackValue(0); 324 ValueNumber next = vnaFrame.getStackValue(1); 325 if (DEBUG) { 326 System.out.println("top=" + top.getNumber() + ", next=" + next.getNumber()); 327 } 328 if (top.equals(next)) { 329 JavaClass javaClass = classContext.getJavaClass(); 330 String sourceFile = javaClass.getSourceFileName(); 331 BugInstance warning = new BugInstance("IL_CONTAINER_ADDED_TO_ITSELF", NORMAL_PRIORITY) 332 .addClassAndMethod(javaClass, method) 333 .addSourceLine(classContext, classContext.getMethodGen(method), sourceFile, thrower); 334 bugReporter.reportBug(warning); 335 } 336 } 337 } 338 339 342 public void report() { 343 } 344 345 } 346 | Popular Tags |