|
1
19
20 package edu.umd.cs.findbugs.detect;
21
22 import java.util.ArrayList  ;
23 import java.util.BitSet ;
24 import java.util.Iterator ;
25 import java.util.LinkedList ;
26 import java.util.List ;
27
28 import org.apache.bcel.classfile.Code;
29 import org.apache.bcel.classfile.JavaClass;
30 import org.apache.bcel.classfile.Method;
31
32 import edu.umd.cs.findbugs.BugInstance;
33 import edu.umd.cs.findbugs.BugReporter;
34 import edu.umd.cs.findbugs.BytecodeScanningDetector;
35 import edu.umd.cs.findbugs.LocalVariableAnnotation;
36 import edu.umd.cs.findbugs.OpcodeStack;
37 import edu.umd.cs.findbugs.OpcodeStack.Item;
38 import edu.umd.cs.findbugs.annotations.NonNull;
39 import edu.umd.cs.findbugs.visitclass.Util;
40
41 public class InfiniteLoop extends BytecodeScanningDetector {
42
43 private static final boolean active = true;
44
45
46 ArrayList <BitSet > regModifiedAt = new ArrayList <BitSet >();
47 @NonNull BitSet getModifiedBitSet(int reg) {
48 while (regModifiedAt.size() <= reg)
49 regModifiedAt.add(new BitSet ());
50 return regModifiedAt.get(reg);
51 }
52 private void regModifiedAt(int reg, int pc) {
53 BitSet b = getModifiedBitSet(reg);
54 b.set(pc);
55 }
56 private void clearRegModified() {
57 for(BitSet b : regModifiedAt )
58 b.clear();
59 }
60 private boolean isRegModified(int reg, int firstPC, int lastPC) {
61 if (reg < 0) return false;
62 BitSet b = getModifiedBitSet(reg);
63 int modified = b.nextSetBit(firstPC);
64 return (modified >= firstPC && modified <= lastPC);
65 }
66 static class Jump {
67 final int from, to;
68 Jump(int from, int to) {
69 this.from = from;
70 this.to = to;
71 }
72 public String toString() {
73 return from + " -> " + to;
74 }
75 }
76 static class BackwardsBranch extends Jump {
77 final List <Integer > invariantRegisters = new LinkedList <Integer >();
78 final int numLastUpdates;
79 BackwardsBranch(OpcodeStack stack, int from, int to) {
80 super(from,to);
81 numLastUpdates = stack.getNumLastUpdates();
82 for(int i = 0; i < numLastUpdates; i++)
83 if (stack.getLastUpdate(i) < to)
84 invariantRegisters.add(i);
85 }
86
87 }
88 static class ForwardConditionalBranch extends Jump {
89 final OpcodeStack.Item item0, item1;
90 ForwardConditionalBranch(OpcodeStack.Item item0, OpcodeStack.Item item1, int from, int to) {
91 super(from,to);
92 this.item0 = item0;
93 this.item1 = item1;
94 }
95
96 }
97 BugReporter bugReporter;
98
99 LinkedList <Jump> backwardReach = new LinkedList <Jump>();
100 LinkedList <BackwardsBranch> backwardBranches = new LinkedList <BackwardsBranch>();
101
102 LinkedList <ForwardConditionalBranch> forwardConditionalBranches = new LinkedList <ForwardConditionalBranch>();
103
104 LinkedList <Jump> forwardJumps = new LinkedList <Jump>();
105 void purgeForwardJumps(int before) {
106 if (true) return;
107 for(Iterator <Jump> i = forwardJumps.iterator(); i.hasNext(); ) {
108 Jump j = i.next();
109 if (j.to < before) i.remove();
110 }
111 }
112 void addForwardJump(int from, int to) {
113 if (from >= to) return;
114 purgeForwardJumps(from);
115 forwardJumps.add(new Jump(from, to));
116 }
117
118 int getFurthestJump(int from) {
119 int result = Integer.MIN_VALUE;
120 int from2 = getBackwardsReach(from);
121 assert from2 <= from;
122 from = from2;
123 for(Jump f : forwardJumps)
124 if (f.from >= from && f.to > result)
125 result = f.to;
126 return result;
127 }
128 OpcodeStack stack = new OpcodeStack();
129
130 public InfiniteLoop(BugReporter bugReporter) {
131 this.bugReporter = bugReporter;
132 }
133
134 @Override
135 public void visit(JavaClass obj) {
136 }
137
138 @Override
139 public void visit(Method obj) {
140 }
141
142 @Override
143 public void visit(Code obj) {
144 clearRegModified();
145 stack.resetForMethodEntry(this);
146 backwardBranches.clear();
147 forwardConditionalBranches.clear();
148 forwardJumps.clear();
149 backwardReach.clear();
150 super.visit(obj);
151 backwardBranchLoop: for(BackwardsBranch bb : backwardBranches) {
152 LinkedList <ForwardConditionalBranch> myForwardBranches = new LinkedList <ForwardConditionalBranch>();
153 for(ForwardConditionalBranch fcb : forwardConditionalBranches)
154 if (getBackwardsReach(bb.to) < fcb.from && fcb.from < bb.from && bb.from < fcb.to)
155 myForwardBranches.add(fcb);
156 if (myForwardBranches.size() != 1) continue;
157 ForwardConditionalBranch fcb = myForwardBranches.get(0);
158 int backwardsReach = getBackwardsReach(bb.to);
159 for(Jump fj : forwardJumps)
160 if (fcb.from != fj.from && backwardsReach < fj.from && fj.from < bb.from && bb.from < fj.to)
161 continue backwardBranchLoop;
162 if (isConstant(fcb.item0, bb) &&
163 isConstant(fcb.item1, bb)) {
164 BugInstance bug = new BugInstance(this, "IL_INFINITE_LOOP",
165 HIGH_PRIORITY).addClassAndMethod(this).addSourceLine(
166 this, fcb.from);
167 int reg0 = fcb.item0.getRegisterNumber();
168 boolean reg0Invariant = true;
169 if (reg0 >= 0) {
170 reg0Invariant = !isRegModified(reg0, backwardsReach, bb.from);
171 bug.add(LocalVariableAnnotation.getLocalVariableAnnotation(getMethod(), reg0, fcb.from, bb.from))
172 .addSourceLine(this, constantSince(fcb.item0));
173 }
174 int reg1 = fcb.item1.getRegisterNumber();
175 if (reg1 >= 0 && reg1 != reg0)
176 bug.add(LocalVariableAnnotation.getLocalVariableAnnotation(getMethod(), reg1, fcb.from, bb.from))
177 .addSourceLine(this, constantSince(fcb.item1));
178 boolean reg1Invariant = true;
179 if (reg1 >= 0)
180 reg1Invariant = !isRegModified(reg1, backwardsReach, bb.from);
181 if (reg0Invariant && reg1Invariant)
182 bugReporter.reportBug(bug);
183 }
184
185 }
186 }
187
192 private boolean isConstant(Item item0, BackwardsBranch bb) {
193
194 int reg = item0.getRegisterNumber();
195 if (reg >= 0) return bb.invariantRegisters.contains(reg) || reg >= bb.numLastUpdates;
196 if (item0.getConstant() != null) return true;
197 return false;
198 }
199 @Override
200 public void sawBranchTo(int target) {
201 addForwardJump(getPC(), target);
202 }
203 @Override
204 public void sawOpcode(int seen) {
205 if (false) System.out.println(getPC() + " " + OPCODE_NAMES[seen] + " " + stack);
206 stack.mergeJumps(this);
207 if (isRegisterStore()) regModifiedAt(getRegisterOperand(), getPC());
208 switch (seen) {
209 case GOTO:
210 if (getBranchOffset() < 0) {
211 BackwardsBranch bb = new BackwardsBranch(stack, getPC(), getBranchTarget());
212 if (bb.invariantRegisters.size() > 0) backwardBranches.add(bb);
213 addBackwardsReach();
214 if (false) {
215 int target = getBranchTarget();
216 if (getFurthestJump(target) > getPC())
217 break;
218 if (getMethodName().equals("run") || getMethodName().equals("main")) break;
219 BugInstance bug = new BugInstance(this, "IL_INFINITE_LOOP",
220 LOW_PRIORITY).addClassAndMethod(this).addSourceLine(
221 this, getPC());
222 reportPossibleBug(bug);
223 }
224 }
225
226 break;
227 case ARETURN:
228 case IRETURN:
229 case RETURN:
230 case DRETURN:
231 case FRETURN:
232 case LRETURN:
233 addForwardJump(getPC(), Integer.MAX_VALUE);
234 break;
235 case LOOKUPSWITCH:
236 case TABLESWITCH:
237 {
238 OpcodeStack.Item item0 = stack.getStackItem(0);
239 if (getDefaultSwitchOffset() > 0)
240 forwardConditionalBranches.add(new ForwardConditionalBranch(item0, item0, getPC(), getPC() + getDefaultSwitchOffset() ));
241 for(int offset : getSwitchOffsets()) if (offset > 0)
242 forwardConditionalBranches.add(new ForwardConditionalBranch(item0, item0, getPC(), getPC() + offset));
243 break;
244 }
245 case IFNE:
246 case IFEQ:
247 case IFLE:
248 case IFLT:
249 case IFGE:
250 case IFGT:
251 case IFNONNULL:
252 case IFNULL:
253 {
254 addBackwardsReach();
255 OpcodeStack.Item item0 = stack.getStackItem(0);
256 int target = getBranchTarget();
257 if (getBranchOffset() > 0) {
258 forwardConditionalBranches.add(new ForwardConditionalBranch(item0, item0, getPC(), target));
259 break;
260 }
261 if (getFurthestJump(target) > getPC())
262 break;
263
264 if (constantSince(item0, target)) {
265 int since0 = constantSince(item0);
266 BugInstance bug = new BugInstance(this, "IL_INFINITE_LOOP",
267 HIGH_PRIORITY).addClassAndMethod(this).addSourceLine(
268 this, getPC());
269 int reg0 = item0.getRegisterNumber();
270 if (reg0 >= 0)
271 bug.add(LocalVariableAnnotation.getLocalVariableAnnotation(getMethod(), reg0, getPC(), target))
272 .addSourceLine(this, since0);
273 if (reg0 < 0 || !isRegModified(reg0, target, getPC()))
274 reportPossibleBug(bug);
275
276 }
277 }
278 break;
279 case IF_ACMPEQ:
280 case IF_ACMPNE:
281 case IF_ICMPNE:
282 case IF_ICMPEQ:
283 case IF_ICMPGT:
284 case IF_ICMPLE:
285 case IF_ICMPLT:
286 case IF_ICMPGE:
287 {
288 addBackwardsReach();
289 OpcodeStack.Item item0 = stack.getStackItem(0);
290 OpcodeStack.Item item1 = stack.getStackItem(1);
291 int target = getBranchTarget();
292 if (getBranchOffset() > 0) {
293 forwardConditionalBranches.add(new ForwardConditionalBranch(item0, item1, getPC(), target));
294 break;
295 }
296 if (getFurthestJump(target) > getPC())
297 break;
298
299 if (constantSince(item0, target)
300 && constantSince(item1, target)) {
301 BugInstance bug = new BugInstance(this, "IL_INFINITE_LOOP",
304 HIGH_PRIORITY).addClassAndMethod(this).addSourceLine(
305 this, getPC());
306 int reg0 = item0.getRegisterNumber();
307 if (reg0 >= 0)
308 bug.add(LocalVariableAnnotation.getLocalVariableAnnotation(getMethod(), reg0, getPC(), target));
309 int reg1 = item1.getRegisterNumber();
310 if (reg1 >= 0)
311 bug.add(LocalVariableAnnotation.getLocalVariableAnnotation(getMethod(), reg1, getPC(), target));
312
313 reportPossibleBug(bug);
314 }
315
316 }
317 break;
318 }
319
320 stack.sawOpcode(this, seen);
321 }
322
323
326 private void addBackwardsReach() {
327 if (getBranchOffset() >= 0) return;
328 int target = getBranchTarget();
329 for(Jump j : backwardReach)
330 if (j.to < target && target <= j.from) target = j.to;
331 assert target <= getBranchTarget();
332 assert target < getPC();
333 for(Iterator <Jump> i = backwardReach.iterator(); i.hasNext(); ) {
334 Jump j = i.next();
335 if (target <= j.to && getPC() >= j.from) i.remove();
336 }
337 backwardReach.add(new Jump(getPC(), target));
338 }
339
340 private int getBackwardsReach(int target) {
341 int originalTarget = target;
342 for(Jump j : backwardReach)
343 if (j.to < target && target <= j.from) target = j.to;
344 assert target <= originalTarget;
345 return target;
346 }
347
348
349
350
355 private boolean constantSince(Item item1, int branchTarget) {
356 int reg = item1.getRegisterNumber();
357 if (reg >= 0)
358 return stack.getLastUpdate(reg) < getBackwardsReach(branchTarget);
359 if (item1.getConstant() != null)
360 return true;
361 return false;
362 }
363 private int constantSince(Item item1) {
364 int reg = item1.getRegisterNumber();
365 if (reg >= 0) return stack.getLastUpdate(reg);
366 return Integer.MAX_VALUE;
367
368 }
369
370 void reportPossibleBug(BugInstance bug) {
371 int catchSize = Util.getSizeOfSurroundingTryBlock(getConstantPool(), getCode(), "java/io/EOFException", getPC());
372 if (catchSize < Integer.MAX_VALUE) bug.lowerPriorityALot();
373 else {
374 catchSize = Util.getSizeOfSurroundingTryBlock(getConstantPool(), getCode(), "java/lang/NoSuchElementException", getPC());
375 if (catchSize < Integer.MAX_VALUE) bug.lowerPriorityALot();
376 else {
377 LocalVariableAnnotation lv = bug.getPrimaryLocalVariableAnnotation();
378 if (lv == null && getMethodName().equals("run")) bug.lowerPriority();
379 }
380 }
381 bugReporter.reportBug(bug);
382 }
383 }
384 |
Popular Tags |
Java API By Example, From Geeks To Geeks.