1
2
3
4 package joeq.Compiler.Analysis.IPA;
5
6 import java.util.Arrays;
7 import java.util.Collection;
8 import java.util.Collections;
9 import java.util.HashMap;
10 import java.util.Iterator;
11 import java.util.LinkedList;
12 import java.util.Map;
13 import java.util.Set;
14 import java.io.PrintStream;
15 import joeq.Class.jq_Array;
16 import joeq.Class.jq_Class;
17 import joeq.Class.jq_Field;
18 import joeq.Class.jq_Initializer;
19 import joeq.Class.jq_InstanceMethod;
20 import joeq.Class.jq_Method;
21 import joeq.Class.jq_Primitive;
22 import joeq.Class.jq_Type;
23 import joeq.Class.jq_TypeVisitor;
24 import joeq.Compiler.Analysis.FlowInsensitive.MethodSummary;
25 import joeq.Compiler.Analysis.FlowInsensitive.MethodSummary.FieldNode;
26 import joeq.Compiler.Analysis.FlowInsensitive.MethodSummary.Node;
27 import joeq.Compiler.Analysis.FlowInsensitive.MethodSummary.NodeSet;
28 import joeq.Compiler.Analysis.FlowInsensitive.MethodSummary.ParamNode;
29 import joeq.Compiler.Analysis.FlowInsensitive.MethodSummary.UnknownTypeNode;
30 import joeq.Compiler.Quad.CallGraph;
31 import joeq.Compiler.Quad.CodeCache;
32 import joeq.Compiler.Quad.ControlFlowGraph;
33 import jwutil.graphs.Navigator;
34 import jwutil.util.Assert;
35
36 /***
37 * ClassInvariantAnalysis
38 *
39 * @author John Whaley
40 * @version $Id: ClassInvariantAnalysis.java 1931 2004-09-22 22:17:47Z joewhaley $
41 */
42 public class ClassInvariantAnalysis
43 implements jq_TypeVisitor {
44
45 public static final boolean TRACE = true;
46 public static final boolean TRACE_INTRA = true;
47 public static final PrintStream out = System.out;
48
49 MethodSummary summary;
50 ParamNode dis;
51 Map returned;
52 Map thrown;
53
54 public void initialize(jq_Class k) {
55 jq_InstanceMethod[] ms = k.getDeclaredInstanceMethods();
56 jq_Initializer init = null;
57 for (int i=0; i<ms.length; ++i) {
58 if (ms[i] instanceof jq_Initializer) {
59 init = (jq_Initializer) ms[i];
60 break;
61 }
62 }
63 dis = ParamNode.get(init, 0, k);
64 summary = new MethodSummary(new ParamNode[] { dis });
65 returned = new HashMap();
66 thrown = new HashMap();
67 }
68
69 static MethodSummary getSummary(jq_Method m) {
70 if (m.getBytecode() == null) {
71 return null;
72 }
73 ControlFlowGraph cfg = CodeCache.getCode(m);
74 MethodSummary ms = MethodSummary.getSummary(cfg);
75 return ms;
76 }
77
78 static class LocalCallGraphNavigator implements Navigator {
79
80 jq_Class klass;
81 CallGraph cg;
82
83 /***
84 * @see jwutil.graphs.Navigator#next(java.lang.Object)
85 */
86 public Collection next(Object node) {
87 jq_Method caller = (jq_Method) node;
88 Collection callees = cg.getCallees(caller);
89 LinkedList ll = new LinkedList();
90 for (Iterator i = callees.iterator(); i.hasNext(); ) {
91 jq_Method callee = (jq_Method) i.next();
92 if (klass.isSubtypeOf(callee.getDeclaringClass())) {
93 ll.add(callee);
94 }
95 }
96 return ll;
97 }
98
99 /***
100 * @see jwutil.graphs.Navigator#prev(java.lang.Object)
101 */
102 public Collection prev(Object node) {
103 jq_Method callee = (jq_Method) node;
104 Collection s = cg.getCallerMethods(callee);
105 LinkedList ll = new LinkedList();
106 for (Iterator i = s.iterator(); i.hasNext(); ) {
107 jq_Method caller = (jq_Method) i.next();
108 if (caller.getDeclaringClass().isSubtypeOf(klass)) {
109 ll.add(caller);
110 }
111 }
112 return s;
113 }
114
115 }
116
117 public void instantiateLocalCalls(jq_Method m) {
118 }
119
120 public void visitMethod(jq_Method m) {
121 if (m.getBytecode() == null) {
122 if (TRACE) out.println("NOTE: "+m.getName()+"() is a native method, we don't know what goes on in there.");
123 return;
124 }
125 if (m.isPrivate()) {
126
127
128 }
129 ControlFlowGraph cfg = CodeCache.getCode(m);
130 MethodSummary ms = MethodSummary.getSummary(cfg);
131 if (m.isStatic()) {
132 if (TRACE) out.println(m.getName()+"() is static.");
133
134 } else {
135 ParamNode n = ms.getParamNode(0);
136 n.replaceBy(Collections.singleton(dis), true);
137
138 NodeSet s1 = new NodeSet(ms.getReturned());
139 if (s1.remove(n)) s1.add(dis);
140 returned.put(m, s1);
141
142 NodeSet s2 = new NodeSet(ms.getThrown());
143 if (s2.remove(n)) s2.add(dis);
144 thrown.put(m, s2);
145 }
146 }
147
148 public void unifyAccessPathEdges(Node n) {
149 if (n instanceof UnknownTypeNode) return;
150 if (TRACE_INTRA) out.println("Unifying access path edges from: "+n);
151 if (n.hasAccessPathEdges()) {
152 for (Iterator i=n.getAccessPathEdges().iterator(); i.hasNext(); ) {
153 java.util.Map.Entry e = (java.util.Map.Entry)i.next();
154 jq_Field f = (jq_Field)e.getKey();
155 Object o = e.getValue();
156 Assert._assert(o != null);
157 FieldNode n2;
158 if (o instanceof FieldNode) {
159 n2 = (FieldNode)o;
160 } else {
161 Set s = (Set)NodeSet.FACTORY.makeSet((Set)o);
162 if (s.size() == 0) {
163 i.remove();
164 continue;
165 }
166 if (s.size() == 1) {
167 n2 = (FieldNode)s.iterator().next();
168 e.setValue(n2);
169 continue;
170 }
171 if (TRACE_INTRA) out.println("Node "+n+" has duplicate access path edges on field "+f+": "+s);
172 n2 = FieldNode.unify(f, s);
173 for (Iterator j=s.iterator(); j.hasNext(); ) {
174 FieldNode n3 = (FieldNode)j.next();
175 for (Iterator k=returned.values().iterator(); k.hasNext(); ) {
176 Set s2 = (Set) k.next();
177 if (s2.remove(n3)) {
178 s2.add(n2);
179 }
180 }
181 for (Iterator k=thrown.values().iterator(); k.hasNext(); ) {
182 Set s2 = (Set) k.next();
183 if (s2.remove(n3)) {
184 s2.add(n2);
185 }
186 }
187
188 }
189
190 e.setValue(n2);
191 }
192 }
193 }
194 }
195
196 public void finish() {
197 unifyAccessPathEdges(dis);
198 for (Iterator i=dis.getAccessPathEdges().iterator(); i.hasNext(); ) {
199 Map.Entry e = (Map.Entry) i.next();
200 jq_Field f = (jq_Field) e.getKey();
201 System.out.println("Field "+f.getName()+" = "+dis.getAllEdges(f));
202 }
203 for (Iterator i=returned.entrySet().iterator(); i.hasNext(); ) {
204 Map.Entry e = (Map.Entry) i.next();
205 jq_Method f = (jq_Method) e.getKey();
206 System.out.println("Method "+f.getName()+" returns "+e.getValue());
207 }
208 }
209
210
211
212
213 public void visitClass(jq_Class c) {
214 this.initialize(c);
215 for (Iterator i=Arrays.asList(c.getDeclaredInstanceMethods()).iterator(); i.hasNext(); ) {
216 jq_Method m = (jq_Method) i.next();
217 visitMethod(m);
218 }
219 this.finish();
220 }
221
222
223
224
225 public void visitArray(jq_Array m) {}
226
227
228
229
230 public void visitPrimitive(jq_Primitive m) {}
231
232
233
234
235 public void visitType(jq_Type m) {}
236
237 }