0001: /*
0002: * Bytecode Analysis Framework
0003: * Copyright (C) 2003-2005 University of Maryland
0004: *
0005: * This library is free software; you can redistribute it and/or
0006: * modify it under the terms of the GNU Lesser General Public
0007: * License as published by the Free Software Foundation; either
0008: * version 2.1 of the License, or (at your option) any later version.
0009: *
0010: * This library is distributed in the hope that it will be useful,
0011: * but WITHOUT ANY WARRANTY; without even the implied warranty of
0012: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
0013: * Lesser General Public License for more details.
0014: *
0015: * You should have received a copy of the GNU Lesser General Public
0016: * License along with this library; if not, write to the Free Software
0017: * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
0018: */
0019:
0020: package edu.umd.cs.findbugs.ba.type;
0021:
0022: import java.util.BitSet;
0023: import java.util.HashMap;
0024: import java.util.Iterator;
0025: import java.util.Map;
0026:
0027: import org.apache.bcel.Constants;
0028: import org.apache.bcel.classfile.Attribute;
0029: import org.apache.bcel.classfile.Code;
0030: import org.apache.bcel.classfile.LocalVariable;
0031: import org.apache.bcel.classfile.LocalVariableTypeTable;
0032: import org.apache.bcel.classfile.Method;
0033: import org.apache.bcel.generic.ATHROW;
0034: import org.apache.bcel.generic.ArrayType;
0035: import org.apache.bcel.generic.CodeExceptionGen;
0036: import org.apache.bcel.generic.ConstantPoolGen;
0037: import org.apache.bcel.generic.ExceptionThrower;
0038: import org.apache.bcel.generic.Instruction;
0039: import org.apache.bcel.generic.InstructionHandle;
0040: import org.apache.bcel.generic.InvokeInstruction;
0041: import org.apache.bcel.generic.MethodGen;
0042: import org.apache.bcel.generic.ObjectType;
0043: import org.apache.bcel.generic.ReferenceType;
0044: import org.apache.bcel.generic.Type;
0045:
0046: import edu.umd.cs.findbugs.Analyze;
0047: import edu.umd.cs.findbugs.SystemProperties;
0048: import edu.umd.cs.findbugs.annotations.CheckForNull;
0049: import edu.umd.cs.findbugs.ba.AnalysisContext;
0050: import edu.umd.cs.findbugs.ba.AnalysisFeatures;
0051: import edu.umd.cs.findbugs.ba.BasicBlock;
0052: import edu.umd.cs.findbugs.ba.CFG;
0053: import edu.umd.cs.findbugs.ba.CFGBuilderException;
0054: import edu.umd.cs.findbugs.ba.ClassContext;
0055: import edu.umd.cs.findbugs.ba.Dataflow;
0056: import edu.umd.cs.findbugs.ba.DataflowAnalysis;
0057: import edu.umd.cs.findbugs.ba.DataflowAnalysisException;
0058: import edu.umd.cs.findbugs.ba.DataflowTestDriver;
0059: import edu.umd.cs.findbugs.ba.DepthFirstSearch;
0060: import edu.umd.cs.findbugs.ba.Edge;
0061: import edu.umd.cs.findbugs.ba.EdgeTypes;
0062: import edu.umd.cs.findbugs.ba.FrameDataflowAnalysis;
0063: import edu.umd.cs.findbugs.ba.Hierarchy;
0064: import edu.umd.cs.findbugs.ba.Hierarchy2;
0065: import edu.umd.cs.findbugs.ba.Location;
0066: import edu.umd.cs.findbugs.ba.MissingClassException;
0067: import edu.umd.cs.findbugs.ba.ObjectTypeFactory;
0068: import edu.umd.cs.findbugs.ba.RepositoryLookupFailureCallback;
0069: import edu.umd.cs.findbugs.ba.SignatureConverter;
0070: import edu.umd.cs.findbugs.ba.generic.GenericObjectType;
0071: import edu.umd.cs.findbugs.ba.generic.GenericSignatureParser;
0072: import edu.umd.cs.findbugs.ba.generic.GenericUtilities;
0073: import edu.umd.cs.findbugs.ba.vna.ValueNumber;
0074: import edu.umd.cs.findbugs.ba.vna.ValueNumberDataflow;
0075: import edu.umd.cs.findbugs.ba.vna.ValueNumberFrame;
0076:
0077: /**
0078: * A forward dataflow analysis to determine the types of all values
0079: * in the Java stack frame at all points in a Java method.
0080: * The values include local variables and values on the Java operand stack.
0081: * <p/>
0082: * <p> As a side effect, the analysis computes the exception
0083: * set throwable on each exception edge in the CFG.
0084: * This information can be used to prune infeasible exception
0085: * edges, and mark exception edges which propagate only
0086: * implicit exceptions.
0087: *
0088: * @author David Hovemeyer
0089: * @see Dataflow
0090: * @see DataflowAnalysis
0091: * @see TypeFrame
0092: */
0093: public class TypeAnalysis extends
0094: FrameDataflowAnalysis<Type, TypeFrame> implements EdgeTypes {
0095:
0096: public static final boolean DEBUG = SystemProperties
0097: .getBoolean("ta.debug");
0098:
0099: /**
0100: * Force computation of accurate exceptions.
0101: */
0102: public static final boolean FORCE_ACCURATE_EXCEPTIONS = SystemProperties
0103: .getBoolean("ta.accurateExceptions");
0104:
0105: /**
0106: * Repository of information about thrown exceptions computed for
0107: * a basic block and its outgoing exception edges.
0108: * It contains a result TypeFrame, which is used to detect
0109: * when the exception information needs to be recomputed
0110: * for the block.
0111: */
0112: private class CachedExceptionSet {
0113: private TypeFrame result;
0114: private ExceptionSet exceptionSet;
0115: private Map<Edge, ExceptionSet> edgeExceptionMap;
0116:
0117: public CachedExceptionSet(TypeFrame result,
0118: ExceptionSet exceptionSet) {
0119: this .result = result;
0120: this .exceptionSet = exceptionSet;
0121: this .edgeExceptionMap = new HashMap<Edge, ExceptionSet>();
0122: }
0123:
0124: public boolean isUpToDate(TypeFrame result) {
0125: return this .result.equals(result);
0126: }
0127:
0128: public ExceptionSet getExceptionSet() {
0129: return exceptionSet;
0130: }
0131:
0132: public void setEdgeExceptionSet(Edge edge,
0133: ExceptionSet exceptionSet) {
0134: edgeExceptionMap.put(edge, exceptionSet);
0135: }
0136:
0137: public ExceptionSet getEdgeExceptionSet(Edge edge) {
0138: ExceptionSet edgeExceptionSet = edgeExceptionMap.get(edge);
0139: if (edgeExceptionSet == null) {
0140: edgeExceptionSet = exceptionSetFactory
0141: .createExceptionSet();
0142: edgeExceptionMap.put(edge, edgeExceptionSet);
0143: }
0144: return edgeExceptionSet;
0145: }
0146: }
0147:
0148: /**
0149: * Cached information about an instanceof check.
0150: */
0151: static class InstanceOfCheck {
0152: final ValueNumber valueNumber;
0153: final Type type;
0154:
0155: InstanceOfCheck(ValueNumber valueNumber, Type type) {
0156: this .valueNumber = valueNumber;
0157: this .type = type;
0158: }
0159:
0160: /**
0161: * @return Returns the valueNumber.
0162: */
0163: public ValueNumber getValueNumber() {
0164: return valueNumber;
0165: }
0166:
0167: /**
0168: * @return Returns the type.
0169: */
0170: public Type getType() {
0171: return type;
0172: }
0173: }
0174:
0175: protected MethodGen methodGen;
0176: private final Method method;
0177: protected CFG cfg;
0178: private TypeMerger typeMerger;
0179: private TypeFrameModelingVisitor visitor;
0180: private LocalVariableTypeTable typeTable;
0181: private BitSet startOfLocalTypedVariables = new BitSet();
0182: private Map<BasicBlock, CachedExceptionSet> thrownExceptionSetMap;
0183: private RepositoryLookupFailureCallback lookupFailureCallback;
0184: private ExceptionSetFactory exceptionSetFactory;
0185: private ValueNumberDataflow valueNumberDataflow;
0186: private Map<BasicBlock, InstanceOfCheck> instanceOfCheckMap;
0187:
0188: /**
0189: * Constructor.
0190: * @param method TODO
0191: * @param methodGen the MethodGen whose CFG we'll be analyzing
0192: * @param cfg the control flow graph
0193: * @param dfs DepthFirstSearch of the method
0194: * @param typeMerger object to merge types
0195: * @param visitor a TypeFrameModelingVisitor to use to model the effect
0196: * of instructions
0197: * @param lookupFailureCallback lookup failure callback
0198: * @param exceptionSetFactory factory for creating ExceptionSet objects
0199: */
0200: public TypeAnalysis(Method method, MethodGen methodGen, CFG cfg,
0201: DepthFirstSearch dfs, TypeMerger typeMerger,
0202: TypeFrameModelingVisitor visitor,
0203: RepositoryLookupFailureCallback lookupFailureCallback,
0204: ExceptionSetFactory exceptionSetFactory) {
0205: super (dfs);
0206: this .method = method;
0207: Code code = method.getCode();
0208: if (code == null)
0209: throw new IllegalArgumentException(method.getName()
0210: + " has no code");
0211: for (Attribute a : code.getAttributes()) {
0212: if (a instanceof LocalVariableTypeTable) {
0213: typeTable = (LocalVariableTypeTable) a;
0214: for (LocalVariable v : typeTable
0215: .getLocalVariableTable()) {
0216: int startPC = v.getStartPC();
0217: if (startPC >= 0)
0218: startOfLocalTypedVariables.set(startPC);
0219: }
0220: }
0221: }
0222: this .methodGen = methodGen;
0223: this .cfg = cfg;
0224: this .typeMerger = typeMerger;
0225: this .visitor = visitor;
0226: this .thrownExceptionSetMap = new HashMap<BasicBlock, CachedExceptionSet>();
0227: this .lookupFailureCallback = lookupFailureCallback;
0228: this .exceptionSetFactory = exceptionSetFactory;
0229: this .instanceOfCheckMap = new HashMap<BasicBlock, InstanceOfCheck>();
0230: if (DEBUG) {
0231: System.out.println("\n\nAnalyzing " + methodGen);
0232: }
0233: }
0234:
0235: /**
0236: * Constructor.
0237: * @param method TODO
0238: * @param methodGen the MethodGen whose CFG we'll be analyzing
0239: * @param cfg the control flow graph
0240: * @param dfs DepthFirstSearch of the method
0241: * @param typeMerger object to merge types
0242: * @param lookupFailureCallback lookup failure callback
0243: * @param exceptionSetFactory factory for creating ExceptionSet objects
0244: */
0245: public TypeAnalysis(Method method, MethodGen methodGen, CFG cfg,
0246: DepthFirstSearch dfs, TypeMerger typeMerger,
0247: RepositoryLookupFailureCallback lookupFailureCallback,
0248: ExceptionSetFactory exceptionSetFactory) {
0249: this (method, methodGen, cfg, dfs, typeMerger,
0250: new TypeFrameModelingVisitor(methodGen
0251: .getConstantPool()), lookupFailureCallback,
0252: exceptionSetFactory);
0253: }
0254:
0255: /**
0256: * Constructor which uses StandardTypeMerger.
0257: * @param method TODO
0258: * @param methodGen the MethodGen whose CFG we'll be analyzing
0259: * @param cfg the control flow graph
0260: * @param dfs DepthFirstSearch of the method
0261: * @param lookupFailureCallback callback for Repository lookup failures
0262: * @param exceptionSetFactory factory for creating ExceptionSet objects
0263: */
0264: public TypeAnalysis(Method method, MethodGen methodGen, CFG cfg,
0265: DepthFirstSearch dfs,
0266: RepositoryLookupFailureCallback lookupFailureCallback,
0267: ExceptionSetFactory exceptionSetFactory) {
0268: this (method, methodGen, cfg, dfs, new StandardTypeMerger(
0269: lookupFailureCallback, exceptionSetFactory),
0270: lookupFailureCallback, exceptionSetFactory);
0271: }
0272:
0273: /**
0274: * Set the ValueNumberDataflow for the method being analyzed.
0275: * This is optional; if set, it will be used to make instanceof
0276: * instructions more precise.
0277: *
0278: * @param valueNumberDataflow the ValueNumberDataflow
0279: */
0280: public void setValueNumberDataflow(
0281: ValueNumberDataflow valueNumberDataflow) {
0282: this .valueNumberDataflow = valueNumberDataflow;
0283: this .visitor.setValueNumberDataflow(valueNumberDataflow);
0284: }
0285:
0286: /**
0287: * Set the FieldStoreTypeDatabase.
0288: * This can be used to get more accurate types for values loaded
0289: * from fields.
0290: *
0291: * @param database the FieldStoreTypeDatabase
0292: */
0293: public void setFieldStoreTypeDatabase(
0294: FieldStoreTypeDatabase database) {
0295: visitor.setFieldStoreTypeDatabase(database);
0296: }
0297:
0298: /**
0299: * Get the set of exceptions that can be thrown on given edge.
0300: * This should only be called after the analysis completes.
0301: *
0302: * @param edge the Edge
0303: * @return the ExceptionSet
0304: */
0305: public ExceptionSet getEdgeExceptionSet(Edge edge) {
0306: CachedExceptionSet cachedExceptionSet = thrownExceptionSetMap
0307: .get(edge.getSource());
0308: return cachedExceptionSet.getEdgeExceptionSet(edge);
0309: }
0310:
0311: public TypeFrame createFact() {
0312: return new TypeFrame(methodGen.getMaxLocals());
0313: }
0314:
0315: public void initEntryFact(TypeFrame result) {
0316: // Make the frame valid
0317: result.setValid();
0318:
0319: int slot = 0;
0320:
0321: // Clear the stack slots in the frame
0322: result.clearStack();
0323:
0324: // Add local for "this" pointer, if present
0325: if (!methodGen.isStatic())
0326: result.setValue(slot++, ObjectTypeFactory
0327: .getInstance(methodGen.getClassName()));
0328:
0329: // [Added: Support for Generics]
0330: // Get a parser that reads the generic signature of the method and
0331: // can be used to get the correct GenericObjectType if an argument
0332: // has a class type
0333: Iterator<String> iter = GenericSignatureParser
0334: .getGenericSignatureIterator(method);
0335:
0336: // Add locals for parameters.
0337: // Note that long and double parameters need to be handled
0338: // specially because they occupy two locals.
0339: Type[] argumentTypes = methodGen.getArgumentTypes();
0340: for (Type argType : argumentTypes) {
0341: // Add special "extra" type for long or double params.
0342: // These occupy the slot before the "plain" type.
0343: if (argType.getType() == Constants.T_LONG) {
0344: result.setValue(slot++, TypeFrame.getLongExtraType());
0345: } else if (argType.getType() == Constants.T_DOUBLE) {
0346: result.setValue(slot++, TypeFrame.getDoubleExtraType());
0347: }
0348:
0349: // [Added: Support for Generics]
0350: String s = (iter == null || !iter.hasNext()) ? null : iter
0351: .next();
0352: if (s != null
0353: && (argType instanceof ObjectType || argType instanceof ArrayType)
0354: && !(argType instanceof ExceptionObjectType)) {
0355: // replace with a generic version of the type
0356: try {
0357: argType = GenericUtilities.getType(s);
0358: } catch (RuntimeException e) {
0359: } // degrade gracefully
0360: }
0361:
0362: // Add the plain parameter type.
0363: result.setValue(slot++, argType);
0364: }
0365:
0366: // Set remaining locals to BOTTOM; this will cause any
0367: // uses of them to be flagged
0368: while (slot < methodGen.getMaxLocals())
0369: result.setValue(slot++, TypeFrame.getBottomType());
0370: }
0371:
0372: @Override
0373: public void copy(TypeFrame source, TypeFrame dest) {
0374: dest.copyFrom(source);
0375: }
0376:
0377: @Override
0378: public void makeFactTop(TypeFrame fact) {
0379: fact.setTop();
0380: }
0381:
0382: @Override
0383: public boolean isFactValid(TypeFrame fact) {
0384: return fact.isValid();
0385: }
0386:
0387: @Override
0388: public boolean same(TypeFrame fact1, TypeFrame fact2) {
0389: return fact1.sameAs(fact2);
0390: }
0391:
0392: @Override
0393: public void transferInstruction(InstructionHandle handle,
0394: BasicBlock basicBlock, TypeFrame fact)
0395: throws DataflowAnalysisException {
0396: if (typeTable != null) {
0397: int pos = handle.getPosition();
0398: if (pos >= 0 && startOfLocalTypedVariables.get(pos))
0399: for (LocalVariable local : typeTable
0400: .getLocalVariableTable()) {
0401: if (local.getStartPC() == pos) {
0402: String signature = local.getSignature();
0403: Type t;
0404: try {
0405: t = GenericUtilities.getType(signature);
0406: } catch (RuntimeException e) {
0407: AnalysisContext.logError("Bad signature "
0408: + signature + " for "
0409: + local.getName() + " in "
0410: + methodGen.getClassName() + "."
0411: + method.getName(), e);
0412: continue;
0413: }
0414: if (t instanceof GenericObjectType) {
0415: int index = local.getIndex();
0416: Type currentValue = fact.getValue(index);
0417: if (!(currentValue instanceof GenericObjectType)
0418: && (currentValue instanceof ObjectType))
0419: fact
0420: .setValue(
0421: index,
0422: GenericUtilities
0423: .merge(
0424: (GenericObjectType) t,
0425: (ObjectType) currentValue));
0426: }
0427:
0428: }
0429: }
0430: }
0431: visitor.setFrameAndLocation(fact, new Location(handle,
0432: basicBlock));
0433: visitor.analyzeInstruction(handle.getInstruction());
0434: }
0435:
0436: /* (non-Javadoc)
0437: * @see edu.umd.cs.findbugs.ba.AbstractDataflowAnalysis#transfer(edu.umd.cs.findbugs.ba.BasicBlock, org.apache.bcel.generic.InstructionHandle, java.lang.Object, java.lang.Object)
0438: */
0439: @Override
0440: public void transfer(BasicBlock basicBlock, @CheckForNull
0441: InstructionHandle end, TypeFrame start, TypeFrame result)
0442: throws DataflowAnalysisException {
0443: visitor.startBasicBlock();
0444:
0445: super .transfer(basicBlock, end, start, result);
0446:
0447: // Compute thrown exception types
0448: computeThrownExceptionTypes(basicBlock, end, result);
0449: if (DEBUG) {
0450: System.out.println("After "
0451: + basicBlock.getFirstInstruction() + " -> "
0452: + basicBlock.getLastInstruction());
0453: System.out.println(" frame: " + result);
0454: }
0455:
0456: // If this block ends with an instanceof check,
0457: // update the cached information about it.
0458: instanceOfCheckMap.remove(basicBlock);
0459: if (visitor.isInstanceOfFollowedByBranch()) {
0460: InstanceOfCheck check = new InstanceOfCheck(visitor
0461: .getInstanceOfValueNumber(), visitor
0462: .getInstanceOfType());
0463: instanceOfCheckMap.put(basicBlock, check);
0464: }
0465: }
0466:
0467: private void computeThrownExceptionTypes(BasicBlock basicBlock,
0468: @CheckForNull
0469: InstructionHandle end, TypeFrame result)
0470: throws DataflowAnalysisException {
0471:
0472: // Do nothing if we're not computing propagated exceptions
0473: if (!(FORCE_ACCURATE_EXCEPTIONS || AnalysisContext
0474: .currentAnalysisContext().getBoolProperty(
0475: AnalysisFeatures.ACCURATE_EXCEPTIONS)))
0476: return;
0477:
0478: // Also, nothing to do if the block is not an exception thrower
0479: if (!basicBlock.isExceptionThrower())
0480: return;
0481:
0482: // If cached results are up to date, don't recompute.
0483: CachedExceptionSet cachedExceptionSet = getCachedExceptionSet(basicBlock);
0484: if (cachedExceptionSet.isUpToDate((TypeFrame) result))
0485: return;
0486:
0487: // Figure out what exceptions can be thrown out
0488: // of the basic block, and mark each exception edge
0489: // with the set of exceptions which can be propagated
0490: // along the edge.
0491:
0492: int exceptionEdgeCount = 0;
0493: Edge lastExceptionEdge = null;
0494:
0495: for (Iterator<Edge> i = cfg.outgoingEdgeIterator(basicBlock); i
0496: .hasNext();) {
0497: Edge e = i.next();
0498: if (e.isExceptionEdge()) {
0499: exceptionEdgeCount++;
0500: lastExceptionEdge = e;
0501: }
0502: }
0503:
0504: if (exceptionEdgeCount == 0) {
0505: // System.out.println("Shouldn't all blocks have an exception edge");
0506: return;
0507: }
0508: // Compute exceptions that can be thrown by the
0509: // basic block.
0510: cachedExceptionSet = computeBlockExceptionSet(basicBlock,
0511: (TypeFrame) result);
0512:
0513: if (exceptionEdgeCount == 1) {
0514: cachedExceptionSet.setEdgeExceptionSet(lastExceptionEdge,
0515: cachedExceptionSet.getExceptionSet());
0516: return;
0517: }
0518:
0519: // For each outgoing exception edge, compute exceptions
0520: // that can be thrown. This assumes that the exception
0521: // edges are enumerated in decreasing order of priority.
0522: // In the process, this will remove exceptions from
0523: // the thrown exception set.
0524: ExceptionSet thrownExceptionSet = cachedExceptionSet
0525: .getExceptionSet();
0526: if (!thrownExceptionSet.isEmpty())
0527: thrownExceptionSet = thrownExceptionSet.duplicate();
0528: for (Iterator<Edge> i = cfg.outgoingEdgeIterator(basicBlock); i
0529: .hasNext();) {
0530: Edge edge = i.next();
0531: if (edge.isExceptionEdge())
0532: cachedExceptionSet.setEdgeExceptionSet(edge,
0533: computeEdgeExceptionSet(edge,
0534: thrownExceptionSet));
0535: }
0536: }
0537:
0538: public void meetInto(TypeFrame fact, Edge edge, TypeFrame result)
0539: throws DataflowAnalysisException {
0540: BasicBlock basicBlock = edge.getTarget();
0541:
0542: if (fact.isValid()) {
0543: TypeFrame tmpFact = null;
0544:
0545: // Handling an exception?
0546: if (basicBlock.isExceptionHandler()) {
0547: tmpFact = modifyFrame(fact, tmpFact);
0548:
0549: // Special case: when merging predecessor facts for entry to
0550: // an exception handler, we clear the stack and push a
0551: // single entry for the exception object. That way, the locals
0552: // can still be merged.
0553: CodeExceptionGen exceptionGen = basicBlock
0554: .getExceptionGen();
0555: tmpFact.clearStack();
0556:
0557: // Determine the type of exception(s) caught.
0558: Type catchType = null;
0559:
0560: if (FORCE_ACCURATE_EXCEPTIONS
0561: || AnalysisContext
0562: .currentAnalysisContext()
0563: .getBoolProperty(
0564: AnalysisFeatures.ACCURATE_EXCEPTIONS)) {
0565: try {
0566: // Ideally, the exceptions that can be propagated
0567: // on this edge has already been computed.
0568: CachedExceptionSet cachedExceptionSet = getCachedExceptionSet(edge
0569: .getSource());
0570: ExceptionSet edgeExceptionSet = cachedExceptionSet
0571: .getEdgeExceptionSet(edge);
0572: if (!edgeExceptionSet.isEmpty()) {
0573: //System.out.println("Using computed edge exception set!");
0574: catchType = ExceptionObjectType
0575: .fromExceptionSet(edgeExceptionSet);
0576: }
0577: } catch (ClassNotFoundException e) {
0578: lookupFailureCallback.reportMissingClass(e);
0579: }
0580: }
0581:
0582: if (catchType == null) {
0583: // No information about propagated exceptions, so
0584: // pick a type conservatively using the handler catch type.
0585: catchType = exceptionGen.getCatchType();
0586: if (catchType == null)
0587: catchType = Type.THROWABLE; // handle catches anything throwable
0588: }
0589:
0590: tmpFact.pushValue(catchType);
0591: }
0592:
0593: // See if we can make some types more precise due to
0594: // a successful instanceof check in the source block.
0595: if (valueNumberDataflow != null) {
0596: tmpFact = handleInstanceOfBranch(fact, tmpFact, edge);
0597: }
0598:
0599: if (tmpFact != null) {
0600: fact = tmpFact;
0601: }
0602: }
0603:
0604: mergeInto(fact, result);
0605: }
0606:
0607: private TypeFrame handleInstanceOfBranch(TypeFrame fact,
0608: TypeFrame tmpFact, Edge edge)
0609: throws DataflowAnalysisException {
0610:
0611: InstanceOfCheck check = instanceOfCheckMap
0612: .get(edge.getSource());
0613: if (check == null) {
0614: //System.out.println("no instanceof check for block " + edge.getSource().getId());
0615: return tmpFact;
0616: }
0617:
0618: if (check.getValueNumber() == null) {
0619: //System.out.println("instanceof check for block " + edge.getSource().getId() + " has no value number");
0620: return tmpFact;
0621: }
0622:
0623: ValueNumber instanceOfValueNumber = check.getValueNumber();
0624: ValueNumberFrame vnaFrame = valueNumberDataflow
0625: .getStartFact(edge.getTarget());
0626: if (!vnaFrame.isValid())
0627: return tmpFact;
0628:
0629: Type instanceOfType = check.getType();
0630: if (!(instanceOfType instanceof ReferenceType || instanceOfType instanceof NullType))
0631: return tmpFact;
0632:
0633: short branchOpcode = edge.getSource().getLastInstruction()
0634: .getInstruction().getOpcode();
0635:
0636: int edgeType = edge.getType();
0637: int numSlots = Math.min(fact.getNumSlots(), vnaFrame
0638: .getNumSlots());
0639:
0640: if ((edgeType == EdgeTypes.IFCMP_EDGE && (branchOpcode == Constants.IFNE
0641: || branchOpcode == Constants.IFGT || branchOpcode == Constants.IFNULL))
0642:
0643: || (edgeType == EdgeTypes.FALL_THROUGH_EDGE && (branchOpcode == Constants.IFEQ
0644: || branchOpcode == Constants.IFLE || branchOpcode == Constants.IFNONNULL))) {
0645: //System.out.println("Successful check on edge " + edge);
0646:
0647: // Successful instanceof check.
0648:
0649: for (int i = 0; i < numSlots; ++i) {
0650: if (!vnaFrame.getValue(i).equals(instanceOfValueNumber))
0651: continue;
0652:
0653: Type checkedType = fact.getValue(i);
0654: if (!(checkedType instanceof ReferenceType))
0655: continue;
0656:
0657: // Only refine the type if the cast is feasible: i.e., a downcast.
0658: // Otherwise, just set it to TOP.
0659: try {
0660: boolean guaranteed = instanceOfType instanceof ReferenceType
0661: && Hierarchy.isSubtype(
0662: (ReferenceType) checkedType,
0663: (ReferenceType) instanceOfType);
0664: if (guaranteed)
0665: continue;
0666:
0667: boolean feasibleCheck = instanceOfType
0668: .equals(NullType.instance())
0669: || Hierarchy.isSubtype(
0670: (ReferenceType) instanceOfType,
0671: (ReferenceType) checkedType);
0672:
0673: if (!feasibleCheck
0674: && instanceOfType instanceof ObjectType
0675: && checkedType instanceof ObjectType) {
0676: double v = Analyze.deepInstanceOf(
0677: ((ObjectType) instanceOfType)
0678: .getClassName(),
0679: ((ObjectType) checkedType)
0680: .getClassName());
0681: if (v > 0.0)
0682: feasibleCheck = true;
0683: }
0684: tmpFact = modifyFrame(fact, tmpFact);
0685: if (feasibleCheck) {
0686: tmpFact.setValue(i, instanceOfType);
0687: } else {
0688: tmpFact.setTop();
0689: return tmpFact;
0690: }
0691: } catch (ClassNotFoundException e) {
0692: lookupFailureCallback.reportMissingClass(e);
0693: throw new MissingClassException(e);
0694: }
0695: }
0696: } else if (!instanceOfType.equals(NullType.instance())) {
0697:
0698: for (int i = 0; i < numSlots; ++i) {
0699: if (!vnaFrame.getValue(i).equals(instanceOfValueNumber))
0700: continue;
0701:
0702: Type checkedType = fact.getValue(i);
0703: if (!(checkedType instanceof ReferenceType))
0704: continue;
0705: try {
0706: boolean guaranteed = Hierarchy.isSubtype(
0707: (ReferenceType) checkedType,
0708: (ReferenceType) instanceOfType);
0709: if (!guaranteed)
0710: continue;
0711: tmpFact = modifyFrame(fact, tmpFact);
0712: tmpFact.setTop();
0713: return tmpFact;
0714: } catch (ClassNotFoundException e) {
0715: lookupFailureCallback.reportMissingClass(e);
0716: throw new MissingClassException(e);
0717: }
0718: }
0719: }
0720:
0721: return tmpFact;
0722: }
0723:
0724: @Override
0725: protected void mergeValues(TypeFrame otherFrame,
0726: TypeFrame resultFrame, int slot)
0727: throws DataflowAnalysisException {
0728: Type value = typeMerger.mergeTypes(resultFrame.getValue(slot),
0729: otherFrame.getValue(slot));
0730: resultFrame.setValue(slot, value);
0731:
0732: // Result type is exact IFF types are identical and both are exact
0733:
0734: boolean typesAreIdentical = otherFrame.getValue(slot).equals(
0735: resultFrame.getValue(slot));
0736:
0737: boolean bothExact = resultFrame.isExact(slot)
0738: && otherFrame.isExact(slot);
0739:
0740: resultFrame.setExact(slot, typesAreIdentical && bothExact);
0741: }
0742:
0743: /**
0744: * Get the cached set of exceptions that can be thrown
0745: * from given basic block. If this information hasn't
0746: * been computed yet, then an empty exception set is
0747: * returned.
0748: *
0749: * @param basicBlock the block to get the cached exception set for
0750: * @return the CachedExceptionSet for the block
0751: */
0752: private CachedExceptionSet getCachedExceptionSet(
0753: BasicBlock basicBlock) {
0754: CachedExceptionSet cachedExceptionSet = thrownExceptionSetMap
0755: .get(basicBlock);
0756: if (cachedExceptionSet == null) {
0757: // When creating the cached exception type set for the first time:
0758: // - the block result is set to TOP, so it won't match
0759: // any block result that has actually been computed
0760: // using the analysis transfer function
0761: // - the exception set is created as empty (which makes it
0762: // return TOP as its common superclass)
0763:
0764: TypeFrame top = createFact();
0765: makeFactTop(top);
0766: cachedExceptionSet = new CachedExceptionSet(top,
0767: exceptionSetFactory.createExceptionSet());
0768:
0769: thrownExceptionSetMap.put(basicBlock, cachedExceptionSet);
0770: }
0771:
0772: return cachedExceptionSet;
0773: }
0774:
0775: /**
0776: * Compute the set of exceptions that can be
0777: * thrown from the given basic block.
0778: * This should only be called if the existing cached
0779: * exception set is out of date.
0780: *
0781: * @param basicBlock the basic block
0782: * @param result the result fact for the block; this is used
0783: * to determine whether or not the cached exception
0784: * set is up to date
0785: * @return the cached exception set for the block
0786: */
0787: private CachedExceptionSet computeBlockExceptionSet(
0788: BasicBlock basicBlock, TypeFrame result)
0789: throws DataflowAnalysisException {
0790:
0791: ExceptionSet exceptionSet;
0792: try {
0793: exceptionSet = computeThrownExceptionTypes(basicBlock);
0794: } catch (ClassNotFoundException e) {
0795: // Special case: be as conservative as possible
0796: // if a class hierarchy lookup fails.
0797: lookupFailureCallback.reportMissingClass(e);
0798: exceptionSet = exceptionSetFactory.createExceptionSet();
0799: exceptionSet.addExplicit(Type.THROWABLE);
0800: }
0801:
0802: TypeFrame copyOfResult = createFact();
0803: copy(result, copyOfResult);
0804:
0805: CachedExceptionSet cachedExceptionSet = new CachedExceptionSet(
0806: copyOfResult, exceptionSet);
0807: thrownExceptionSetMap.put(basicBlock, cachedExceptionSet);
0808:
0809: return cachedExceptionSet;
0810: }
0811:
0812: /**
0813: * Based on the set of exceptions that can be thrown
0814: * from the source basic block,
0815: * compute the set of exceptions that can propagate
0816: * along given exception edge. This method should be
0817: * called for each outgoing exception edge in sequence,
0818: * so the caught exceptions can be removed from the
0819: * thrown exception set as needed.
0820: *
0821: * @param edge the exception edge
0822: * @param thrownExceptionSet current set of exceptions that
0823: * can be thrown, taking earlier (higher priority)
0824: * exception edges into account
0825: * @return the set of exceptions that can propagate
0826: * along this edge
0827: */
0828: private ExceptionSet computeEdgeExceptionSet(Edge edge,
0829: ExceptionSet thrownExceptionSet) {
0830:
0831: if (thrownExceptionSet.isEmpty())
0832: return thrownExceptionSet;
0833: ExceptionSet result = exceptionSetFactory.createExceptionSet();
0834:
0835: if (edge.getType() == UNHANDLED_EXCEPTION_EDGE) {
0836: // The unhandled exception edge always comes
0837: // after all of the handled exception edges.
0838: result.addAll(thrownExceptionSet);
0839: thrownExceptionSet.clear();
0840: return result;
0841: }
0842:
0843: BasicBlock handlerBlock = edge.getTarget();
0844: CodeExceptionGen handler = handlerBlock.getExceptionGen();
0845: ObjectType catchType = handler.getCatchType();
0846:
0847: if (Hierarchy.isUniversalExceptionHandler(catchType)) {
0848: result.addAll(thrownExceptionSet);
0849: thrownExceptionSet.clear();
0850: } else {
0851: // Go through the set of thrown exceptions.
0852: // Any that will DEFINITELY be caught be this handler, remove.
0853: // Any that MIGHT be caught, but won't definitely be caught,
0854: // remain.
0855:
0856: for (ExceptionSet.ThrownExceptionIterator i = thrownExceptionSet
0857: .iterator(); i.hasNext();) {
0858: //ThrownException thrownException = i.next();
0859: ObjectType thrownType = i.next();
0860: boolean explicit = i.isExplicit();
0861:
0862: if (DEBUG)
0863: System.out.println("\texception type " + thrownType
0864: + ", catch type " + catchType);
0865:
0866: try {
0867: if (Hierarchy.isSubtype(thrownType, catchType)) {
0868: // Exception can be thrown along this edge
0869: result.add(thrownType, explicit);
0870:
0871: // And it will definitely be caught
0872: i.remove();
0873:
0874: if (DEBUG)
0875: System.out
0876: .println("\tException is subtype of catch type: "
0877: + "will definitely catch");
0878: } else if (Hierarchy.isSubtype(catchType,
0879: thrownType)) {
0880: // Exception possibly thrown along this edge
0881: result.add(thrownType, explicit);
0882:
0883: if (DEBUG)
0884: System.out
0885: .println("\tException is supertype of catch type: "
0886: + "might catch");
0887: }
0888: } catch (ClassNotFoundException e) {
0889: // As a special case, if a class hierarchy lookup
0890: // fails, then we will conservatively assume that the
0891: // exception in question CAN, but WON'T NECESSARILY
0892: // be caught by the handler.
0893: AnalysisContext.reportMissingClass(e);
0894: result.add(thrownType, explicit);
0895: }
0896: }
0897: }
0898:
0899: return result;
0900: }
0901:
0902: /**
0903: * Compute the set of exception types that can
0904: * be thrown by given basic block.
0905: *
0906: * @param basicBlock the basic block
0907: * @return the set of exceptions that can be thrown by the block
0908: */
0909: private ExceptionSet computeThrownExceptionTypes(
0910: BasicBlock basicBlock) throws ClassNotFoundException,
0911: DataflowAnalysisException {
0912:
0913: ExceptionSet exceptionTypeSet = exceptionSetFactory
0914: .createExceptionSet();
0915: InstructionHandle pei = basicBlock.getExceptionThrower();
0916: Instruction ins = pei.getInstruction();
0917:
0918: // Get the exceptions that BCEL knows about.
0919: // Note that all of these are unchecked.
0920: ExceptionThrower exceptionThrower = (ExceptionThrower) ins;
0921: Class<?>[] exceptionList = exceptionThrower.getExceptions();
0922: for (Class<?> aExceptionList : exceptionList) {
0923: exceptionTypeSet.addImplicit(ObjectTypeFactory
0924: .getInstance(aExceptionList.getName()));
0925: }
0926:
0927: // Assume that an Error may be thrown by any instruction.
0928: exceptionTypeSet.addImplicit(Hierarchy.ERROR_TYPE);
0929:
0930: if (ins instanceof ATHROW) {
0931: // For ATHROW instructions, we generate *two* blocks
0932: // for which the ATHROW is an exception thrower.
0933: //
0934: // - The first, empty basic block, does the null check
0935: // - The second block, which actually contains the ATHROW,
0936: // throws the object on the top of the operand stack
0937: //
0938: // We make a special case of the block containing the ATHROW,
0939: // by removing all of the implicit exceptions,
0940: // and using type information to figure out what is thrown.
0941:
0942: if (basicBlock.containsInstruction(pei)) {
0943: // This is the actual ATHROW, not the null check
0944: // and implicit exceptions.
0945: exceptionTypeSet.clear();
0946:
0947: // The frame containing the thrown value is the start fact
0948: // for the block, because ATHROW is guaranteed to be
0949: // the only instruction in the block.
0950: TypeFrame frame = getStartFact(basicBlock);
0951:
0952: // Check whether or not the frame is valid.
0953: // Sun's javac sometimes emits unreachable code.
0954: // For example, it will emit code that follows a JSR
0955: // subroutine call that never returns.
0956: // If the frame is invalid, then we can just make
0957: // a conservative assumption that anything could be
0958: // thrown at this ATHROW.
0959: if (!frame.isValid()) {
0960: exceptionTypeSet.addExplicit(Type.THROWABLE);
0961: } else if (frame.getStackDepth() == 0) {
0962: throw new IllegalStateException("empty stack "
0963: + " thrown by "
0964: + pei
0965: + " in "
0966: + SignatureConverter
0967: .convertMethodSignature(methodGen));
0968: } else {
0969:
0970: Type throwType = frame.getTopValue();
0971: if (throwType instanceof ObjectType) {
0972: exceptionTypeSet
0973: .addExplicit((ObjectType) throwType);
0974: } else if (throwType instanceof ExceptionObjectType) {
0975: exceptionTypeSet
0976: .addAll(((ExceptionObjectType) throwType)
0977: .getExceptionSet());
0978: } else {
0979: // Not sure what is being thrown here.
0980: // Be conservative.
0981: if (DEBUG) {
0982: System.out
0983: .println("Non object type "
0984: + throwType
0985: + " thrown by "
0986: + pei
0987: + " in "
0988: + SignatureConverter
0989: .convertMethodSignature(methodGen));
0990: }
0991: exceptionTypeSet.addExplicit(Type.THROWABLE);
0992: }
0993: }
0994: }
0995: }
0996:
0997: // If it's an InvokeInstruction, add declared exceptions and RuntimeException
0998: if (ins instanceof InvokeInstruction) {
0999: ConstantPoolGen cpg = methodGen.getConstantPool();
1000:
1001: InvokeInstruction inv = (InvokeInstruction) ins;
1002: ObjectType[] declaredExceptionList = Hierarchy2
1003: .findDeclaredExceptions(inv, cpg);
1004: if (declaredExceptionList == null) {
1005: // Couldn't find declared exceptions,
1006: // so conservatively assume it could thrown any checked exception.
1007: if (DEBUG)
1008: System.out
1009: .println("Couldn't find declared exceptions for "
1010: + SignatureConverter
1011: .convertMethodSignature(
1012: inv, cpg));
1013: exceptionTypeSet.addExplicit(Hierarchy.EXCEPTION_TYPE);
1014: } else {
1015: for (ObjectType aDeclaredExceptionList : declaredExceptionList) {
1016: exceptionTypeSet
1017: .addExplicit(aDeclaredExceptionList);
1018: }
1019: }
1020:
1021: exceptionTypeSet
1022: .addImplicit(Hierarchy.RUNTIME_EXCEPTION_TYPE);
1023: }
1024:
1025: if (DEBUG)
1026: System.out.println(pei + " can throw " + exceptionTypeSet);
1027:
1028: return exceptionTypeSet;
1029: }
1030:
1031: public static void main(String[] argv) throws Exception {
1032: if (argv.length != 1) {
1033: System.err.println("Usage: " + TypeAnalysis.class.getName()
1034: + " <class file>");
1035: System.exit(1);
1036: }
1037:
1038: DataflowTestDriver<TypeFrame, TypeAnalysis> driver = new DataflowTestDriver<TypeFrame, TypeAnalysis>() {
1039: @Override
1040: public Dataflow<TypeFrame, TypeAnalysis> createDataflow(
1041: ClassContext classContext, Method method)
1042: throws CFGBuilderException,
1043: DataflowAnalysisException {
1044: return classContext.getTypeDataflow(method);
1045: }
1046: };
1047:
1048: driver.execute(argv[0]);
1049: }
1050: }
1051:
1052: // vim:ts=3
|