edu.umd.cs.findbugs.ba
Class TypeAnalysis

java.lang.Object
  extended by edu.umd.cs.findbugs.ba.AbstractDataflowAnalysis<Fact>
      extended by edu.umd.cs.findbugs.ba.ForwardDataflowAnalysis<FrameType>
          extended by edu.umd.cs.findbugs.ba.FrameDataflowAnalysis<org.apache.bcel.generic.Type,TypeFrame>
              extended by edu.umd.cs.findbugs.ba.TypeAnalysis
All Implemented Interfaces:
DataflowAnalysis<TypeFrame>, EdgeTypes

public class TypeAnalysis
extends FrameDataflowAnalysis<org.apache.bcel.generic.Type,TypeFrame>
implements EdgeTypes

A forward dataflow analysis to determine the types of all values in the Java stack frame at all points in a Java method. The values include local variables and values on the Java operand stack.

As a side effect, the analysis computes the exception set throwable on each exception edge in the CFG. This information can be used to prune infeasible exception edges, and mark exception edges which propagate only implicit exceptions.

Author:
David Hovemeyer
See Also:
Dataflow, DataflowAnalysis, TypeFrame

Nested Class Summary
private  class TypeAnalysis.CachedExceptionSet
          Repository of information about thrown exceptions computed for a basic block and its outgoing exception edges.
 
Field Summary
private static boolean ACCURATE_EXCEPTIONS
          Compute what kinds of exceptions can propagate on each exception edge.
private  CFG cfg
           
private static boolean DEBUG
           
private  ExceptionSetFactory exceptionSetFactory
           
private  RepositoryLookupFailureCallback lookupFailureCallback
           
private  org.apache.bcel.generic.MethodGen methodGen
           
private  java.util.Map<BasicBlock,TypeAnalysis.CachedExceptionSet> thrownExceptionSetMap
           
private  TypeMerger typeMerger
           
private  TypeFrameModelingVisitor visitor
           
 
Fields inherited from interface edu.umd.cs.findbugs.ba.EdgeTypes
BACKEDGE_SOURCE_EDGE, BACKEDGE_TARGET_EDGE, CHECKED_EXCEPTIONS_FLAG, EXIT_EDGE, EXPLICIT_EXCEPTIONS_FLAG, FALL_THROUGH_EDGE, GOTO_EDGE, HANDLED_EXCEPTION_EDGE, IFCMP_EDGE, JSR_EDGE, RET_EDGE, RETURN_EDGE, START_EDGE, SWITCH_DEFAULT_EDGE, SWITCH_EDGE, UNHANDLED_EXCEPTION_EDGE, UNKNOWN_EDGE
 
Constructor Summary
TypeAnalysis(org.apache.bcel.generic.MethodGen methodGen, CFG cfg, DepthFirstSearch dfs, RepositoryLookupFailureCallback lookupFailureCallback, ExceptionSetFactory exceptionSetFactory)
          Constructor which uses StandardTypeMerger.
TypeAnalysis(org.apache.bcel.generic.MethodGen methodGen, CFG cfg, DepthFirstSearch dfs, TypeMerger typeMerger, RepositoryLookupFailureCallback lookupFailureCallback, ExceptionSetFactory exceptionSetFactory)
          Constructor.
TypeAnalysis(org.apache.bcel.generic.MethodGen methodGen, CFG cfg, DepthFirstSearch dfs, TypeMerger typeMerger, TypeFrameModelingVisitor visitor, RepositoryLookupFailureCallback lookupFailureCallback, ExceptionSetFactory exceptionSetFactory)
          Constructor.
 
Method Summary
private  TypeAnalysis.CachedExceptionSet computeBlockExceptionSet(BasicBlock basicBlock, TypeFrame result)
          Compute the set of exceptions that can be thrown from the given basic block.
private  ExceptionSet computeEdgeExceptionSet(Edge edge, ExceptionSet thrownExceptionSet)
          Based on the set of exceptions that can be thrown from the source basic block, compute the set of exceptions that can propagate along given exception edge.
