ClassContext


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;
21  
22  import java.util.ArrayList  ;
23  import java.util.BitSet  ;
24  import java.util.Collections  ;
25  import java.util.HashMap  ;
26  import java.util.HashSet  ;
27  import java.util.Iterator  ;
28  import java.util.LinkedList  ;
29  import java.util.List  ;
30  import java.util.Set  ;
31  import java.util.TreeSet  ;
32  
33  import org.apache.bcel.Constants;
34  import org.apache.bcel.classfile.Code;
35  import org.apache.bcel.classfile.JavaClass;
36  import org.apache.bcel.classfile.LineNumber;
37  import org.apache.bcel.classfile.LineNumberTable;
38  import org.apache.bcel.classfile.Method;
39  import org.apache.bcel.generic.ClassGen;
40  import org.apache.bcel.generic.ConstantPoolGen;
41  import org.apache.bcel.generic.FieldInstruction;
42  import org.apache.bcel.generic.GETSTATIC;
43  import org.apache.bcel.generic.IFNE;
44  import org.apache.bcel.generic.INVOKESTATIC;
45  import org.apache.bcel.generic.Instruction;
46  import org.apache.bcel.generic.InstructionHandle;
47  import org.apache.bcel.generic.InstructionList;
48  import org.apache.bcel.generic.MethodGen;
49  
50  import edu.umd.cs.findbugs.SystemProperties;
51  import edu.umd.cs.findbugs.annotations.CheckForNull;
52  import edu.umd.cs.findbugs.annotations.NonNull;
53  import edu.umd.cs.findbugs.annotations.Nullable;
54  import edu.umd.cs.findbugs.ba.ca.CallListAnalysis;
55  import edu.umd.cs.findbugs.ba.ca.CallListDataflow;
56  import edu.umd.cs.findbugs.ba.constant.ConstantAnalysis;
57  import edu.umd.cs.findbugs.ba.constant.ConstantDataflow;
58  import edu.umd.cs.findbugs.ba.deref.UnconditionalValueDerefAnalysis;
59  import edu.umd.cs.findbugs.ba.deref.UnconditionalValueDerefDataflow;
60  import edu.umd.cs.findbugs.ba.deref.UnconditionalValueDerefSet;
61  import edu.umd.cs.findbugs.ba.heap.LoadAnalysis;
62  import edu.umd.cs.findbugs.ba.heap.LoadDataflow;
63  import edu.umd.cs.findbugs.ba.heap.StoreAnalysis;
64  import edu.umd.cs.findbugs.ba.heap.StoreDataflow;
65  import edu.umd.cs.findbugs.ba.npe.IsNullValueAnalysis;
66  import edu.umd.cs.findbugs.ba.npe.IsNullValueDataflow;
67  import edu.umd.cs.findbugs.ba.npe.UnconditionalDerefAnalysis;
68  import edu.umd.cs.findbugs.ba.npe.UnconditionalDerefDataflow;
69  import edu.umd.cs.findbugs.ba.npe2.DefinitelyNullSetAnalysis;
70  import edu.umd.cs.findbugs.ba.npe2.DefinitelyNullSetDataflow;
71  import edu.umd.cs.findbugs.ba.type.ExceptionSetFactory;
72  import edu.umd.cs.findbugs.ba.type.TypeAnalysis;
73  import edu.umd.cs.findbugs.ba.type.TypeDataflow;
74  import edu.umd.cs.findbugs.ba.vna.LoadedFieldSet;
75  import edu.umd.cs.findbugs.ba.vna.MergeTree;
76  import edu.umd.cs.findbugs.ba.vna.ValueNumberAnalysis;
77  import edu.umd.cs.findbugs.ba.vna.ValueNumberDataflow;
78  import edu.umd.cs.findbugs.util.MapCache;
79  
80  /**
81   * A ClassContext caches all of the auxiliary objects used to analyze
82   * the methods of a class.  That way, these objects don't need to
83   * be created over and over again.
84   *
85   * @author David Hovemeyer
86   */
87  public class ClassContext {
88      public static final boolean DEBUG = SystemProperties.getBoolean("classContext.debug");
89  
90      private static final int PRUNED_INFEASIBLE_EXCEPTIONS = 1;
91      private static final int PRUNED_UNCONDITIONAL_THROWERS = 2;
92      private static final int REFINED = 4;
93  
94      private static final boolean TIME_ANALYSES = SystemProperties.getBoolean("classContext.timeAnalyses");
95  
96      private static final boolean DEBUG_CFG = SystemProperties.getBoolean("classContext.debugCFG");
97      private static final boolean DUMP_DATAFLOW_ANALYSIS = SystemProperties.getBoolean("dataflow.dump");
98  
99      /* ----------------------------------------------------------------------
100      * Helper classes
101      * ---------------------------------------------------------------------- */
102     
103     /**
104      * Unpacked code for a method.
105      * Contains set of all opcodes in the method, as well as a map
106      * of bytecode offsets to opcodes.
107      */
108     private static class UnpackedCode {
109         private BitSet   bytecodeSet;
110         private short[] offsetToBytecodeMap;
111         public UnpackedCode(BitSet   bytecodeSet, short[] offsetToBytecodeMap) {
112             this.bytecodeSet = bytecodeSet;
113             this.offsetToBytecodeMap = offsetToBytecodeMap;
114         }
115         
116         /**
117          * @return Returns the bytecodeSet.
118          */
119         public BitSet   getBytecodeSet() {
120             return bytecodeSet;
121         }
122         
123         /**
124          * @return Returns the offsetToBytecodeMap.
125          */
126         public short[] getOffsetToBytecodeMap() {
127             return offsetToBytecodeMap;
128         }
129     }
130 
131     private static int depth;
132 
133     private static void indent() {
134         for (int i = 0; i < depth; ++i) System.out.print("  ");
135     }
136     
137     /**
138      * An AnalysisResult stores the result of requesting an analysis
139      * from an AnalysisFactory.  It can represent a successful outcome
140      * (where the Analysis object can be returned), or an unsuccessful
141      * outcome (where an exception was thrown trying to create the
142      * analysis).  For unsuccessful outcomes, we rethrow the original
143      * exception rather than making another attempt to create the analysis
144      * (since if it fails once, it will never succeed). 
145      */
146     private static class AnalysisResult<Analysis> {
147         private boolean analysisSetExplicitly;
148         private Analysis analysis;
149         private AnalysisException analysisException;
150         private CFGBuilderException cfgBuilderException;
151         private DataflowAnalysisException dataflowAnalysisException;
152         
153         public Analysis getAnalysis() throws CFGBuilderException, DataflowAnalysisException {
154             if (analysisSetExplicitly)
155                 return analysis;
156             if (dataflowAnalysisException != null)
157                 throw dataflowAnalysisException;
158             if (analysisException != null)
159                 throw analysisException;
160             if (cfgBuilderException != null)
161                 throw cfgBuilderException;
162             throw new IllegalStateException  ();
163         }
164         
165         /**
166          * Record a successful outcome, where the analysis was created.
167          * 
168          * @param analysis the Analysis
169          */
170         public void setAnalysis(@Nullable Analysis analysis) {
171             this.analysisSetExplicitly = true;
172             this.analysis = analysis;
173         }
174         
175         /**
176          * Record that an AnalysisException occurred while attempting
177          * to create the Analysis.
178          * 
179          * @param analysisException the AnalysisException
180          */
181         public void setAnalysisException(AnalysisException analysisException) {
182             this.analysisException = analysisException;
183         }
184         
185         /**
186          * Record that a CFGBuilderException occurred while attempting
187          * to create the Analysis.
188          * 
189          * @param cfgBuilderException the CFGBuilderException
190          */
191         public void setCFGBuilderException(CFGBuilderException cfgBuilderException) {
192             this.cfgBuilderException = cfgBuilderException;
193         }
194         
195         /**
196          * Record that a DataflowAnalysisException occurred while attempting
197          * to create the Analysis.
198          *  
199          * @param dataflowException the DataflowAnalysisException
200          */
201         public void setDataflowAnalysisException(DataflowAnalysisException dataflowException) {
202             this.dataflowAnalysisException = dataflowException;
203         }
204     }
205 
206     /**
207      * Abstract factory class for creating analysis objects.
208      * Handles caching of analysis results for a method.
209      */
210     private abstract class AnalysisFactory <Analysis> {
211         private String   analysisName;
212         private HashMap  <Method, AnalysisResult<Analysis>> map =
213             new HashMap  <Method, ClassContext.AnalysisResult<Analysis>>();
214 
215         /**
216          * Constructor.
217          * 
218          * @param analysisName name of the analysis factory: for diagnostics/debugging
219          */
220         public AnalysisFactory(String   analysisName) {
221             this.analysisName = analysisName;
222             
223             analysisFactoryList.add(this);
224         }
225 
226         /**
227          * Get the Analysis for given method.
228          * If Analysis has already been performed, the cached result is
229          * returned.
230          * 
231          * @param method the method to analyze
232          * @return the Analysis object representing the result of analyzing the method
233          * @throws CFGBuilderException       if the CFG can't be constructed for the method
234          * @throws DataflowAnalysisException if dataflow analysis fails on the method
235          */
236         @CheckForNull public Analysis getAnalysis(Method method) throws CFGBuilderException, DataflowAnalysisException {
237             AnalysisResult<Analysis> result = map.get(method);
238             if (result == null) {
239                 if (TIME_ANALYSES) {
240                     ++depth;
241                     indent();
242                     System.out.println("CC: Starting " + analysisName + " for " +
243                             SignatureConverter.convertMethodSignature(jclass, method) + ":");
244                 }
245 
246                 long begin = System.currentTimeMillis();
247                 
248                 // Create a new AnalysisResult
249                 result = new AnalysisResult<Analysis>();
250 
251                 // Attempt to create the Analysis and store it in the AnalysisResult.
252                 // If an exception occurs, record it in the AnalysisResult.
253                 Analysis analysis;
254                 try {
255                     analysis = analyze(method);
256                     result.setAnalysis(analysis);
257                 } catch (CFGBuilderException e) {
258                     result.setCFGBuilderException(e);
259                 } catch (DataflowAnalysisException e) {
260                     result.setDataflowAnalysisException(e);
261                 } catch (AnalysisException e) {
262                     result.setAnalysisException(e);
263                 }
264 
265                 if (TIME_ANALYSES) {
266                     long end = System.currentTimeMillis();
267                     indent();
268                     System.out.println("CC: finished " + analysisName + " in " + (end - begin) + " millis");
269                     --depth;
270                 }
271 
272                 // Cache the outcome of this analysis attempt.
273                 map.put(method, result);
274             }
275             
276             return result.getAnalysis();
277         }
278 
279         @CheckForNull protected abstract Analysis analyze(Method method)
280                 throws CFGBuilderException, DataflowAnalysisException;
281 
282         /**
283          * @return true if this analysis factory is a dataflow analysis,
284          *          false if not
285          */
286         public abstract boolean isDataflow();
287 
288         /**
289          * Purge result for given method.
290          * 
291          * @param method the method whose analysis result should purged 
292          */
293         public void purge(Method method) {
294             map.remove(method);
295         }
296     }
297 
298     private abstract class NoExceptionAnalysisFactory <Analysis> extends AnalysisFactory<Analysis> {
299         public NoExceptionAnalysisFactory(String   analysisName) {
300             super(analysisName);
301         }
302 
303         @Override  
304         public Analysis getAnalysis(Method method) {
305             try {
306                 return super.getAnalysis(method);
307             } catch (DataflowAnalysisException e) {
308                 throw new IllegalStateException  ("Should not happen");
309             } catch (CFGBuilderException e) {
310                 throw new IllegalStateException  ("Should not happen");
311             }
312         }
313         
314         /* (non-Javadoc)
315          * @see edu.umd.cs.findbugs.ba.ClassContext.AnalysisFactory#isDataflow()
316          */
317         @Override  
318         public boolean isDataflow() {
319             return false;
320         }
321     }
322 
323     private abstract class NoDataflowAnalysisFactory <Analysis> extends AnalysisFactory<Analysis> {
324         public NoDataflowAnalysisFactory(String   analysisName) {
325             super(analysisName);
326         }
327 
328         @Override  
329         public Analysis getAnalysis(Method method) throws CFGBuilderException {
330             try {
331                 return super.getAnalysis(method);
332             } catch (DataflowAnalysisException e) {
333                 throw new IllegalStateException  ("Should not happen");
334             }
335         }
336         
337         /* (non-Javadoc)
338          * @see edu.umd.cs.findbugs.ba.ClassContext.AnalysisFactory#isDataflow()
339          */
340         @Override  
341         public boolean isDataflow() {
342             return false;
343         }
344     }
345 
346     private final Set  <String  > busyCFGSet = new HashSet  <String  >();
347 
348     private class CFGFactory extends AnalysisFactory<CFG> {
349 
350         public CFGFactory() {
351             super("CFG construction");
352         }
353 
354         @Override  
355         public CFG getAnalysis(Method method) throws CFGBuilderException {
356             try {
357                 return super.getAnalysis(method);
358             } catch (DataflowAnalysisException e) {
359                 throw new IllegalStateException  ("Should not happen");
360             }
361         }
362 
363         public CFG getRawCFG(Method method) throws CFGBuilderException {
364             return getAnalysis(method);
365         }
366 
367         public CFG getRefinedCFG(Method method) throws CFGBuilderException {
368             CFG cfg = getRawCFG(method);
369             if (cfg.isFlagSet(REFINED)) return cfg;
370             
371             MethodGen methodGen = getMethodGen(method);
372             if (methodGen == null) {
373                 JavaClassAndMethod javaClassAndMethod = new JavaClassAndMethod(jclass, method);
374                 getLookupFailureCallback().reportSkippedAnalysis(javaClassAndMethod.toMethodDescriptor());
375                 throw new MethodUnprofitableException(javaClassAndMethod);
376             }
377 
378             // Record method name and signature for informational purposes
379             cfg.setMethodName(SignatureConverter.convertMethodSignature(methodGen));
380             cfg.setMethodGen(methodGen);
381             
382             // HACK:
383             // Due to recursive method invocations, we may get a recursive
384             // request for the pruned CFG of a method.  In this case,
385             // we just return the raw CFG.
386             String   methodId = methodGen.getClassName() + "." + methodGen.getName() + ":" + methodGen.getSignature();
387             // System.out.println("CC: getting refined CFG for " + methodId);
388             if (DEBUG_CFG) {
389                 indent();
390                 System.out.println("CC: getting refined CFG for " + methodId);
391             }
392             if (DEBUG) System.out.println("ClassContext: request to prune " + methodId);
393             if (!busyCFGSet.add(methodId))
394                 return cfg;
395 
396             cfg.setFlags(REFINED);
397             
398             boolean changed = false;
399             boolean ASSUME_ASSERTIONS_ENABLED = true;
400             if (ASSUME_ASSERTIONS_ENABLED) {
401                 LinkedList  <Edge> edgesToRemove = new LinkedList  <Edge>();
402                 for (Iterator  <Edge> i = cfg.edgeIterator(); i.hasNext();) {
403                     Edge e = i.next();
404                     if (e.getType() == EdgeTypes.IFCMP_EDGE) {
405                         try {
406                             BasicBlock source = e.getSource();
407                             InstructionHandle last = source
408                                     .getLastInstruction();
409                             Instruction lastInstruction = last.getInstruction();
410                             InstructionHandle prev = last.getPrev();
411                             Instruction prevInstruction = prev.getInstruction();
412                             if (prevInstruction instanceof GETSTATIC
413                                     && lastInstruction instanceof IFNE) {
414                                 GETSTATIC getStatic = (GETSTATIC) prevInstruction;
415                                 if (false) {
416                                     System.out.println(prev);
417 
418                                     System.out.println(getStatic
419                                             .getClassName(methodGen
420                                                     .getConstantPool()));
421                                     System.out.println(getStatic
422                                             .getFieldName(methodGen
423                                                     .getConstantPool()));
424                                     System.out.println(getStatic
425                                             .getSignature(methodGen
426                                                     .getConstantPool()));
427                                     System.out.println(last);
428                                 }
429                                 if (getStatic.getFieldName(
430                                         methodGen.getConstantPool()).equals(
431                                         "$assertionsDisabled")
432                                         && getStatic.getSignature(
433                                                 methodGen.getConstantPool())
434                                                 .equals("Z"))
435                                     edgesToRemove.add(e);
436                             }
437                         } catch (RuntimeException   exception) {
438                             assert true; // ignore it
439                         }
440                     }
441                 }
442                 for (Edge e : edgesToRemove) {
443                     cfg.removeEdge(e);
444                 }
445             }
446             
447             final boolean PRUNE_INFEASIBLE_EXCEPTION_EDGES =
448                 analysisContext.getBoolProperty(AnalysisFeatures.ACCURATE_EXCEPTIONS);
449         
450             if (PRUNE_INFEASIBLE_EXCEPTION_EDGES && !cfg.isFlagSet(PRUNED_INFEASIBLE_EXCEPTIONS)) {
451                 try {
452                     TypeDataflow typeDataflow = getTypeDataflow(method);
453                     // Exception edge pruning based on ExceptionSets.
454                     // Note: this is quite slow.
455                     PruneInfeasibleExceptionEdges pruner =
456                         new PruneInfeasibleExceptionEdges(cfg, methodGen, typeDataflow);
457                     pruner.execute();
458                     changed  = changed || pruner.wasCFGModified();
459                 } catch (DataflowAnalysisException e) {
460                     // FIXME: should report the error
461                 } catch (ClassNotFoundException   e) {
462                     getLookupFailureCallback().reportMissingClass(e);
463                 }
464             }
465             cfg.setFlags(cfg.getFlags() | PRUNED_INFEASIBLE_EXCEPTIONS);
466             
467             final boolean PRUNE_UNCONDITIONAL_EXCEPTION_THROWER_EDGES =
468                 !analysisContext.getBoolProperty(AnalysisFeatures.CONSERVE_SPACE);
469 
470             if (PRUNE_UNCONDITIONAL_EXCEPTION_THROWER_EDGES && !cfg.isFlagSet(PRUNED_UNCONDITIONAL_THROWERS)) {
471                 try {
472                     PruneUnconditionalExceptionThrowerEdges pruner =
473                         new PruneUnconditionalExceptionThrowerEdges(methodGen, cfg, getConstantPoolGen(), analysisContext);
474                     pruner.execute();
475                     changed = changed || pruner.wasCFGModified();
476                 } catch (DataflowAnalysisException e) {
477                     // FIXME: should report the error
478                 }
479             }
480             cfg.setFlags(cfg.getFlags() | PRUNED_UNCONDITIONAL_THROWERS);
481             
482             if (changed) {
483                 ClassContext.this.purgeAnalysisResultsAfterCFGPruning(method);
484             }
485 
486             busyCFGSet.remove(methodId);
487 
488             return cfg;
489         }
490 
491         @Override  
492         protected CFG analyze(Method method) throws CFGBuilderException {
493             MethodGen methodGen = getMethodGen(method);
494             if (methodGen == null) {
495                 JavaClassAndMethod javaClassAndMethod = new JavaClassAndMethod(jclass, method);
496                 getLookupFailureCallback().reportSkippedAnalysis(javaClassAndMethod.toMethodDescriptor());
497                 throw new MethodUnprofitableException(javaClassAndMethod);
498             }
499             CFGBuilder cfgBuilder = CFGBuilderFactory.create(methodGen);
500             cfgBuilder.build();
501             return cfgBuilder.getCFG();
502         }
503         
504         /* (non-Javadoc)
505          * @see edu.umd.cs.findbugs.ba.ClassContext.AnalysisFactory#isDataflow()
506          */
507         @Override  
508         public boolean isDataflow() {
509             return false;
510         }
511     }
512     
513     private abstract class DataflowAnalysisFactory<Analysis>
514         extends AnalysisFactory<Analysis> {
515         
516         DataflowAnalysisFactory(String   desc) {
517             super(desc);
518         }
519         
520         /* (non-Javadoc)
521          * @see edu.umd.cs.findbugs.ba.ClassContext.AnalysisFactory#isDataflow()
522          */
523         @Override  
524         public boolean isDataflow() {
525             return true;
526         }
527     }
528 
529     /* ----------------------------------------------------------------------
530      * Fields
531      * ---------------------------------------------------------------------- */
532 
533     private JavaClass jclass;
534     private AnalysisContext analysisContext;
535     
536     // List of all analysis factories.
537     private List  <AnalysisFactory<?>> analysisFactoryList =
538         new LinkedList  <AnalysisFactory<?>>();
539 
540     
541     private NoExceptionAnalysisFactory<MethodGen> methodGenFactory =
542         new NoExceptionAnalysisFactory<MethodGen>("MethodGen construction") {
543         @CheckForNull
544         @Override  
545         protected MethodGen analyze(Method method) {
546             if (method.getCode() == null)
547                 return null;
548             String   methodName = method.getName();
549             if (analysisContext.getBoolProperty(AnalysisFeatures.SKIP_HUGE_METHODS)) {
550                 int codeLength = method.getCode().getLength();
551                 if (codeLength > 3000 
552                         || (methodName.equals("<clinit>") || methodName.equals("getContents")) && codeLength > 1000) {
553                     getLookupFailureCallback().reportSkippedAnalysis(new JavaClassAndMethod(jclass, method).toMethodDescriptor());
554                     return null;
555                 }
556             }
557             return  new MethodGen(method, jclass.getClassName(), getConstantPoolGen());
558 
559         }
560     };
561 
562     private CFGFactory cfgFactory = new CFGFactory();
563 
564     private AnalysisFactory<ValueNumberDataflow> vnaDataflowFactory =
565             new DataflowAnalysisFactory<ValueNumberDataflow>("value number analysis") {
566                 @Override  
567                 protected ValueNumberDataflow analyze(Method method) throws DataflowAnalysisException, CFGBuilderException {
568                     MethodGen methodGen = getMethodGen(method);
569                     if (methodGen == null) throw new MethodUnprofitableException(getJavaClass(),method);
570                     DepthFirstSearch dfs = getDepthFirstSearch(method);
571                     LoadedFieldSet loadedFieldSet = getLoadedFieldSet(method);
572                     ValueNumberAnalysis analysis = new ValueNumberAnalysis(methodGen, dfs, loadedFieldSet,
573                             getLookupFailureCallback());
574                     analysis.setMergeTree(new MergeTree(analysis.getFactory()));
575                     CFG cfg = getCFG(method);
576                     
577                     ValueNumberDataflow vnaDataflow = new ValueNumberDataflow(cfg, analysis);
578                     vnaDataflow.execute();
579                     if (DUMP_DATAFLOW_ANALYSIS) {
580                         TreeSet  <Location> tree = new TreeSet  <Location>();
581                         for(Iterator  <Location> locs = cfg.locationIterator(); locs.hasNext(); ) {
582                             Location loc = locs.next();
583                             tree.add(loc);
584                         }
585                         System.out.println("\n\nValue number analysis for " + method.getName() + " {");
586                         for(Location loc : tree) {
587                             System.out.println("\nBefore: " + vnaDataflow.getFactAtLocation(loc));
588                             System.out.println("Location: " + loc);
589                             System.out.println("After: " + vnaDataflow.getFactAfterLocation(loc));  
590                         }
591                         System.out.println("}\n");
592                     }
593                     return vnaDataflow;
594                 }
595             };
596 
597     private AnalysisFactory<IsNullValueDataflow> invDataflowFactory =
598             new DataflowAnalysisFactory<IsNullValueDataflow>("null value analysis") {
599                 @Override  
600                    protected IsNullValueDataflow analyze(Method method) throws DataflowAnalysisException, CFGBuilderException {
601                     MethodGen methodGen = getMethodGen(method);
602                     if (methodGen == null) throw new MethodUnprofitableException(getJavaClass(),method);
603                     CFG cfg = getCFG(method);
604                     ValueNumberDataflow vnaDataflow = getValueNumberDataflow(method);
605                     DepthFirstSearch dfs = getDepthFirstSearch(method);
606                     AssertionMethods assertionMethods = getAssertionMethods();
607 
608                     IsNullValueAnalysis invAnalysis = new IsNullValueAnalysis(methodGen, cfg, vnaDataflow, dfs, assertionMethods);
609 
610                     // Set return value and parameter databases
611 
612                     invAnalysis.setClassAndMethod(new JavaClassAndMethod(getJavaClass(), method));
613                     
614                     IsNullValueDataflow invDataflow = new IsNullValueDataflow(cfg, invAnalysis);
615                     invDataflow.execute();
616                     if (DUMP_DATAFLOW_ANALYSIS) {
617                         TreeSet  <Location> tree = new TreeSet  <Location>();
618                         for(Iterator  <Location> locs = cfg.locationIterator(); locs.hasNext(); ) {
619                             Location loc = locs.next();
620                             tree.add(loc);
621                         }
622                         System.out.println("\n\nInv analysis for " + method.getName() + " {");
623                         for(Location loc : tree) {
624                             System.out.println("\nBefore: " + invDataflow.getFactAtLocation(loc));
625                             System.out.println("Location: " + loc);
626                             System.out.println("After: " + invDataflow.getFactAfterLocation(loc));  
627                         }
628                         System.out.println("}\n");
629                     }
630                     return invDataflow;
631                 }
632             };
633 
634     private AnalysisFactory<TypeDataflow> typeDataflowFactory =
635             new DataflowAnalysisFactory<TypeDataflow>("type analysis") {
636                 @Override  
637                 protected TypeDataflow analyze(Method method) throws DataflowAnalysisException, CFGBuilderException {
638                     MethodGen methodGen = getMethodGen(method);
639                     if (methodGen == null) throw new MethodUnprofitableException(getJavaClass(),method);
640                     CFG cfg = getRawCFG(method);
641                     DepthFirstSearch dfs = getDepthFirstSearch(method);
642                     ExceptionSetFactory exceptionSetFactory = getExceptionSetFactory(method);
643 
644                     TypeAnalysis typeAnalysis =
645                             new TypeAnalysis(methodGen, cfg, dfs, getLookupFailureCallback(), exceptionSetFactory);
646                     
647                     if (analysisContext.getBoolProperty(AnalysisFeatures.MODEL_INSTANCEOF)) {
648                         typeAnalysis.setValueNumberDataflow(getValueNumberDataflow(method));
649                     }
650                     
651                     // Field store type database.
652                     // If present, this can give us more accurate type information
653                     // for values loaded from fields.
654                     typeAnalysis.setFieldStoreTypeDatabase(analysisContext.getFieldStoreTypeDatabase());
655                     
656                     TypeDataflow typeDataflow = new TypeDataflow(cfg, typeAnalysis);
657                     typeDataflow.execute();
658                     if (TypeAnalysis.DEBUG) {
659                         dumpTypeDataflow(method, cfg, typeDataflow);
660                     }
661 
662                     return typeDataflow;
663                 }
664             };
665 
666     private NoDataflowAnalysisFactory<DepthFirstSearch> dfsFactory =
667             new NoDataflowAnalysisFactory<DepthFirstSearch>("depth first search") {
668                 @Override  
669                 protected DepthFirstSearch analyze(Method method) throws CFGBuilderException {
670                     CFG cfg = getRawCFG(method);
671                     DepthFirstSearch dfs = new DepthFirstSearch(cfg);
672                     dfs.search();
673                     return dfs;
674                 }
675             };
676 
677     private NoDataflowAnalysisFactory<ReverseDepthFirstSearch> rdfsFactory =
678             new NoDataflowAnalysisFactory<ReverseDepthFirstSearch>("reverse depth first search") {
679                 @Override  
680                 protected ReverseDepthFirstSearch analyze(Method method) throws CFGBuilderException {
681                     CFG cfg = getRawCFG(method);
682                     ReverseDepthFirstSearch rdfs = new ReverseDepthFirstSearch(cfg);
683                     rdfs.search();
684                     return rdfs;
685                 }
686             };
687     private static class UnpackedBytecodeCallback implements BytecodeScanner.Callback {
688         private BitSet   bytecodeSet;
689         private short[] offsetToOpcodeMap;
690         
691         public UnpackedBytecodeCallback(int codeSize) {
692             this.bytecodeSet = new BitSet  ();
693             this.offsetToOpcodeMap = new short[codeSize];
694         }
695         
696         /* (non-Javadoc)
697          * @see edu.umd.cs.findbugs.ba.BytecodeScanner.Callback#handleInstruction(int, int)
698          */
699         public void handleInstruction(int opcode, int index) {
700             bytecodeSet.set(opcode);
701             offsetToOpcodeMap[index] = (short) opcode;
702         }
703         
704         public UnpackedCode getUnpackedCode() {
705             return new UnpackedCode(bytecodeSet, offsetToOpcodeMap);
706         }
707     }
708 
709     private NoExceptionAnalysisFactory<UnpackedCode> unpackedCodeFactory =
710             new NoExceptionAnalysisFactory<UnpackedCode>("unpacked bytecode") {
711                 @Override  
712                          protected UnpackedCode analyze(Method method) {
713 
714                     Code code = method.getCode();
715                     if (code == null)
716                         return null;
717 
718                     byte[] instructionList = code.getCode();
719 
720                     // Create callback
721                     UnpackedBytecodeCallback callback = new UnpackedBytecodeCallback(instructionList.length);
722 
723                     // Scan the method.
724                     BytecodeScanner scanner = new BytecodeScanner();
725                     scanner.scan(instructionList, callback);
726 
727                     return callback.getUnpackedCode();
728                 }
729             };
730 
731     private AnalysisFactory<LockDataflow> lockDataflowFactory =
732             new DataflowAnalysisFactory<LockDataflow>("lock set analysis") {
733                 @Override  
734                          protected LockDataflow analyze(Method method) throws DataflowAnalysisException, CFGBuilderException {
735                     MethodGen methodGen = getMethodGen(method);
736                     if (methodGen == null) throw new MethodUnprofitableException(getJavaClass(),method);
737                     ValueNumberDataflow vnaDataflow = getValueNumberDataflow(method);
738                     DepthFirstSearch dfs = getDepthFirstSearch(method);
739                     CFG cfg = getCFG(method);
740 
741                     LockAnalysis analysis = new LockAnalysis(methodGen, vnaDataflow, dfs);
742                     LockDataflow dataflow = new LockDataflow(cfg, analysis);
743                     dataflow.execute();
744                     return dataflow;
745                 }
746             };
747 
748     private AnalysisFactory<LockChecker> lockCheckerFactory =
749             new DataflowAnalysisFactory<LockChecker>("lock checker meta-analysis") {
750                 /* (non-Javadoc)
751                  * @see edu.umd.cs.findbugs.ba.ClassContext.AnalysisFactory#analyze(org.apache.bcel.classfile.Method)
752                  */
753                 @Override  
754                                  protected LockChecker analyze(Method method) throws CFGBuilderException,
755                         DataflowAnalysisException {
756                     LockChecker lockChecker = new LockChecker(ClassContext.this, method);
757                     lockChecker.execute();
758                     return lockChecker;
759                 }
760             };
761             
762     private AnalysisFactory<ReturnPathDataflow> returnPathDataflowFactory =
763             new DataflowAnalysisFactory<ReturnPathDataflow>("return path analysis") {
764                 @Override  
765                          protected ReturnPathDataflow analyze(Method method) throws DataflowAnalysisException, CFGBuilderException {
766                     CFG cfg = getCFG(method);
767                     DepthFirstSearch dfs = getDepthFirstSearch(method);
768                     ReturnPathAnalysis analysis = new ReturnPathAnalysis(dfs);
769                     ReturnPathDataflow dataflow = new ReturnPathDataflow(cfg, analysis);
770                     dataflow.execute();
771                     return dataflow;
772                 }
773             };
774 
775     private AnalysisFactory<DominatorsAnalysis> nonExceptionDominatorsAnalysisFactory =
776             new DataflowAnalysisFactory<DominatorsAnalysis>("non-exception dominators analysis") {
777                 @Override  
778                          protected DominatorsAnalysis analyze(Method method) throws DataflowAnalysisException, CFGBuilderException {
779                     CFG cfg = getCFG(method);
780                     DepthFirstSearch dfs = getDepthFirstSearch(method);
781                     DominatorsAnalysis analysis = new DominatorsAnalysis(cfg, dfs, true);
782                     Dataflow<java.util.BitSet  , DominatorsAnalysis> dataflow =
783                             new Dataflow<java.util.BitSet  , DominatorsAnalysis>(cfg, analysis);
784                     dataflow.execute();
785                     return analysis;
786                 }
787             };
788 
789     private AnalysisFactory<PostDominatorsAnalysis> nonExceptionPostDominatorsAnalysisFactory =
790             new DataflowAnalysisFactory<PostDominatorsAnalysis>("non-exception postdominators analysis") {
791                 @Override  
792                          protected PostDominatorsAnalysis analyze(Method method) throws DataflowAnalysisException, CFGBuilderException {
793                     CFG cfg = getCFG(method);
794                     ReverseDepthFirstSearch rdfs = getReverseDepthFirstSearch(method);
795                     PostDominatorsAnalysis analysis = new PostDominatorsAnalysis(cfg, rdfs, getDepthFirstSearch(method), true);
796                     Dataflow<java.util.BitSet  , PostDominatorsAnalysis> dataflow =
797                             new Dataflow<java.util.BitSet  , PostDominatorsAnalysis>(cfg, analysis);
798                     dataflow.execute();
799                     return analysis;
800                 }
801             };
802 
803     private AnalysisFactory<PostDominatorsAnalysis> nonImplicitExceptionPostDominatorsAnalysisFactory =
804         new DataflowAnalysisFactory<PostDominatorsAnalysis>("non-implicit-exception postdominators analysis") {
805             @Override  
806                          protected PostDominatorsAnalysis analyze(Method method) throws CFGBuilderException, DataflowAnalysisException {
807                 CFG cfg = getCFG(method);
808                 PostDominatorsAnalysis analysis = new PostDominatorsAnalysis(
809                         cfg,
810                         getReverseDepthFirstSearch(method),
811                         getDepthFirstSearch(method), new EdgeChooser() {
812                     public boolean choose(Edge edge) {
813                         return !edge.isExceptionEdge()
814                             ||  edge.isFlagSet(EdgeTypes.EXPLICIT_EXCEPTIONS_FLAG);
815                         }
816                     }
817                 );
818                 Dataflow<BitSet  , PostDominatorsAnalysis> dataflow =
819                     new Dataflow<BitSet  , PostDominatorsAnalysis>(cfg, analysis);
820                 dataflow.execute();
821                 
822                 return analysis;
823             }
824         };
825             
826     private NoExceptionAnalysisFactory<ExceptionSetFactory> exceptionSetFactoryFactory =
827             new NoExceptionAnalysisFactory<ExceptionSetFactory>("exception set factory") {
828                 @Override  
829                          protected ExceptionSetFactory analyze(Method method) {
830                     return new ExceptionSetFactory();
831                 }
832             };
833 
834     private NoExceptionAnalysisFactory<String  []> parameterSignatureListFactory =
835             new NoExceptionAnalysisFactory<String  []>("parameter signature list factory") {
836                 @Override  
837                          protected String  [] analyze(Method method) {
838                     SignatureParser parser = new SignatureParser(method.getSignature());
839                     ArrayList  <String  > resultList = new ArrayList  <String  >();
840                     for (Iterator  <String  > i = parser.parameterSignatureIterator(); i.hasNext();) {
841                         resultList.add(i.next());
842                     }
843                     return resultList.toArray(new String  [resultList.size()]);
844                 }
845             };
846 
847     private AnalysisFactory<ConstantDataflow> constantDataflowFactory =
848         new DataflowAnalysisFactory<ConstantDataflow>("constant propagation analysis") {
849             @Override   @CheckForNull
850             protected ConstantDataflow analyze(Method method) throws CFGBuilderException, DataflowAnalysisException {
851                 MethodGen methodGen = getMethodGen(method);
852                 if (methodGen == null) return null;
853                 ConstantAnalysis analysis = new ConstantAnalysis(
854                     methodGen,
855                     getDepthFirstSearch(method)
856                 );
857                 ConstantDataflow dataflow = new ConstantDataflow(getCFG(method), analysis);
858                 dataflow.execute();
859                 
860                 return dataflow;
861             }
862         };
863 
864 //  private AnalysisFactory<UnconditionalDerefDataflow> unconditionalDerefDataflowFactory =
865 //      new DataflowAnalysisFactory<UnconditionalDerefDataflow>("unconditional deref analysis") {
866 //          @Override @CheckForNull
867 //          protected UnconditionalDerefDataflow analyze(Method method) throws CFGBuilderException, DataflowAnalysisException {
868 //              MethodGen methodGen = getMethodGen(method);
869 //              if (methodGen == null)
870 //                  return null;
871 //              CFG cfg = getCFG(method); 
872 //              
873 //  
874 //              UnconditionalDerefAnalysis analysis = new UnconditionalDerefAnalysis(
875 //                      getReverseDepthFirstSearch(method),
876 //                      getDepthFirstSearch(method),
877 //                      cfg,
878 //                      methodGen,
879 //                      getValueNumberDataflow(method),
880 //                      getTypeDataflow(method));
881 //              UnconditionalDerefDataflow dataflow = new UnconditionalDerefDataflow(cfg, analysis);
882 //              
883 //              dataflow.execute();
884 //              
885 //              return dataflow;
886 //          }
887 //      };
888     
889     private AnalysisFactory<LoadDataflow> loadDataflowFactory =
890         new DataflowAnalysisFactory<LoadDataflow>("field load analysis") {
891             @Override   @CheckForNull
892             protected LoadDataflow analyze(Method method) throws CFGBuilderException, DataflowAnalysisException {
893                 MethodGen methodGen = getMethodGen(method);
894                 if (methodGen == null)
895                     return null;
896                 LoadAnalysis analysis = new LoadAnalysis(
897                         getDepthFirstSearch(method),
898                         getConstantPoolGen()
899                         );
900                 LoadDataflow dataflow = new LoadDataflow(getCFG(method), analysis);
901                 dataflow.execute();
902                 return dataflow;
903             }
904         };
905 
906     private AnalysisFactory<StoreDataflow> storeDataflowFactory =
907         new DataflowAnalysisFactory<StoreDataflow>("field store analysis") {
908             @Override   @CheckForNull
909             protected StoreDataflow analyze(Method method) throws CFGBuilderException, DataflowAnalysisException {
910                 MethodGen methodGen = getMethodGen(method);
911                 if (methodGen == null)
912                     return null;
913                 StoreAnalysis analysis = new StoreAnalysis(
914                         getDepthFirstSearch(method),
915                         getConstantPoolGen()
916                         );
917                 StoreDataflow dataflow = new StoreDataflow(getCFG(method), analysis);
918                 dataflow.execute();
919                 return dataflow;
920             }
921         };
922         
923     private static final BitSet   fieldInstructionOpcodeSet = new BitSet  ();
924     static {
925         fieldInstructionOpcodeSet.set(Constants.GETFIELD);
926         fieldInstructionOpcodeSet.set(Constants.PUTFIELD);
927         fieldInstructionOpcodeSet.set(Constants.GETSTATIC);
928         fieldInstructionOpcodeSet.set(Constants.PUTSTATIC);
929     }
930 
931     /**
932      * Factory to determine which fields are loaded and stored
933      * by the instructions in a method, and the overall method.
934      * The main purpose is to support efficient redundant load elimination
935      * and forward substitution in ValueNumberAnalysis (there is no need to
936      * remember stores of fields that are never read,
937      * or loads of fields that are only loaded in one location).
938      * However, it might be useful for other kinds of analysis.
939      *
940      * <p> The tricky part is that in addition to fields loaded and stored
941      * with get/putfield and get/putstatic, we also try to figure
942      * out field accessed through calls to inner-class access methods.
943      */
944     private NoExceptionAnalysisFactory<LoadedFieldSet> loadedFieldSetFactory =
945             new NoExceptionAnalysisFactory<LoadedFieldSet>("loaded field set factory") {
946                 @Override  
947                                  protected LoadedFieldSet analyze(Method method) {
948                     MethodGen methodGen = getMethodGen(method);
949                     if (methodGen == null) return null;
950                     InstructionList il = methodGen.getInstructionList();
951 
952                     LoadedFieldSet loadedFieldSet = new LoadedFieldSet(methodGen);
953 
954                     for (InstructionHandle handle = il.getStart(); handle != null; handle = handle.getNext()) {
955                         Instruction ins = handle.getInstruction();
956                         short opcode = ins.getOpcode();
957                         try {
958                             if (opcode == Constants.INVOKESTATIC) {
959                                 INVOKESTATIC inv = (INVOKESTATIC) ins;
960                                 if (Hierarchy.isInnerClassAccess(inv, getConstantPoolGen())) {
961                                     InnerClassAccess access = Hierarchy.getInnerClassAccess(inv, getConstantPoolGen());
962 /*
963                                     if (access == null) {
964                                         System.out.println("Missing inner class access in " +
965                                             SignatureConverter.convertMethodSignature(methodGen) + " at " +
966                                             inv);
967                                     }
968 */
969                                     if (access != null) {
970                                         if (access.isLoad())
971                                             loadedFieldSet.addLoad(handle, access.getField());
972                                         else
973                                             loadedFieldSet.addStore(handle, access.getField());
974                                     }
975                                 }
976                             } else if (fieldInstructionOpcodeSet.get(opcode)) {
977                                 boolean isLoad = (opcode == Constants.GETFIELD || opcode == Constants.GETSTATIC);
978                                 XField field = Hierarchy.findXField((FieldInstruction) ins, getConstantPoolGen());
979                                 if (field != null) {
980                                     if (isLoad)
981                                         loadedFieldSet.addLoad(handle, field);
982                                     else
983                                         loadedFieldSet.addStore(handle, field);
984                                 }
985                             }
986                         } catch (ClassNotFoundException   e) {
987                             analysisContext.getLookupFailureCallback().reportMissingClass(e);
988                         }
989                     }
990 
991                     return loadedFieldSet;
992                 }
993             };
994 
995     private AnalysisFactory<LiveLocalStoreDataflow> liveLocalStoreDataflowFactory =
996             new DataflowAnalysisFactory<LiveLocalStoreDataflow>("live local stores analysis") {
997                 @Override  
998                                  protected LiveLocalStoreDataflow analyze(Method method)
999                     throws DataflowAnalysisException, CFGBuilderException {
1000                        MethodGen methodGen = getMethodGen(method);
1001                        if (methodGen == null) return null;
1002                        CFG cfg = getCFG(method);
1003
1004                        ReverseDepthFirstSearch rdfs = getReverseDepthFirstSearch(method);
1005
1006                        LiveLocalStoreAnalysis analysis = new LiveLocalStoreAnalysis(methodGen, rdfs, getDepthFirstSearch(method));
1007                        LiveLocalStoreDataflow dataflow = new LiveLocalStoreDataflow(cfg, analysis);
1008
1009                        dataflow.execute();
1010
1011                        return dataflow;
1012                }
1013            };
1014
1015    private AnalysisFactory<Dataflow<BlockType, BlockTypeAnalysis>> blockTypeDataflowFactory =
1016            new DataflowAnalysisFactory<Dataflow<BlockType, BlockTypeAnalysis>>("block type analysis") {
1017                @Override  
1018                                 protected Dataflow<BlockType, BlockTypeAnalysis> analyze(Method method)
1019                        throws DataflowAnalysisException, CFGBuilderException {
1020                    CFG cfg = getCFG(method);
1021                    DepthFirstSearch dfs = getDepthFirstSearch(method);
1022
1023                    BlockTypeAnalysis analysis = new BlockTypeAnalysis(dfs);
1024                    Dataflow<BlockType, BlockTypeAnalysis> dataflow =
1025                        new Dataflow<BlockType, BlockTypeAnalysis>(cfg, analysis);
1026                    dataflow.execute();
1027
1028                    return dataflow;
1029                }
1030            };
1031
1032    private AnalysisFactory<CallListDataflow> callListDataflowFactory =
1033        new DataflowAnalysisFactory<CallListDataflow>("call list analysis") {
1034            //@Override
1035            @Override  
1036                         protected CallListDataflow analyze(Method method) throws CFGBuilderException, DataflowAnalysisException {
1037
1038                CallListAnalysis analysis = new CallListAnalysis(
1039                        getCFG(method),
1040                        getDepthFirstSearch(method),
1041                        getConstantPoolGen());
1042                
1043                CallListDataflow dataflow = new CallListDataflow(getCFG(method), analysis);
1044                dataflow.execute();
1045                
1046                return dataflow;
1047            }
1048        };
1049        
1050    private AnalysisFactory<UnconditionalValueDerefDataflow> unconditionalValueDerefDataflowFactory =
1051        new DataflowAnalysisFactory<UnconditionalValueDerefDataflow>("unconditional value dereference analysis") {
1052            /* (non-Javadoc)
1053             * @see edu.umd.cs.findbugs.ba.ClassContext.AnalysisFactory#analyze(org.apache.bcel.classfile.Method)
1054             */
1055            @Override  
1056            protected UnconditionalValueDerefDataflow analyze(Method method) throws CFGBuilderException, DataflowAnalysisException {
1057                
1058                CFG cfg = getCFG(method);
1059                
1060                ValueNumberDataflow vnd = getValueNumberDataflow(method);
1061                
1062                UnconditionalValueDerefAnalysis analysis = new UnconditionalValueDerefAnalysis(
1063                        getReverseDepthFirstSearch(method),
1064                        getDepthFirstSearch(method),
1065                        cfg,
1066                        getMethodGen(method),
1067                        vnd, getAssertionMethods()
1068                        );
1069                
1070                IsNullValueDataflow inv = getIsNullValueDataflow(method);
1071                // XXX: hack to clear derefs on not-null branches
1072                analysis.clearDerefsOnNonNullBranches(inv);
1073                
1074                // XXX: type analysis is needed to resolve method calls for
1075                // checking whether call targets unconditionally dereference parameters
1076                analysis.setTypeDataflow(getTypeDataflow(method));
1077                
1078                UnconditionalValueDerefDataflow dataflow =
1079                    new UnconditionalValueDerefDataflow(getCFG(method), analysis);
1080                dataflow.execute();
1081                 if (UnconditionalValueDerefAnalysis.DEBUG) {
1082                        dumpUnconditionalValueDerefDataflow(method, cfg, vnd, inv, dataflow);
1083                    }
1084             
1085                return dataflow;
1086            }
1087        };
1088        
1089    private NoDataflowAnalysisFactory<CompactLocationNumbering> compactLocationNumberingFactory =
1090        new NoDataflowAnalysisFactory<CompactLocationNumbering>("compact location numbering") {
1091        /* (non-Javadoc)
1092         * @see edu.umd.cs.findbugs.ba.ClassContext.AnalysisFactory#analyze(org.apache.bcel.classfile.Method)
1093         */
1094        @Override  
1095        protected CompactLocationNumbering analyze(Method method) throws CFGBuilderException, DataflowAnalysisException {
1096            if (method.getCode() == null) {
1097                return null;
1098            }
1099            
1100            CFG cfg = getCFG(method);
1101            return new CompactLocationNumbering(cfg);
1102        }
1103    };
1104    
1105    private DataflowAnalysisFactory<DefinitelyNullSetDataflow> definitelyNullSetDataflowFactory =
1106        new DataflowAnalysisFactory<DefinitelyNullSetDataflow>("definitely null set dataflow") {
1107        /* (non-Javadoc)
1108         * @see edu.umd.cs.findbugs.ba.ClassContext.AnalysisFactory#analyze(org.apache.bcel.classfile.Method)
1109         */
1110        @Override  
1111        protected DefinitelyNullSetDataflow analyze(Method method) throws CFGBuilderException, DataflowAnalysisException {
1112            
1113            CFG cfg = getCFG(method);
1114            DepthFirstSearch  dfs = getDepthFirstSearch(method);
1115            ValueNumberDataflow vnaDataflow = getValueNumberDataflow(method);
1116            CompactLocationNumbering compactLocationNumbering = getCompactLocationNumbering(method);
1117            
1118            DefinitelyNullSetAnalysis analysis = new DefinitelyNullSetAnalysis(dfs, vnaDataflow, compactLocationNumbering);
1119            DefinitelyNullSetDataflow dataflow = new DefinitelyNullSetDataflow(cfg, analysis);
1120            
1121            dataflow.execute();
1122            
1123            return dataflow;
1124        }
1125    };
1126            
1127    private ClassGen classGen;
1128    private AssignedFieldMap assignedFieldMap;
1129    private AssertionMethods assertionMethods;
1130
1131    /* ----------------------------------------------------------------------
1132     * Public methods
1133     * ---------------------------------------------------------------------- */
1134
1135    /**
1136     * Constructor.
1137     *
1138     * @param jclass the JavaClass
1139     */
1140    public ClassContext(JavaClass jclass, AnalysisContext analysisContext) {
1141        this.jclass = jclass;
1142        this.analysisContext = analysisContext;
1143        this.classGen = null;
1144        this.assignedFieldMap = null;
1145        this.assertionMethods = null;
1146    }
1147
1148    /**
1149     * Purge dataflow analysis results after CFG-pruning of given method.
1150     * 
1151     * @param method the method whose CFG has just been pruned
1152     */
1153    void purgeAnalysisResultsAfterCFGPruning(Method method) {
1154        for (AnalysisFactory<?> factory : analysisFactoryList) {
1155            if (factory.isDataflow()) {
1156                factory.purge(method);
1157            }
1158        }
1159    }
1160
1161    /**
1162     * Get the JavaClass.
1163     */
1164    public JavaClass getJavaClass() {
1165        return jclass;
1166    }
1167    
1168    /**
1169     * Look up the Method represented by given MethodGen.
1170     * 
1171     * @param methodGen a MethodGen
1172     * @return the Method represented by the MethodGen
1173     */
1174    public Method getMethod(MethodGen methodGen) {
1175        Method[] methodList = jclass.getMethods();
1176        for (Method method : methodList) {
1177            if (method.getName().equals(methodGen.getName())
1178                    && method.getSignature().equals(methodGen.getSignature())
1179                    && method.getAccessFlags() == methodGen.getAccessFlags()) {
1180                return method;
1181            }
1182        }
1183        return null;
1184    }
1185
1186    /**
1187     * Get the AnalysisContext.
1188     */
1189    public AnalysisContext getAnalysisContext() {
1190        return analysisContext;
1191    }
1192
1193    /**
1194     * Get the RepositoryLookupFailureCallback.
1195     *
1196     * @return the RepositoryLookupFailureCallback
1197     */
1198    public RepositoryLookupFailureCallback getLookupFailureCallback() {
1199        return analysisContext.getLookupFailureCallback();
1200    }
1201
1202    /**
1203     * Get a MethodGen object for given method.
1204     *
1205     * @param method the method
1206     * @return the MethodGen object for the method, or null
1207     *         if the method has no Code attribute (and thus cannot be analyzed)
1208     *         or if the method seems unprofitable to analyze
1209     */
1210    @CheckForNull public MethodGen getMethodGen(Method method) {
1211        return methodGenFactory.getAnalysis(method);
1212    }
1213
1214    /**
1215     * Get a "raw" CFG for given method.
1216     * No pruning is done, although the CFG may already be pruned.
1217     *
1218     * @param method the method
1219     * @return the raw CFG
1220     */
1221    public CFG getRawCFG(Method method) throws CFGBuilderException {
1222        return cfgFactory.getRawCFG(method);
1223    }
1224
1225    /**
1226     * Get a CFG for given method.
1227     * If pruning options are in effect, pruning will be done.
1228     * Because the CFG pruning can involve interprocedural analysis,
1229     * it is done on a best-effort basis, so the CFG returned might
1230     * not actually be pruned.
1231     *
1232     * @param method the method
1233     * @return the CFG
1234     * @throws CFGBuilderException if a CFG cannot be constructed for the method
1235     */
1236    public CFG getCFG(Method method) throws CFGBuilderException {
1237        if (method == cachedMethod) {
1238            // System.out.println("hit on " + method.getName());
1239            return cachedCFG;
1240        }
1241        if (false && cachedMethod != null) System.out.println(cachedMethod.getName() + " -> " + method.getName());
1242        CFG cfg = cfgFactory.getRefinedCFG(method);
1243        cachedMethod = method;
1244        cachedCFG = cfg;
1245        return cfg;
1246    }
1247
1248    Method cachedMethod;
1249    CFG cachedCFG = null;
1250    /**
1251     * Get the ConstantPoolGen used to create the MethodGens
1252     * for this class.
1253     *
1254     * @return the ConstantPoolGen
1255     */
1256    public @NonNull ConstantPoolGen getConstantPoolGen() {
1257        if (classGen == null)
1258            classGen = new ClassGen(jclass);
1259        return classGen.getConstantPool();
1260    }
1261
1262    /**
1263     * Get a ValueNumberDataflow for given method.
1264     *
1265     * @param method the method
1266     * @return the ValueNumberDataflow
1267     */
1268    public ValueNumberDataflow getValueNumberDataflow(Method method) throws DataflowAnalysisException, CFGBuilderException {
1269        return vnaDataflowFactory.getAnalysis(method);
1270    }
1271
1272    /**
1273     * Get an IsNullValueDataflow for given method.
1274     *
1275     * @param method the method
1276     * @return the IsNullValueDataflow
1277     */
1278    public IsNullValueDataflow getIsNullValueDataflow(Method method) throws DataflowAnalysisException, CFGBuilderException {
1279        return invDataflowFactory.getAnalysis(method);
1280    }
1281
1282    /**
1283     * Get a TypeDataflow for given method.
1284     *
1285     * @param method the method
1286     * @return the TypeDataflow
1287     */
1288    public TypeDataflow getTypeDataflow(Method method) throws DataflowAnalysisException, CFGBuilderException {
1289        return typeDataflowFactory.getAnalysis(method);
1290    }
1291
1292    /**
1293     * Get a DepthFirstSearch for given method.
1294     *
1295     * @param method the method
1296     * @return the DepthFirstSearch
1297     */
1298    public DepthFirstSearch getDepthFirstSearch(Method method) throws CFGBuilderException {
1299        return dfsFactory.getAnalysis(method);
1300    }
1301
1302    /**
1303     * Get a ReverseDepthFirstSearch for given method.
1304     *
1305     * @param method the method
1306     * @return the ReverseDepthFirstSearch
1307     */
1308    public ReverseDepthFirstSearch getReverseDepthFirstSearch(Method method)
1309            throws CFGBuilderException {
1310        return rdfsFactory.getAnalysis(method);
1311    }
1312
1313    static MapCache<XMethod,BitSet  > cachedBitsets = new MapCache<XMethod, BitSet  >(64);
1314    static MapCache<XMethod,Set  <Integer  >> cachedLoopExits = new MapCache<XMethod, Set  <Integer  >>(13);
1315    
1316    /**
1317     * Get a BitSet representing the bytecodes that are used in the given method.
1318     * This is useful for prescreening a method for the existence of particular instructions.
1319     * Because this step doesn't require building a MethodGen, it is very
1320     * fast and memory-efficient.  It may allow a Detector to avoid some
1321     * very expensive analysis, which is a Big Win for the user.
1322     *
1323     * @param method the method
1324     * @return the BitSet containing the opcodes which appear in the method,
1325     *          or null if the method has no code
1326     */
1327    @CheckForNull   public BitSet   getBytecodeSet(Method method) {
1328        return getBytecodeSet(jclass, method);
1329    }
1330    /**
1331     * Get a BitSet representing the bytecodes that are used in the given method.
1332     * This is useful for prescreening a method for the existence of particular instructions.
1333     * Because this step doesn't require building a MethodGen, it is very
1334     * fast and memory-efficient.  It may allow a Detector to avoid some
1335     * very expensive analysis, which is a Big Win for the user.
1336     *
1337     * @param method the method
1338     * @return the BitSet containing the opcodes which appear in the method,
1339     *          or null if the method has no code
1340     */
1341    @CheckForNull static public BitSet   getBytecodeSet(JavaClass clazz, Method method) {
1342
1343                XMethod xmethod = XFactory.createXMethod(clazz, method);
1344                if (cachedBitsets.containsKey(xmethod)) {
1345                    return cachedBitsets.get(xmethod);
1346                }
1347                Code code = method.getCode();
1348                if (code == null)
1349                    return null;
1350
1351                byte[] instructionList = code.getCode();
1352
1353                // Create callback
1354                UnpackedBytecodeCallback callback = new UnpackedBytecodeCallback(instructionList.length);
1355
1356                // Scan the method.
1357                BytecodeScanner scanner = new BytecodeScanner();
1358                scanner.scan(instructionList, callback);
1359
1360                UnpackedCode unpackedCode = callback.getUnpackedCode();
1361                BitSet   result =  null;
1362                if (unpackedCode != null) result =  unpackedCode.getBytecodeSet();
1363                cachedBitsets.put(xmethod, result);
1364                return result;
1365    }
1366    
1367    @CheckForNull static public Set  <Integer  > getLoopExitBranches(MethodGen methodGen) {
1368
1369        XMethod xmethod = XFactory.createXMethod(methodGen);
1370        if (cachedLoopExits.containsKey(xmethod)) {
1371            return cachedLoopExits.get(xmethod);
1372        }
1373        Code code = methodGen.getMethod().getCode();
1374        if (code == null)
1375            return null;
1376
1377        byte[] instructionList = code.getCode();
1378
1379        Set  <Integer  > result = new HashSet  <Integer  >();
1380        for(int i = 0; i < instructionList.length; i++)
1381            if (checkForBranchExit(instructionList,i)) result.add(i);
1382        if (result.size() == 0)
1383            result = Collections.EMPTY_SET; // alas, emptySet() is @since 1.5
1384        
1385        cachedLoopExits.put(xmethod, result);
1386        return result;
1387}
1388    static short getBranchOffset(byte [] codeBytes, int pos) {
1389        int branchByte1 = 0xff & codeBytes[pos];
1390        int branchByte2 = 0xff & codeBytes[pos+1];
1391        int branchOffset = (short) (branchByte1 << 8 | branchByte2);
1392        return (short) branchOffset;
1393    
1394    }
1395
1396    static boolean checkForBranchExit(byte [] codeBytes, int pos) {
1397        if (pos < 0 || pos+2 >= codeBytes.length) return false;
1398        switch(0xff & codeBytes[pos]) {
1399        case Constants.IF_ACMPEQ:
1400        case Constants.IF_ACMPNE:
1401        case Constants.IF_ICMPEQ:
1402        case Constants.IF_ICMPGE:
1403        case Constants.IF_ICMPGT:
1404        case Constants.IF_ICMPLE:
1405        case Constants.IF_ICMPLT:
1406        case Constants.IF_ICMPNE:
1407            break;
1408            default: 
1409                return false;
1410        }
1411        int branchTarget = pos+getBranchOffset(codeBytes, pos+1);
1412        if (branchTarget-3 < pos || branchTarget >= codeBytes.length) return false;
1413        if ((codeBytes[branchTarget-3] & 0xff) != Constants.GOTO) return false;
1414        int backBranchTarget = branchTarget + getBranchOffset(codeBytes, branchTarget-2);
1415        if (backBranchTarget <= pos && backBranchTarget + 12 >= pos) return true;
1416        return false;
1417    }
1418
1419    /**
1420     * Get array mapping bytecode offsets to opcodes for given method.
1421     * Array elements containing zero are either not valid instruction offsets,
1422     * or contain a NOP instruction.  (It is convenient not to distinguish
1423     * these cases.)
1424     * 
1425     * @param method the method
1426     * @return map of bytecode offsets to opcodes, or null if the method has no code
1427     */
1428    public short[] getOffsetToOpcodeMap(Method method) {
1429        UnpackedCode unpackedCode = unpackedCodeFactory.getAnalysis(method);
1430        return unpackedCode != null ? unpackedCode.getOffsetToBytecodeMap() : null;
1431    }
1432
1433    /**
1434     * Get dataflow for LockAnalysis for given method.
1435     *
1436     * @param method the method
1437     * @return the LockDataflow
1438     */
1439    public LockDataflow getLockDataflow(Method method)
1440            throws CFGBuilderException, DataflowAnalysisException {
1441        return lockDataflowFactory.getAnalysis(method);
1442    }
1443
1444    /**
1445     * Get LockChecker for method.
1446     * This is like LockDataflow, but may be able to avoid performing
1447     * the actual dataflow analyses if the method doesn't contain
1448     * explicit monitorenter/monitorexit instructions.
1449     * 
1450     * @param method the method
1451     * @return the LockChecker
1452     * @throws CFGBuilderException
1453     * @throws DataflowAnalysisException
1454     */
1455    public LockChecker getLockChecker(Method method) throws CFGBuilderException, DataflowAnalysisException {
1456        return lockCheckerFactory.getAnalysis(method);
1457    }
1458    
1459    /**
1460     * Get ReturnPathDataflow for method.
1461     *
1462     * @param method the method
1463     * @return the ReturnPathDataflow
1464     */
1465    public ReturnPathDataflow getReturnPathDataflow(Method method)
1466            throws CFGBuilderException, DataflowAnalysisException {
1467        return returnPathDataflowFactory.getAnalysis(method);
1468    }
1469
1470    /**
1471     * Get DominatorsAnalysis for given method,
1472     * where exception edges are ignored.
1473     *
1474     * @param method the method
1475     * @return the DominatorsAnalysis
1476     */
1477    public DominatorsAnalysis getNonExceptionDominatorsAnalysis(Method method)
1478            throws CFGBuilderException, DataflowAnalysisException {
1479        return nonExceptionDominatorsAnalysisFactory.getAnalysis(method);
1480    }
1481
1482    /**
1483     * Get DominatorsAnalysis for given method,
1484     * where implicit exception edges are ignored.
1485     *
1486     * @param method the method
1487     * @return the DominatorsAnalysis
1488     */
1489    public PostDominatorsAnalysis getNonImplicitExceptionDominatorsAnalysis(Method method)
1490            throws CFGBuilderException, DataflowAnalysisException {
1491        return nonImplicitExceptionPostDominatorsAnalysisFactory.getAnalysis(method);
1492    }
1493
1494    /**
1495     * Get PostDominatorsAnalysis for given method,
1496     * where exception edges are ignored.
1497     *
1498     * @param method the method
1499     * @return the PostDominatorsAnalysis
1500     */
1501    public PostDominatorsAnalysis getNonExceptionPostDominatorsAnalysis(Method method)
1502            throws CFGBuilderException, DataflowAnalysisException {
1503        return nonExceptionPostDominatorsAnalysisFactory.getAnalysis(method);
1504    }
1505
1506    /**
1507     * Get ExceptionSetFactory for given method.
1508     *
1509     * @param method the method
1510     * @return the ExceptionSetFactory
1511     */
1512    public ExceptionSetFactory getExceptionSetFactory(Method method) {
1513        return exceptionSetFactoryFactory.getAnalysis(method);
1514    }
1515
1516    /**
1517     * Get array of type signatures of parameters for given method.
1518     *
1519     * @param method the method
1520     * @return an array of type signatures indicating the types
1521     *         of the method's parameters
1522     */
1523    public String  [] getParameterSignatureList(Method method) {
1524        return parameterSignatureListFactory.getAnalysis(method);
1525    }
1526
1527    /**
1528     * Get the set of fields loaded by given method.
1529     *
1530     * @param method the method
1531     * @return the set of fields loaded by the method
1532     */
1533    public LoadedFieldSet getLoadedFieldSet(Method method) {
1534        return loadedFieldSetFactory.getAnalysis(method);
1535    }
1536
1537    /**
1538     * Get LiveLocalStoreAnalysis dataflow for given method.
1539     *
1540     * @param method the method
1541     * @return the Dataflow object for LiveLocalStoreAnalysis on the method
1542     */
1543    public LiveLocalStoreDataflow getLiveLocalStoreDataflow(Method method)
1544            throws DataflowAnalysisException, CFGBuilderException {
1545        return liveLocalStoreDataflowFactory.getAnalysis(method);
1546    }
1547
1548    /**
1549     * Get BlockType dataflow for given method.
1550     *
1551     * @param method the method
1552     * @return the Dataflow object for BlockTypeAnalysis on the method
1553     */
1554    public Dataflow<BlockType, BlockTypeAnalysis> getBlockTypeDataflow(Method method)
1555            throws DataflowAnalysisException, CFGBuilderException {
1556        return blockTypeDataflowFactory.getAnalysis(method);
1557    }
1558
1559    /**
1560     * Get the assigned field map for the class.
1561     *
1562     * @return the AssignedFieldMap
1563     * @throws ClassNotFoundException if a class lookup prevents
1564     *                                the class's superclasses from being searched for
1565     *                                assignable fields
1566     */
1567    public AssignedFieldMap getAssignedFieldMap() throws ClassNotFoundException   {
1568        if (assignedFieldMap == null) {
1569            assignedFieldMap = new AssignedFieldMap(this);
1570        }
1571        return assignedFieldMap;
1572    }
1573
1574    /**
1575     * Get AssertionMethods for class.
1576     *
1577     * @return the AssertionMethods
1578     */
1579    public AssertionMethods getAssertionMethods() {
1580        if (assertionMethods == null) {
1581            assertionMethods = new AssertionMethods(jclass);
1582        }
1583        return assertionMethods;
1584    }
1585    
1586    /**
1587     * Get ConstantDataflow for method.
1588     * 
1589     * @param method the method
1590     * @return the ConstantDataflow
1591     * @throws CFGBuilderException
1592     * @throws DataflowAnalysisException
1593     */
1594    public ConstantDataflow getConstantDataflow(Method method)
1595            throws CFGBuilderException, DataflowAnalysisException {
1596        return constantDataflowFactory.getAnalysis(method);
1597    }
1598    
1599    /**
1600     * Get load dataflow.
1601     * 
1602     * @param method the method
1603     * @return the LoadDataflow
1604     * @throws CFGBuilderException
1605     * @throws DataflowAnalysisException
1606     */
1607    public LoadDataflow getLoadDataflow(Method method) throws CFGBuilderException, DataflowAnalysisException {
1608        return loadDataflowFactory.getAnalysis(method);
1609    }
1610    
1611    /**
1612     * Get store dataflow.
1613     * 
1614     * @param method the method
1615     * @return the StoreDataflow
1616     * @throws CFGBuilderException
1617     * @throws DataflowAnalysisException
1618     */
1619    public StoreDataflow getStoreDataflow(Method method) throws CFGBuilderException, DataflowAnalysisException {
1620        return storeDataflowFactory.getAnalysis(method);
1621    }
1622    
1623    /**
1624     * Get CallListDataflow for method.
1625     * 
1626     * @param method the method
1627     * @return the CallListDataflow
1628     * @throws CFGBuilderException
1629     * @throws DataflowAnalysisException
1630     */
1631    public CallListDataflow getCallListDataflow(Method method)
1632            throws CFGBuilderException, DataflowAnalysisException {
1633        return callListDataflowFactory.getAnalysis(method);
1634    }
1635    
1636    public static BitSet   linesMentionedMultipleTimes(Method method) {
1637        BitSet   lineMentionedMultipleTimes = new BitSet  ();
1638        Code code = method.getCode();
1639        if (code == null || code.getExceptionTable() == null) return lineMentionedMultipleTimes;
1640        BitSet   foundOnce = new BitSet  ();
1641        LineNumberTable lineNumberTable = method.getLineNumberTable();
1642        int lineNum = -1;
1643        if (lineNumberTable != null) 
1644            for(LineNumber  line : lineNumberTable.getLineNumberTable()) {
1645                int newLine = line.getLineNumber();
1646                if (newLine == lineNum || newLine == -1) continue;
1647                lineNum = newLine;
1648                if (foundOnce.get(lineNum))
1649                    lineMentionedMultipleTimes.set(lineNum);
1650                else 
1651                    foundOnce.set(lineNum); 
1652            }
1653        return lineMentionedMultipleTimes;
1654    }
1655    
1656    /**
1657     * Get the UnconditionalValueDerefDataflow for a method.
1658     * 
1659     * @param method the method
1660     * @return the UnconditionalValueDerefDataflow 
1661     * @throws CFGBuilderException
1662     * @throws DataflowAnalysisException
1663     */
1664    public UnconditionalValueDerefDataflow getUnconditionalValueDerefDataflow(Method method)
1665            throws CFGBuilderException, DataflowAnalysisException {
1666        return  unconditionalValueDerefDataflowFactory.getAnalysis(method);
1667    }
1668    
1669    /**
1670     * Get a CompactLocationNumbering for a method.
1671     * 
1672     * @param method a method
1673     * @return the CompactLocationNumbering for the method
1674     * @throws CFGBuilderException
1675     */
1676    public CompactLocationNumbering getCompactLocationNumbering(Method method)
1677            throws CFGBuilderException {
1678        return compactLocationNumberingFactory.getAnalysis(method); 
1679    }
1680
1681    /**
1682     * Get DefinitelyNullSetDataflow for a method.
1683     * 
1684     * @param method a method
1685     * @return the DefinitelyNullSetDataflow for the method 
1686     * @throws DataflowAnalysisException 
1687     * @throws CFGBuilderException 
1688     */
1689    public DefinitelyNullSetDataflow getDefinitelyNullSetDataflow(Method method)
1690            throws CFGBuilderException, DataflowAnalysisException {
1691        return definitelyNullSetDataflowFactory.getAnalysis(method);
1692    }
1693
1694    /**
1695     * @param method
1696     * @param cfg
1697     * @param vnd
1698     * @param inv
1699     * @param dataflow
1700     * @throws DataflowAnalysisException
1701     */
1702    public static void dumpUnconditionalValueDerefDataflow(Method method, CFG cfg, ValueNumberDataflow vnd, IsNullValueDataflow inv, UnconditionalValueDerefDataflow dataflow) throws DataflowAnalysisException {
1703        System.out.println("\n\n{ UnconditionalValueDerefAnalysis analysis for " + method.getName());
1704        TreeSet  <Location> tree = new TreeSet  <Location>();
1705        
1706        for(Iterator  <Location> locs = cfg.locationIterator(); locs.hasNext(); ) {
1707            Location loc = locs.next();
1708            tree.add(loc);
1709        }
1710        for(Location loc : tree) {
1711            UnconditionalValueDerefSet factAfterLocation = dataflow.getFactAfterLocation(loc);
1712            System.out.println("\n Pre: " + factAfterLocation);
1713            System.out.println("Vna: " + vnd.getFactAtLocation(loc));
1714            System.out.println("inv: " + inv.getFactAtLocation(loc));
1715            System.out.println("Location: " + loc);
1716            System.out.println("Post: " + dataflow.getFactAtLocation(loc));
1717            System.out.println("Vna: " + vnd.getFactAfterLocation(loc));
1718            System.out.println("inv: " + inv.getFactAfterLocation(loc));
1719            
1720            
1721            
1722            
1723        }
1724        System.out.println("}\n\n");
1725    }
1726    /**
1727     * @param method
1728     * @param cfg
1729     * @param typeDataflow
1730     * @throws DataflowAnalysisException
1731     */
1732    public static void dumpTypeDataflow(Method method, CFG cfg, TypeDataflow typeDataflow) throws DataflowAnalysisException {
1733        System.out.println("\n\n{ Type analysis for " + cfg.getMethodGen().getClassName() + "." + method.getName());
1734        TreeSet  <Location> tree = new TreeSet  <Location>();
1735        
1736        for(Iterator  <Location> locs = cfg.locationIterator(); locs.hasNext(); ) {
1737            Location loc = locs.next();
1738            tree.add(loc);
1739        }
1740        for(Location loc : tree) {
1741            System.out.println("\n Pre: " + typeDataflow.getFactAtLocation(loc));
1742            System.out.println("Location: " + loc);
1743            System.out.println("Post: " + typeDataflow.getFactAfterLocation(loc));  
1744        }
1745        System.out.println("}\n\n");
1746    }
1747
1748}
1749
1750// vim:ts=3
1751
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags