KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > edu > umd > cs > findbugs > detect > InfiniteRecursiveLoop2


1 /*
2  * FindBugs - Find Bugs in Java programs
3  * Copyright (C) 2005, University of Maryland
4  *
5  * This library is free software; you can redistribute it and/or
6  * modify it under the terms of the GNU Lesser General Public
7  * License as published by the Free Software Foundation; either
8  * version 2.1 of the License, or (at your option) any later version.
9  *
10  * This library is distributed in the hope that it will be useful,
11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13  * Lesser General Public License for more details.
14  *
15  * You should have received a copy of the GNU Lesser General Public
16  * License along with this library; if not, write to the Free Software
17  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
18  */

19
20 package edu.umd.cs.findbugs.detect;
21
22 import java.util.BitSet JavaDoc;
23 import java.util.Iterator JavaDoc;
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 /**
56  * Signal an infinite loop if either:
57  * we see a call to the same method with the same parameters, or
58  * we see a call to the same (dynamically dispatched method), and there
59  * has been no transfer of control.
60  *
61  * <p>This does the same thing as InfiniteRecursiveLoop, but uses CFG-based
62  * analysis for greater precision.</p>
63  *
64  * @author Bill Pugh
65  * @author David Hovemeyer
66  */

67 public @Deprecated JavaDoc class InfiniteRecursiveLoop2 implements Detector {
68     private static final boolean DEBUG = SystemProperties.getBoolean("irl.debug");
69     private static final String JavaDoc IRL_METHOD = SystemProperties.getProperty("irl.method");
70     
71     private BugReporter bugReporter;
72     
73     public InfiniteRecursiveLoop2(BugReporter bugReporter) {
74         this.bugReporter = bugReporter;
75     }
76
77     /* (non-Javadoc)
78      * @see edu.umd.cs.findbugs.Detector#visitClassContext(edu.umd.cs.findbugs.ba.ClassContext)
79      */

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         // Look for recursive calls which either
109
// - postdominate the CFG entry, or
110
// - pass all of the parameters as arguments
111
for (Iterator JavaDoc<BasicBlock> i = cfg.blockIterator(); i.hasNext(); ) {
112             BasicBlock basicBlock = i.next();
113
114             // Check if it's a method invocation.
115
if (!basicBlock.isExceptionThrower())
116                 continue;
117             InstructionHandle thrower = basicBlock.getExceptionThrower();
118             Instruction ins = thrower.getInstruction();
119             if (!(ins instanceof InvokeInstruction))
120                 continue;
121
122             // Recursive call?
123
if (isRecursiveCall((InvokeInstruction) ins, classContext, method)) {
124                 checkRecursiveCall(classContext, method, cfg, basicBlock, thrower, (InvokeInstruction) ins);
125             }
126             
127             // Call to add(Object)?
128
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         // Get blocks which postdominate the method entry
168
BitSet JavaDoc entryPostDominators = postDominators.getAllDominatorsOf(cfg.getEntry());
169
170         // How many arguments need to be checked to find out whether
171
// the parameters are passed to recursive calls verbatim?
172
int numArgsToCheck = new SignatureParser(method.getSignature()).getNumParameters();
173         if (!method.isStatic())
174             ++numArgsToCheck;
175
176         boolean report = false;
177
178         // Check to see if this block postdominates the method entry,
179
// and the called method is known exactly.
180
report = entryPostDominators.get(basicBlock.getId())
181                 && targetMethodKnownExactly(classContext, method, basicBlock, ins);
182         
183         if (!report) {
184             // See if
185
// (1) all parameters are passed unconditionally as arguments
186
// (2) no fields which might have been read have been written to
187
// (meaning a different path could be taken in the called method)
188
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 JavaDoc 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         // Ways in which we can be confident that the called method
206
// is the same as the calling method:
207
// 1. invocation is nonvirtual: invokestatic or invokespecial
208
// 2. method is private
209
// 3. method or class is final
210
// 4. receiver instance is the same as "this"
211
// 5. receiver type is known exactly, and is the same as the class
212
// containing the calling method
213

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         // See if caller and callee are the same.
224
// Technically, the call could still dispatch to a subclass,
225
// but that's pretty unlikely.
226
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         // Bottom means "any field is potentially loaded or stored"
298
if (loadSet.isBottom() || storeSet.isBottom())
299             return true;
300         
301         // Top generally means dead code, so we should repress the warning
302
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 JavaDoc 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     /* (non-Javadoc)
340      * @see edu.umd.cs.findbugs.Detector#report()
341      */

342     public void report() {
343     }
344
345 }
346
Popular Tags