001: /*
002: * Bytecode Analysis Framework
003: * Copyright (C) 2003-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.ba.npe;
021:
022: import edu.umd.cs.findbugs.SystemProperties;
023: import edu.umd.cs.findbugs.annotations.NonNull;
024: import edu.umd.cs.findbugs.ba.Debug;
025: import edu.umd.cs.findbugs.ba.Location;
026: import edu.umd.cs.findbugs.ba.XField;
027: import edu.umd.cs.findbugs.ba.XMethod;
028: import edu.umd.cs.findbugs.ba.XMethodParameter;
029:
030: /**
031: * A class to abstractly represent values in stack slots,
032: * indicating whether thoses values can be null, non-null,
033: * null on some incoming path, or unknown.
034: *
035: * @author David Hovemeyer
036: * @see IsNullValueFrame
037: * @see IsNullValueAnalysis
038: */
039: public class IsNullValue implements IsNullValueAnalysisFeatures, Debug {
040: private static final boolean DEBUG_EXCEPTION = SystemProperties
041: .getBoolean("inv.debugException");
042: private static final boolean DEBUG_KABOOM = SystemProperties
043: .getBoolean("inv.debugKaboom");
044:
045: /** Definitely null. */
046: private static final int NULL = 0;
047: /** Definitely null because of a comparison to a known null value. */
048: private static final int CHECKED_NULL = 1;
049:
050: /** Definitely not null. */
051: private static final int NN = 2;
052: /** Definitely not null because of a comparison to a known null value. */
053: private static final int CHECKED_NN = 3;
054: /** Definitely not null an NPE would have occurred and we would not be here if it were null. */
055: private static final int NO_KABOOM_NN = 4;
056:
057: /** Null on some simple path (at most one branch) to current location. */
058: private static final int NSP = 5;
059: /** Unknown value (method param, value read from heap, etc.), assumed not null. */
060: private static final int NN_UNKNOWN = 6;
061: /** Null on some complex path (at least two branches) to current location. */
062: private static final int NCP2 = 7;
063: /** Null on some complex path (at least three branches) to current location. */
064: private static final int NCP3 = 8;
065:
066: private static final int FLAG_SHIFT = 8;
067:
068: /** Value was propagated along an exception path. */
069: private static final int EXCEPTION = 1 << FLAG_SHIFT;
070: /** Value is (potentially) null because of a parameter passed to the method. */
071: private static final int PARAM = 2 << FLAG_SHIFT;
072: /** Value is (potentially) null because of a value returned from a called method. */
073: private static final int RETURN_VAL = 4 << FLAG_SHIFT;
074: private static final int FIELD_VAL = 8 << FLAG_SHIFT;
075:
076: private static final int FLAG_MASK = EXCEPTION | PARAM | RETURN_VAL
077: | FIELD_VAL;
078:
079: private static final int[][] mergeMatrix = {
080: // NULL, CHECKED_NULL, NN, CHECKED_NN, NO_KABOOM_NN, NSP, NN_UNKNOWN, NCP2, NCP3
081: { NULL }, // NULL
082: { NULL, CHECKED_NULL, }, // CHECKED_NULL
083: { NSP, NSP, NN }, // NN
084: { NSP, NSP, NN, CHECKED_NN, }, // CHECKED_NN
085: { NSP, NSP, NN, NN, NO_KABOOM_NN }, // NO_KABOOM_NN
086: { NSP, NSP, NSP, NSP, NSP, NSP }, // NSP
087: { NSP, NSP, NN_UNKNOWN, NN_UNKNOWN, NN_UNKNOWN, NSP,
088: NN_UNKNOWN, }, // NN_UNKNOWN
089: { NSP, NSP, NCP2, NCP2, NCP2, NSP, NCP2, NCP2, }, // NCP2
090: { NSP, NSP, NCP3, NCP3, NCP3, NSP, NCP3, NCP3, NCP3 } // NCP3
091: };
092:
093: private static final IsNullValue[][] instanceByFlagsList = createInstanceByFlagList();
094:
095: private static IsNullValue[][] createInstanceByFlagList() {
096: final int max = FLAG_MASK >>> FLAG_SHIFT;
097: IsNullValue[][] result = new IsNullValue[max + 1][];
098: for (int i = 0; i <= max; ++i) {
099: final int flags = i << FLAG_SHIFT;
100: result[i] = new IsNullValue[] {
101: new IsNullValue(NULL | flags),
102: new IsNullValue(CHECKED_NULL | flags),
103: new IsNullValue(NN | flags),
104: new IsNullValue(CHECKED_NN | flags),
105: null, // NO_KABOOM_NN values must be allocated dynamically
106: new IsNullValue(NSP | flags),
107: new IsNullValue(NN_UNKNOWN | flags),
108: new IsNullValue(NCP2 | flags),
109: new IsNullValue(NCP3 | flags), };
110: }
111:
112: return result;
113: }
114:
115: // Fields
116: private final int kind;
117: private final Location locationOfKaBoom;
118:
119: private IsNullValue(int kind) {
120: this .kind = kind;
121: locationOfKaBoom = null;
122: if (VERIFY_INTEGRITY)
123: checkNoKaboomNNLocation();
124: }
125:
126: private IsNullValue(int kind, Location ins) {
127: this .kind = kind;
128: locationOfKaBoom = ins;
129: if (VERIFY_INTEGRITY)
130: checkNoKaboomNNLocation();
131: }
132:
133: private void checkNoKaboomNNLocation() {
134: if (getBaseKind() == NO_KABOOM_NN && locationOfKaBoom == null) {
135: throw new IllegalStateException(
136: "construction of no-KaBoom NN without Location");
137: }
138: }
139:
140: @Override
141: public boolean equals(Object o) {
142: if (o == null || this .getClass() != o.getClass())
143: return false;
144: IsNullValue other = (IsNullValue) o;
145: if (kind != other.kind)
146: return false;
147: if (locationOfKaBoom == other.locationOfKaBoom)
148: return true;
149: if (locationOfKaBoom == null || other.locationOfKaBoom == null)
150: return false;
151: return locationOfKaBoom.equals(other.locationOfKaBoom);
152: }
153:
154: @Override
155: public int hashCode() {
156: int hashCode = kind;
157: if (locationOfKaBoom != null)
158: hashCode += locationOfKaBoom.hashCode();
159: return hashCode;
160: }
161:
162: private int getBaseKind() {
163: return kind & ~FLAG_MASK;
164: }
165:
166: private int getFlags() {
167: return kind & FLAG_MASK;
168: }
169:
170: /**
171: * Was this value propagated on an exception path?
172: */
173: public boolean isException() {
174: return (kind & EXCEPTION) != 0;
175: }
176:
177: /**
178: * Was this value marked as a possibly null return value?
179: */
180: public boolean isReturnValue() {
181: return (kind & RETURN_VAL) != 0;
182: }
183:
184: public boolean isFieldValue() {
185: return (kind & FIELD_VAL) != 0;
186: }
187:
188: /**
189: * Was this value marked as a possibly null parameter?
190: */
191: public boolean isParamValue() {
192: return (kind & PARAM) != 0;
193: }
194:
195: /**
196: * Is this value known because of an explicit null check?
197: */
198: public boolean isChecked() {
199: return getBaseKind() == CHECKED_NULL
200: || getBaseKind() == CHECKED_NN;
201: }
202:
203: /**
204: * Is this value known to be non null because a NPE would have occurred otherwise?
205: */
206: public boolean wouldHaveBeenAKaboom() {
207: return getBaseKind() == NO_KABOOM_NN;
208: }
209:
210: private IsNullValue toBaseValue() {
211: return instanceByFlagsList[0][getBaseKind()];
212: }
213:
214: /**
215: * Convert to an exception path value.
216: */
217: public IsNullValue toExceptionValue() {
218: if (getBaseKind() == NO_KABOOM_NN)
219: return new IsNullValue(kind | EXCEPTION, locationOfKaBoom);
220: return instanceByFlagsList[(getFlags() | EXCEPTION) >> FLAG_SHIFT][getBaseKind()];
221: }
222:
223: /**
224: * Convert to a value known because it was returned from a method
225: * in a method property database.
226: * @param methodInvoked TODO
227: */
228: public IsNullValue markInformationAsComingFromReturnValueOfMethod(
229: XMethod methodInvoked) {
230: if (getBaseKind() == NO_KABOOM_NN)
231: return new IsNullValue(kind | RETURN_VAL, locationOfKaBoom);
232: return instanceByFlagsList[(getFlags() | RETURN_VAL) >> FLAG_SHIFT][getBaseKind()];
233: }
234:
235: /**
236: * Convert to a value known because it was returned from a method
237: * in a method property database.
238: * @param methodInvoked TODO
239: */
240: public IsNullValue markInformationAsComingFromFieldValue(
241: XField field) {
242: if (getBaseKind() == NO_KABOOM_NN)
243: return new IsNullValue(kind | FIELD_VAL, locationOfKaBoom);
244: return instanceByFlagsList[(getFlags() | FIELD_VAL) >> FLAG_SHIFT][getBaseKind()];
245: }
246:
247: /**
248: * Get the instance representing values that are definitely null.
249: */
250: public static IsNullValue nullValue() {
251: return instanceByFlagsList[0][NULL];
252: }
253:
254: /**
255: * Get the instance representing a value known to be null
256: * because it was compared against null value, or because
257: * we saw that it was assigned the null constant.
258: */
259: public static IsNullValue checkedNullValue() {
260: return instanceByFlagsList[0][CHECKED_NULL];
261: }
262:
263: /**
264: * Get the instance representing values that are definitely not null.
265: */
266: public static IsNullValue nonNullValue() {
267: return instanceByFlagsList[0][NN];
268: }
269:
270: /**
271: * Get the instance representing a value known to be non-null
272: * because it was compared against null value, or because
273: * we saw the object creation.
274: */
275: public static IsNullValue checkedNonNullValue() {
276: return instanceByFlagsList[0][CHECKED_NN];
277: }
278:
279: /**
280: * Get the instance representing a value known to be non-null
281: * because a NPE would have occurred if it were null.
282: */
283: public static IsNullValue noKaboomNonNullValue(@NonNull
284: Location ins) {
285: if (ins == null)
286: throw new NullPointerException("ins cannot be null");
287: return new IsNullValue(NO_KABOOM_NN, ins);
288: }
289:
290: /**
291: * Get the instance representing values that are definitely null
292: * on some simple (no branches) incoming path.
293: */
294: public static IsNullValue nullOnSimplePathValue() {
295: return instanceByFlagsList[0][NSP];
296: }
297:
298: /**
299: * Get instance representing a parameter marked as MightBeNull
300: */
301: public static IsNullValue parameterMarkedAsMightBeNull(
302: XMethodParameter mp) {
303: return instanceByFlagsList[PARAM >> FLAG_SHIFT][NSP];
304: }
305:
306: /**
307: * Get non-reporting non-null value.
308: * This is what we use for unknown values.
309: */
310: public static IsNullValue nonReportingNotNullValue() {
311: return instanceByFlagsList[0][NN_UNKNOWN];
312: }
313:
314: /**
315: * Get null on complex path value.
316: * This is like null on simple path value, but there
317: * are at least two branches between the explicit null value
318: * and the current location. If the conditions are correlated,
319: * then the path on which the value is null may be infeasible.
320: */
321: public static IsNullValue nullOnComplexPathValue() {
322: return instanceByFlagsList[0][NCP2];
323: }
324:
325: /**
326: * Like "null on complex path" except that there are at least
327: * <em>three</em> branches between the explicit null value
328: * and the current location.
329: */
330: public static IsNullValue nullOnComplexPathValue3() {
331: return instanceByFlagsList[0][NCP3];
332: }
333:
334: /**
335: * Get null value resulting from comparison to explicit null.
336: */
337: public static IsNullValue pathSensitiveNullValue() {
338: return instanceByFlagsList[0][CHECKED_NULL];
339: }
340:
341: /**
342: * Get non-null value resulting from comparison to explicit null.
343: */
344: public static IsNullValue pathSensitiveNonNullValue() {
345: return instanceByFlagsList[0][CHECKED_NN];
346: }
347:
348: /**
349: * Merge two values.
350: */
351: public static IsNullValue merge(IsNullValue a, IsNullValue b) {
352: if (a == b)
353: return a;
354: if (a.equals(b))
355: return a;
356: int aKind = a.kind & 0xff;
357: int bKind = b.kind & 0xff;
358: int aFlags = a.getFlags();
359: int bFlags = b.getFlags();
360:
361: int combinedFlags = aFlags & bFlags;
362:
363: if (!(a.isNullOnSomePath() || a.isDefinitelyNull())
364: && b.isException())
365: combinedFlags |= EXCEPTION;
366: else if (!(b.isNullOnSomePath() || b.isDefinitelyNull())
367: && a.isException())
368: combinedFlags |= EXCEPTION;
369:
370: // Left hand value should be >=, since it is used
371: // as the first dimension of the matrix to index.
372: if (aKind < bKind) {
373: int tmp = aKind;
374: aKind = bKind;
375: bKind = tmp;
376: }
377: assert aKind >= bKind;
378: int result = mergeMatrix[aKind][bKind];
379:
380: IsNullValue resultValue = (result == NO_KABOOM_NN) ? noKaboomNonNullValue(a.locationOfKaBoom)
381: : instanceByFlagsList[combinedFlags >> FLAG_SHIFT][result];
382:
383: return resultValue;
384: }
385:
386: /**
387: * Is this value definitely null?
388: */
389: public boolean isDefinitelyNull() {
390: int baseKind = getBaseKind();
391: return baseKind == NULL || baseKind == CHECKED_NULL;
392: }
393:
394: /**
395: * Is this value null on some path?
396: */
397: public boolean isNullOnSomePath() {
398: int baseKind = getBaseKind();
399: if (NCP_EXTRA_BRANCH) {
400: // Note: NCP_EXTRA_BRANCH is an experimental feature
401: // to see how many false warnings we get when we allow
402: // two branches between an explicit null and a
403: // a dereference.
404: return baseKind == NSP || baseKind == NCP2;
405: } else {
406: return baseKind == NSP;
407: }
408: }
409:
410: /**
411: * Is this value null on a complicated path?
412: */
413: public boolean isNullOnComplicatedPath() {
414: int baseKind = getBaseKind();
415: return baseKind == NN_UNKNOWN || baseKind == NCP2
416: || baseKind == NCP3;
417: }
418:
419: /**
420: * Return true if this value is either definitely null,
421: * or might be null on a simple path.
422: *
423: * @return true if this value is either definitely null,
424: * or might be null on a simple path, false otherwise
425: */
426: public boolean mightBeNull() {
427: return isDefinitelyNull() || isNullOnSomePath();
428: }
429:
430: /**
431: * Is this value definitely not null?
432: */
433: public boolean isDefinitelyNotNull() {
434: int baseKind = getBaseKind();
435: return baseKind == NN || baseKind == CHECKED_NN
436: || baseKind == NO_KABOOM_NN;
437: }
438:
439: @Override
440: public String toString() {
441: String pfx = "";
442: if (DEBUG_EXCEPTION) {
443: int flags = getFlags();
444: if (flags == 0)
445: pfx = "_";
446: else {
447: if ((flags & EXCEPTION) != 0)
448: pfx += "e";
449: if ((flags & PARAM) != 0)
450: pfx += "p";
451: if ((flags & RETURN_VAL) != 0)
452: pfx += "r";
453: if ((flags & FIELD_VAL) != 0)
454: pfx += "f";
455: }
456: }
457: if (DEBUG_KABOOM && locationOfKaBoom == null) {
458: pfx += "[?]";
459: }
460: switch (getBaseKind()) {
461: case NULL:
462: return pfx + "n" + ",";
463: case CHECKED_NULL:
464: return pfx + "w" + ",";
465: case NN:
466: return pfx + "N" + ",";
467: case CHECKED_NN:
468: return pfx + "W" + ",";
469: case NO_KABOOM_NN:
470: return pfx + "K" + ",";
471: case NSP:
472: return pfx + "s" + ",";
473: case NN_UNKNOWN:
474: return pfx + "-" + ",";
475: case NCP2:
476: return pfx + "/" + ",";
477: default:
478: throw new IllegalStateException(
479: "unknown kind of IsNullValue: " + kind);
480: }
481: }
482:
483: public Location getLocationOfKaBoom() {
484: return locationOfKaBoom;
485: }
486:
487: /**
488: * Control split: move given value down in the lattice
489: * if it is a conditionally-null value.
490: *
491: * @return another value (equal or further down in the lattice)
492: */
493: public IsNullValue downgradeOnControlSplit() {
494: IsNullValue value = this ;
495:
496: if (NCP_EXTRA_BRANCH) {
497: // Experimental: track two distinct kinds of "null on complex path" values.
498: if (value.isNullOnSomePath())
499: value = nullOnComplexPathValue();
500: else if (value.equals(nullOnComplexPathValue()))
501: value = nullOnComplexPathValue3();
502:
503: } else {
504: // Downgrade "null on simple path" values to
505: // "null on complex path".
506: if (value.isNullOnSomePath())
507: value = nullOnComplexPathValue();
508: }
509: return value;
510: }
511: }
512:
513: // vim:ts=4
|