001: /*
002: * FindBugs - Find Bugs in Java programs
003: * Copyright (C) 2006-2007 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 java.util.HashMap;
023:
024: import org.apache.bcel.generic.InstructionHandle;
025:
026: import edu.umd.cs.findbugs.ba.BasicAbstractDataflowAnalysis;
027: import edu.umd.cs.findbugs.ba.BasicBlock;
028: import edu.umd.cs.findbugs.ba.BlockOrder;
029: import edu.umd.cs.findbugs.ba.CFG;
030: import edu.umd.cs.findbugs.ba.DataflowAnalysisException;
031: import edu.umd.cs.findbugs.ba.DepthFirstSearch;
032: import edu.umd.cs.findbugs.ba.Edge;
033: import edu.umd.cs.findbugs.ba.ReverseDFSOrder;
034: import edu.umd.cs.findbugs.ba.ReverseDepthFirstSearch;
035:
036: /**
037: * A dataflow analysis to determine, at each location in a method's
038: * CFG, whether or not it is possible to return normally
039: * at that location.
040: *
041: * @author David Hovemeyer
042: */
043: public class ReturnPathTypeAnalysis extends
044: BasicAbstractDataflowAnalysis<ReturnPathType> {
045: private CFG cfg;
046: private DepthFirstSearch dfs;
047: private ReverseDepthFirstSearch rdfs;
048:
049: /**
050: * Constructor.
051: *
052: * @param cfg the method's CFG
053: * @param rdfs a ReverseDepthFirstSearch on the method's CFG
054: * @param dfs a DepthFirstSearch on the method's CFG
055: */
056: public ReturnPathTypeAnalysis(CFG cfg,
057: ReverseDepthFirstSearch rdfs, DepthFirstSearch dfs) {
058: this .cfg = cfg;
059: this .dfs = dfs;
060: this .rdfs = rdfs;
061: }
062:
063: /* (non-Javadoc)
064: * @see edu.umd.cs.findbugs.ba.DataflowAnalysis#copy(java.lang.Object, java.lang.Object)
065: */
066: public void copy(ReturnPathType source, ReturnPathType dest) {
067: dest.copyFrom(source);
068: }
069:
070: /* (non-Javadoc)
071: * @see edu.umd.cs.findbugs.ba.DataflowAnalysis#createFact()
072: */
073: public ReturnPathType createFact() {
074: ReturnPathType fact = new ReturnPathType();
075: fact.setTop();
076: return fact;
077: }
078:
079: /* (non-Javadoc)
080: * @see edu.umd.cs.findbugs.ba.DataflowAnalysis#edgeTransfer(edu.umd.cs.findbugs.ba.Edge, java.lang.Object)
081: */
082: @Override
083: public void edgeTransfer(Edge edge, ReturnPathType fact) {
084: // The edges leading into the exit block create the "seed" values
085: // for the analysis. The exception edges create values indicating
086: // that a normal (non-exception) return is not possible,
087: // while the non-exception edges create values indicating that
088: // a normal return is possible.
089: if (edge.getTarget() == cfg.getExit()) {
090: fact.setCanReturnNormally(!edge.isExceptionEdge());
091: }
092: }
093:
094: /* (non-Javadoc)
095: * @see edu.umd.cs.findbugs.ba.DataflowAnalysis#finishIteration()
096: */
097: @Override
098: public void finishIteration() {
099: // nothing to do
100: }
101:
102: /* (non-Javadoc)
103: * @see edu.umd.cs.findbugs.ba.DataflowAnalysis#getBlockOrder(edu.umd.cs.findbugs.ba.CFG)
104: */
105: public BlockOrder getBlockOrder(CFG cfg) {
106: return new ReverseDFSOrder(cfg, rdfs, dfs);
107: }
108:
109: /* (non-Javadoc)
110: * @see edu.umd.cs.findbugs.ba.DataflowAnalysis#getLastUpdateTimestamp(java.lang.Object)
111: */
112: @Override
113: public int getLastUpdateTimestamp(ReturnPathType fact) {
114: return 0;
115: }
116:
117: /**
118: * Look up a dataflow value in given map,
119: * creating a new (top) fact if no fact currently exists.
120: *
121: * @param map the map
122: * @param block BasicBlock used as key in map
123: * @return the dataflow fact for the block
124: */
125: private ReturnPathType getOrCreateFact(
126: HashMap<BasicBlock, ReturnPathType> map, BasicBlock block) {
127: ReturnPathType returnPathType = map.get(block);
128: if (returnPathType == null) {
129: returnPathType = createFact();
130: map.put(block, returnPathType);
131: }
132: return returnPathType;
133: }
134:
135: /* (non-Javadoc)
136: * @see edu.umd.cs.findbugs.ba.DataflowAnalysis#initEntryFact(java.lang.Object)
137: */
138: public void initEntryFact(ReturnPathType result)
139: throws DataflowAnalysisException {
140: // By default, we assume that paths reaching the exit block
141: // can return normally. If we traverse exception edges which
142: // lead to the exit block, then we'll mark those as "can't return
143: // normally" (see edgeTransfer() method).
144:
145: result.setCanReturnNormally(true);
146: }
147:
148: /* (non-Javadoc)
149: * @see edu.umd.cs.findbugs.ba.DataflowAnalysis#isForwards()
150: */
151: public boolean isForwards() {
152: return false;
153: }
154:
155: /* (non-Javadoc)
156: * @see edu.umd.cs.findbugs.ba.DataflowAnalysis#isTop(java.lang.Object)
157: */
158: public boolean isTop(ReturnPathType fact) {
159: return fact.isTop();
160: }
161:
162: /* (non-Javadoc)
163: * @see edu.umd.cs.findbugs.ba.DataflowAnalysis#makeFactTop(java.lang.Object)
164: */
165: public void makeFactTop(ReturnPathType fact) {
166: fact.setTop();
167: }
168:
169: /* (non-Javadoc)
170: * @see edu.umd.cs.findbugs.ba.DataflowAnalysis#meetInto(java.lang.Object, edu.umd.cs.findbugs.ba.Edge, java.lang.Object)
171: */
172: public void meetInto(ReturnPathType fact, Edge edge,
173: ReturnPathType result) throws DataflowAnalysisException {
174: result.mergeWith(fact);
175: }
176:
177: /* (non-Javadoc)
178: * @see edu.umd.cs.findbugs.ba.DataflowAnalysis#same(java.lang.Object, java.lang.Object)
179: */
180: public boolean same(ReturnPathType fact1, ReturnPathType fact2) {
181: return fact1.sameAs(fact2);
182: }
183:
184: /* (non-Javadoc)
185: * @see edu.umd.cs.findbugs.ba.DataflowAnalysis#setLastUpdateTimestamp(java.lang.Object, int)
186: */
187: @Override
188: public void setLastUpdateTimestamp(ReturnPathType fact,
189: int timestamp) {
190: // ignore
191: }
192:
193: /* (non-Javadoc)
194: * @see edu.umd.cs.findbugs.ba.DataflowAnalysis#startIteration()
195: */
196: @Override
197: public void startIteration() {
198: // nothing to do
199: }
200:
201: /* (non-Javadoc)
202: * @see edu.umd.cs.findbugs.ba.DataflowAnalysis#transfer(edu.umd.cs.findbugs.ba.BasicBlock, org.apache.bcel.generic.InstructionHandle, java.lang.Object, java.lang.Object)
203: */
204: public void transfer(BasicBlock basicBlock, InstructionHandle end,
205: ReturnPathType start, ReturnPathType result)
206: throws DataflowAnalysisException {
207: // just copy the start fact
208: result.copyFrom(start);
209: }
210:
211: }
|