View Javadoc

1   // PACallGraph.java, created Oct 21, 2003 12:56:45 AM by joewhaley
2   // Copyright (C) 2003 John Whaley <jwhaley@alum.mit.edu>
3   // Licensed under the terms of the GNU LGPL; see COPYING for details.
4   package joeq.Compiler.Analysis.Primitive;
5   
6   import java.util.AbstractMap;
7   import java.util.AbstractSet;
8   import java.util.Collection;
9   import java.util.Iterator;
10  import java.util.Map;
11  import java.util.Set;
12  import joeq.Compiler.Analysis.IPA.ProgramLocation;
13  import joeq.Compiler.Quad.CallGraph;
14  import joeq.Compiler.Quad.LoadedCallGraph;
15  import jwutil.collections.IndexMap;
16  import jwutil.collections.IndexedMap;
17  import jwutil.collections.UnmodifiableIterator;
18  import jwutil.util.Assert;
19  import net.sf.javabdd.BDD;
20  import net.sf.javabdd.BDDDomain;
21  import net.sf.javabdd.BDDFactory;
22  import net.sf.javabdd.BDDVarSet;
23  
24  /***
25   * PrimitivePACallGraph
26   * 
27   * @author John Whaley
28   * @version $Id: PrimitivePACallGraph.java 2470 2006-07-17 05:20:48Z joewhaley $
29   */
30  public class PrimitivePACallGraph extends CallGraph {
31  
32      public static final boolean TRACE = false;
33      
34      final BDDFactory bdd;
35      final BDDDomain M, I;
36      final Collection roots;
37      final BDD visited;
38      final BDD IE;
39      final IndexMap Mmap, Imap;
40  
41      private PrimitivePA pa;
42      
43      public PrimitivePACallGraph(PrimitivePA pa) {
44          this.bdd = pa.bdd;
45          this.M = pa.M;
46          this.I = pa.I;
47          this.roots = pa.rootMethods;
48          this.visited = pa.visited;
49          //this.IE = pa.IE.exist(pa.V1cV2cset);
50          this.IE = pa.IE;
51          this.Mmap = pa.Mmap;
52          this.Imap = pa.Imap;
53          this.pa = pa;
54      }
55      
56      /* (non-Javadoc)
57       * @see joeq.Compiler.Quad.CallGraph#setRoots(java.util.Collection)
58       */
59      public void setRoots(Collection roots) {
60          Assert.UNREACHABLE();
61      }
62  
63      /* (non-Javadoc)
64       * @see joeq.Compiler.Quad.CallGraph#getRoots()
65       */
66      public Collection getRoots() {
67          return roots;
68      }
69  
70      /* (non-Javadoc)
71       * @see joeq.Compiler.Quad.CallGraph#getTargetMethods(java.lang.Object, joeq.Compiler.Analysis.IPA.ProgramLocation)
72       */
73      public Collection getTargetMethods(Object context, ProgramLocation callSite) {
74          callSite = LoadedCallGraph.mapCall(callSite);
75          int I_i = Imap.get(callSite);
76          BDD I_bdd = I.ithVar(I_i);
77          BDD b = IE.restrict(I_bdd);
78          if (TRACE) 
79              System.out.println("Target methods of "+callSite+" = "+b.toStringWithDomains(pa.TS));
80          I_bdd.free();
81          return new BDDSet(b, M, Mmap);
82      }
83      
84      /* (non-Javadoc)
85       * @see joeq.Compiler.Quad.CallGraph#getAllMethods()
86       */
87      public Collection getAllMethods() {
88          BDD b = visited.id();
89          //b.orWith(pa.IE.exist(pa.Iset));
90          //b.orWith(pa.Mret.exist(pa.V2set));
91          return new BDDSet(b, M, Mmap);
92      }
93  
94      public static class BDDSet extends AbstractSet {
95          BDD b;
96          BDDDomain d;
97          BDDVarSet dset;
98          IndexedMap map;
99          public BDDSet(BDD b, BDDDomain d, IndexedMap map) {
100             this.b = b;
101             this.d = d;
102             this.dset = d.set();
103             this.map = map;
104         }
105         public int size() {
106             return (int) b.satCount(dset);
107         }
108         public Iterator iterator() {
109             final BDD b1 = b.id();
110             return new UnmodifiableIterator() {
111                 public boolean hasNext() {
112                     return !b1.isZero();
113                 }
114                 public Object next() {
115                     BDD b2 = b1.satOne(dset, false);
116                     final int d_i = b2.scanVar(d).intValue();
117                     b1.applyWith(b2, BDDFactory.diff);
118                     return map.get(d_i);
119                 }
120             };
121         }
122     }
123     
124     // Not used.
125     public static class PACallTargetMap extends AbstractMap {
126         PrimitivePA pa;
127         
128         /* (non-Javadoc)
129          * @see java.util.Map#get(java.lang.Object)
130          */
131         public Object get(Object key) {
132             int I_i = pa.Imap.get(key);
133             BDD m = pa.IE.restrict(pa.I.ithVar(I_i));
134             return new BDDSet(m, pa.M, pa.Mmap);
135         }
136         
137         /* (non-Javadoc)
138          * @see java.util.AbstractMap#entrySet()
139          */
140         public Set entrySet() {
141             return new AbstractSet() {
142 
143                 public int size() {
144                     return (int) pa.IE.satCount(pa.IMset);
145                 }
146 
147                 public Iterator iterator() {
148                     final BDD bdd1 = pa.IE.id();
149                     return new UnmodifiableIterator() {
150 
151                         public boolean hasNext() {
152                             return !bdd1.isZero();
153                         }
154 
155                         public Object next() {
156                             BDD bdd2 = bdd1.satOne(pa.IMset, false);
157                             final int I_i = bdd2.scanVar(pa.I).intValue();
158                             BDD bdd3 = pa.IE.restrict(pa.I.ithVar(I_i));
159                             final Collection result = new BDDSet(bdd3, pa.M, pa.Mmap);
160                             bdd1.applyWith(bdd2, BDDFactory.diff);
161                             return new Map.Entry() {
162 
163                                 public Object getKey() {
164                                     return pa.Imap.get(I_i);
165                                 }
166 
167                                 public Object getValue() {
168                                     return result;
169                                 }
170 
171                                 public Object setValue(Object value) {
172                                     throw new UnsupportedOperationException();
173                                 }
174                                 
175                             };
176                         }
177                         
178                     };
179                 }
180                 
181             };
182         }
183         
184     }
185     
186 }