1
2
3
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
50 this.IE = pa.IE;
51 this.Mmap = pa.Mmap;
52 this.Imap = pa.Imap;
53 this.pa = pa;
54 }
55
56
57
58
59 public void setRoots(Collection roots) {
60 Assert.UNREACHABLE();
61 }
62
63
64
65
66 public Collection getRoots() {
67 return roots;
68 }
69
70
71
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
85
86
87 public Collection getAllMethods() {
88 BDD b = visited.id();
89
90
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
125 public static class PACallTargetMap extends AbstractMap {
126 PrimitivePA pa;
127
128
129
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
138
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 }