KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > edu > umd > cs > findbugs > ba > npe > IsNullValue


1 /*
2  * Bytecode Analysis Framework
3  * Copyright (C) 2003-2005 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.ba.npe;
21
22 import edu.umd.cs.findbugs.SystemProperties;
23 import edu.umd.cs.findbugs.annotations.NonNull;
24 import edu.umd.cs.findbugs.ba.Debug;
25 import edu.umd.cs.findbugs.ba.Location;
26 import edu.umd.cs.findbugs.ba.XMethod;
27 import edu.umd.cs.findbugs.ba.XMethodParameter;
28
29 /**
30  * A class to abstractly represent values in stack slots,
31  * indicating whether thoses values can be null, non-null,
32  * null on some incoming path, or unknown.
33  *
34  * @author David Hovemeyer
35  * @see IsNullValueFrame
36  * @see IsNullValueAnalysis
37  */
38 public class IsNullValue implements IsNullValueAnalysisFeatures, Debug {
39     private static final boolean DEBUG_EXCEPTION = SystemProperties.getBoolean("inv.debugException");
40     private static final boolean DEBUG_KABOOM = SystemProperties.getBoolean("inv.debugKaboom");
41
42     /** Definitely null. */
43     private static final int NULL = 0;
44     /** Definitely null because of a comparison to a known null value. */
45     private static final int CHECKED_NULL = 1;
46     
47     /** Definitely not null. */
48     private static final int NN = 2;
49     /** Definitely not null because of a comparison to a known null value. */
50     private static final int CHECKED_NN = 3;
51     /** Definitely not null an NPE would have occurred and we would not be here if it were null. */
52     private static final int NO_KABOOM_NN = 4;
53     
54     
55     /** Null on some simple path (at most one branch) to current location. */
56     private static final int NSP = 5;
57     /** Unknown value (method param, value read from heap, etc.), assumed not null. */
58     private static final int NN_UNKNOWN = 6;
59     /** Null on some complex path (at least two branches) to current location. */
60     private static final int NCP2 = 7;
61     /** Null on some complex path (at least three branches) to current location. */
62     private static final int NCP3 = 8;
63
64     private static final int FLAG_SHIFT = 8;
65     
66     /** Value was propagated along an exception path. */
67     private static final int EXCEPTION = 1 << FLAG_SHIFT;
68     /** Value is (potentially) null because of a parameter passed to the method. */
69     private static final int PARAM = 2 << FLAG_SHIFT;
70     /** Value is (potentially) null because of a value returned from a called method. */
71     private static final int RETURN_VAL = 4 << FLAG_SHIFT;
72
73     private static final int FLAG_MASK = EXCEPTION | PARAM | RETURN_VAL;
74
75     private static final int[][] mergeMatrix = {
76         // NULL, CHECKED_NULL, NN, CHECKED_NN, NO_KABOOM_NN, NSP, NN_UNKNOWN, NCP2, NCP3
77 {NULL}, // NULL
78 {NULL, CHECKED_NULL, }, // CHECKED_NULL
79 {NSP, NSP, NN}, // NN
80 {NSP, NSP, NN, CHECKED_NN, }, // CHECKED_NN
81 {NSP, NSP, NN, NN, NO_KABOOM_NN}, // NO_KABOOM_NN
82 {NSP, NSP, NSP, NSP, NSP, NSP}, // NSP
83 {NSP, NSP, NN_UNKNOWN, NN_UNKNOWN, NN_UNKNOWN, NSP, NN_UNKNOWN, }, // NN_UNKNOWN
84 {NSP, NSP, NCP2, NCP2, NCP2, NCP2, NCP2, NCP2,}, // NCP2
85 {NSP, NSP, NCP3, NCP3, NCP3, NCP3, NCP3, NCP3, NCP3}// NCP3
86 };
87     
88     private static final IsNullValue[][] instanceByFlagsList = createInstanceByFlagList();
89
90     private static IsNullValue[][] createInstanceByFlagList() {
91         final int max = FLAG_MASK >>> FLAG_SHIFT;
92         IsNullValue[][] result = new IsNullValue[max + 1][];
93         for (int i = 0; i <= max; ++i) {
94             final int flags = i << FLAG_SHIFT;
95             result[i] = new IsNullValue[]{
96                     new IsNullValue(NULL | flags),
97                     new IsNullValue(CHECKED_NULL | flags),
98                     new IsNullValue(NN | flags),
99                     new IsNullValue(CHECKED_NN | flags),
100                     null, // NO_KABOOM_NN values must be allocated dynamically
101 new IsNullValue(NSP | flags),
102                     new IsNullValue(NN_UNKNOWN | flags),
103                     new IsNullValue(NCP2 | flags),
104                     new IsNullValue(NCP3 | flags),
105             };
106         }
107         
108         return result;
109     }
110
111     // Fields
112 private final int kind;
113     private final Location locationOfKaBoom;
114
115     private IsNullValue(int kind) {
116         this.kind = kind;
117         locationOfKaBoom = null;
118         if (VERIFY_INTEGRITY) checkNoKaboomNNLocation();
119     }
120     
121     private IsNullValue(int kind, Location ins) {
122         this.kind = kind;
123         locationOfKaBoom = ins;
124         if (VERIFY_INTEGRITY) checkNoKaboomNNLocation();
125     }
126     
127     private void checkNoKaboomNNLocation() {
128         if (getBaseKind() == NO_KABOOM_NN && locationOfKaBoom == null) {
129             throw new IllegalStateException JavaDoc("construction of no-KaBoom NN without Location");
130         }
131     }
132
133     @Override JavaDoc
134     public boolean equals(Object JavaDoc o) {
135         if (o == null || this.getClass() != o.getClass())
136             return false;
137         IsNullValue other = (IsNullValue) o;
138         if ( kind != other.kind) return false;
139         if (locationOfKaBoom == other.locationOfKaBoom) return true;
140         if (locationOfKaBoom == null || other.locationOfKaBoom == null) return false;
141         return locationOfKaBoom.equals(other.locationOfKaBoom);
142     }
143
144     @Override JavaDoc
145     public int hashCode() {
146         int hashCode = kind;
147         if (locationOfKaBoom != null)
148             hashCode += locationOfKaBoom.hashCode();
149         return hashCode;
150     }
151
152     private int getBaseKind() {
153         return kind & ~FLAG_MASK;
154     }
155     
156     private int getFlags() {
157         return kind & FLAG_MASK;
158     }
159
160     /**
161      * Was this value propagated on an exception path?
162      */
163     public boolean isException() {
164         return (kind & EXCEPTION) != 0;
165     }
166     /**
167      * Was this value marked as a possibly null return value?
168      */
169     public boolean isReturnValue() {
170         return (kind & RETURN_VAL) != 0;
171     }
172     /**
173      * Was this value marked as a possibly null parameter?
174      */
175     public boolean isParamValue() {
176         return (kind & PARAM) != 0;
177     }
178
179     /**
180      * Is this value known because of an explicit null check?
181      */
182     public boolean isChecked() {
183         return getBaseKind() == CHECKED_NULL || getBaseKind() == CHECKED_NN;
184     }
185
186     /**
187      * Is this value known to be non null because a NPE would have occurred otherwise?
188      */
189     public boolean wouldHaveBeenAKaboom() {
190         return getBaseKind() == NO_KABOOM_NN;
191     }
192
193     private IsNullValue toBaseValue() {
194         return instanceByFlagsList[0][getBaseKind()];
195     }
196
197     /**
198      * Convert to an exception path value.
199      */
200     public IsNullValue toExceptionValue() {
201         if (getBaseKind() == NO_KABOOM_NN) return new IsNullValue(kind | EXCEPTION, locationOfKaBoom);
202         return instanceByFlagsList[(getFlags() | EXCEPTION) >> FLAG_SHIFT][getBaseKind()];
203     }
204     
205     /**
206      * Convert to a value known because it was returned from a method
207      * in a method property database.
208      * @param methodInvoked TODO
209      */
210     public IsNullValue markInformationAsComingFromReturnValueOfMethod(XMethod methodInvoked) {
211         if (getBaseKind() == NO_KABOOM_NN) return new IsNullValue(kind | RETURN_VAL, locationOfKaBoom);
212         return instanceByFlagsList[(getFlags() | RETURN_VAL) >> FLAG_SHIFT][getBaseKind()];
213     }
214
215     
216     /**
217      * Get the instance representing values that are definitely null.
218      */
219     public static IsNullValue nullValue() {
220         return instanceByFlagsList[0][NULL];
221     }
222
223     /**
224      * Get the instance representing a value known to be null
225      * because it was compared against null value, or because
226      * we saw that it was assigned the null constant.
227      */
228     public static IsNullValue checkedNullValue() {
229         return instanceByFlagsList[0][CHECKED_NULL];
230     }
231
232     /**
233      * Get the instance representing values that are definitely not null.
234      */
235     public static IsNullValue nonNullValue() {
236         return instanceByFlagsList[0][NN];
237     }
238
239     /**
240      * Get the instance representing a value known to be non-null
241      * because it was compared against null value, or because
242      * we saw the object creation.
243      */
244     public static IsNullValue checkedNonNullValue() {
245         return instanceByFlagsList[0][CHECKED_NN];
246     }
247
248     /**
249      * Get the instance representing a value known to be non-null
250      * because a NPE would have occurred if it were null.
251      */
252     public static IsNullValue noKaboomNonNullValue(@NonNull Location ins) {
253         if (ins == null)
254             throw new NullPointerException JavaDoc("ins cannot be null");
255         return new IsNullValue(NO_KABOOM_NN, ins);
256     }
257
258     /**
259      * Get the instance representing values that are definitely null
260      * on some simple (no branches) incoming path.
261      */
262     public static IsNullValue nullOnSimplePathValue() {
263         return instanceByFlagsList[0][NSP];
264     }
265
266     /**
267      * Get instance representing a parameter marked as MightBeNull
268      */
269     public static IsNullValue parameterMarkedAsMightBeNull(XMethodParameter mp) {
270         return instanceByFlagsList[PARAM >> FLAG_SHIFT][NSP];
271     }
272     
273     /**
274      * Get non-reporting non-null value.
275      * This is what we use for unknown values.
276      */
277     public static IsNullValue nonReportingNotNullValue() {
278         return instanceByFlagsList[0][NN_UNKNOWN];
279     }
280
281     /**
282      * Get null on complex path value.
283      * This is like null on simple path value, but there
284      * are at least two branches between the explicit null value
285      * and the current location. If the conditions are correlated,
286      * then the path on which the value is null may be infeasible.
287      */
288     public static IsNullValue nullOnComplexPathValue() {
289         return instanceByFlagsList[0][NCP2];
290     }
291     
292     /**
293      * Like "null on complex path" except that there are at least
294      * <em>three</em> branches between the explicit null value
295      * and the current location.
296      */
297     public static IsNullValue nullOnComplexPathValue3() {
298         return instanceByFlagsList[0][NCP3];
299     }
300
301     /**
302      * Get null value resulting from comparison to explicit null.
303      */
304     public static IsNullValue pathSensitiveNullValue() {
305         return instanceByFlagsList[0][CHECKED_NULL];
306     }
307
308     /**
309      * Get non-null value resulting from comparison to explicit null.
310      */
311     public static IsNullValue pathSensitiveNonNullValue() {
312         return instanceByFlagsList[0][CHECKED_NN];
313     }
314
315     /**
316      * Merge two values.
317      */
318     public static IsNullValue merge(IsNullValue a, IsNullValue b) {
319         if (a == b) return a;
320         if (a.equals(b)) return a;
321         int aKind = a.kind & 0xff;
322         int bKind = b.kind & 0xff;
323         int aFlags = a.getFlags();
324         int bFlags = b.getFlags();
325         
326
327         int combinedFlags = aFlags & bFlags;
328
329         
330         if (!(a.isNullOnSomePath() || a.isDefinitelyNull()) && b.isException())
331                 combinedFlags |= EXCEPTION;
332         else
333             if (!(b.isNullOnSomePath() || b.isDefinitelyNull()) && a.isException())
334                 combinedFlags |= EXCEPTION;
335         
336         // Left hand value should be >=, since it is used
337 // as the first dimension of the matrix to index.
338 if (aKind < bKind) {
339             int tmp = aKind;
340             aKind = bKind;
341             bKind = tmp;
342         }
343         assert aKind >= bKind;
344         int result = mergeMatrix[aKind][bKind];
345         
346         IsNullValue resultValue = (result == NO_KABOOM_NN)
347                 ? noKaboomNonNullValue(a.locationOfKaBoom)
348                 : instanceByFlagsList[combinedFlags >> FLAG_SHIFT][result];
349
350         return resultValue;
351     }
352
353     /**
354      * Is this value definitely null?
355      */
356     public boolean isDefinitelyNull() {
357         int baseKind = getBaseKind();
358         return baseKind == NULL || baseKind == CHECKED_NULL;
359     }
360
361     /**
362      * Is this value null on some path?
363      */
364     public boolean isNullOnSomePath() {
365         int baseKind = getBaseKind();
366         if (NCP_EXTRA_BRANCH) {
367             // Note: NCP_EXTRA_BRANCH is an experimental feature
368 // to see how many false warnings we get when we allow
369 // two branches between an explicit null and a
370 // a dereference.
371 return baseKind == NSP || baseKind == NCP2;
372         } else {
373             return baseKind == NSP;
374         }
375     }
376     /**
377      * Is this value null on a complicated path?
378      */
379     public boolean isNullOnComplicatedPath() {
380         int baseKind = getBaseKind();
381          return baseKind == NN_UNKNOWN || baseKind == NCP2 || baseKind == NCP3;
382     }
383     /**
384      * Return true if this value is either definitely null,
385      * or might be null on a simple path.
386      *
387      * @return true if this value is either definitely null,
388      * or might be null on a simple path, false otherwise
389      */
390     public boolean mightBeNull() {
391         return isDefinitelyNull() || isNullOnSomePath();
392     }
393
394     /**
395      * Is this value definitely not null?
396      */
397     public boolean isDefinitelyNotNull() {
398         int baseKind = getBaseKind();
399         return baseKind == NN || baseKind == CHECKED_NN || baseKind == NO_KABOOM_NN;
400     }
401
402     @Override JavaDoc
403     public String JavaDoc toString() {
404         String JavaDoc pfx = "";
405         if (DEBUG_EXCEPTION) {
406             int flags = getFlags();
407             if (flags == 0)
408                 pfx = "_";
409             else {
410                 if ((flags & EXCEPTION) != 0) pfx += "e";
411                 if ((flags & PARAM) != 0) pfx += "p";
412                 if ((flags & RETURN_VAL) != 0) pfx += "r";
413             }
414         }
415         if (DEBUG_KABOOM && locationOfKaBoom == null) {
416             pfx += "[?]";
417         }
418         switch (getBaseKind()) {
419         case NULL:
420             return pfx + "n" + ",";
421         case CHECKED_NULL:
422             return pfx + "w" + ",";
423         case NN:
424             return pfx + "N" + ",";
425         case CHECKED_NN:
426             return pfx + "W" + ",";
427         case NO_KABOOM_NN:
428             return pfx + "K" + ",";
429         case NSP:
430             return pfx + "s" + ",";
431         case NN_UNKNOWN:
432             return pfx + "-" + ",";
433         case NCP2:
434             return pfx + "/" + ",";
435         default:
436             throw new IllegalStateException JavaDoc("unknown kind of IsNullValue: " + kind);
437         }
438     }
439     public Location getLocationOfKaBoom() {
440         return locationOfKaBoom;
441     }
442
443     /**
444      * Control split: move given value down in the lattice
445      * if it is a conditionally-null value.
446      *
447      * @return another value (equal or further down in the lattice)
448      */
449     public IsNullValue downgradeOnControlSplit() {
450         IsNullValue value = this;
451         
452         if (NCP_EXTRA_BRANCH) {
453             // Experimental: track two distinct kinds of "null on complex path" values.
454 if (value.isNullOnSomePath())
455                 value = nullOnComplexPathValue();
456             else if (value.equals(nullOnComplexPathValue()))
457                 value = nullOnComplexPathValue3();
458                 
459         } else {
460             // Downgrade "null on simple path" values to
461 // "null on complex path".
462 if (value.isNullOnSomePath())
463                 value = nullOnComplexPathValue();
464         }
465         return value;
466     }
467 }
468
469 // vim:ts=4
470
Popular Tags