private  ExceptionSet computeThrownExceptionTypes(BasicBlock basicBlock)
          Compute the set of exception types that can be thrown by given basic block.
 void copy(TypeFrame source, TypeFrame dest)
          Copy dataflow facts.
 TypeFrame createFact()
          Create empty (uninitialized) dataflow facts for one program point.
 void endTransfer(BasicBlock basicBlock, org.apache.bcel.generic.InstructionHandle end, java.lang.Object result)
          Subclasses may override this.
private  TypeAnalysis.CachedExceptionSet getCachedExceptionSet(BasicBlock basicBlock)
          Get the cached set of exceptions that can be thrown from given basic block.
 ExceptionSet getEdgeExceptionSet(Edge edge)
          Get the set of exceptions that can be thrown on given edge.
 void initEntryFact(TypeFrame result)
          Initialize the "entry" fact for the graph.
 void initResultFact(TypeFrame result)
          Initialize result fact for block.
 boolean isFactValid(TypeFrame fact)
          Determine whether the given fact is valid (neither top nor bottom).
static void main(java.lang.String[] argv)
           
 void makeFactTop(TypeFrame fact)
          Make given fact the top value.
 void meetInto(TypeFrame fact, Edge edge, TypeFrame result)
          Meet a dataflow fact associated with an incoming edge into another fact.
protected  org.apache.bcel.generic.Type mergeValues(TypeFrame frame, int slot, org.apache.bcel.generic.Type a, org.apache.bcel.generic.Type b)
          Merge two values in a particular slot of a Frame.
 boolean same(TypeFrame fact1, TypeFrame fact2)
          Are given dataflow facts the same?
 void transferInstruction(org.apache.bcel.generic.InstructionHandle handle, BasicBlock basicBlock, TypeFrame fact)
          Transfer function for a single instruction.
 
Methods inherited from class edu.umd.cs.findbugs.ba.FrameDataflowAnalysis
mergeInto, modifyFrame
 
Methods inherited from class edu.umd.cs.findbugs.ba.ForwardDataflowAnalysis
getBlockOrder, getDepthFirstSearch, isForwards
 
Methods inherited from class edu.umd.cs.findbugs.ba.AbstractDataflowAnalysis
factToString, getFactAfterLocation, getFactAtLocation, getResultFact, getStartFact, resultFactIterator, startTransfer, transfer
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

DEBUG

private static final boolean DEBUG

ACCURATE_EXCEPTIONS

private static final boolean ACCURATE_EXCEPTIONS
Compute what kinds of exceptions can propagate on each exception edge.


methodGen

private org.apache.bcel.generic.MethodGen methodGen

cfg

private CFG cfg

typeMerger

private TypeMerger typeMerger

visitor

private TypeFrameModelingVisitor visitor

thrownExceptionSetMap

private java.util.Map<BasicBlock,TypeAnalysis.CachedExceptionSet> thrownExceptionSetMap

lookupFailureCallback

private RepositoryLookupFailureCallback lookupFailureCallback

exceptionSetFactory

private ExceptionSetFactory exceptionSetFactory
Constructor Detail

TypeAnalysis

public TypeAnalysis(org.apache.bcel.generic.MethodGen methodGen,
                    CFG cfg,
                    DepthFirstSearch dfs,
                    TypeMerger typeMerger,
                    TypeFrameModelingVisitor visitor,
                    RepositoryLookupFailureCallback lookupFailureCallback,
                    ExceptionSetFactory exceptionSetFactory)
Constructor.

Parameters:
methodGen - the MethodGen whose CFG we'll be analyzing
cfg - the control flow graph
dfs - DepthFirstSearch of the method
typeMerger - object to merge types
visitor - a TypeFrameModelingVisitor to use to model the effect of instructions
lookupFailureCallback - lookup failure callback
exceptionSetFactory - factory for creating ExceptionSet objects

TypeAnalysis

public TypeAnalysis(org.apache.bcel.generic.MethodGen methodGen,
                    CFG cfg,
                    DepthFirstSearch dfs,
                    TypeMerger typeMerger,
                    RepositoryLookupFailureCallback lookupFailureCallback,
                    ExceptionSetFactory exceptionSetFactory)
Constructor.

Parameters:
methodGen - the MethodGen whose CFG we'll be analyzing
cfg - the control flow graph
dfs - DepthFirstSearch of the method
typeMerger - object to merge types
lookupFailureCallback - lookup failure callback
exceptionSetFactory - factory for creating ExceptionSet objects

TypeAnalysis

public TypeAnalysis(org.apache.bcel.generic.MethodGen methodGen,
                    CFG cfg,
                    DepthFirstSearch dfs,
                    RepositoryLookupFailureCallback lookupFailureCallback,
                    ExceptionSetFactory exceptionSetFactory)
Constructor which uses StandardTypeMerger.

Parameters:
methodGen - the MethodGen whose CFG we'll be analyzing
cfg - the control flow graph
dfs - DepthFirstSearch of the method
lookupFailureCallback - callback for Repository lookup failures
exceptionSetFactory - factory for creating ExceptionSet objects
Method Detail

getEdgeExceptionSet

public ExceptionSet getEdgeExceptionSet(Edge edge)
Get the set of exceptions that can be thrown on given edge. This should only be called after the analysis completes.

Parameters:
edge - the Edge
Returns:
the ExceptionSet

createFact

public TypeFrame createFact()
Description copied from interface: DataflowAnalysis
Create empty (uninitialized) dataflow facts for one program point. A valid value will be copied into it before it is used.

Specified by:
createFact in interface DataflowAnalysis<TypeFrame>

initEntryFact

public void initEntryFact(TypeFrame result)
Description copied from interface: DataflowAnalysis
Initialize the "entry" fact for the graph.

Specified by:
initEntryFact in interface DataflowAnalysis<TypeFrame>

copy

public void copy(TypeFrame source,
                 TypeFrame dest)
Description copied from interface: DataflowAnalysis
Copy dataflow facts.

Specified by:
copy in interface DataflowAnalysis<TypeFrame>
Overrides:
copy in class FrameDataflowAnalysis<org.apache.bcel.generic.Type,TypeFrame>

initResultFact

public void initResultFact(TypeFrame result)
Description copied from interface: DataflowAnalysis
Initialize result fact for block. The start facts for a block are initialized as the meet of the "logical" predecessor's result facts. Note that a "logical predecessor" is actually a CFG successor if the analysis is backwards.

Specified by:
initResultFact in interface DataflowAnalysis<TypeFrame>
Overrides:
initResultFact in class FrameDataflowAnalysis<org.apache.bcel.generic.Type,TypeFrame>

makeFactTop

public void makeFactTop(TypeFrame fact)
Description copied from interface: DataflowAnalysis
Make given fact the top value.

Specified by:
makeFactTop in interface DataflowAnalysis<TypeFrame>
Overrides:
makeFactTop in class FrameDataflowAnalysis<org.apache.bcel.generic.Type,TypeFrame>

isFactValid

public boolean isFactValid(TypeFrame fact)
Description copied from class: AbstractDataflowAnalysis
Determine whether the given fact is valid (neither top nor bottom).

Overrides:
isFactValid in class FrameDataflowAnalysis<org.apache.bcel.generic.Type,TypeFrame>

same

public boolean same(TypeFrame fact1,
                    TypeFrame fact2)
Description copied from interface: DataflowAnalysis
Are given dataflow facts the same?

Specified by:
same in interface DataflowAnalysis<TypeFrame>
Overrides:
same in class FrameDataflowAnalysis<org.apache.bcel.generic.Type,TypeFrame>

transferInstruction

public void transferInstruction(org.apache.bcel.generic.InstructionHandle handle,
                                BasicBlock basicBlock,
                                TypeFrame fact)
                         throws DataflowAnalysisException
Description copied from class: AbstractDataflowAnalysis
Transfer function for a single instruction.

