KickJava   Java API By Example, From Geeks To Geeks.

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


1 /*
2  * FindBugs - Find bugs in Java programs
3  * Copyright (C) 2004-2006 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
23 import org.apache.bcel.classfile.JavaClass;
24 import org.apache.bcel.classfile.Method;
25 import org.apache.bcel.generic.Type;
26
27 import edu.umd.cs.findbugs.BugInstance;
28 import edu.umd.cs.findbugs.BugReporter;
29 import edu.umd.cs.findbugs.BytecodeScanningDetector;
30 import edu.umd.cs.findbugs.OpcodeStack;
31 import edu.umd.cs.findbugs.StatelessDetector;
32 import edu.umd.cs.findbugs.SystemProperties;
33 import edu.umd.cs.findbugs.ba.XFactory;
34 import edu.umd.cs.findbugs.ba.XMethod;
35
36 public class InfiniteRecursiveLoop extends BytecodeScanningDetector implements
37         StatelessDetector {
38
39     private BugReporter bugReporter;
40
41     private boolean seenTransferOfControl;
42
43     private boolean seenReturn;
44
45     private boolean seenThrow;
46
47     private boolean seenStateChange;
48
49     private int largestBranchTarget;
50
51     private final static boolean DEBUG = SystemProperties.getBoolean("irl.debug");
52
53     public InfiniteRecursiveLoop(BugReporter bugReporter) {
54         this.bugReporter = bugReporter;
55     }
56
57
58
59     @Override JavaDoc
60          public void visit(JavaClass obj) {
61     }
62
63
64     @Override JavaDoc
65          public void visit(Method obj) {
66         seenTransferOfControl = false;
67         seenStateChange = false;
68         seenReturn = false;
69         seenThrow = false;
70         largestBranchTarget = -1;
71         try {
72         stack.resetForMethodEntry(this);
73         } catch (Throwable JavaDoc e) {
74             throw new RuntimeException JavaDoc("error in " + getFullyQualifiedMethodName() + " " + e.getMessage(), e);
75         }
76         if (DEBUG) {
77             System.out.println();
78             System.out.println(" --- " + getFullyQualifiedMethodName());
79             System.out.println();
80         }
81     }
82
83     @Override JavaDoc
84          public void sawBranchTo(int seen) {
85         if (largestBranchTarget < seen)
86             largestBranchTarget = seen;
87         seenTransferOfControl = true;
88     }
89
90     OpcodeStack stack = new OpcodeStack();
91
92     /** Signal an infinite loop if either:
93      * we see a call to the same method with the same parameters, or
94      * we see a call to the same (dynamically dispatched method), and there
95      * has been no transfer of control.
96      */
97     @Override JavaDoc
98          public void sawOpcode(int seen) {
99         stack.mergeJumps(this);
100         if (seenReturn && seenTransferOfControl && seenStateChange)
101             return;
102
103         if (DEBUG) {
104             System.out.println(stack);
105             System.out.println(getPC() + " : " + OPCODE_NAMES[seen]);
106         }
107
108         if ((seen == INVOKEVIRTUAL || seen == INVOKEINTERFACE)
109                 && getNameConstantOperand().equals("add")
110                 && getSigConstantOperand().equals("(Ljava/lang/Object;)Z")
111                 && stack.getStackDepth() >= 2) {
112             OpcodeStack.Item it0 = stack.getStackItem(0);
113             int r0 = it0.getRegisterNumber();
114             OpcodeStack.Item it1 = stack.getStackItem(1);
115             int r1 = it1.getRegisterNumber();
116             if (r0 == r1 && r0 > 0)
117                 bugReporter.reportBug(new BugInstance(this, "IL_CONTAINER_ADDED_TO_ITSELF",
118                         NORMAL_PRIORITY).addClassAndMethod(this).addSourceLine(this));
119         }
120
121         if ((seen == INVOKEVIRTUAL || seen == INVOKESPECIAL || seen == INVOKEINTERFACE || seen == INVOKESTATIC)
122                 && getNameConstantOperand().equals(getMethodName())
123                 && getSigConstantOperand().equals(getMethodSig())
124                 && (seen == INVOKESTATIC) == getMethod().isStatic()
125                 && (seen == INVOKESPECIAL) == (getMethod().isPrivate() || getMethodName().equals("<init>"))
126                 ) {
127             Type arguments[] = getMethod().getArgumentTypes();
128                 // stack.getStackDepth() >= parameters
129 int parameters = arguments.length;
130             if (!getMethod().isStatic()) parameters++;
131             XMethod xMethod = XFactory.createReferencedXMethod(this);
132             if (DEBUG) {
133                 System.out.println("IL: Checking...");
134                 System.out.println(xMethod);
135                 System.out.println("vs. " + getClassName() + "." + getMethodName() + " : "
136                         + getMethodSig());
137             
138             }
139             if (xMethod.getClassName().replace('.','/').equals(getClassName()) || seen == INVOKEINTERFACE) {
140                 // Invocation of same method
141 // Now need to see if parameters are the same
142 int firstParameter = 0;
143                 if (getMethodName().equals("<init>"))
144                     firstParameter = 1;
145
146                 // match1 should be true if it is any call to the exact same method
147 // and no state has been change.
148 // if match1 is true, the method may not always perform
149 // a recursive infinite loop, but this particular method call is an infinite
150 // recursive loop
151
152                 boolean match1 = !seenStateChange;
153                 for (int i = firstParameter; match1 && i < parameters; i++) {
154                     OpcodeStack.Item it = stack.getStackItem(parameters - 1 - i);
155                     if (!it.isInitialParameter() || it.getRegisterNumber() != i)
156                         match1 = false;
157                 }
158
159                 boolean sameMethod = seen == INVOKESTATIC
160                         || getNameConstantOperand().equals("<init>");
161                 if (!sameMethod) {
162                     // Have to check if first parmeter is the same
163 // know there must be a this argument
164 if (DEBUG)
165                         System.out.println("Stack is " + stack);
166                     OpcodeStack.Item p = stack.getStackItem(parameters - 1);
167                     if (DEBUG)
168                         System.out.println("parameters = " + parameters + ", Item is " + p);
169                     String JavaDoc sig = p.getSignature();
170                     sameMethod = p.isInitialParameter() && p.getRegisterNumber() == 0 && sig.equals("L" + getClassName() +";");
171
172                 }
173
174                 // match2 and match3 are two different ways of seeing if the call site
175 // postdominates the method entry.
176
177                 // technically, we use (!seenTransferOfControl || !seenReturn && largestBranchTarget < getPC())
178 // as a check that the call site postdominates the method entry. If those are true,
179 // and sameMethod is true, we have a guaranteed IL.
180
181                 boolean match2 = sameMethod && !seenTransferOfControl;
182                 boolean match3 = sameMethod && !seenReturn && largestBranchTarget < getPC();
183                 if (match1 || match2 || match3) {
184                     if (DEBUG)
185                         System.out.println("IL: " + sameMethod + " " + match1 + " " + match2 + " " + match3);
186                     int priority = HIGH_PRIORITY;
187                     if (!match1 && !match2 && seenThrow) priority = NORMAL_PRIORITY;
188                     if (seen == INVOKEINTERFACE) priority = NORMAL_PRIORITY;
189                     bugReporter.reportBug(new BugInstance(this, "IL_INFINITE_RECURSIVE_LOOP",
190                             HIGH_PRIORITY).addClassAndMethod(this).addSourceLine(this));
191                 }
192             }
193         }
194
195         switch (seen) {
196         case ARETURN:
197         case IRETURN:
198         case LRETURN:
199         case RETURN:
200         case DRETURN:
201         case FRETURN:
202             seenReturn = true;
203             seenTransferOfControl = true;
204             break;
205         case ATHROW:
206             seenThrow = true;
207             seenTransferOfControl = true;
208             break;
209         case PUTSTATIC:
210         case PUTFIELD:
211         case IASTORE:
212         case AASTORE:
213         case DASTORE:
214         case FASTORE:
215         case LASTORE:
216         case SASTORE:
217         case CASTORE:
218         case BASTORE:
219         case INVOKEVIRTUAL:
220         case INVOKESPECIAL:
221         case INVOKEINTERFACE:
222         case INVOKESTATIC:
223             seenStateChange = true;
224             break;
225         }
226         stack.sawOpcode(this, seen);
227     }
228
229 }
Popular Tags