Java > Open Source Codes > soot > jimple > toolkits > annotation > nullcheck > BranchedRefVarsAnalysis


1 /* BranchedRefVarsAnalysis
2  * Copyright (C) 2000 Patrick Lam, Janus
3  *
4  * This library is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU Lesser General Public
6  * License as published by the Free Software Foundation; either
7  * version 2.1 of the License, or (at your option) any later version.
8  *
9  * This library is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12  * Lesser General Public License for more details.
13  *
14  * You should have received a copy of the GNU Lesser General Public
15  * License along with this library; if not, write to the
16  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
17  * Boston, MA 02111-1307, USA.
18  */
19
20
21 package soot.jimple.toolkits.annotation.nullcheck;
22
23 import soot.*;
24 import soot.jimple.*;
25 import soot.toolkits.graph.*;
26 import soot.toolkits.scalar.*;
27 import soot.util.*;
28 import java.util.*;
29
30
31 /*
32      README FIRST - IMPORTANT IMPLEMENTATION NOTE
33
34      As per the analysis presented in the report, there are four possible
35      pairs for given reference r:
36      (r, kBottom)
37      (r, kNonNull)
38      (r, kNull)
39      (r, kTop)
40
41      To save space an simplify operations, we implemented those 4 values
42      with two bits rather than four, namely:
43
44      (r, kTop) in a set is represented by having (r, kNull) and (r, kNonNull)
45      in the set. Ditto, (r, kBottom) is represented by having neither in the set.
46     
47      Keep this in mind as you read the code, it helps. Honnest :)
48
49      -- Janus
50
51  */
52
53
54 /*
55       BranchedRefVarsAnalysis class
56
57       Perform the analysis presented in the report.
58
59       
60       KNOWN LIMITATION: there is a problem in the ForwardBranchedFlowAnalysis
61       or maybe the CompleteUnitGraph that prevent the analysis
62       (at the ForwardBranchedFlowAnalysis level) to handle properly traps.
63       We make the analysis conservative in case of exceptions by setting
64       exceptions handler statements In to TOP.
65       
66
67  */
68
69
70 public class BranchedRefVarsAnalysis extends ForwardBranchedFlowAnalysis
71 {
72     /*
73         COMPILATION OPTIONS
74     */
75
76     // we don't want the analysis to be conservative?
77 // i.e. we don't want it to only care for locals
78 private boolean isNotConservative = false;
79     
80     // do we want the analysis to handle if statements?
81 private boolean isBranched = true;
82     
83     // do we want the analysis to care that f and g
84 // could be the same reference?
85 private boolean careForAliases = false;
86     
87     // do we want the analysis to care that a method
88 // call could have side effects?
89 private boolean careForMethodCalls = true;
90
91     // **** END OF COMPILATION OPTIONS *****
92
93 /*
94     {
95         if (true) {
96             G.v().out.println();
97             G.v().out.println();
98             G.v().out.println("BranchedRefVarsAnalysis:");
99             G.v().out.println(" isNotConservative = "+isNotConservative);
100             G.v().out.println(" isBranched = "+isBranched);
101             G.v().out.println(" careForAliases = "+careForAliases);
102             G.v().out.println(" careForMethodCalls = "+careForMethodCalls);
103         }
104     } // end
105 */
106
107     // constants for the analysis
108 public final static int kBottom = 0;
109     public final static int kNull = 1;
110     public final static int kNonNull = 2;
111     public final static int kTop = 99;
112
113
114     // bottom and top sets
115 protected FlowSet emptySet;
116     protected FlowSet fullSet;
117
118
119     // gen and preserve sets (for each statement)
120 protected Map unitToGenerateSet;
121     protected Map unitToPreserveSet;
122
123     
124     // sets of variables that need a null pointer check (for each statement)
125 protected Map unitToAnalyzedChecksSet;
126     protected Map unitToArrayRefChecksSet;
127     protected Map unitToInstanceFieldRefChecksSet;
128     protected Map unitToInstanceInvokeExprChecksSet;
129     protected Map unitToLengthExprChecksSet;
130
131
132     // keep track of the different kinds of reference types this analysis is working on
133 protected List refTypeLocals;
134     protected List refTypeInstFields;
135     protected List refTypeInstFieldBases;
136     protected List refTypeStaticFields;
137     protected List refTypeValues; // sum of all the above
138
139
140     // used in flowThrough.
141 protected FlowSet tempFlowSet = null;
142
143     // fast conversion from Value -> EquivalentValue
144 // because used in methods
145 private HashMap valueToEquivValue = new HashMap(2293, 0.7f);
146
147     public EquivalentValue getEquivalentValue(Value v)
148     {
149         if (valueToEquivValue.containsKey(v))
150             return (EquivalentValue) valueToEquivValue.get(v);
151         else {
152             EquivalentValue ev = new EquivalentValue(v);
153             valueToEquivValue.put(v, ev);
154             return ev;
155         }
156     } // end getEquivalentValue
157
158     // constant (r, v) pairs
159 // because used in methods
160 private HashMap kRefBotttomPairs = new HashMap(2293, 0.7f);
161     private HashMap kRefNonNullPairs = new HashMap(2293, 0.7f);
162     private HashMap kRefNullPairs = new HashMap(2293, 0.7f);
163     private HashMap kRefTopPairs = new HashMap(2293, 0.7f);
164
165     // make that (r, v) pairs are constants
166 // i.e. the same r and v values always generate the same (r, v) object
167 public RefIntPair getKRefIntPair(EquivalentValue r, int v)
168     {
169         HashMap pairsMap = null;
170
171         if (v == kNonNull)
172             pairsMap = kRefNonNullPairs;
173         else if (v == kNull)
174             pairsMap = kRefNullPairs;
175         else if (v == kTop)
176             pairsMap = kRefTopPairs;
177         else if (v == kBottom)
178             pairsMap = kRefBotttomPairs;
179         else
180             throw new RuntimeException ("invalid constant ("+v+")");
181         
182         if (pairsMap.containsKey(r))
183             return (RefIntPair) pairsMap.get(r);
184         else {
185             RefIntPair pair = new RefIntPair(r, v, this);
186             pairsMap.put(r, pair);
187             return pair;
188         }
189     } // end getKRefIntPair
190
191     /*
192         Utility methods.
193
194         They are used all over the place. Most of them are declared
195         "private final" so they can be inlined with javac -O.
196
197      */
198
199
200     // isAlwaysNull returns true if the reference r is known to be always null
201 private final boolean isAlwaysNull(Value r)
202     {
203         return ((r instanceof NullConstant) ||
204                 (r.getType() instanceof NullType));
205     } // end isAlwaysNull
206
207
208     // isAlwaysTop returns true if the reference r is known to be always top for this analysis
209 // i.e. its value is undecidable by this analysis
210 private final boolean isAlwaysTop(Value r)
211     {
212         if (isNotConservative)
213             return false;
214         else
215             return r instanceof InstanceFieldRef || r instanceof StaticFieldRef;
216     } // end isAlwaysTop
217
218     protected boolean isAlwaysNonNull(Value ro) {
219         if( ro instanceof NewExpr ) return true;
220         if( ro instanceof NewArrayExpr ) return true;
221         if( ro instanceof NewMultiArrayExpr ) return true;
222         if( ro instanceof ThisRef ) return true;
223         if( ro instanceof CaughtExceptionRef ) return true;
224         if( ro instanceof StringConstant ) return true;
225         return false;
226     }
227
228
229
230     // isAnalyzedRef returns true if the reference r is to be analyzed by this analysis
231 // i.e. its value is not always known (or undecidable)
232 private final boolean isAnalyzedRef(Value r)
233     {
234         if (isAlwaysNull(r) || isAlwaysTop(r))
235             return false;
236         else if (r instanceof Local ||
237                  r instanceof InstanceFieldRef ||
238                  r instanceof StaticFieldRef) {
239             Type rType = r.getType();
240             
241             return (rType instanceof RefType || rType instanceof ArrayType);
242         } else
243             return false;
244     } // end isAnalyzedRef
245
246     // refInfo is a helper method to tranform our two bit representation back to the four constants
247 // For a given reference and a flow set, tell us if r is bottom, top, null or non-null
248 // Note: this method will fail if r is not in the flow set
249 protected final int refInfo(EquivalentValue r, FlowSet fs)
250     {
251         boolean isNull = fs.contains(getKRefIntPair(r, kNull));
252         boolean isNonNull = fs.contains(getKRefIntPair(r, kNonNull));
253         
254         if (isNull && isNonNull)
255             return kTop;
256         else if (isNull)
257             return kNull;
258         else if (isNonNull)
259             return kNonNull;
260         else
261             return kBottom;
262     } // end refInfo
263
264     protected final int refInfo(Value r, FlowSet fs)
265     {
266         return refInfo(getEquivalentValue(r), fs);
267     } // end refInfo
268
269     // Like refInfo, but the reference doesn't have to be in the flow set
270 // note: it still need to be a reference, i.e. ArrayType or RefType
271 public int anyRefInfo(Value r, FlowSet f)
272     {
273         if (isAlwaysNull(r))
274             return kNull;
275         else if (isAlwaysTop(r))
276             return kTop;
277         else if( isAlwaysNonNull(r) )
278             return kNonNull;
279         else
280             return refInfo(r, f);
281     } // end anyRefInfo
282
283
284     /*
285        methods: uAddTopToFlowSet
286                 uAddInfoToFlowSet
287                 uListAddTopToFlowSet
288
289        Adding a pair (r, v) to a set is always a two steps process:
290        a) remove all pairs (r, *)
291        b) add the pair (r, v)
292        
293        The methods above handle that.
294
295        Most of them come in two flavors: to act on one set or two act on separate
296        generate and preserve sets.
297
298     */
299
300     // method to add (r, kTop) to the gen set (and remove it from the pre set)
301 private final void uAddTopToFlowSet(EquivalentValue r, FlowSet genFS, FlowSet preFS)
302     {
303         RefIntPair nullPair = getKRefIntPair(r, kNull);
304         RefIntPair nullNonPair = getKRefIntPair(r, kNonNull);
305         
306         if (genFS != preFS) {
307             preFS.remove(nullPair, preFS);
308             preFS.remove(nullNonPair, preFS);
309         }
310         
311         genFS.add(nullPair, genFS);
312         genFS.add(nullNonPair, genFS);
313     } // end uAddTopToFlowSet
314
315     private final void uAddTopToFlowSet(Value r, FlowSet genFS, FlowSet preFS)
316     {
317         uAddTopToFlowSet(getEquivalentValue(r), genFS, preFS);
318     } // end uAddTopToFlowSet
319
320     // method to add (r, kTop) to a set
321 private final void uAddTopToFlowSet(Value r, FlowSet fs)
322     {
323         uAddTopToFlowSet(getEquivalentValue(r), fs, fs);
324     } // end uAddTopToFlowSet
325
326     // method to add (r, kTop) to a set
327 private final void uAddTopToFlowSet(EquivalentValue r, FlowSet fs)
328     {
329         uAddTopToFlowSet(r, fs, fs);
330     } // end uAddTopToFlowSet
331
332     // method to add (r, kNonNull) or (r, kNull) to the gen set (and remove it from the pre set)
333 private final void uAddInfoToFlowSet(EquivalentValue r, int v, FlowSet genFS, FlowSet preFS)
334     {
335         int kill;
336         if (v == kNull)
337             kill = kNonNull;
338         else if (v == kNonNull)
339             kill = kNull;
340         else
341             throw new RuntimeException ("invalid info");
342         
343         if (genFS != preFS) {
344             preFS.remove(getKRefIntPair(r, kill), preFS);
345         }
346         
347         genFS.remove(getKRefIntPair(r, kill), genFS);
348         genFS.add(getKRefIntPair(r, v), genFS);
349     } // end uAddInfoToFlowSet
350
351     private final void uAddInfoToFlowSet(Value r, int v, FlowSet genF, FlowSet preF)
352     {
353         uAddInfoToFlowSet(getEquivalentValue(r), v, genF, preF);
354     } // end uAddInfoToFlowSet
355
356     // method to add (r, kNonNull) or (r, kNull) to a set
357 private final void uAddInfoToFlowSet(Value r, int v, FlowSet fs)
358     {
359         uAddInfoToFlowSet(getEquivalentValue(r), v, fs, fs);
360     } // end uAddInfoToFlowSet
361
362     // method to add (r, kNonNull) or (r, kNull) to a set
363 private final void uAddInfoToFlowSet(EquivalentValue r, int v, FlowSet fs)
364     {
365         uAddInfoToFlowSet(r, v, fs, fs);
366     } // end uAddInfoToFlowSet
367
368
369     // method to apply uAddTopToFlowSet to a whole list of references
370 private final void uListAddTopToFlowSet(List refs, FlowSet genFS, FlowSet preFS)
371     {
372         Iterator it = refs.iterator();
373
374         while (it.hasNext()) {
375             uAddTopToFlowSet((EquivalentValue) it.next(), genFS, preFS);
376         }
377     } // end uListAddTopToFlowSet
378
379
380     /********** end of utility methods *********/
381
382
383     // here come the method that start it all, the constructor
384 // initialize the object and run the analysis
385 public BranchedRefVarsAnalysis (UnitGraph g)
386     {
387         super(g);
388
389         // initialize all the refType lists
390 initRefTypeLists();
391         
392         // initialize emptySet, fullSet and tempFlowSet
393 initUniverseSets();
394         
395         // initialize unitTo...Sets
396 // perform preservation and generation
397 initUnitSets();
398         
399         doAnalysis();
400     } // end constructor
401
402
403     // method to initialize refTypeLocals, refTypeInstFields, refTypeInstFieldBases
404 // refTypeStaticFields, and refTypeValues
405 // those lists contains fields that can/need to be analyzed
406 private void initRefTypeLists()
407     {
408         refTypeLocals = new ArrayList();
409         refTypeInstFields = new ArrayList();
410         refTypeInstFieldBases = new ArrayList();
411         refTypeStaticFields = new ArrayList();
412         refTypeValues = new ArrayList();
413
414         // build list of locals
415 Iterator it = ((UnitGraph)graph).getBody().getLocals().iterator();
416         
417         while (it.hasNext()) {
418             Local l = (Local) (it.next());
419             
420             if (l.getType() instanceof RefType ||
421                 l.getType() instanceof ArrayType) {
422                 refTypeLocals.add(getEquivalentValue(l));
423             }
424         }
425         
426         if (isNotConservative) {
427             // build list of fields
428 // if the analysis is not conservative (if it is then we will only work on locals)
429
430             Iterator unitIt = graph.iterator();
431             
432             while(unitIt.hasNext()) {
433                 
434                 Unit s = (Unit) unitIt.next();
435                 
436                 Iterator boxIt;
437                 boxIt = s.getUseBoxes().iterator();
438                 while(boxIt.hasNext()) initRefTypeLists( (ValueBox) boxIt.next() );
439                 boxIt = s.getDefBoxes().iterator();
440                 while(boxIt.hasNext()) initRefTypeLists( (ValueBox) boxIt.next() );
441                 
442             }
443             
444         } // end build list of fields
445
446         refTypeValues.addAll(refTypeLocals);
447         refTypeValues.addAll(refTypeInstFields);
448         refTypeValues.addAll(refTypeStaticFields);
449         
450         // G.v().out.println("Analyzed references: " + refTypeValues);
451 } // end initRefTypeLists
452
453     private void initRefTypeLists( ValueBox box ) {
454         Value val = box.getValue();
455         Type opType = null;
456         
457         if (val instanceof InstanceFieldRef) {
458             
459             InstanceFieldRef ir = (InstanceFieldRef) val;
460             
461             opType = ir.getType();
462             if (opType instanceof RefType ||
463                 opType instanceof ArrayType) {
464                 
465                 EquivalentValue eir = getEquivalentValue(ir);
466                 
467                 if (!refTypeInstFields.contains(eir)) {
468                     refTypeInstFields.add(eir);
469
470                     EquivalentValue eirbase = getEquivalentValue(ir.getBase());
471                     if (!refTypeInstFieldBases.contains(eirbase))
472                         refTypeInstFieldBases.add(eirbase);
473                 }
474
475             }
476         } else if (val instanceof StaticFieldRef) {
477             
478             StaticFieldRef sr = (StaticFieldRef) val;
479             opType = sr.getType();
480             
481             if (opType instanceof RefType ||
482                 opType instanceof ArrayType) {
483                 
484                 EquivalentValue esr = getEquivalentValue(sr);
485
486                 if (!refTypeStaticFields.contains(esr)) {
487                     refTypeStaticFields.add(esr);
488                 }
489             }
490         }
491     }
492     // method to initialize the emptySet, fullSet and tempFlowSet
493 // from the refTypeValues
494 private void initUniverseSets()
495     {
496         FlowUniverse localUniverse;
497         
498         Object [] refTypeValuesArray = refTypeValues.toArray();
499         int len = refTypeValuesArray.length;
500         Object [] universeArray = new Object [2*len];
501         int i;
502         
503         // kRefIntPairs = new HashMap(len*2 + 1, 0.7f);
504 // ideally we would like to be able to do the above to avoid that Map growth
505 // but that would screw concurent execution of this analysis
506 // and making that field non- would require changing our utility methods to non-
507
508         for (i = 0; i < len; i++) {
509             int j = i*2;
510             EquivalentValue r = (EquivalentValue) refTypeValuesArray[i];
511             universeArray[j] = getKRefIntPair(r, kNull);
512             universeArray[j+1] = getKRefIntPair(r, kNonNull);
513         }
514         
515         localUniverse = new ArrayFlowUniverse(universeArray);
516         
517         emptySet = new ArrayPackedSet(localUniverse);
518         fullSet = (FlowSet) emptySet.clone();
519         ((ArrayPackedSet) emptySet).complement(fullSet);
520         
521         tempFlowSet = (FlowSet) newInitialFlow();
522     } // end initUniverseSets
523
524
525
526     private void initUnitSets()
527     {
528         int cap = graph.size() * 2 + 1;
529         float load = 0.7f;
530         
531         unitToGenerateSet = new HashMap(cap, load);
532         unitToPreserveSet = new HashMap(cap, load);
533         
534         unitToAnalyzedChecksSet = new HashMap(cap, load);
535         unitToArrayRefChecksSet = new HashMap(cap, load);
536         unitToInstanceFieldRefChecksSet = new HashMap(cap, load);
537         unitToInstanceInvokeExprChecksSet = new HashMap(cap, load);
538         unitToLengthExprChecksSet = new HashMap(cap, load);
539         
540         
541         Iterator unitIt = graph.iterator();
542         
543         while(unitIt.hasNext()) {
544             
545             Unit s = (Unit) unitIt.next();
546             
547             FlowSet genSet = (FlowSet) emptySet.clone();
548             FlowSet preSet = (FlowSet) fullSet.clone();
549             
550             HashSet analyzedChecksSet = new HashSet(5, load);
551             HashSet arrayRefChecksSet = new HashSet(5, load);
552             HashSet instanceFieldRefChecksSet = new HashSet(5, load);
553             HashSet instanceInvokeExprChecksSet = new HashSet(5, load);
554             HashSet lengthExprChecksSet = new HashSet(5, load);
555             
556             
557             // *** KILL PHASE ***
558
559             // naivity here. kill all the fields after an invoke, i.e. promote them to top
560 if (careForMethodCalls && ((Stmt)s).containsInvokeExpr()) {
561                 uListAddTopToFlowSet(refTypeInstFields, genSet, preSet);
562                 uListAddTopToFlowSet(refTypeStaticFields, genSet, preSet);
563             }
564             
565             if (careForAliases && (s instanceof AssignStmt)) {
566                 AssignStmt as = (AssignStmt) s;
567                 Value lhs = as.getLeftOp();
568                 
569                 if (refTypeInstFieldBases.contains(lhs)) {
570                     // we have a write to a local 'f' and
571 // there is a reference to f.x.
572 // The LHS will certainly be a local.
573 // here, we kill "f.*".
574
575                     Iterator refTypeInstFieldsIt=refTypeInstFields.iterator();
576                     
577                     while (refTypeInstFieldsIt.hasNext()) {
578                         EquivalentValue eifr = (EquivalentValue) refTypeInstFieldsIt.next();
579                         InstanceFieldRef ifr = (InstanceFieldRef) eifr.getValue();
580                         
581                         if (ifr.getBase() == lhs) {
582                             uAddTopToFlowSet(eifr, genSet, preSet);
583                         }
584                     }
585                 }
586                 
587                 if (lhs instanceof InstanceFieldRef) {
588                     
589                     // we have a write to 'f.x',
590 // so we'd better kill 'g.x' for all g.
591
592                     String lhsName =
593                         ((InstanceFieldRef) lhs).getField().getName();
594                     
595                     Iterator refTypeInstFieldsIt = refTypeInstFields.iterator();
596                     
597                     while (refTypeInstFieldsIt.hasNext()) {
598                         EquivalentValue eifr = (EquivalentValue) refTypeInstFieldsIt.next();
599                         InstanceFieldRef ifr = (InstanceFieldRef) eifr.getValue();
600                         
601                         String name = ifr.getField().getName();
602                         
603                         if (name.equals(lhsName)) {
604                             uAddTopToFlowSet(eifr, genSet, preSet);
605                         }
606                     }
607                 }
608             } // end if (s instanceof AssignStmt)
609
610             // kill rhs of defs
611 {
612                 Iterator boxIt = s.getDefBoxes().iterator();
613                 
614                 while(boxIt.hasNext()) {
615                     
616                     ValueBox box = (ValueBox) boxIt.next();
617                     Value boxValue = box.getValue();
618                     
619                     if (isAnalyzedRef(boxValue)) {
620                         uAddTopToFlowSet(boxValue, genSet, preSet);
621                     }
622                 }
623             } // done killing rhs of defs
624
625             // GENERATION PHASE
626
627             if (s instanceof DefinitionStmt) {
628                 DefinitionStmt as = (DefinitionStmt) s;
629                 Value ro = as.getRightOp();
630                 Value lo = as.getLeftOp();
631                 
632                 // take out the cast from "x = (type) y;"
633 if (ro instanceof CastExpr)
634                     ro = ((CastExpr) ro).getOp();
635                 
636                 if (isAnalyzedRef(lo)) {
637                     if (isAlwaysNonNull(ro)) {
638                         uAddInfoToFlowSet(lo, kNonNull, genSet, preSet);
639                     } else if (isAlwaysNull(ro)) {
640                         uAddInfoToFlowSet(lo, kNull, genSet, preSet);
641                     } else if (isAlwaysTop(ro)) {
642                         uAddTopToFlowSet(lo, genSet, preSet);
643                     }
644                 }
645             } // end DefinitionStmt gen case
646
647             // check use and def boxes for dereferencing operations
648 // since those operations cause a null pointer check
649 // after the statement we know the involved references are non-null
650 {
651                 Iterator boxIt;
652                 boxIt = s.getUseBoxes().iterator();
653                 while(boxIt.hasNext()) {
654                     Value boxValue = ((ValueBox) boxIt.next()).getValue();
655                     Value base = null;
656                     
657                     if(boxValue instanceof InstanceFieldRef) {
658                         base = ((InstanceFieldRef) (boxValue)).getBase();
659                         instanceFieldRefChecksSet.add(base);
660                     } else if (boxValue instanceof ArrayRef) {
661                         base = ((ArrayRef) (boxValue)).getBase();
662                         arrayRefChecksSet.add(base);
663                     } else if (boxValue instanceof InstanceInvokeExpr) {
664                         base = ((InstanceInvokeExpr) boxValue).getBase();
665                         instanceInvokeExprChecksSet.add(base);
666                     } else if (boxValue instanceof LengthExpr) {
667                         base = ((LengthExpr) boxValue).getOp();
668                         lengthExprChecksSet.add(base);
669                     } else if (s instanceof ThrowStmt) {
670                         base = ((ThrowStmt)s).getOp();
671                     } else if (s instanceof MonitorStmt) {
672                         base = ((MonitorStmt)s).getOp();
673                     }
674                     
675                     if (base != null && isAnalyzedRef(base)) {
676                         uAddInfoToFlowSet(base, kNonNull, genSet, preSet);
677                         analyzedChecksSet.add(base);
678                     }
679                 }
680                 boxIt = s.getDefBoxes().iterator();
681                 while(boxIt.hasNext()) {
682                     
683                     Value boxValue = ((ValueBox) boxIt.next()).getValue();
684                     Value base = null;
685                     
686                     if(boxValue instanceof InstanceFieldRef) {
687                         base = ((InstanceFieldRef) (boxValue)).getBase();
688                         instanceFieldRefChecksSet.add(base);
689                     } else if (boxValue instanceof ArrayRef) {
690                         base = ((ArrayRef) (boxValue)).getBase();
691                         arrayRefChecksSet.add(base);
692                     } else if (boxValue instanceof InstanceInvokeExpr) {
693                         base = ((InstanceInvokeExpr) boxValue).getBase();
694                         instanceInvokeExprChecksSet.add(base);
695                     } else if (boxValue instanceof LengthExpr) {
696                         base = ((LengthExpr) boxValue).getOp();
697                         lengthExprChecksSet.add(base);
698                     } else if (s instanceof ThrowStmt) {
699                         base = ((ThrowStmt)s).getOp();
700                     } else if (s instanceof MonitorStmt) {
701                         base = ((MonitorStmt)s).getOp();
702                     }
703                     
704                     if (base != null && isAnalyzedRef(base)) {
705                         uAddInfoToFlowSet(base, kNonNull, genSet, preSet);
706                         analyzedChecksSet.add(base);
707                     }
708                 }
709             } // done check use and def boxes
710
711             unitToGenerateSet.put(s, genSet);
712             unitToPreserveSet.put(s, preSet);
713             
714             unitToAnalyzedChecksSet.put(s, analyzedChecksSet);
715             unitToArrayRefChecksSet.put(s, arrayRefChecksSet);
716             unitToInstanceFieldRefChecksSet.put(s, instanceFieldRefChecksSet);
717             unitToInstanceInvokeExprChecksSet.put(s, instanceInvokeExprChecksSet);
718             unitToLengthExprChecksSet.put(s, lengthExprChecksSet);
719         }
720     } // initUnitSets
721
722     protected void flowThrough(Object inValue, Unit stmt, List outFallValue, List outBranchValues)
723     {
724         FlowSet in = (FlowSet) inValue;
725         FlowSet out = tempFlowSet;
726         FlowSet pre = (FlowSet) unitToPreserveSet.get(stmt);
727         FlowSet gen = (FlowSet) unitToGenerateSet.get(stmt);
728
729         // Perform perservation
730 in.intersection(pre, out);
731         
732         // Perform generation
733 out.union(gen, out);
734         
735         // Manually add any x = y; when x and y are both analyzed references
736 // these are not sets.
737 if (stmt instanceof AssignStmt) {
738             AssignStmt as = (AssignStmt) stmt;
739             Value rightOp = as.getRightOp();
740             Value leftOp = as.getLeftOp();
741             
742             // take out the cast from "x = (type) y;"
743 if (rightOp instanceof CastExpr)
744                 rightOp = ((CastExpr) rightOp).getOp();
745             
746             if (isAnalyzedRef(leftOp) && isAnalyzedRef(rightOp)) {
747                 int roInfo = refInfo(rightOp, in);
748                 
749                 if (roInfo == kTop)
750                     uAddTopToFlowSet(leftOp, out);
751                 else if (roInfo != kBottom)
752                     uAddInfoToFlowSet(leftOp, roInfo, out);
753             }
754         }
755         
756         // Copy the out value to all branch boxes.
757 {
758             Iterator it = outBranchValues.iterator();
759             while (it.hasNext()) {
760                 FlowSet fs = (FlowSet) (it.next());
761                 
762                 copy(out, fs);
763             }
764         }
765         
766         // Copy the out value to the fallthrough box (don't need iterator)
767 {
768             Iterator it = outFallValue.iterator();
769             while (it.hasNext()) {
770                 FlowSet fs = (FlowSet) (it.next());
771                 
772                 copy(out, fs);
773             }
774         }
775         
776         if (isBranched && (stmt instanceof IfStmt)) {
777             Value cond = ((IfStmt) stmt).getCondition();
778             Value op1 = ((BinopExpr) cond).getOp1();
779             Value op2 = ((BinopExpr) cond).getOp2();
780
781             // make sure at least one of the op is a reference being analyzed
782 // and that none is a reference that is always Top
783 if ((!(isAlwaysTop(op1) || isAlwaysTop(op2))) && (isAnalyzedRef(op1) || isAnalyzedRef(op2))) {
784                 Value toGen = null;
785                 int toGenInfo = kBottom;
786
787                 int op1Info = anyRefInfo(op1, in);
788                 int op2Info = anyRefInfo(op2, in);
789                 boolean op1isKnown = (op1Info == kNull || op1Info == kNonNull);
790                 boolean op2isKnown = (op2Info == kNull || op2Info == kNonNull);
791                 
792                 if (op1isKnown) {
793                     if (!op2isKnown) {
794                         toGen = op2;
795                         toGenInfo = op1Info;
796                     }
797                 } else if (op2isKnown) {
798                     toGen = op1;
799                     toGenInfo = op2Info;
800                 }
801                 
802                 // only generate info for analyzed references that are top or bottom
803 if ((toGen != null) && isAnalyzedRef(toGen)) {
804                     int fInfo = kBottom;
805                     int bInfo = kBottom;
806                     
807                     if (cond instanceof EqExpr) {
808                         // branching mean op1 == op2
809 bInfo = toGenInfo;
810                         if (toGenInfo == kNull) {
811                             // falling through mean toGen != null
812 fInfo = kNonNull;
813                         }
814                         
815                     } else if (cond instanceof NeExpr) {
816                         // if we don't branch that mean op1 == op2
817 fInfo = toGenInfo;
818                         if (toGenInfo == kNull) {
819                             // branching through mean toGen != null
820 bInfo = kNonNull;
821                         }
822                     } else
823                         throw new RuntimeException ("invalid condition");
824
825                     if (fInfo != kBottom) {
826                         Iterator it = outFallValue.iterator();
827
828                         while(it.hasNext()) {
829                             FlowSet fs = (FlowSet) (it.next());
830
831                             copy(out, fs);
832                             uAddInfoToFlowSet(toGen, fInfo, fs);
833                         }
834                     }
835
836                     if (bInfo != kBottom) {
837                         Iterator it = outBranchValues.iterator();
838
839                         while (it.hasNext()) {
840                             FlowSet fs = (FlowSet) (it.next());
841
842                             copy(out, fs);
843                             uAddInfoToFlowSet(toGen, bInfo, fs);
844                         }
845                     }
846                 }
847             }
848         }
849     } // end flowThrough
850
851
852     protected void merge(Object in1, Object in2, Object out)
853     {
854         FlowSet inSet1 = (FlowSet) in1;
855         FlowSet inSet2 = (FlowSet) in2;
856         FlowSet inSet1Copy = (FlowSet) inSet1.clone();
857         FlowSet inSet2Copy = (FlowSet) inSet2.clone();
858         // we do that in case out is in1 or in2
859
860         FlowSet outSet = (FlowSet) out;
861
862         inSet1.intersection(inSet2, outSet);
863         // first step, set out to the intersection of in1 & in2
864 // but we are not over, the intersection doesn't handle the top & bottom cases
865 Iterator it = refTypeValues.iterator();
866         while (it.hasNext()) {
867             EquivalentValue r = (EquivalentValue) it.next();
868             int refInfoIn1 = refInfo(r, inSet1Copy);
869             int refInfoIn2 = refInfo(r, inSet2Copy);
870             if (refInfoIn1 != refInfoIn2) {
871                 // only process if they are not equal, otherwise the intersection has done its job
872 if ((refInfoIn1 == kTop) || (refInfoIn2 == kTop)) {
873                     // ok, r is top in one of the sets but not the other, make it top in the outSet
874 uAddTopToFlowSet(r, outSet);
875                 } else if (refInfoIn1 == kBottom) {
876                     // r is bottom in set1 but not set2, promote to the value in set2
877 uAddInfoToFlowSet(r, refInfoIn2, outSet);
878                 } else if (refInfoIn2 == kBottom) {
879                     // r is bottom in set2 but not set1, promote to the value in set1
880 uAddInfoToFlowSet(r, refInfoIn1, outSet);
881                 } else {
882                     // r is known in both set, but it's a different value in each set, make it top
883 uAddTopToFlowSet(r, outSet);
884                 }
885             }
886         }
887     } // end merge
888
889
890     protected void copy(Object source, Object dest)
891     {
892         FlowSet sourceSet = (FlowSet) source,
893             destSet = (FlowSet) dest;
894             
895         sourceSet.copy(destSet);
896     } // end copy
897
898
899     protected Object newInitialFlow()
900     {
901         return emptySet.clone();
902     } // end newInitialFlow
903
904
905     protected Object entryInitialFlow()
906     {
907         return fullSet.clone();
908     }
909
910     // try to workaround exception limitation of ForwardBranchedFlowAnalysis
911 // this will make for a very conservative analysys when exception handling
912 // statements are in the code :-(
913 public boolean treatTrapHandlersAsEntries()
914     {
915         return true;
916     }
917
918 } // end class BranchedRefVarsAnalysis
919
920

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags