FindUnrelatedTypesInGenericContainer


1   /*
2    * FindBugs - Find Bugs in Java programs
3    * Copyright (C) 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  import java.util.Arrays  ;
23  import java.util.BitSet  ;
24  import java.util.HashMap  ;
25  import java.util.Iterator  ;
26  import java.util.Map  ;
27  
28  import org.apache.bcel.Constants;
29  import org.apache.bcel.Repository;
30  import org.apache.bcel.classfile.Attribute;
31  import org.apache.bcel.classfile.ConstantCP;
32  import org.apache.bcel.classfile.ConstantMethodref;
33  import org.apache.bcel.classfile.ConstantNameAndType;
34  import org.apache.bcel.classfile.JavaClass;
35  import org.apache.bcel.classfile.Method;
36  import org.apache.bcel.classfile.Synthetic;
37  import org.apache.bcel.generic.ArrayType;
38  import org.apache.bcel.generic.BasicType;
39  import org.apache.bcel.generic.ConstantPoolGen;
40  import org.apache.bcel.generic.Instruction;
41  import org.apache.bcel.generic.InstructionHandle;
42  import org.apache.bcel.generic.InvokeInstruction;
43  import org.apache.bcel.generic.MethodGen;
44  import org.apache.bcel.generic.ObjectType;
45  import org.apache.bcel.generic.ReferenceType;
46  import org.apache.bcel.generic.Type;
47  
48  import edu.umd.cs.findbugs.BugAccumulator;
49  import edu.umd.cs.findbugs.BugInstance;
50  import edu.umd.cs.findbugs.BugReporter;
51  import edu.umd.cs.findbugs.Detector;
52  import edu.umd.cs.findbugs.SourceLineAnnotation;
53  import edu.umd.cs.findbugs.SystemProperties;
54  import edu.umd.cs.findbugs.annotations.CheckForNull;
55  import edu.umd.cs.findbugs.ba.CFG;
56  import edu.umd.cs.findbugs.ba.CFGBuilderException;
57  import edu.umd.cs.findbugs.ba.ClassContext;
58  import edu.umd.cs.findbugs.ba.DataflowAnalysisException;
59  import edu.umd.cs.findbugs.ba.IncompatibleTypes;
60  import edu.umd.cs.findbugs.ba.Location;
61  import edu.umd.cs.findbugs.ba.MethodUnprofitableException;
62  import edu.umd.cs.findbugs.ba.generic.GenericObjectType;
63  import edu.umd.cs.findbugs.ba.generic.GenericUtilities;
64  import edu.umd.cs.findbugs.ba.generic.GenericUtilities.TypeCategory;
65  import edu.umd.cs.findbugs.ba.type.TopType;
66  import edu.umd.cs.findbugs.ba.type.TypeDataflow;
67  import edu.umd.cs.findbugs.ba.type.TypeFrame;
68  
69  /**
70   * @author Nat Ayewah
71   */
72  public class FindUnrelatedTypesInGenericContainer implements Detector {
73  
74      private BugReporter bugReporter;
75  
76      private static final boolean DEBUG = SystemProperties.getBoolean("gc.debug");
77              
78      /** 
79       * Map classname, methodname and signature to an int []. 
80       * Each position in the int [] corresponds to an argument in the methodSignature.
81       * For each argument i, the value at position i corresponds to the index of the 
82       * corresponding type in the class type parameters. If the argument
83       * has no correspondence, then the value is -1. <p>
84       * 
85       * Get the String key by calling getCollectionsMapKey()
86       */
87      private Map  <String  , int []> collectionsMap = new HashMap  <String  , int[]>();
88      
89      /**
90       * @param triplet[0] = className. 
91       *          The name of the collection e.g. <code>java.util.List</code>
92       * @param triplet[1] = methodName.
93       *          The method's name e.g. <code>contains</code>
94       * @param triplet[2] = methodSignature.
95       *          The method's signature e.g. <code>(Ljava/lang/Object;)Z</code>
96       * @return
97       */
98      public static String   getCollectionsMapKey(String  ...triplet) {
99          return triplet[0] + "??" + triplet[1] + "???" + triplet[2];
100     }
101     
102     private void addToCollectionsMap(String   className, String   methodName, 
103             String   methodSignature, int... argumentParameterIndex) {
104         collectionsMap.put(
105                 getCollectionsMapKey(className, methodName, methodSignature), 
106                 argumentParameterIndex);
107     }
108 
109     private void addToCollectionsMap(String   [] classNames, String   methodName, 
110             String   methodSignature, int... argumentParameterIndex) {
111         for (String   className : classNames)
112             addToCollectionsMap(
113                     className, methodName, methodSignature, 
114                     argumentParameterIndex);
115     }
116 
117     String   [] collectionMembers = new String   [] {
118             "java.util.Collection",
119             "java.util.AbstractCollection",
120             "java.util.List",
121             "java.util.AbstractList",
122             "java.util.ArrayList",
123             "java.util.LinkedList",
124             "java.util.Set",
125             "java.util.SortedSet",
126             "java.util.LinkedHashSet",
127             "java.util.HashSet",
128             "java.util.TreeSet" 
129     };
130     
131     String   [] mapMembers = new String   [] {
132             "java.util.Map",
133             "java.util.AbstractMap",
134             "java.util.SortedMap",
135             "java.util.TreeMap",
136             "java.util.HashMap",
137             "java.util.LinkedHashMap",
138             "java.util.concurrent.ConcurrentHashMap",
139             "java.util.EnumMap",
140             "java.util.Hashtable",
141             "java.util.IdentityHashMap",
142             "java.util.WeakHashMap"
143     };
144     
145     String   [] listMembers = new String   [] {
146             "java.util.List",
147             "java.util.AbstractList",
148             "java.util.ArrayList",
149             "java.util.LinkedList"
150     };
151 
152     public FindUnrelatedTypesInGenericContainer(BugReporter bugReporter) {
153         this.bugReporter = bugReporter;
154         String   basicSignature = "(Ljava/lang/Object;)Z";
155         String   collectionSignature = "(Ljava/util/Collection<*>;)Z";
156         String   indexSignature = "(Ljava/lang/Object;)I";
157         
158         // Collection<E>
159         addToCollectionsMap(collectionMembers, "contains", basicSignature, 0);
160         //addToCollectionsMap(collectionMembers, "equals",   basicSignature, 0);
161         addToCollectionsMap(collectionMembers, "remove",   basicSignature, 0);
162 
163         //addToCollectionsMap(collectionMembers, "containsAll", collectionSignature, 0);
164         //addToCollectionsMap(collectionMembers, "removeAll",   collectionSignature, 0);
165         //addToCollectionsMap(collectionMembers, "retainAll",   collectionSignature, 0);
166         
167         // List<E>
168         addToCollectionsMap(listMembers, "indexOf", indexSignature, 0);
169         addToCollectionsMap(listMembers, "lastIndexOf", indexSignature, 0);
170         
171         // Map<K,V>
172         addToCollectionsMap(mapMembers, "containsKey", basicSignature, 0);
173         addToCollectionsMap(mapMembers, "containsValue", basicSignature, 1);
174         
175         // XXX these do not work, to support these need changeable return types
176         addToCollectionsMap(mapMembers, "get", basicSignature, 0);
177         addToCollectionsMap(mapMembers, "remove", basicSignature, 0);
178     }
179     
180     /**
181      * Visit the class context
182      * @see edu.umd.cs.findbugs.Detector#visitClassContext(edu.umd.cs.findbugs.ba.ClassContext)
183      */
184     public void visitClassContext(ClassContext classContext) {
185         JavaClass javaClass = classContext.getJavaClass();
186         Method[] methodList = javaClass.getMethods();
187 
188         for (Method method : methodList) {
189             if (method.getCode() == null)
190                 continue;
191 
192             try {
193                 analyzeMethod(classContext, method);
194             } catch (MethodUnprofitableException e) {
195                 assert true; // move along; nothing to see
196             } catch (CFGBuilderException e) {
197                 String   msg = "Detector " + this.getClass().getName()
198                                         + " caught exception while analyzing " + javaClass.getClassName() + "." + method.getName() + " : " + method.getSignature();
199                 bugReporter.logError(msg , e);
200             } catch (DataflowAnalysisException e) {
201                 String   msg = "Detector " + this.getClass().getName()
202                                         + " caught exception while analyzing " + javaClass.getClassName() + "." + method.getName() + " : " + method.getSignature();
203                 bugReporter.logError(msg, e);
204             }
205         }
206     }
207 
208     /**
209      * Use this to screen out methods that do not contain invocations.
210      */
211     public boolean prescreen(ClassContext classContext, Method method) {
212         BitSet   bytecodeSet = classContext.getBytecodeSet(method);
213         return bytecodeSet != null && (
214                   bytecodeSet.get(Constants.INVOKEINTERFACE) || 
215                   bytecodeSet.get(Constants.INVOKEVIRTUAL)   ||
216                   bytecodeSet.get(Constants.INVOKESPECIAL)   ||
217                   bytecodeSet.get(Constants.INVOKESTATIC)    ||
218                   bytecodeSet.get(Constants.INVOKENONVIRTUAL)                 
219                 );
220     }
221 
222     /**
223      * Methods marked with the "Synthetic" attribute do not appear 
224      * in the source code
225      */
226     private boolean isSynthetic(Method m) {
227         Attribute[] attrs = m.getAttributes();
228         for (Attribute attr : attrs) {
229             if (attr instanceof Synthetic)
230                 return true;
231         }
232         return false;
233     }
234 
235     private void analyzeMethod(ClassContext classContext, Method method)
236     throws CFGBuilderException, DataflowAnalysisException {
237         if (isSynthetic(method) || !prescreen(classContext, method))
238             return;
239         
240         BugAccumulator accumulator = new BugAccumulator(bugReporter);
241         
242         CFG cfg = classContext.getCFG(method);
243         TypeDataflow typeDataflow = classContext.getTypeDataflow(method);
244 
245         ConstantPoolGen cpg = classContext.getConstantPoolGen();
246         MethodGen methodGen = classContext.getMethodGen(method);
247         if (methodGen == null) return;
248         String   fullMethodName = 
249             methodGen.getClassName() + "." + methodGen.getName(); 
250 
251         String   sourceFile = classContext.getJavaClass().getSourceFileName();
252         if (DEBUG) {
253             System.out.println("Checking " + fullMethodName);
254         }
255 
256         // Process each instruction
257         for (Iterator  <Location> iter = cfg.locationIterator(); iter.hasNext();) {
258             Location location = iter.next();
259             InstructionHandle handle = location.getHandle();
260             Instruction ins = handle.getInstruction();
261 
262             // Only consider invoke instructions
263             if (!(ins instanceof InvokeInstruction))
264                 continue;
265 
266             InvokeInstruction inv = (InvokeInstruction)ins;
267             
268             // check the relevance of this instruction
269             String   [] itriplet = getInstructionTriplet(inv, cpg);
270             String   [] triplet = getRelevantTriplet(itriplet);
271             if (triplet == null)
272                 continue;
273             
274             // get the list of parameter indexes for each argument position
275             int [] argumentParameterIndex = 
276                 collectionsMap.get( getCollectionsMapKey(triplet) );
277             
278             TypeFrame frame = typeDataflow.getFactAtLocation(location);
279             if (!frame.isValid()) {
280                 // This basic block is probably dead
281                 continue;
282             }
283 
284             Type operandType = frame.getTopValue();
285             if (operandType.equals(TopType.instance())) {
286                 // unreachable
287                 continue;
288             }           
289             
290             // Only consider generic... 
291             Type objectType = frame.getInstance(inv, cpg);          
292             if (!(objectType instanceof GenericObjectType))
293                 continue;
294             
295             GenericObjectType operand = (GenericObjectType) objectType;
296             
297             // ... containers
298             if (!operand.hasParameters()) continue;
299             
300             int numArguments = frame.getNumArguments(inv, cpg);
301             
302             if (numArguments <= 0 || argumentParameterIndex.length != numArguments)
303                 continue; 
304             
305             // compare containers type parameters to corresponding arguments
306             boolean match = true;
307             IncompatibleTypes [] matches = new IncompatibleTypes [numArguments];
308             for (int i=0; i<numArguments; i++) matches[i] = IncompatibleTypes.SEEMS_OK;
309             
310             for (int ii=0; ii < numArguments; ii++) {
311                 if (argumentParameterIndex[ii] < 0) continue; // not relevant argument
312                 if (argumentParameterIndex[ii] >= operand.getNumParameters()) 
313                     continue; // should never happen
314         
315                 Type parmType = operand.getParameterAt(argumentParameterIndex[ii]);
316                 Type argType = frame.getArgument(inv, cpg, ii, numArguments);
317                 matches[ii] = compareTypes(parmType, argType);
318 
319                 if (matches[ii] != IncompatibleTypes.SEEMS_OK) match = false;
320             }
321             
322             if (match)
323                 continue; // no bug
324 
325             // Prepare bug report
326             SourceLineAnnotation sourceLineAnnotation = SourceLineAnnotation
327             .fromVisitedInstruction(classContext, methodGen, sourceFile, handle);
328 
329             // Report a bug that mentions each of the failed arguments in matches
330             for (int i=0; i<numArguments; i++) {
331                 if (matches[i] == IncompatibleTypes.SEEMS_OK) continue;
332 
333                 Type parmType = operand.getParameterAt(argumentParameterIndex[i]);
334                 if (parmType instanceof GenericObjectType)
335                     parmType = ((GenericObjectType)parmType).getUpperBound();
336                 Type argType = frame.getArgument(inv, cpg, i, numArguments);
337                 
338                 accumulator.accumulateBug(new BugInstance(this,
339                         "GC_UNRELATED_TYPES", matches[i].getPriority())
340                         .addClassAndMethod(methodGen, sourceFile)                   
341                         //.addString(GenericUtilities.getString(parmType))
342                         //.addString(GenericUtilities.getString(argType))
343                         .addType(parmType.getSignature()) //XXX addType not handling 
344                         .addType(argType.getSignature())  //    generics properly
345                         .addCalledMethod(methodGen, (InvokeInstruction) ins)
346                         ,sourceLineAnnotation);
347             }
348             
349         }
350                         
351         accumulator.reportAccumulatedBugs();
352     }
353     
354     /**
355      * Get a String triplet representing the information in this instruction:
356      * the className, methodName, and methodSignature
357      */
358     private String   [] getInstructionTriplet(InvokeInstruction inv, ConstantPoolGen cpg) {
359 
360         // get the class name
361         ConstantCP ref = (ConstantCP) cpg.getConstant( inv.getIndex() );
362         String   className = ref.getClass(cpg.getConstantPool());
363         
364         // get the method name
365         ConstantNameAndType refNT = 
366             (ConstantNameAndType) cpg.getConstant( ref.getNameAndTypeIndex() );
367         String   methodName = refNT.getName(cpg.getConstantPool());
368 
369         // get the method signature
370         String   methodSignature = refNT.getSignature(cpg.getConstantPool());
371         
372         return new String  [] { className, methodName, methodSignature };
373     }
374     
375     /**
376      * Given a triplet representing the className, methodName, and methodSignature
377      * of an instruction, check to see if it is in our collectionsMap. <p>
378      * [Not Implemented] If not, search harder to see if one of the super classes 
379      * of className is in our collectionMap
380      */
381     private @CheckForNull String   [] getRelevantTriplet(String   [] instructionTriplet) {
382         if (collectionsMap.containsKey( getCollectionsMapKey(instructionTriplet) ))
383             return instructionTriplet;
384         
385         // HARDCODES
386         // Map "get" and "remove"
387         if (Arrays.asList(mapMembers).contains(instructionTriplet[0])) {
388             if ( "get"   .equals(instructionTriplet[1]) || 
389                  "remove".equals(instructionTriplet[1]) ) {
390                 addToCollectionsMap(instructionTriplet[0], 
391                         instructionTriplet[1], instructionTriplet[2], 0);
392                 return instructionTriplet;
393             }
394         }
395         
396         // XXX The rest not implemented
397         
398         // Not found
399         return null;
400     }
401     
402     /**
403      * Compare to see if the argument <code>argType</code> passed to the method 
404      * matches the type of the corresponding parameter. The simplest case is when
405      * both are equal. <p>
406      * This is a conservative comparison - returns true if it cannot decide.
407      * If the parameter type is a type variable (e.g. <code>T</code>) then we don't 
408      * know enough (yet) to decide if they do not match so return true.
409      */
410     private IncompatibleTypes compareTypes(Type parmType, Type argType) {
411         // XXX equality not implemented for GenericObjectType
412         // if (parmType.equals(argType)) return true;
413         // Compare type signatures instead
414         String   parmString = GenericUtilities.getString(parmType);
415         String   argString = GenericUtilities.getString(argType);
416         if (parmString.equals(argString)) return IncompatibleTypes.SEEMS_OK;
417 
418         // if either type is java.lang.Object, then automatically true!
419         // again compare strings...
420         String   objString = GenericUtilities.getString(Type.OBJECT);
421         if ( parmString.equals(objString) || 
422                 argString.equals(objString) ) {
423             return IncompatibleTypes.SEEMS_OK;
424         }
425 
426         // get a category for each type
427         TypeCategory parmCat = GenericUtilities.getTypeCategory(parmType);
428         TypeCategory argCat  = GenericUtilities.getTypeCategory(argType);
429 
430         // -~- plain objects are easy
431         if ( parmCat == TypeCategory.PLAIN_OBJECT_TYPE && 
432                 argCat == TypeCategory.PLAIN_OBJECT_TYPE ) 
433 
434 
435             return IncompatibleTypes.getPriorityForAssumingCompatible(parmType, argType);
436 
437         // -~- parmType is: "? extends Another Type" OR "? super Another Type"
438         if ( parmCat == TypeCategory.WILDCARD_EXTENDS || 
439                 parmCat == TypeCategory.WILDCARD_SUPER ) 
440             return compareTypes( 
441                     ((GenericObjectType)parmType).getExtension(), argType);
442 
443 
444         // -~- Not handling type variables
445         if ( parmCat == TypeCategory.TYPE_VARIABLE || 
446                 argCat == TypeCategory.TYPE_VARIABLE ) 
447             return IncompatibleTypes.SEEMS_OK;
448 
449 
450         // -~- Array Types: compare dimensions, then base type
451         if ( parmCat == TypeCategory.ARRAY_TYPE && 
452                 argCat  == TypeCategory.ARRAY_TYPE ) {
453             ArrayType parmArray = (ArrayType) parmType;
454             ArrayType argArray  = (ArrayType) argType;
455 
456             if (parmArray.getDimensions() != argArray.getDimensions())
457                 return IncompatibleTypes.ARRAY_AND_NON_ARRAY;
458 
459             return compareTypes(parmArray.getBasicType(), argArray.getBasicType());
460         }
461         //     If one is an Array Type and the other is not, then they
462         //     are incompatible. (We already know neither is java.lang.Object)
463         if ( parmCat == TypeCategory.ARRAY_TYPE ^ 
464                 argCat  == TypeCategory.ARRAY_TYPE ) {
465             return IncompatibleTypes.ARRAY_AND_NON_ARRAY;
466         }
467 
468         // -~- Parameter Types: compare base type then parameters
469         if ( parmCat == TypeCategory.PARAMETERS && 
470                 argCat  == TypeCategory.PARAMETERS ) {
471             GenericObjectType parmGeneric = (GenericObjectType) parmType;
472             GenericObjectType argGeneric  = (GenericObjectType) argType;
473 
474             // base types should be related
475             return compareTypes( parmGeneric.getObjectType(), 
476                     argGeneric.getObjectType());
477 
478             // XXX More to come
479         }
480         //     If one is a Parameter Type and the other is not, then they
481         //     are incompatible. (We already know neither is java.lang.Object)
482         if (false) {
483             // not true. Consider class Foo extends ArrayList<String>
484             if ( parmCat == TypeCategory.PARAMETERS ^ 
485                     argCat  == TypeCategory.PARAMETERS ) {
486                 return IncompatibleTypes.SEEMS_OK; // fix this when we know what we are doing here
487             }
488         }
489 
490         // -~- Wildcard e.g. List<*>.contains(...)      
491         if (parmCat == TypeCategory.WILDCARD) // No Way to know 
492             return IncompatibleTypes.SEEMS_OK;
493 
494         // -~- Non Reference types
495         // if ( parmCat == TypeCategory.NON_REFERENCE_TYPE || 
496         //      argCat == TypeCategory.NON_REFERENCE_TYPE )
497         if (parmType instanceof BasicType || argType instanceof BasicType) {
498             // this should not be possible, compiler will complain (pre 1.5) 
499             // or autobox primitive types (1.5 +)
500             throw new IllegalArgumentException  ("checking for compatibility of " + parmType + " with " + argType);
501         }
502 
503         return IncompatibleTypes.SEEMS_OK;
504 
505     }
506     
507     // old version of compare types
508     private boolean compareTypesOld(Type parmType, Type argType) {
509         // XXX equality not implemented for GenericObjectType
510         // if (parmType.equals(argType)) return true;
511         // Compare type signatures instead
512         if (GenericUtilities.getString(parmType)
513                 .equals(GenericUtilities.getString(argType)))
514             return true;
515         
516         if (parmType instanceof GenericObjectType) {
517             GenericObjectType o = (GenericObjectType) parmType;
518             if (o.getTypeCategory() == GenericUtilities.TypeCategory.WILDCARD_EXTENDS) {
519                 return compareTypesOld(o.getExtension(), argType);
520             }
521         }
522         // ignore type variables for now
523         if (parmType instanceof GenericObjectType && 
524                 !((GenericObjectType) parmType).hasParameters()) return true;
525         if (argType instanceof GenericObjectType && 
526                 !((GenericObjectType) argType).hasParameters()) return true;
527         
528         // Case: Both are generic containers
529         if (parmType instanceof GenericObjectType && argType instanceof GenericObjectType) {
530             return true;
531         } else {
532             // Don't consider non reference types (should not be possible)
533             if (!(parmType instanceof ReferenceType && argType instanceof ReferenceType))
534                 return true;
535             
536             // Don't consider non object types (for now)
537             if (!(parmType instanceof ObjectType && argType instanceof ObjectType))
538                 return true;
539             
540             // Otherwise, compare base types ignoring generic information
541             try {               
542                 return Repository.instanceOf(
543                         ((ObjectType)argType).getClassName(), 
544                         ((ObjectType)parmType).getClassName());
545             } catch (ClassNotFoundException   e) {}
546         }
547                  
548         return true;
549     }
550     
551     /**
552      * Empty
553      * @see edu.umd.cs.findbugs.Detector#report()
554      */
555     public void report() {
556     }
557 
558 }
559
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags