DuplicateBranches


1   /*
2    * FindBugs - Find bugs in Java programs
3    * Copyright (C) 2005 Dave Brosius <dbrosius@users.sourceforge.net>
4    * Copyright (C) 2005-2006 University of Maryland
5    * 
6    * This library is free software; you can redistribute it and/or
7    * modify it under the terms of the GNU Lesser General Public
8    * License as published by the Free Software Foundation; either
9    * version 2.1 of the License, or (at your option) any later version.
10   * 
11   * This library is distributed in the hope that it will be useful,
12   * but WITHOUT ANY WARRANTY; without even the implied warranty of
13   * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
14   * Lesser General Public License for more details.
15   * 
16   * You should have received a copy of the GNU Lesser General Public
17   * License along with this library; if not, write to the Free Software
18   * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
19   */
20  package edu.umd.cs.findbugs.detect;
21  
22  
23  import edu.umd.cs.findbugs.*;
24  import edu.umd.cs.findbugs.ba.*;
25  import edu.umd.cs.findbugs.visitclass.PreorderVisitor;
26  import java.io.IOException  ;
27  import java.math.BigInteger  ;
28  import java.util.*;
29  import org.apache.bcel.classfile.Method;
30  import org.apache.bcel.generic.*;
31  import org.apache.bcel.util.ByteSequence;
32  
33  /** @author Dave Brousius  4/2005  original author
34   *  @author Brian Cole     7/2006  serious reworking
35   */
36  public class DuplicateBranches extends PreorderVisitor implements Detector
37  {
38      private ClassContext classContext;
39      private BugReporter bugReporter;
40      
41      public DuplicateBranches(BugReporter bugReporter) {
42          this.bugReporter = bugReporter;
43      }
44  
45  
46      public void visitClassContext(ClassContext classContext) {
47          this.classContext = classContext;
48          classContext.getJavaClass().accept(this);
49      }
50  
51      @Override  
52           public void visitMethod(Method method) {
53          try {
54              if (method.getCode() == null)
55                  return;
56              
57              CFG cfg = classContext.getCFG(method);
58      
59              Iterator<BasicBlock> bbi = cfg.blockIterator();
60              while (bbi.hasNext()) {
61                  BasicBlock bb = bbi.next();
62                  
63                  int numOutgoing = cfg.getNumOutgoingEdges(bb);
64                  if (numOutgoing == 2)
65                      findIfElseDuplicates(cfg, method, bb);
66                  else if (numOutgoing > 2)
67                      findSwitchDuplicates(cfg, method, bb);
68              }
69          } catch (MethodUnprofitableException mue) {
70              if (SystemProperties.getBoolean("unprofitable.debug")) // otherwise don't report
71                  bugReporter.logError("skipping unprofitable method in " + getClass().getName());
72          } catch (Exception   e) {
73              bugReporter.logError("Failure examining basic blocks in Duplicate Branches detector", e);
74          }
75      }
76      
77      private void findIfElseDuplicates(CFG cfg, Method method, BasicBlock bb) {
78          BasicBlock thenBB = null, elseBB = null;
79  
80          Iterator<Edge> iei = cfg.outgoingEdgeIterator(bb);
81          while (iei.hasNext()) {
82              Edge e = iei.next();
83              if (e.getType() == EdgeTypes.IFCMP_EDGE) {
84                  elseBB = e.getTarget();
85              }
86              else if (e.getType() == EdgeTypes.FALL_THROUGH_EDGE) {
87                  thenBB = e.getTarget();
88              }
89          }
90          
91          if ((thenBB == null) || (elseBB == null))
92              return;
93          InstructionHandle thenStartHandle = getDeepFirstInstruction(cfg, thenBB);
94          InstructionHandle elseStartHandle = getDeepFirstInstruction(cfg, elseBB);
95          if ((thenStartHandle == null) || (elseStartHandle == null))
96              return;
97          
98          int thenStartPos = thenStartHandle.getPosition();
99          int elseStartPos = elseStartHandle.getPosition();
100         
101         InstructionHandle thenFinishIns = findThenFinish(cfg, thenBB, elseStartPos);
102         int thenFinishPos = thenFinishIns.getPosition();
103         
104         if (!(thenFinishIns.getInstruction() instanceof GotoInstruction))
105             return;
106         
107         InstructionHandle elseFinishHandle =
108                 ((GotoInstruction) thenFinishIns.getInstruction()).getTarget();
109         int elseFinishPos = elseFinishHandle.getPosition();
110         
111         if (thenFinishPos >= elseStartPos)
112             return;
113         
114         if ((thenFinishPos - thenStartPos) != (elseFinishPos - elseStartPos))
115             return;
116         
117         byte[] thenBytes = getCodeBytes(method, thenStartPos, thenFinishPos);
118         byte[] elseBytes = getCodeBytes(method, elseStartPos, elseFinishPos);
119         
120         if (!Arrays.equals(thenBytes, elseBytes))
121             return;
122         
123         // adjust elseFinishPos to be inclusive (for source line attribution)
124         InstructionHandle elseLastIns = elseFinishHandle.getPrev();
125         if (elseLastIns != null) elseFinishPos = elseLastIns.getPosition();
126         
127         bugReporter.reportBug(new BugInstance(this, "DB_DUPLICATE_BRANCHES", NORMAL_PRIORITY)
128                 .addClass(classContext.getJavaClass())
129                 .addMethod(classContext.getJavaClass(), method)
130                 .addSourceLineRange(classContext, this, thenStartPos, thenFinishPos)
131                 .addSourceLineRange(classContext, this, elseStartPos, elseFinishPos));
132     }
133     
134     /** Like bb.getFirstInstruction() except that if null is
135      *  returned it will follow the FALL_THROUGH_EDGE (if any) */
136     private static InstructionHandle getDeepFirstInstruction(CFG cfg, BasicBlock bb) {
137         InstructionHandle ih = bb.getFirstInstruction();
138         if (ih != null) return ih;
139         Iterator<Edge> iei = cfg.outgoingEdgeIterator(bb);
140         while (iei.hasNext()) {
141             Edge e = iei.next();
142             String   edgeString = e.toString();
143             if (EdgeTypes.FALL_THROUGH_EDGE == e.getType())
144                 return getDeepFirstInstruction(cfg, e.getTarget());
145         }
146         return null;
147     }
148 
149     private void findSwitchDuplicates(CFG cfg, Method method, BasicBlock bb) {      
150                 
151         int[] switchPos = new int[cfg.getNumOutgoingEdges(bb)+1];
152         HashMap<Integer  , InstructionHandle> prevHandle = new HashMap<Integer  , InstructionHandle>();
153 
154         Iterator<Edge> iei = cfg.outgoingEdgeIterator(bb);
155         int idx = 0;
156         
157         while (iei.hasNext()) {
158             Edge e = iei.next();
159             int eType = e.getType();
160             if (eType == EdgeTypes.SWITCH_EDGE || eType == EdgeTypes.SWITCH_DEFAULT_EDGE) {
161                 BasicBlock target = e.getTarget();
162                 InstructionHandle firstIns = getDeepFirstInstruction(cfg, target);
163                 if (firstIns == null)
164                     continue; // give up on this edge
165                 int firstInsPosition = firstIns.getPosition();
166                 switchPos[idx++] = firstInsPosition;
167                 InstructionHandle prevIns = firstIns.getPrev(); // prev in bytecode, not flow
168                 if (prevIns != null) prevHandle.put((Integer  )firstInsPosition, prevIns);
169             } else {
170                 // hmm, this must not be a switch statement, so give up
171                 return;
172             }
173         }
174         
175         if (idx < 2) // need at least two edges to tango
176             return;
177                         
178         Arrays.sort(switchPos, 0, idx); // sort the 'idx' switch positions
179         
180         // compute end position of final case (ok if set to 0 or <= switchPos[idx-1])
181         switchPos[idx] = getFinalTarget(cfg, switchPos[idx-1], prevHandle.values());
182         
183         HashMap<BigInteger  , Collection<Integer  >> map = new HashMap<BigInteger  ,Collection<Integer  >>();
184         for (int i = 0; i < idx; i++) {
185             if (switchPos[i]+1 >= switchPos[i+1]) continue; // why the +1 on lhs?
186             
187             int endPos = switchPos[i+1];
188             InstructionHandle last = prevHandle.get((Integer  )switchPos[i+1]);
189             if (last == null) {
190                 // should be default case -- leave endPos as is
191             } else if (last.getInstruction() instanceof GotoInstruction) {
192                 endPos = last.getPosition(); // don't store the goto
193             } else if (last.getInstruction() instanceof ReturnInstruction) {
194                 // leave endPos as is (store the return instruction)
195         //  } else if (last.getInstruction() instanceof ATHROW) {
196         //      // leave endPos as is (store the throw instruction)
197         // Don't do this since many cases may throw "not implemented".
198             } else {
199                 if (i+2 < idx) continue; // falls through to next case, so don't store it at all
200                 if (i+1 < idx && switchPos[idx]!=switchPos[idx-1]) continue; // also falls through unless switch has no default case
201             }
202             
203             byte[] clause = getCodeBytes(method, switchPos[i], endPos);
204             
205             BigInteger   clauseAsInt;
206             if (clause.length == 0) clauseAsInt = BigInteger.ZERO;
207             else clauseAsInt = new BigInteger  (clause);
208             
209             Collection<Integer  > values = map.get(clauseAsInt);
210             
211             if (values == null) {
212                 values = new LinkedList<Integer  >();
213                 map.put(clauseAsInt,values);
214             }
215             values.add((Integer  )i); // index into the sorted array
216         }
217         for(Collection<Integer  > clauses : map.values()) {
218             if (clauses.size() > 1) {
219                 BugInstance bug = new BugInstance(this, "DB_DUPLICATE_SWITCH_CLAUSES", LOW_PRIORITY)
220                         .addClass(classContext.getJavaClass())
221                         .addMethod(classContext.getJavaClass(), method);
222                 for(int i : clauses) 
223                     bug.addSourceLineRange(this.classContext, this, 
224                             switchPos[i],
225                             switchPos[i+1]-1); // not endPos, but that's ok
226                 bugReporter.reportBug(bug);
227             }
228         }
229     }
230     
231     /** determine the end position (exclusive) of the final case
232      *  by looking at the gotos at the ends of the other cases */
233     private static int getFinalTarget(CFG cfg, int myPos, Collection<InstructionHandle> prevs) {
234         int maxGoto = 0;
235         BasicBlock myBB = null;
236         // note: InstructionHandle doesn't override equals(), so use prevs.contains() with caution.
237         Iterator<BasicBlock> bbi = cfg.blockIterator();
238         while (bbi.hasNext()) {
239             BasicBlock bb = bbi.next();
240             InstructionHandle last = bb.getLastInstruction(); // may be null
241             if (prevs.contains(last)) { // danger will robinson
242                 Iterator<Edge> iei = cfg.outgoingEdgeIterator(bb);
243                 while (iei.hasNext()) {
244                     Edge e = iei.next();
245                     int eType = e.getType();
246                     String   aab = e.toString();
247                     if (eType == EdgeTypes.GOTO_EDGE) {
248                         BasicBlock target = e.getTarget();
249                         InstructionHandle targetFirst = getDeepFirstInstruction(cfg, target);
250                         if (targetFirst != null) {
251                             int targetPos = targetFirst.getPosition();
252                             if (targetPos > maxGoto) maxGoto = targetPos;
253                         }   
254                     }
255                 }
256             } else if (last!=null && myPos==bb.getFirstInstruction().getPosition()) {
257                 // note: getFirstInstruction() may return null, but won't if last!=null.
258                 myBB = bb; // used in case (c) below
259             }
260         }
261         /* ok, there are three cases:
262          * a) maxGoto == myPos: There is no default case within the switch.
263          * b) maxGoto > myPos: maxGoto is the end (exclusive) of the default case
264          * c) maxGoto < myPos: all the cases do something like return or throw, so
265          *                     who knows if there is a default case (and it's length)? */
266         if (maxGoto < myPos && myBB != null) {
267             /* We're in case (c), so let's guess that the end of the basic block
268              * is the end of the default case (if it exists). This may give false
269              * negatives (if the default case has branches, for example) but
270              * shouldn't give false negatives (because if it matches one of the
271              * cases, then it has also matched that case's return/throw). */
272             InstructionHandle last = myBB.getLastInstruction();
273             if (last != null) {
274                 // note: last.getNext() may return null, so do it this way
275                 return last.getPosition() + last.getInstruction().getLength();
276             }
277         }
278         return maxGoto;
279     }
280     
281     private byte[] getCodeBytes(Method m, int start, int end) {
282         byte[] code = m.getCode().getCode();
283         byte[] bytes = new byte[end-start];
284         System.arraycopy( code, start, bytes, 0, end - start);
285         
286         try {
287             ByteSequence sequence = new ByteSequence(code);
288             while ((sequence.available() > 0) && (sequence.getIndex() < start)) {
289                 Instruction.readInstruction(sequence);
290             }
291             
292             int pos;
293             while (sequence.available() > 0 && ((pos = sequence.getIndex()) < end)) {
294                 Instruction ins = Instruction.readInstruction(sequence);
295                 if ((ins instanceof BranchInstruction)
296                 &&  !(ins instanceof TABLESWITCH)
297                 &&  !(ins instanceof LOOKUPSWITCH)) {
298                     BranchInstruction bi = (BranchInstruction)ins;
299                     int offset = bi.getIndex();
300                     int target = offset + pos;
301                     if (target >= end) { // or target < start ??
302                         byte hiByte = (byte)((target >> 8) & 0x000000FF);
303                         byte loByte = (byte)(target & 0x000000FF);
304                         bytes[pos+bi.getLength()-2 - start] = hiByte;
305                         bytes[pos+bi.getLength()-1 - start] = loByte;
306                     }
307                 }
308             }
309         } catch (IOException   ioe) {
310         }
311         
312         return bytes;
313     }
314     
315     private InstructionHandle findThenFinish(CFG cfg, BasicBlock thenBB, int elsePos) {
316         InstructionHandle inst = thenBB.getFirstInstruction();
317         while (inst == null) {
318             Iterator<Edge> ie = cfg.outgoingEdgeIterator(thenBB);
319             while (ie.hasNext()) {
320                 Edge e = ie.next();
321                 if (e.getType() == EdgeTypes.FALL_THROUGH_EDGE) {
322                     thenBB = e.getTarget();
323                     break;
324                 }
325             }
326             inst = thenBB.getFirstInstruction();
327         }
328         
329         InstructionHandle lastIns = inst;
330         while (inst.getPosition() < elsePos) {
331             lastIns = inst;
332             inst = inst.getNext();
333         }
334         
335         return lastIns;
336     }
337     
338     public void report() {
339     }
340 }
341
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags