1
2
3
4 package joeq.Compiler.Analysis.IPA;
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.Quad.CallGraph;
13 import joeq.Compiler.Quad.LoadedCallGraph;
14 import jwutil.collections.IndexMap;
15 import jwutil.collections.IndexedMap;
16 import jwutil.collections.UnmodifiableIterator;
17 import jwutil.util.Assert;
18 import net.sf.javabdd.BDD;
19 import net.sf.javabdd.BDDDomain;
20 import net.sf.javabdd.BDDFactory;
21 import net.sf.javabdd.BDDVarSet;
22
23 /***
24 * PACallGraph
25 *
26 * @author John Whaley
27 * @version $Id: PACallGraph.java 2470 2006-07-17 05:20:48Z joewhaley $
28 */
29 public class PACallGraph extends CallGraph {
30
31 public static final boolean TRACE = false;
32
33 final BDDFactory bdd;
34 final BDDDomain M, I;
35 final Collection roots;
36 final BDD visited;
37 final BDD IE;
38 final IndexMap Mmap, Imap;
39
40 private PA pa;
41
42 public PACallGraph(PA pa) {
43 this.bdd = pa.bdd;
44 this.M = pa.M;
45 this.I = pa.I;
46 this.roots = pa.rootMethods;
47 this.visited = pa.visited;
48
49 this.IE = pa.IE;
50 this.Mmap = pa.Mmap;
51 this.Imap = pa.Imap;
52 this.pa = pa;
53 }
54
55
56
57
58 public void setRoots(Collection roots) {
59 Assert.UNREACHABLE();
60 }
61
62
63
64
65 public Collection getRoots() {
66 return roots;
67 }
68
69
70
71
72 public Collection getTargetMethods(Object context, ProgramLocation callSite) {
73 callSite = LoadedCallGraph.mapCall(callSite);
74 int I_i = Imap.get(callSite);
75 BDD I_bdd = I.ithVar(I_i);
76 BDD b = IE.restrict(I_bdd);
77 if (TRACE)
78 System.out.println("Target methods of "+callSite+" = "+b.toStringWithDomains(pa.TS));
79 I_bdd.free();
80 return new BDDSet(b, M, Mmap);
81 }
82
83
84
85
86 public Collection getAllMethods() {
87 BDD b = visited.id();
88
89
90 return new BDDSet(b, M, Mmap);
91 }
92
93 public static class BDDSet extends AbstractSet {
94 BDD b;
95 BDDDomain d;
96 BDDVarSet dset;
97 IndexedMap map;
98 public BDDSet(BDD b, BDDDomain d, IndexedMap map) {
99 this.b = b;
100 this.d = d;
101 this.dset = d.set();
102 this.map = map;
103 }
104 public int size() {
105 return (int) b.satCount(dset);
106 }
107 public Iterator iterator() {
108 final BDD b1 = b.id();
109 return new UnmodifiableIterator() {
110 public boolean hasNext() {
111 return !b1.isZero();
112 }
113 public Object next() {
114 BDD b2 = b1.satOne(dset, false);
115 final int d_i = b2.scanVar(d).intValue();
116 b1.applyWith(b2, BDDFactory.diff);
117 return map.get(d_i);
118 }
119 };
120 }
121 }
122
123
124 public static class PACallTargetMap extends AbstractMap {
125
126 PA 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 }