TypeAnalysis


1   /*
2    * Bytecode Analysis Framework
3    * Copyright (C) 2003-2005 University of Maryland
4    * 
5    * This library is free software; you can redistribute it and/or
6    * modify it under the terms of the GNU Lesser General Public
7    * License as published by the Free Software Foundation; either
8    * version 2.1 of the License, or (at your option) any later version.
9    * 
10   * This library is distributed in the hope that it will be useful,
11   * but WITHOUT ANY WARRANTY; without even the implied warranty of
12   * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
13   * Lesser General Public License for more details.
14   * 
15   * You should have received a copy of the GNU Lesser General Public
16   * License along with this library; if not, write to the Free Software
17   * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
18   */
19  
20  package edu.umd.cs.findbugs.ba.type;
21  
22  import java.util.HashMap  ;
23  import java.util.Iterator  ;
24  import java.util.Map  ;
25  
26  import org.apache.bcel.Constants;
27  import org.apache.bcel.classfile.Attribute;
28  import org.apache.bcel.classfile.Method;
29  import org.apache.bcel.classfile.Signature;
30  import org.apache.bcel.generic.ATHROW;
31  import org.apache.bcel.generic.ArrayType;
32  import org.apache.bcel.generic.CodeExceptionGen;
33  import org.apache.bcel.generic.ConstantPoolGen;
34  import org.apache.bcel.generic.ExceptionThrower;
35  import org.apache.bcel.generic.Instruction;
36  import org.apache.bcel.generic.InstructionHandle;
37  import org.apache.bcel.generic.InvokeInstruction;
38  import org.apache.bcel.generic.MethodGen;
39  import org.apache.bcel.generic.ObjectType;
40  import org.apache.bcel.generic.ReferenceType;
41  import org.apache.bcel.generic.Type;
42  
43  import edu.umd.cs.findbugs.DeepSubtypeAnalysis;
44  import edu.umd.cs.findbugs.SystemProperties;
45  import edu.umd.cs.findbugs.annotations.CheckForNull;
46  import edu.umd.cs.findbugs.ba.AnalysisContext;
47  import edu.umd.cs.findbugs.ba.AnalysisFeatures;
48  import edu.umd.cs.findbugs.ba.BasicBlock;
49  import edu.umd.cs.findbugs.ba.CFG;
50  import edu.umd.cs.findbugs.ba.CFGBuilderException;
51  import edu.umd.cs.findbugs.ba.ClassContext;
52  import edu.umd.cs.findbugs.ba.Dataflow;
53  import edu.umd.cs.findbugs.ba.DataflowAnalysis;
54  import edu.umd.cs.findbugs.ba.DataflowAnalysisException;
55  import edu.umd.cs.findbugs.ba.DataflowTestDriver;
56  import edu.umd.cs.findbugs.ba.DepthFirstSearch;
57  import edu.umd.cs.findbugs.ba.Edge;
58  import edu.umd.cs.findbugs.ba.EdgeTypes;
59  import edu.umd.cs.findbugs.ba.FrameDataflowAnalysis;
60  import edu.umd.cs.findbugs.ba.Hierarchy;
61  import edu.umd.cs.findbugs.ba.Location;
62  import edu.umd.cs.findbugs.ba.MissingClassException;
63  import edu.umd.cs.findbugs.ba.ObjectTypeFactory;
64  import edu.umd.cs.findbugs.ba.RepositoryLookupFailureCallback;
65  import edu.umd.cs.findbugs.ba.SignatureConverter;
66  import edu.umd.cs.findbugs.ba.generic.GenericSignatureParser;
67  import edu.umd.cs.findbugs.ba.generic.GenericUtilities;
68  import edu.umd.cs.findbugs.ba.vna.ValueNumber;
69  import edu.umd.cs.findbugs.ba.vna.ValueNumberDataflow;
70  import edu.umd.cs.findbugs.ba.vna.ValueNumberFrame;
71  
72  /**
73   * A forward dataflow analysis to determine the types of all values
74   * in the Java stack frame at all points in a Java method.
75   * The values include local variables and values on the Java operand stack.
76   * <p/>
77   * <p> As a side effect, the analysis computes the exception
78   * set throwable on each exception edge in the CFG.
79   * This information can be used to prune infeasible exception
80   * edges, and mark exception edges which propagate only
81   * implicit exceptions.
82   *
83   * @author David Hovemeyer
84   * @see Dataflow
85   * @see DataflowAnalysis
86   * @see TypeFrame
87   */
88  public class TypeAnalysis extends FrameDataflowAnalysis<Type, TypeFrame>
89          implements EdgeTypes {
90  
91      public static final boolean DEBUG = SystemProperties.getBoolean("ta.debug");
92  
93      /**
94       * Force computation of accurate exceptions.
95       */
96      public static final boolean FORCE_ACCURATE_EXCEPTIONS =SystemProperties.getBoolean("ta.accurateExceptions");
97  
98      /**
99       * Repository of information about thrown exceptions computed for
100      * a basic block and its outgoing exception edges.
101      * It contains a result TypeFrame, which is used to detect
102      * when the exception information needs to be recomputed
103      * for the block.
104      */
105     private class CachedExceptionSet {
106         private TypeFrame result;
107         private ExceptionSet exceptionSet;
108         private Map  <Edge, ExceptionSet> edgeExceptionMap;
109 
110         public CachedExceptionSet(TypeFrame result, ExceptionSet exceptionSet) {
111             this.result = result;
112             this.exceptionSet = exceptionSet;
113             this.edgeExceptionMap = new HashMap  <Edge, ExceptionSet>();
114         }
115 
116         public boolean isUpToDate(TypeFrame result) {
117             return this.result.equals(result);
118         }
119 
120         public ExceptionSet getExceptionSet() {
121             return exceptionSet;
122         }
123 
124         public void setEdgeExceptionSet(Edge edge, ExceptionSet exceptionSet) {
125             edgeExceptionMap.put(edge, exceptionSet);
126         }
127 
128         public ExceptionSet getEdgeExceptionSet(Edge edge) {
129             ExceptionSet edgeExceptionSet = edgeExceptionMap.get(edge);
130             if (edgeExceptionSet == null) {
131                 edgeExceptionSet = exceptionSetFactory.createExceptionSet();
132                 edgeExceptionMap.put(edge, edgeExceptionSet);
133             }
134             return edgeExceptionSet;
135         }
136     }
137 
138     /**
139      * Cached information about an instanceof check.
140      */
141     static class InstanceOfCheck {
142         final ValueNumber valueNumber;
143         final Type type;
144         
145         InstanceOfCheck(ValueNumber valueNumber, Type type) {
146             this.valueNumber = valueNumber;
147             this.type = type;
148         }
149         
150         /**
151          * @return Returns the valueNumber.
152          */
153         public ValueNumber getValueNumber() {
154             return valueNumber;
155         }
156         
157         /**
158          * @return Returns the type.
159          */
160         public Type getType() {
161             return type;
162         }
163     }
164 
165     protected MethodGen methodGen;
166     protected CFG cfg;
167     private TypeMerger typeMerger;
168     private TypeFrameModelingVisitor visitor;
169     private Map  <BasicBlock, CachedExceptionSet> thrownExceptionSetMap;
170     private RepositoryLookupFailureCallback lookupFailureCallback;
171     private ExceptionSetFactory exceptionSetFactory;
172     private ValueNumberDataflow valueNumberDataflow;
173     private Map  <BasicBlock, InstanceOfCheck> instanceOfCheckMap;
174 
175     /**
176      * Constructor.
177      *
178      * @param methodGen             the MethodGen whose CFG we'll be analyzing
179      * @param cfg                   the control flow graph
180      * @param dfs                   DepthFirstSearch of the method
181      * @param typeMerger            object to merge types
182      * @param visitor               a TypeFrameModelingVisitor to use to model the effect
183      *                              of instructions
184      * @param lookupFailureCallback lookup failure callback
185      * @param exceptionSetFactory   factory for creating ExceptionSet objects
186      */
187     public TypeAnalysis(MethodGen methodGen, CFG cfg, DepthFirstSearch dfs,
188                         TypeMerger typeMerger, TypeFrameModelingVisitor visitor,
189                         RepositoryLookupFailureCallback lookupFailureCallback,
190                         ExceptionSetFactory exceptionSetFactory) {
191         super(dfs);
192         this.methodGen = methodGen;
193         this.cfg = cfg;
194         this.typeMerger = typeMerger;
195         this.visitor = visitor;
196         this.thrownExceptionSetMap = new HashMap  <BasicBlock, CachedExceptionSet>();
197         this.lookupFailureCallback = lookupFailureCallback;
198         this.exceptionSetFactory = exceptionSetFactory;
199         this.instanceOfCheckMap = new HashMap  <BasicBlock, InstanceOfCheck>();
200         if (DEBUG) {
201             System.out.println("\n\nAnalyzing " + methodGen);
202         }
203     }
204 
205     /**
206      * Constructor.
207      *
208      * @param methodGen             the MethodGen whose CFG we'll be analyzing
209      * @param cfg                   the control flow graph
210      * @param dfs                   DepthFirstSearch of the method
211      * @param typeMerger            object to merge types
212      * @param lookupFailureCallback lookup failure callback
213      * @param exceptionSetFactory   factory for creating ExceptionSet objects
214      */
215     public TypeAnalysis(MethodGen methodGen, CFG cfg, DepthFirstSearch dfs,
216                         TypeMerger typeMerger, RepositoryLookupFailureCallback lookupFailureCallback,
217                         ExceptionSetFactory exceptionSetFactory) {
218         this(methodGen, cfg, dfs, typeMerger,
219                 new TypeFrameModelingVisitor(methodGen.getConstantPool()), lookupFailureCallback,
220                 exceptionSetFactory);
221     }
222 
223     /**
224      * Constructor which uses StandardTypeMerger.
225      *
226      * @param methodGen             the MethodGen whose CFG we'll be analyzing
227      * @param cfg                   the control flow graph
228      * @param dfs                   DepthFirstSearch of the method
229      * @param lookupFailureCallback callback for Repository lookup failures
230      * @param exceptionSetFactory   factory for creating ExceptionSet objects
231      */
232     public TypeAnalysis(MethodGen methodGen, CFG cfg, DepthFirstSearch dfs,
233                         RepositoryLookupFailureCallback lookupFailureCallback,
234                         ExceptionSetFactory exceptionSetFactory) {
235         this(methodGen, cfg, dfs,
236                 new StandardTypeMerger(lookupFailureCallback, exceptionSetFactory),
237                 lookupFailureCallback, exceptionSetFactory);
238     }
239     
240     /**
241      * Set the ValueNumberDataflow for the method being analyzed.
242      * This is optional; if set, it will be used to make instanceof
243      * instructions more precise.
244      * 
245      * @param valueNumberDataflow the ValueNumberDataflow
246      */
247     public void setValueNumberDataflow(ValueNumberDataflow valueNumberDataflow) {
248         this.valueNumberDataflow = valueNumberDataflow;
249         this.visitor.setValueNumberDataflow(valueNumberDataflow);
250     }
251     
252     /**
253      * Set the FieldStoreTypeDatabase.
254      * This can be used to get more accurate types for values loaded
255      * from fields.
256      * 
257      * @param database the FieldStoreTypeDatabase 
258      */
259     public void setFieldStoreTypeDatabase(FieldStoreTypeDatabase database) {
260         visitor.setFieldStoreTypeDatabase(database);
261     }
262 
263     /**
264      * Get the set of exceptions that can be thrown on given edge.
265      * This should only be called after the analysis completes.
266      *
267      * @param edge the Edge
268      * @return the ExceptionSet
269      */
270     public ExceptionSet getEdgeExceptionSet(Edge edge) {
271         CachedExceptionSet cachedExceptionSet = thrownExceptionSetMap.get(edge.getSource());
272         return cachedExceptionSet.getEdgeExceptionSet(edge);
273     }
274 
275     public TypeFrame createFact() {
276         return new TypeFrame(methodGen.getMaxLocals());
277     }
278 
279     public void initEntryFact(TypeFrame result) {
280         // Make the frame valid
281         result.setValid();
282 
283         int slot = 0;
284 
285         // Clear the stack slots in the frame
286         result.clearStack();
287 
288         // Add local for "this" pointer, if present
289         if (!methodGen.isStatic())
290             result.setValue(slot++, ObjectTypeFactory.getInstance(methodGen.getClassName()));
291 
292         // [Added: Support for Generics]
293         // Get a parser that reads the generic signature of the method and
294         // can be used to get the correct GenericObjectType if an argument
295         // has a class type
296         Iterator  <String  > iter = 
297             GenericSignatureParser.getGenericSignatureIterator(methodGen.getMethod());
298         
299         // Add locals for parameters.
300         // Note that long and double parameters need to be handled
301         // specially because they occupy two locals.
302         Type[] argumentTypes = methodGen.getArgumentTypes();        
303         for (Type argType : argumentTypes) {
304             // Add special "extra" type for long or double params.
305             // These occupy the slot before the "plain" type.
306             if (argType.getType() == Constants.T_LONG) {
307                 result.setValue(slot++, TypeFrame.getLongExtraType());
308             } else if (argType.getType() == Constants.T_DOUBLE) {
309                 result.setValue(slot++, TypeFrame.getDoubleExtraType());
310             }
311             
312             // [Added: Support for Generics]
313             String   s = ( iter == null  || !iter.hasNext() )? null : iter.next();
314             if (    s != null && 
315                     (argType instanceof ObjectType || argType instanceof ArrayType) &&
316                     !(argType instanceof ExceptionObjectType) 
317                 ) {
318                 // replace with a generic version of the type
319                 try { 
320                     argType = GenericUtilities.getType(s);
321                 } catch (RuntimeException   e) {} // degrade gracefully
322             }
323 
324             // Add the plain parameter type.
325             result.setValue(slot++, argType);
326         }
327 
328         // Set remaining locals to BOTTOM; this will cause any
329         // uses of them to be flagged
330         while (slot < methodGen.getMaxLocals())
331             result.setValue(slot++, TypeFrame.getBottomType());
332     }
333 
334     @Override  
335     public void copy(TypeFrame source, TypeFrame dest) {
336         dest.copyFrom(source);
337     }
338 
339     @Override  
340     public void initResultFact(TypeFrame result) {
341         // This is important.  Sometimes we need to use a result value
342         // before having a chance to initialize it.  We don't want such
343         // values to corrupt other TypeFrame values that we merge them with.
344         // So, all result values must be TOP.
345         result.setTop();
346     }
347 
348     @Override  
349     public void makeFactTop(TypeFrame fact) {
350         fact.setTop();
351     }
352 
353     @Override  
354     public boolean isFactValid(TypeFrame fact) {
355         return fact.isValid();
356     }
357 
358     @Override  
359     public boolean same(TypeFrame fact1, TypeFrame fact2) {
360         return fact1.sameAs(fact2);
361     }
362 
363     @Override  
364     public void transferInstruction(InstructionHandle handle, BasicBlock basicBlock, TypeFrame fact)
365             throws DataflowAnalysisException {
366         visitor.setFrameAndLocation(fact, new Location(handle, basicBlock));
367         visitor.analyzeInstruction(handle.getInstruction());
368     }
369     
370     /* (non-Javadoc)
371      * @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)
372      */
373     @Override  
374     public void transfer(BasicBlock basicBlock, @CheckForNull InstructionHandle end, TypeFrame start, TypeFrame result) throws DataflowAnalysisException {
375         visitor.startBasicBlock();
376         
377         super.transfer(basicBlock, end, start, result);
378         
379         // Compute thrown exception types
380         computeThrownExceptionTypes(basicBlock, end, result);
381         if (DEBUG) {
382             System.out.println("After " + basicBlock.getFirstInstruction() + " -> " + basicBlock.getLastInstruction());
383             System.out.println("    frame: " + result);
384         }
385         
386         // If this block ends with an instanceof check,
387         // update the cached information about it.
388         instanceOfCheckMap.remove(basicBlock);
389         if (visitor.isInstanceOfFollowedByBranch()) {
390             InstanceOfCheck check = new InstanceOfCheck(visitor.getInstanceOfValueNumber(), visitor.getInstanceOfType());
391             instanceOfCheckMap.put(basicBlock, check);
392         }
393     }
394 
395     private void computeThrownExceptionTypes(BasicBlock basicBlock, @CheckForNull InstructionHandle end, TypeFrame result)
396             throws DataflowAnalysisException {
397 
398         // Do nothing if we're not computing propagated exceptions
399         if (!(FORCE_ACCURATE_EXCEPTIONS ||
400                 AnalysisContext.currentAnalysisContext().getBoolProperty(AnalysisFeatures.ACCURATE_EXCEPTIONS)))
401             return;
402 
403         // Also, nothing to do if the block is not an exception thrower
404         if (!basicBlock.isExceptionThrower())
405             return;
406 
407         // If cached results are up to date, don't recompute.
408         CachedExceptionSet cachedExceptionSet = getCachedExceptionSet(basicBlock);
409         if (cachedExceptionSet.isUpToDate((TypeFrame) result))
410             return;
411 
412         // Figure out what exceptions can be thrown out
413         // of the basic block, and mark each exception edge
414         // with the set of exceptions which can be propagated
415         // along the edge.
416 
417         int exceptionEdgeCount = 0;
418         Edge lastExceptionEdge = null;
419         
420         for (Iterator  <Edge> i = cfg.outgoingEdgeIterator(basicBlock); i.hasNext();) {
421             Edge e = i.next();
422             if (e.isExceptionEdge()) {
423                 exceptionEdgeCount++;
424                 lastExceptionEdge = e;
425             }
426         }
427         
428         if (exceptionEdgeCount == 0) {
429             // System.out.println("Shouldn't all blocks have an exception edge");
430             return;
431         }
432         // Compute exceptions that can be thrown by the
433         // basic block.
434         cachedExceptionSet = computeBlockExceptionSet(basicBlock, (TypeFrame) result);
435         
436         if (exceptionEdgeCount == 1) {
437             cachedExceptionSet.setEdgeExceptionSet(lastExceptionEdge, cachedExceptionSet.getExceptionSet());
438             return;
439         }
440         
441 
442         // For each outgoing exception edge, compute exceptions
443         // that can be thrown.  This assumes that the exception
444         // edges are enumerated in decreasing order of priority.
445         // In the process, this will remove exceptions from
446         // the thrown exception set.
447         ExceptionSet thrownExceptionSet = cachedExceptionSet.getExceptionSet();
448         if (!thrownExceptionSet.isEmpty()) thrownExceptionSet = thrownExceptionSet.duplicate();
449         for (Iterator  <Edge> i = cfg.outgoingEdgeIterator(basicBlock); i.hasNext();) {
450             Edge edge = i.next();
451             if (edge.isExceptionEdge())
452                 cachedExceptionSet.setEdgeExceptionSet(edge, computeEdgeExceptionSet(edge, thrownExceptionSet));
453         }
454     }
455 
456     public void meetInto(TypeFrame fact, Edge edge, TypeFrame result) throws DataflowAnalysisException {
457         BasicBlock basicBlock = edge.getTarget();
458 
459         if (fact.isValid()) {
460             TypeFrame tmpFact = null;
461 
462             // Handling an exception?
463             if (basicBlock.isExceptionHandler()) {
464                 tmpFact = modifyFrame(fact, tmpFact);
465                 
466                 // Special case: when merging predecessor facts for entry to
467                 // an exception handler, we clear the stack and push a
468                 // single entry for the exception object.  That way, the locals
469                 // can still be merged.
470                 CodeExceptionGen exceptionGen = basicBlock.getExceptionGen();
471                 tmpFact.clearStack();
472                 
473                 // Determine the type of exception(s) caught.
474                 Type catchType = null;
475                 
476                 if (FORCE_ACCURATE_EXCEPTIONS ||
477                         AnalysisContext.currentAnalysisContext().getBoolProperty(AnalysisFeatures.ACCURATE_EXCEPTIONS)) {
478                     try {
479                         // Ideally, the exceptions that can be propagated
480                         // on this edge has already been computed.
481                         CachedExceptionSet cachedExceptionSet = getCachedExceptionSet(edge.getSource());
482                         ExceptionSet edgeExceptionSet = cachedExceptionSet.getEdgeExceptionSet(edge);
483                         if (!edgeExceptionSet.isEmpty()) {
484                             //System.out.println("Using computed edge exception set!");
485                             catchType = ExceptionObjectType.fromExceptionSet(edgeExceptionSet);
486                         }
487                     } catch (ClassNotFoundException   e) {
488                         lookupFailureCallback.reportMissingClass(e);
489                     }
490                 }
491                 
492                 if (catchType == null) {
493                     // No information about propagated exceptions, so
494                     // pick a type conservatively using the handler catch type.
495                     catchType = exceptionGen.getCatchType();
496                     if (catchType == null)
497                         catchType = Type.THROWABLE; // handle catches anything throwable
498                 }
499                 
500                 tmpFact.pushValue(catchType);
501             }
502             
503             // See if we can make some types more precise due to
504             // a successful instanceof check in the source block.
505             if (valueNumberDataflow != null) {
506                 tmpFact = handleInstanceOfBranch(fact, tmpFact, edge);
507             }
508 
509             if (tmpFact != null) {
510                 fact = tmpFact;
511             }
512         }
513 
514         mergeInto(fact, result);
515     }
516 
517     private TypeFrame handleInstanceOfBranch(TypeFrame fact, TypeFrame tmpFact, Edge edge) throws DataflowAnalysisException {
518 
519         InstanceOfCheck check = instanceOfCheckMap.get(edge.getSource());
520         if (check == null) {
521             //System.out.println("no instanceof check for block " + edge.getSource().getId());
522             return tmpFact;
523         }
524 
525         if (check.getValueNumber() == null) {
526             //System.out.println("instanceof check for block " + edge.getSource().getId() + " has no value number");
527             return tmpFact;
528         }
529         
530         ValueNumber instanceOfValueNumber = check.getValueNumber();
531 
532         short branchOpcode = edge.getSource().getLastInstruction().getInstruction().getOpcode();
533         
534         int edgeType = edge.getType();
535         if (    (edgeType == EdgeTypes.IFCMP_EDGE &&
536                         (branchOpcode == Constants.IFNE || branchOpcode == Constants.IFGT || branchOpcode == Constants.IFNULL))
537                 
538             || (edgeType == EdgeTypes.FALL_THROUGH_EDGE &&
539                         (branchOpcode == Constants.IFEQ || branchOpcode == Constants.IFLE || branchOpcode == Constants.IFNONNULL))
540         ) {
541             //System.out.println("Successful check on edge " + edge);
542             
543             // Successful instanceof check.
544             ValueNumberFrame vnaFrame = valueNumberDataflow.getStartFact(edge.getTarget());
545             if (!vnaFrame.isValid())
546                 return tmpFact;
547             
548             Type instanceOfType = check.getType();
549             if (!(instanceOfType instanceof ReferenceType || instanceOfType instanceof NullType))
550                 return tmpFact;
551             
552             int numSlots = Math.min(fact.getNumSlots(), vnaFrame.getNumSlots());
553             for (int i = 0; i < numSlots; ++i) {
554                 if (!vnaFrame.getValue(i).equals(instanceOfValueNumber))
555                     continue;
556 
557                 Type checkedType = fact.getValue(i);
558                 if (!(checkedType instanceof ReferenceType))
559                     continue;
560 
561 
562                 // Only refine the type if the cast is feasible: i.e., a downcast.
563                 // Otherwise, just set it to TOP.
564                 try {
565                     boolean feasibleCheck = instanceOfType.equals(NullType.instance()) 
566                         || Hierarchy.isSubtype(
567                             (ReferenceType) instanceOfType,
568                             (ReferenceType) checkedType);
569                     if (!feasibleCheck && instanceOfType instanceof ObjectType 
570                             && checkedType instanceof ObjectType) {
571                         double v = DeepSubtypeAnalysis.deepInstanceOf(((ObjectType)instanceOfType).getClassName(), 
572                                 ((ObjectType)checkedType).getClassName());
573                         if (v > 0.0) feasibleCheck = true;
574                     }
575                     tmpFact = modifyFrame(fact, tmpFact);
576                     tmpFact.setValue(i, feasibleCheck ? instanceOfType : TopType.instance());
577                 } catch (ClassNotFoundException   e) {
578                     lookupFailureCallback.reportMissingClass(e);
579                     throw new MissingClassException(e);
580                 }
581             }
582         }
583         
584         return tmpFact;
585     }
586     
587     @Override  
588     protected void mergeValues(TypeFrame otherFrame, TypeFrame resultFrame, int slot) throws DataflowAnalysisException {
589         Type value = typeMerger.mergeTypes(resultFrame.getValue(slot), otherFrame.getValue(slot));
590         resultFrame.setValue(slot, value);
591         
592         // Result type is exact IFF types are identical and both are exact
593         
594         boolean typesAreIdentical =
595             otherFrame.getValue(slot).equals(resultFrame.getValue(slot));
596         
597         boolean bothExact =
598             resultFrame.isExact(slot) && otherFrame.isExact(slot);
599         
600         resultFrame.setExact(slot, typesAreIdentical && bothExact);
601     }
602 
603     /**
604      * Get the cached set of exceptions that can be thrown
605      * from given basic block.  If this information hasn't
606      * been computed yet, then an empty exception set is
607      * returned.
608      *
609      * @param basicBlock the block to get the cached exception set for
610      * @return the CachedExceptionSet for the block
611      */
612     private CachedExceptionSet getCachedExceptionSet(BasicBlock basicBlock) {
613         CachedExceptionSet cachedExceptionSet = thrownExceptionSetMap.get(basicBlock);
614         if (cachedExceptionSet == null) {
615             // When creating the cached exception type set for the first time:
616             // - the block result is set to TOP, so it won't match
617             //   any block result that has actually been computed
618             //   using the analysis transfer function
619             // - the exception set is created as empty (which makes it
620             //   return TOP as its common superclass)
621 
622             TypeFrame top = createFact();
623             makeFactTop(top);
624             cachedExceptionSet = new CachedExceptionSet(top, exceptionSetFactory.createExceptionSet());
625 
626             thrownExceptionSetMap.put(basicBlock, cachedExceptionSet);
627         }
628 
629         return cachedExceptionSet;
630     }
631 
632     /**
633      * Compute the set of exceptions that can be
634      * thrown from the given basic block.
635      * This should only be called if the existing cached
636      * exception set is out of date.
637      *
638      * @param basicBlock the basic block
639      * @param result     the result fact for the block; this is used
640      *                   to determine whether or not the cached exception
641      *                   set is up to date
642      * @return the cached exception set for the block
643      */
644     private CachedExceptionSet computeBlockExceptionSet(BasicBlock basicBlock, TypeFrame result)
645             throws DataflowAnalysisException {
646 
647         ExceptionSet exceptionSet;
648         try {
649             exceptionSet = computeThrownExceptionTypes(basicBlock);
650         } catch (ClassNotFoundException   e) {
651             // Special case: be as conservative as possible
652             // if a class hierarchy lookup fails.
653             lookupFailureCallback.reportMissingClass(e);
654             exceptionSet = exceptionSetFactory.createExceptionSet();
655             exceptionSet.addExplicit(Type.THROWABLE);
656         }
657 
658         TypeFrame copyOfResult = createFact();
659         copy(result, copyOfResult);
660 
661         CachedExceptionSet cachedExceptionSet = new CachedExceptionSet(copyOfResult, exceptionSet);
662         thrownExceptionSetMap.put(basicBlock, cachedExceptionSet);
663 
664         return cachedExceptionSet;
665     }
666 
667     /**
668      * Based on the set of exceptions that can be thrown
669      * from the source basic block,
670      * compute the set of exceptions that can propagate
671      * along given exception edge.  This method should be
672      * called for each outgoing exception edge in sequence,
673      * so the caught exceptions can be removed from the
674      * thrown exception set as needed.
675      *
676      * @param edge               the exception edge
677      * @param thrownExceptionSet current set of exceptions that
678      *                           can be thrown, taking earlier (higher priority)
679      *                           exception edges into account
680      * @return the set of exceptions that can propagate
681      *         along this edge
682      */
683     private ExceptionSet computeEdgeExceptionSet(Edge edge, ExceptionSet thrownExceptionSet) {
684 
685 
686         if (thrownExceptionSet.isEmpty()) return thrownExceptionSet;
687         ExceptionSet result = exceptionSetFactory.createExceptionSet();
688 
689         if (edge.getType() == UNHANDLED_EXCEPTION_EDGE) {
690             // The unhandled exception edge always comes
691             // after all of the handled exception edges.
692             result.addAll(thrownExceptionSet);
693             thrownExceptionSet.clear();
694             return result;
695         }
696 
697         BasicBlock handlerBlock = edge.getTarget();
698         CodeExceptionGen handler = handlerBlock.getExceptionGen();
699         ObjectType catchType = handler.getCatchType();
700 
701         if (Hierarchy.isUniversalExceptionHandler(catchType)) {
702             result.addAll(thrownExceptionSet);
703             thrownExceptionSet.clear();
704         } else {
705             // Go through the set of thrown exceptions.
706             // Any that will DEFINITELY be caught be this handler, remove.
707             // Any that MIGHT be caught, but won't definitely be caught,
708             // remain.
709 
710             for (ExceptionSet.ThrownExceptionIterator i = thrownExceptionSet.iterator(); i.hasNext();) {
711                 //ThrownException thrownException = i.next();
712                 ObjectType thrownType = i.next();
713                 boolean explicit = i.isExplicit();
714 
715                 if (DEBUG)
716                     System.out.println("\texception type " + thrownType +
717                             ", catch type " + catchType);
718 
719                 try {
720                     if (Hierarchy.isSubtype(thrownType, catchType)) {
721                         // Exception can be thrown along this edge
722                         result.add(thrownType, explicit);
723     
724                         // And it will definitely be caught
725                         i.remove();
726 
727                         if (DEBUG)
728                             System.out.println("\tException is subtype of catch type: " +
729                                     "will definitely catch");
730                     } else if (Hierarchy.isSubtype(catchType, thrownType)) {
731                         // Exception possibly thrown along this edge
732                         result.add(thrownType, explicit);
733 
734                         if (DEBUG)
735                             System.out.println("\tException is supertype of catch type: " +
736                                     "might catch");
737                     }
738                 } catch (ClassNotFoundException   e) {
739                     // As a special case, if a class hierarchy lookup
740                     // fails, then we will conservatively assume that the
741                     // exception in question CAN, but WON'T NECESSARILY
742                     // be caught by the handler.
743                     AnalysisContext.reportMissingClass(e);
744                     result.add(thrownType, explicit);
745                 }
746             }
747         }
748 
749         return result;
750     }
751 
752     /**
753      * Compute the set of exception types that can
754      * be thrown by given basic block.
755      *
756      * @param basicBlock the basic block
757      * @return the set of exceptions that can be thrown by the block
758      */
759     private ExceptionSet computeThrownExceptionTypes(BasicBlock basicBlock)
760             throws ClassNotFoundException  , DataflowAnalysisException {
761 
762         ExceptionSet exceptionTypeSet = exceptionSetFactory.createExceptionSet();
763         InstructionHandle pei = basicBlock.getExceptionThrower();
764         Instruction ins = pei.getInstruction();
765 
766         // Get the exceptions that BCEL knows about.
767         // Note that all of these are unchecked.
768         ExceptionThrower exceptionThrower = (ExceptionThrower) ins;
769         Class  [] exceptionList = exceptionThrower.getExceptions();
770         for (Class   aExceptionList : exceptionList) {
771             exceptionTypeSet.addImplicit(ObjectTypeFactory.getInstance(aExceptionList.getName()));
772         }
773 
774         // Assume that an Error may be thrown by any instruction.
775         exceptionTypeSet.addImplicit(Hierarchy.ERROR_TYPE);
776 
777         if (ins instanceof ATHROW) {
778             // For ATHROW instructions, we generate *two* blocks
779             // for which the ATHROW is an exception thrower.
780             //
781             // - The first, empty basic block, does the null check
782             // - The second block, which actually contains the ATHROW,
783             //   throws the object on the top of the operand stack
784             //
785             // We make a special case of the block containing the ATHROW,
786             // by removing all of the implicit exceptions,
787             // and using type information to figure out what is thrown.
788 
789             if (basicBlock.containsInstruction(pei)) {
790                 // This is the actual ATHROW, not the null check
791                 // and implicit exceptions.
792                 exceptionTypeSet.clear();
793 
794                 // The frame containing the thrown value is the start fact
795                 // for the block, because ATHROW is guaranteed to be
796                 // the only instruction in the block.
797                 TypeFrame frame = getStartFact(basicBlock);
798     
799                 // Check whether or not the frame is valid.
800                 // Sun's javac sometimes emits unreachable code.
801                 // For example, it will emit code that follows a JSR
802                 // subroutine call that never returns.
803                 // If the frame is invalid, then we can just make
804                 // a conservative assumption that anything could be
805                 // thrown at this ATHROW.
806                 if (!frame.isValid()) {
807                     exceptionTypeSet.addExplicit(Type.THROWABLE);
808                 } else if (frame.getStackDepth() == 0) {
809                     throw new IllegalStateException  ("empty stack " +
810                             " thrown by " + pei + " in " +
811                             SignatureConverter.convertMethodSignature(methodGen));
812                 } else {
813                     
814                     Type throwType = frame.getTopValue();
815                     if (throwType instanceof ObjectType) {
816                         exceptionTypeSet.addExplicit((ObjectType) throwType);
817                     } else if (throwType instanceof ExceptionObjectType) {
818                         exceptionTypeSet.addAll(((ExceptionObjectType) throwType).getExceptionSet());
819                     } else {
820                         // Not sure what is being thrown here.
821                         // Be conservative.
822                         if (DEBUG) {
823                             System.out.println("Non object type " + throwType +
824                                     " thrown by " + pei + " in " +
825                                     SignatureConverter.convertMethodSignature(methodGen));
826                         }
827                         exceptionTypeSet.addExplicit(Type.THROWABLE);
828                     }
829                 }
830             }
831         }
832 
833         // If it's an InvokeInstruction, add declared exceptions and RuntimeException
834         if (ins instanceof InvokeInstruction) {
835             ConstantPoolGen cpg = methodGen.getConstantPool();
836 
837             InvokeInstruction inv = (InvokeInstruction) ins;
838             ObjectType[] declaredExceptionList = Hierarchy.findDeclaredExceptions(inv, cpg);
839             if (declaredExceptionList == null) {
840                 // Couldn't find declared exceptions,
841                 // so conservatively assume it could thrown any checked exception.
842                 if (DEBUG)
843                     System.out.println("Couldn't find declared exceptions for " +
844                             SignatureConverter.convertMethodSignature(inv, cpg));
845                 exceptionTypeSet.addExplicit(Hierarchy.EXCEPTION_TYPE);
846             } else {
847                 for (ObjectType aDeclaredExceptionList : declaredExceptionList) {
848                     exceptionTypeSet.addExplicit(aDeclaredExceptionList);
849                 }
850             }
851 
852             exceptionTypeSet.addImplicit(Hierarchy.RUNTIME_EXCEPTION_TYPE);
853         }
854 
855         if (DEBUG) System.out.println(pei + " can throw " + exceptionTypeSet);
856 
857         return exceptionTypeSet;
858     }
859 
860     public static void main(String  [] argv) throws Exception   {
861         if (argv.length != 1) {
862             System.err.println("Usage: " + TypeAnalysis.class.getName() + " <class file>");
863             System.exit(1);
864         }
865 
866         DataflowTestDriver<TypeFrame, TypeAnalysis> driver = new DataflowTestDriver<TypeFrame, TypeAnalysis>() {
867             @Override  
868             public Dataflow<TypeFrame, TypeAnalysis> createDataflow(ClassContext classContext, Method method)
869                     throws CFGBuilderException, DataflowAnalysisException {
870                 return classContext.getTypeDataflow(method);
871             }
872         };
873 
874         driver.execute(argv[0]);
875     }
876 }
877 
878 // vim:ts=3
879
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags