001: /* NullnessAssumptionAnalysis
002: * Copyright (C) 2006 Richard L. Halpert
003: *
004: * This library is free software; you can redistribute it and/or
005: * modify it under the terms of the GNU Lesser General Public
006: * License as published by the Free Software Foundation; either
007: * version 2.1 of the License, or (at your option) any later version.
008: *
009: * This library is distributed in the hope that it will be useful,
010: * but WITHOUT ANY WARRANTY; without even the implied warranty of
011: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
012: * Lesser General Public License for more details.
013: *
014: * You should have received a copy of the GNU Lesser General Public
015: * License along with this library; if not, write to the
016: * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
017: * Boston, MA 02111-1307, USA.
018: */
019:
020: package soot.jimple.toolkits.annotation.nullcheck;
021:
022: import java.util.HashMap;
023: import java.util.HashSet;
024: import java.util.Iterator;
025: import java.util.Map;
026: import java.util.Set;
027: import java.util.Map.Entry;
028:
029: import soot.Immediate;
030: import soot.Local;
031: import soot.RefLikeType;
032: import soot.Unit;
033: import soot.Value;
034: import soot.jimple.ArrayRef;
035: import soot.jimple.DefinitionStmt;
036: import soot.jimple.FieldRef;
037: import soot.jimple.InstanceFieldRef;
038: import soot.jimple.InstanceInvokeExpr;
039: import soot.jimple.InvokeExpr;
040: import soot.jimple.MonitorStmt;
041: import soot.jimple.Stmt;
042: import soot.jimple.internal.JCastExpr;
043: import soot.toolkits.graph.UnitGraph;
044: import soot.toolkits.scalar.BackwardFlowAnalysis;
045:
046: /**
047: * An intraprocedural nullness assumption analysis that computes for each location and each value
048: * in a method if the value (before or after that location) is treated as definetely null,
049: * definetely non-null or neither. This information could be useful in deciding whether
050: * or not to insert code that accesses a potentially null object. If the original
051: * program assumes a value is non-null, then adding a use of that value
052: * will not introduce any NEW nullness errors into the program.
053: * This code may be buggy, or just plain wrong. It has not been checked.
054: *
055: * @author Richard L. Halpert
056: * Adapted from Eric Bodden's NullnessAnalysis
057: */
058: public class NullnessAssumptionAnalysis extends BackwardFlowAnalysis {
059: protected final static Object BOTTOM = new Object() {
060: public String toString() {
061: return "bottom";
062: }
063: };
064:
065: protected final static Object NULL = new Object() {
066: public String toString() {
067: return "null";
068: }
069: };
070:
071: protected final static Object NON_NULL = new Object() {
072: public String toString() {
073: return "non-null";
074: }
075: };
076:
077: // TOP IS MEANINGLESS FOR THIS ANALYSIS: YOU CAN'T ASSUME A VALUE IS NULL AND NON_NULL. BOTTOM IS USED FOR THAT CASE
078: protected final static Object TOP = new Object() {
079: public String toString() {
080: return "top";
081: }
082: };
083:
084: /**
085: * Creates a new analysis for the given graph/
086: * @param graph any unit graph
087: */
088: public NullnessAssumptionAnalysis(UnitGraph graph) {
089: super (graph);
090:
091: doAnalysis();
092: }
093:
094: /**
095: * {@inheritDoc}
096: */
097: protected void flowThrough(Object inValue, Object unit,
098: Object outValue)
099: // protected void flowThrough(Object flowin, Unit u, List fallOut, List branchOuts)
100: {
101: AnalysisInfo in = (AnalysisInfo) inValue;
102: AnalysisInfo out = new AnalysisInfo(in);
103:
104: Stmt s = (Stmt) unit;
105:
106: //in case of an if statement, we neet to compute the branch-flow;
107: //e.g. for a statement "if(x!=null) goto s" we have x==null for the fallOut and
108: //x!=null for the branchOut
109: //or for an instanceof expression
110: // if(s instanceof JIfStmt) {
111: // JIfStmt ifStmt = (JIfStmt) s;
112: // handleIfStmt(ifStmt, in, out, outBranch);
113: // }
114: //in case of a monitor statement, we know that the programmer assumes we have a non-null value
115: if (s instanceof MonitorStmt) {
116: MonitorStmt monitorStmt = (MonitorStmt) s;
117: out.put(monitorStmt.getOp(), NON_NULL);
118: }
119:
120: //if we have an array ref, set the info for this ref to TOP,
121: //cause we need to be conservative here
122: if (s.containsArrayRef()) {
123: ArrayRef arrayRef = s.getArrayRef();
124: handleArrayRef(arrayRef, out);
125: }
126: //same for field refs, but also set the receiver object to non-null, if there is one
127: if (s.containsFieldRef()) {
128: FieldRef fieldRef = s.getFieldRef();
129: handleFieldRef(fieldRef, out);
130: }
131: //same for invoke expr., also set the receiver object to non-null, if there is one
132: if (s.containsInvokeExpr()) {
133: InvokeExpr invokeExpr = s.getInvokeExpr();
134: handleInvokeExpr(invokeExpr, out);
135: }
136:
137: //allow sublasses to define certain values as always-non-null
138: for (Iterator outIter = out.entrySet().iterator(); outIter
139: .hasNext();) {
140: Entry entry = (Entry) outIter.next();
141: Value v = (Value) entry.getKey();
142: if (isAlwaysNonNull(v)) {
143: entry.setValue(NON_NULL);
144: }
145: }
146:
147: //if we have a definition (assignment) statement to a ref-like type, handle it,
148: if (s instanceof DefinitionStmt) {
149: //need to copy the current out set because we need to assign under this assumption;
150: //so this copy becomes the in-set to handleRefTypeAssignment
151: AnalysisInfo temp = new AnalysisInfo(out);
152: DefinitionStmt defStmt = (DefinitionStmt) s;
153: if (defStmt.getLeftOp().getType() instanceof RefLikeType) {
154: handleRefTypeAssignment(defStmt, temp, out);
155: }
156: }
157:
158: //save memory by only retaining information about locals
159: for (Iterator outIter = out.keySet().iterator(); outIter
160: .hasNext();) {
161: Value v = (Value) outIter.next();
162: if (!(v instanceof Local)) {
163: outIter.remove();
164: }
165: }
166: // for (Iterator outBranchIter = outBranch.keySet().iterator(); outBranchIter.hasNext();) {
167: // Value v = (Value) outBranchIter.next();
168: // if(!(v instanceof Local)) {
169: // outBranchIter.remove();
170: // }
171: // }
172:
173: // now copy the computed info to out
174: copy(out, outValue);
175: }
176:
177: /**
178: * This can be overridden by sublasses to mark a certain value
179: * as constantly non-null.
180: * @param v any value
181: * @return true if it is known that this value (e.g. a method
182: * return value) is never null
183: */
184: protected boolean isAlwaysNonNull(Value v) {
185: return false;
186: }
187:
188: private void handleArrayRef(ArrayRef arrayRef, AnalysisInfo out) {
189: Value array = arrayRef.getBase();
190: //here we know that the array must point to an object, but the array value might be anything
191: out.put(array, NON_NULL);
192: // out.put(arrayRef, TOP);
193: }
194:
195: private void handleFieldRef(FieldRef fieldRef, AnalysisInfo out) {
196: if (fieldRef instanceof InstanceFieldRef) {
197: InstanceFieldRef instanceFieldRef = (InstanceFieldRef) fieldRef;
198: //here we know that the receiver must point to an object
199: Value base = instanceFieldRef.getBase();
200: out.put(base, NON_NULL);
201: }
202: //but the referenced object might point to everything
203: // out.put(fieldRef, TOP);
204: }
205:
206: private void handleInvokeExpr(InvokeExpr invokeExpr,
207: AnalysisInfo out) {
208: if (invokeExpr instanceof InstanceInvokeExpr) {
209: InstanceInvokeExpr instanceInvokeExpr = (InstanceInvokeExpr) invokeExpr;
210: //here we know that the receiver must point to an object
211: Value base = instanceInvokeExpr.getBase();
212: out.put(base, NON_NULL);
213: }
214: //but the returned object might point to everything
215: // out.put(invokeExpr, TOP);
216: }
217:
218: private void handleRefTypeAssignment(DefinitionStmt assignStmt,
219: AnalysisInfo rhsInfo, AnalysisInfo out) {
220: Value left = assignStmt.getLeftOp();
221: Value right = assignStmt.getRightOp();
222:
223: //unbox casted value
224: if (right instanceof JCastExpr) {
225: JCastExpr castExpr = (JCastExpr) right;
226: right = castExpr.getOp();
227: }
228:
229: // An assignment invalidates any assumptions of null/non-null for lhs
230: // We COULD be more accurate by assigning those assumptions to the rhs prior to this statement
231: rhsInfo.put(right, BOTTOM);
232:
233: //assign from rhs to lhs
234: out.put(left, rhsInfo.get(right));
235: }
236:
237: /**
238: * {@inheritDoc}
239: */
240: protected void copy(Object source, Object dest) {
241: Map s = (Map) source;
242: Map d = (Map) dest;
243: d.clear();
244: d.putAll(s);
245: }
246:
247: /**
248: * {@inheritDoc}
249: */
250: protected Object entryInitialFlow() {
251: return new AnalysisInfo();
252: }
253:
254: /**
255: * {@inheritDoc}
256: */
257: protected void merge(Object in1, Object in2, Object out) {
258: AnalysisInfo left = (AnalysisInfo) in1;
259: AnalysisInfo right = (AnalysisInfo) in2;
260: AnalysisInfo res = (AnalysisInfo) out;
261:
262: Set values = new HashSet();
263: values.addAll(left.keySet());
264: values.addAll(right.keySet());
265:
266: res.clear();
267:
268: for (Iterator keyIter = values.iterator(); keyIter.hasNext();) {
269: Value v = (Value) keyIter.next();
270: Set<Object> leftAndRight = new HashSet<Object>();
271: leftAndRight.add(left.get(v));
272: leftAndRight.add(right.get(v));
273:
274: Object result;
275: // This needs to be corrected for assumption *** TODO
276: //TOP stays TOP
277: if (leftAndRight.contains(BOTTOM)) // if on either side we know nothing... then together we know nothing for sure
278: {
279: result = BOTTOM;
280: } else if (leftAndRight.contains(NON_NULL)) {
281: if (leftAndRight.contains(NULL)) {
282: //NULL and NON_NULL merges to BOTTOM
283: result = BOTTOM;
284: } else {
285: //NON_NULL and NON_NULL stays NON_NULL
286: result = NON_NULL;
287: }
288: } else if (leftAndRight.contains(NULL)) {
289: //NULL and NULL stays NULL
290: result = NULL;
291: } else {
292: //only BOTTOM remains
293: result = BOTTOM;
294: }
295:
296: res.put(v, result);
297: }
298: }
299:
300: /**
301: * {@inheritDoc}
302: */
303: protected Object newInitialFlow() {
304: return new AnalysisInfo();
305: }
306:
307: /**
308: * Returns <code>true</code> if the analysis could determine that i is always treated as null
309: * after and including the statement s.
310: * @param s a statement of the respective body
311: * @param i a local or constant of that body
312: * @return true if i is always null right before this statement
313: */
314: public boolean isAssumedNullBefore(Unit s, Immediate i) {
315: AnalysisInfo ai = (AnalysisInfo) getFlowBefore(s);
316: return ai.get(i) == NULL;
317: }
318:
319: /**
320: * Returns <code>true</code> if the analysis could determine that i is always treated as non-null
321: * after and including the statement s.
322: * @param s a statement of the respective body
323: * @param i a local of that body
324: * @return true if i is always non-null right before this statement
325: */
326: public boolean isAssumedNonNullBefore(Unit s, Immediate i) {
327: AnalysisInfo ai = (AnalysisInfo) getFlowBefore(s);
328: return ai.get(i) == NON_NULL;
329: }
330:
331: /**
332: * The analysis info is a simple mapping of type {@link Value} to
333: * any of the constants BOTTOM, NON_NULL, NULL or TOP.
334: * This class returns BOTTOM by default.
335: *
336: * @author Eric Bodden
337: */
338: protected static class AnalysisInfo extends HashMap {
339:
340: public AnalysisInfo() {
341: super ();
342: }
343:
344: public AnalysisInfo(Map m) {
345: super (m);
346: }
347:
348: public Object get(Object key) {
349: Object object = super.get(key);
350: if (object == null) {
351: return BOTTOM;
352: }
353: return object;
354: }
355:
356: }
357:
358: }
|