Specified by:
transferInstruction in class AbstractDataflowAnalysis<TypeFrame>
Parameters:
handle - the instruction
basicBlock - the BasicBlock containing the instruction; needed to disambiguate instructions in inlined JSR subroutines
fact - which should be modified based on the instruction
Throws:
DataflowAnalysisException

endTransfer

public void endTransfer(BasicBlock basicBlock,
                        org.apache.bcel.generic.InstructionHandle end,
                        java.lang.Object result)
                 throws DataflowAnalysisException
Description copied from class: AbstractDataflowAnalysis
Subclasses may override this. Due to a bug in the 2.2 version of the generics-enabled javac, it is not possible to directly override the transfer() method. This method will be called just before exiting transfer().

Overrides:
endTransfer in class AbstractDataflowAnalysis<TypeFrame>
Parameters:
basicBlock - the basic block
end - last instruction analyzed (null if entire block was analyzed)
result - the result fact for the block
Throws:
DataflowAnalysisException

meetInto

public void meetInto(TypeFrame fact,
                     Edge edge,
                     TypeFrame result)
              throws DataflowAnalysisException
Description copied from interface: DataflowAnalysis
Meet a dataflow fact associated with an incoming edge into another fact. This is used to determine the start fact for a basic block.

Specified by:
meetInto in interface DataflowAnalysis<TypeFrame>
Parameters:
fact - the predecessor fact (incoming edge)
edge - the edge from the predecessor
result - the result fact
Throws:
DataflowAnalysisException

mergeValues

protected org.apache.bcel.generic.Type mergeValues(TypeFrame frame,
                                                   int slot,
                                                   org.apache.bcel.generic.Type a,
                                                   org.apache.bcel.generic.Type b)
                                            throws DataflowAnalysisException
Description copied from class: FrameDataflowAnalysis
Merge two values in a particular slot of a Frame.

Specified by:
mergeValues in class FrameDataflowAnalysis<org.apache.bcel.generic.Type,TypeFrame>
Parameters:
frame - the Frame
slot - the slot of the Frame
a - a value
b - another value
Returns:
the merged value
Throws:
DataflowAnalysisException

getCachedExceptionSet

private TypeAnalysis.CachedExceptionSet getCachedExceptionSet(BasicBlock basicBlock)
Get the cached set of exceptions that can be thrown from given basic block. If this information hasn't been computed yet, then an empty exception set is returned.

Parameters:
basicBlock - the block to get the cached exception set for
Returns:
the CachedExceptionSet for the block

computeBlockExceptionSet

private TypeAnalysis.CachedExceptionSet computeBlockExceptionSet(BasicBlock basicBlock,
                                                                 TypeFrame result)
                                                          throws DataflowAnalysisException
Compute the set of exceptions that can be thrown from the given basic block. This should only be called if the existing cached exception set is out of date.

Parameters:
basicBlock - the basic block
result - the result fact for the block; this is used to determine whether or not the cached exception set is up to date
Returns:
the cached exception set for the block
Throws:
DataflowAnalysisException

computeEdgeExceptionSet

private ExceptionSet computeEdgeExceptionSet(Edge edge,
                                             ExceptionSet thrownExceptionSet)
Based on the set of exceptions that can be thrown from the source basic block, compute the set of exceptions that can propagate along given exception edge. This method should be called for each outgoing exception edge in sequence, so the caught exceptions can be removed from the thrown exception set as needed.

Parameters:
edge - the exception edge
thrownExceptionSet - current set of exceptions that can be thrown, taking earlier (higher priority) exception edges into account
Returns:
the set of exceptions that can propagate along this edge

computeThrownExceptionTypes

private ExceptionSet computeThrownExceptionTypes(BasicBlock basicBlock)
                                          throws java.lang.ClassNotFoundException,
                                                 DataflowAnalysisException
Compute the set of exception types that can be thrown by given basic block.

Parameters:
basicBlock - the basic block
Returns:
the set of exceptions that can be thrown by the block
Throws:
java.lang.ClassNotFoundException
DataflowAnalysisException

main

public static void main(java.lang.String[] argv)
                 throws java.lang.Exception
Throws:
java.lang.Exception