001: /*
002: * FindBugs - Find Bugs in Java programs
003: * Copyright (C) 2005, University of Maryland
004: *
005: * This library is free software; you can redistribute it and/or
006: * modify it under the terms of the GNU Lesser General Public
007: * License as published by the Free Software Foundation; either
008: * version 2.1 of the License, or (at your option) any later version.
009: *
010: * This library is distributed in the hope that it will be useful,
011: * but WITHOUT ANY WARRANTY; without even the implied warranty of
012: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
013: * Lesser General Public License for more details.
014: *
015: * You should have received a copy of the GNU Lesser General Public
016: * License along with this library; if not, write to the Free Software
017: * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
018: */
019:
020: package edu.umd.cs.findbugs;
021:
022: import java.util.HashSet;
023: import java.util.IdentityHashMap;
024: import java.util.Iterator;
025: import java.util.NoSuchElementException;
026:
027: import edu.umd.cs.findbugs.model.ClassNameRewriter;
028:
029: /**
030: * A slightly more intellegent way of comparing BugInstances from two versions
031: * to see if they are the "same". Uses class and method hashes to try to
032: * handle renamings, at least for simple cases. (<em>Hashes disabled for the
033: * time being.</em>) Uses opcode context to try to identify code that is the
034: * same, even if it moves within the method. Also compares by bug abbreviation
035: * rather than bug type, since the "same" bug can change type if the context
036: * changes (e.g., "definitely null" to "null on simple path" for a null pointer
037: * dereference). Also, we often change bug types between different versions
038: * of FindBugs.
039: *
040: * @see edu.umd.cs.findbugs.BugInstance
041: * @see edu.umd.cs.findbugs.VersionInsensitiveBugComparator
042: * @author David Hovemeyer
043: */
044: public class FuzzyBugComparator implements WarningComparator {
045: private static final boolean DEBUG = false;
046:
047: // Don't use hashes for now. Still ironing out issues there.
048: private static final boolean USE_HASHES = false;
049:
050: private static final long serialVersionUID = 1L;
051:
052: /**
053: * Filter ignored BugAnnotations from given Iterator.
054: */
055: private static class FilteringBugAnnotationIterator implements
056: Iterator<BugAnnotation> {
057:
058: Iterator<BugAnnotation> iter;
059: BugAnnotation next;
060:
061: public FilteringBugAnnotationIterator(
062: Iterator<BugAnnotation> iter) {
063: this .iter = iter;
064: }
065:
066: private void findNext() {
067: if (next == null) {
068: while (iter.hasNext()) {
069: BugAnnotation candidate = iter.next();
070: if (!ignore(candidate)) {
071: next = candidate;
072: break;
073: }
074: }
075: }
076: }
077:
078: /* (non-Javadoc)
079: * @see java.util.Iterator#hasNext()
080: */
081: public boolean hasNext() {
082: findNext();
083: return next != null;
084: }
085:
086: /* (non-Javadoc)
087: * @see java.util.Iterator#next()
088: */
089: public BugAnnotation next() {
090: findNext();
091: if (next == null)
092: throw new NoSuchElementException();
093: BugAnnotation result = next;
094: next = null;
095: return result;
096: }
097:
098: /* (non-Javadoc)
099: * @see java.util.Iterator#remove()
100: */
101: public void remove() {
102: throw new UnsupportedOperationException();
103: }
104: }
105:
106: /** Keep track of which BugCollections the various BugInstances have come from. */
107: private IdentityHashMap<BugInstance, BugCollection> bugCollectionMap;
108:
109: private ClassNameRewriter classNameRewriter;
110:
111: /**
112: * Map of class hashes to canonicate class names used for comparison purposes.
113: */
114: //private Map<ClassHash, String> classHashToCanonicalClassNameMap;
115: public FuzzyBugComparator() {
116: if (DEBUG)
117: System.out.println("Created fuzzy comparator");
118: this .bugCollectionMap = new IdentityHashMap<BugInstance, BugCollection>();
119: //this.classHashToCanonicalClassNameMap = new TreeMap<ClassHash, String>();
120: }
121:
122: /**
123: * Register a BugCollection. This allows us to find the class and method
124: * hashes for BugInstances to be compared.
125: *
126: * @param bugCollection a BugCollection
127: */
128: public void registerBugCollection(BugCollection bugCollection) {
129: // For now, nothing to do
130: }
131:
132: /* (non-Javadoc)
133: * @see edu.umd.cs.findbugs.WarningComparator#setClassNameRewriter(edu.umd.cs.findbugs.model.MovedClassMap)
134: */
135: public void setClassNameRewriter(ClassNameRewriter classNameRewriter) {
136: this .classNameRewriter = classNameRewriter;
137: }
138:
139: public int compare(BugInstance lhs, BugInstance rhs) {
140: int cmp;
141:
142: if (DEBUG)
143: System.out.println("Fuzzy comparison");
144:
145: // Bug abbreviations must match.
146: BugPattern lhsPattern = lhs.getBugPattern();
147: BugPattern rhsPattern = rhs.getBugPattern();
148:
149: if (lhsPattern == null || rhsPattern == null) {
150: if (DEBUG) {
151: if (lhsPattern == null)
152: System.out.println("Missing pattern: "
153: + lhs.getType());
154: if (rhsPattern == null)
155: System.out.println("Missing pattern: "
156: + rhs.getType());
157: }
158: String lhsCode = getCode(lhs.getType());
159: String rhsCode = getCode(rhs.getType());
160: if ((cmp = lhsCode.compareTo(rhsCode)) != 0)
161: return cmp;
162: } else {
163: if ((cmp = lhsPattern.getAbbrev().compareTo(
164: rhsPattern.getAbbrev())) != 0)
165: return cmp;
166: }
167:
168: BugCollection lhsCollection = bugCollectionMap.get(lhs);
169: BugCollection rhsCollection = bugCollectionMap.get(rhs);
170:
171: // Scan through bug annotations, comparing fuzzily if possible
172:
173: Iterator<BugAnnotation> lhsIter = new FilteringBugAnnotationIterator(
174: lhs.annotationIterator());
175: Iterator<BugAnnotation> rhsIter = new FilteringBugAnnotationIterator(
176: rhs.annotationIterator());
177:
178: while (lhsIter.hasNext() && rhsIter.hasNext()) {
179: BugAnnotation lhsAnnotation = lhsIter.next();
180: BugAnnotation rhsAnnotation = rhsIter.next();
181:
182: if (DEBUG)
183: System.out.println("Compare annotations: "
184: + lhsAnnotation + "," + rhsAnnotation);
185:
186: // Annotation classes must match exactly
187: cmp = lhsAnnotation.getClass().getName().compareTo(
188: rhsAnnotation.getClass().getName());
189: if (cmp != 0) {
190: if (DEBUG)
191: System.out.println("annotation class mismatch: "
192: + lhsAnnotation.getClass().getName() + ","
193: + rhsAnnotation.getClass().getName());
194: return cmp;
195: }
196:
197: if (lhsAnnotation.getClass() == ClassAnnotation.class)
198: cmp = compareClasses(lhsCollection, rhsCollection,
199: (ClassAnnotation) lhsAnnotation,
200: (ClassAnnotation) rhsAnnotation);
201: else if (lhsAnnotation.getClass() == MethodAnnotation.class)
202: cmp = compareMethods(lhsCollection, rhsCollection,
203: (MethodAnnotation) lhsAnnotation,
204: (MethodAnnotation) rhsAnnotation);
205: else if (lhsAnnotation.getClass() == SourceLineAnnotation.class)
206: cmp = compareSourceLines(lhsCollection, rhsCollection,
207: (SourceLineAnnotation) lhsAnnotation,
208: (SourceLineAnnotation) rhsAnnotation);
209: else
210: // everything else just compare directly
211: cmp = lhsAnnotation.compareTo(rhsAnnotation);
212:
213: if (cmp != 0)
214: return cmp;
215: }
216:
217: // Number of bug annotations must match
218: if (!lhsIter.hasNext() && !rhsIter.hasNext()) {
219: if (DEBUG)
220: System.out.println("Match!");
221: return 0;
222: } else
223: return (lhsIter.hasNext() ? 1 : -1);
224: }
225:
226: /**
227: * @param type
228: * @return the code of the Bug
229: */
230: private String getCode(String type) {
231: int bar = type.indexOf('_');
232: if (bar < 0)
233: return "";
234: else
235: return type.substring(0, bar);
236: }
237:
238: private static int compareNullElements(Object a, Object b) {
239: if (a != null)
240: return 1;
241: else if (b != null)
242: return -1;
243: else
244: return 0;
245: }
246:
247: public int compareClasses(BugCollection lhsCollection,
248: BugCollection rhsCollection, ClassAnnotation lhsClass,
249: ClassAnnotation rhsClass) {
250: if (lhsClass == null || rhsClass == null) {
251: return compareNullElements(lhsClass, rhsClass);
252: } else {
253: return compareClassesByName(lhsCollection, rhsCollection,
254: lhsClass.getClassName(), rhsClass.getClassName());
255: }
256: }
257:
258: // Compare classes: either exact fully qualified name must match, or class hash must match
259: public int compareClassesByName(BugCollection lhsCollection,
260: BugCollection rhsCollection, String lhsClassName,
261: String rhsClassName) {
262:
263: lhsClassName = rewriteClassName(lhsClassName);
264: rhsClassName = rewriteClassName(rhsClassName);
265:
266: return lhsClassName.compareTo(rhsClassName);
267: }
268:
269: /**
270: * @param className
271: * @return the rewritten class name
272: */
273: private String rewriteClassName(String className) {
274: if (classNameRewriter != null) {
275: className = classNameRewriter.rewriteClassName(className);
276: }
277: return className;
278: }
279:
280: // Compare methods: either exact name and signature must match, or method hash must match
281: public int compareMethods(BugCollection lhsCollection,
282: BugCollection rhsCollection, MethodAnnotation lhsMethod,
283: MethodAnnotation rhsMethod) {
284: if (lhsMethod == null || rhsMethod == null) {
285: return compareNullElements(lhsMethod, rhsMethod);
286: }
287:
288: // Compare for exact match
289: int cmp = lhsMethod.compareTo(rhsMethod);
290:
291: return cmp;
292: }
293:
294: /**
295: * For now, just look at the 2 preceeding and succeeding opcodes
296: * for fuzzy source line matching.
297: */
298: private static final int NUM_CONTEXT_OPCODES = 2;
299:
300: /**
301: * Compare source line annotations.
302: *
303: * @param rhsCollection lhs BugCollection
304: * @param lhsCollection rhs BugCollection
305: * @param lhs a SourceLineAnnotation
306: * @param rhs another SourceLineAnnotation
307: * @return comparison of lhs and rhs
308: */
309: public int compareSourceLines(BugCollection lhsCollection,
310: BugCollection rhsCollection, SourceLineAnnotation lhs,
311: SourceLineAnnotation rhs) {
312: if (lhs == null || rhs == null) {
313: return compareNullElements(lhs, rhs);
314: }
315:
316: // Classes must match fuzzily.
317: int cmp = compareClassesByName(lhsCollection, rhsCollection,
318: lhs.getClassName(), rhs.getClassName());
319: if (cmp != 0)
320: return cmp;
321:
322: return 0;
323: }
324:
325: // See "FindBugsAnnotationDescriptions.properties"
326: private static final HashSet<String> significantDescriptionSet = new HashSet<String>();
327: static {
328: // Classes, methods, and fields are significant.
329: significantDescriptionSet.add("CLASS_DEFAULT");
330: significantDescriptionSet.add("CLASS_EXCEPTION");
331: significantDescriptionSet.add("CLASS_REFTYPE");
332: significantDescriptionSet.add("INTERFACE_TYPE");
333: significantDescriptionSet.add("METHOD_DEFAULT");
334: significantDescriptionSet.add("METHOD_CALLED");
335: significantDescriptionSet.add("METHOD_DANGEROUS_TARGET"); // but do NOT use safe targets
336: significantDescriptionSet.add("METHOD_DECLARED_NONNULL");
337: significantDescriptionSet.add("FIELD_DEFAULT");
338: significantDescriptionSet.add("FIELD_ON");
339: significantDescriptionSet.add("FIELD_SUPER");
340: significantDescriptionSet.add("FIELD_MASKED");
341: significantDescriptionSet.add("FIELD_MASKING");
342: significantDescriptionSet.add("FIELD_STORED");
343: significantDescriptionSet.add("TYPE_DEFAULT");
344: significantDescriptionSet.add("TYPE_EXPECTED");
345: significantDescriptionSet.add("TYPE_FOUND");
346:
347: significantDescriptionSet.add("LOCAL_VARIABLE_NAMED");
348:
349: // Many int annotations are NOT significant: e.g., sync %, biased locked %, bytecode offset, etc.
350: // The null parameter annotations, however, are definitely significant.
351: significantDescriptionSet.add("INT_NULL_ARG");
352: significantDescriptionSet.add("INT_MAYBE_NULL_ARG");
353: significantDescriptionSet.add("INT_NONNULL_PARAM");
354: // Only DEFAULT source line annotations are significant.
355: significantDescriptionSet.add("SOURCE_LINE_DEFAULT");
356: }
357:
358: public static boolean ignore(BugAnnotation annotation) {
359: return !significantDescriptionSet.contains(annotation
360: .getDescription());
361: }
362: }
|