8 import Analysis.CallGraph.CallGraph;
10 public class JavaBuilder implements CallGraph {
12 HashSet<Descriptor> checkedDesc=new HashSet<Descriptor>();
13 HashMap<ClassDescriptor, Integer> classStatus=new HashMap<ClassDescriptor, Integer>();
14 public final int CDNONE=0;
15 public final int CDINIT=1;
16 public final int CDINSTANTIATED=2;
21 Stack<MethodDescriptor> toprocess=new Stack<MethodDescriptor>();
22 HashSet<MethodDescriptor> discovered=new HashSet<MethodDescriptor>();
23 HashMap<MethodDescriptor, Set<MethodDescriptor>> canCall=new HashMap<MethodDescriptor, Set<MethodDescriptor>>();
24 MethodDescriptor mainMethod;
26 /* Maps class/interfaces to all instantiated classes that extend or
27 * implement those classes or interfaces */
29 HashMap<ClassDescriptor, Set<ClassDescriptor>> implementationMap=new HashMap<ClassDescriptor, Set<ClassDescriptor>>();
31 /* Maps methods to the methods they call */
33 HashMap<MethodDescriptor, Set<MethodDescriptor>> callMap=new HashMap<MethodDescriptor, Set<MethodDescriptor>>();
35 HashMap<MethodDescriptor, Set<MethodDescriptor>> revCallMap=new HashMap<MethodDescriptor, Set<MethodDescriptor>>();
38 HashMap<ClassDescriptor, Set<Pair<MethodDescriptor, MethodDescriptor>>> invocationMap=new HashMap<ClassDescriptor, Set<Pair<MethodDescriptor, MethodDescriptor>>>();
40 public Set getAllMethods(Descriptor d) {
41 HashSet tovisit=new HashSet();
43 HashSet callable=new HashSet();
44 while(!tovisit.isEmpty()) {
45 Descriptor md=(Descriptor)tovisit.iterator().next();
47 Set s=getCalleeSet(md);
50 for(Iterator it=s.iterator(); it.hasNext(); ) {
51 MethodDescriptor md2=(MethodDescriptor)it.next();
52 if( !callable.contains(md2) ) {
62 public Set getMethods(MethodDescriptor md, TypeDescriptor type) {
63 if (canCall.containsKey(md))
64 return canCall.get(md);
69 public Set getMethods(MethodDescriptor md) {
70 return getMethods(md, null);
73 public Set getMethodCalls(Descriptor d) {
74 Set set=getAllMethods(d);
79 /* Returns whether there is a reachable call to this method descriptor...Not whether the implementation is called */
81 public boolean isCalled(MethodDescriptor md) {
82 return canCall.containsKey(md);
85 public boolean isCallable(MethodDescriptor md) {
86 return !getCallerSet(md).isEmpty()||md==mainMethod;
89 public Set getCalleeSet(Descriptor d) {
90 Set calleeset=callMap.get((MethodDescriptor)d);
97 public Set getCallerSet(MethodDescriptor md) {
98 Set callerset=revCallMap.get(md);
100 return new HashSet();
105 public Set getFirstReachableMethodContainingSESE(Descriptor d,
106 Set<MethodDescriptor> methodsContainingSESEs) {
110 public boolean hasLayout(ClassDescriptor cd) {
111 return sc.hasLayout(cd);
114 public JavaBuilder(State state) {
116 bir=new BuildIR(state);
117 tu=new TypeUtil(state, bir);
118 sc=new SemanticCheck(state, tu, false);
119 bf=new BuildFlat(state,tu);
122 public TypeUtil getTypeUtil() {
126 public BuildFlat getBuildFlat() {
130 public void build() {
131 //Initialize Strings to keep runtime happy
132 ClassDescriptor stringClass=sc.getClass(null, TypeUtil.StringClass, SemanticCheck.INIT);
133 instantiateClass(stringClass);
135 ClassDescriptor mainClass=sc.getClass(null, state.main, SemanticCheck.INIT);
136 mainMethod=tu.getMain();
138 canCall.put(mainMethod, new HashSet<MethodDescriptor>());
139 canCall.get(mainMethod).add(mainMethod);
141 toprocess.push(mainMethod);
143 tu.createFullTable();
146 void checkMethod(MethodDescriptor md) {
148 sc.checkMethodBody(md.getClassDesc(), md);
150 System.out.println("Error in "+md);
155 public boolean isInit(ClassDescriptor cd) {
156 return classStatus.get(cd)!=null&&classStatus.get(cd)>=CDINIT;
159 void initClassDesc(ClassDescriptor cd, int init) {
160 if (classStatus.get(cd)==null||classStatus.get(cd)<init) {
161 if (classStatus.get(cd)==null) {
162 MethodDescriptor mdstaticinit = (MethodDescriptor)cd.getMethodTable().get("staticblocks");
163 if (mdstaticinit!=null) {
164 discovered.add(mdstaticinit);
165 toprocess.push(mdstaticinit);
168 classStatus.put(cd, init);
172 void computeFixPoint() {
173 while(!toprocess.isEmpty()) {
174 MethodDescriptor md=toprocess.pop();
176 initClassDesc(md.getClassDesc(), CDINIT);
177 bf.flattenMethod(md.getClassDesc(), md);
178 processFlatMethod(md);
181 //make sure every called method descriptor has a flat method
182 for(MethodDescriptor callmd : canCall.keySet())
183 bf.addJustFlatMethod(callmd);
186 void processCall(MethodDescriptor md, FlatCall fcall) {
187 MethodDescriptor callmd=fcall.getMethod();
188 //make sure we have a FlatMethod for the base method...
189 if (!canCall.containsKey(callmd))
190 canCall.put(callmd, new HashSet<MethodDescriptor>());
192 //First handle easy cases...
193 if (callmd.isStatic()||callmd.isConstructor()) {
194 if (!discovered.contains(callmd)) {
195 discovered.add(callmd);
196 toprocess.push(callmd);
198 if (!revCallMap.containsKey(callmd))
199 revCallMap.put(callmd, new HashSet<MethodDescriptor>());
200 revCallMap.get(callmd).add(md);
201 callMap.get(md).add(callmd);
202 canCall.get(callmd).add(callmd);
206 //Otherwise, handle virtual dispatch...
207 ClassDescriptor cn=callmd.getClassDesc();
208 Set<ClassDescriptor> impSet=implementationMap.get(cn);
210 if (!invocationMap.containsKey(cn))
211 invocationMap.put(cn, new HashSet<Pair<MethodDescriptor,MethodDescriptor>>());
212 invocationMap.get(cn).add(new Pair<MethodDescriptor, MethodDescriptor>(md, callmd));
215 for(ClassDescriptor cdactual : impSet) {
217 while(cdactual!=null) {
218 Set possiblematches=cdactual.getMethodTable().getSetFromSameScope(callmd.getSymbol());
220 for(Iterator matchit=possiblematches.iterator(); matchit.hasNext(); ) {
221 MethodDescriptor matchmd=(MethodDescriptor)matchit.next();
222 if (callmd.matches(matchmd)) {
223 //Found the method that will be called
224 if (!discovered.contains(matchmd)) {
225 discovered.add(matchmd);
226 toprocess.push(matchmd);
229 if (!revCallMap.containsKey(matchmd))
230 revCallMap.put(matchmd, new HashSet<MethodDescriptor>());
231 revCallMap.get(matchmd).add(md);
233 callMap.get(md).add(matchmd);
234 canCall.get(callmd).add(matchmd);
239 //Didn't find method...look in super class
240 cdactual=cdactual.getSuperDesc();
246 void processNew(FlatNew fnew) {
247 TypeDescriptor tdnew=fnew.getType();
248 if (!tdnew.isClass())
250 ClassDescriptor cdnew=tdnew.getClassDesc();
251 //Make sure class is fully initialized
252 sc.checkClass(cdnew, SemanticCheck.INIT);
253 instantiateClass(cdnew);
256 void instantiateClass(ClassDescriptor cdnew) {
257 if (classStatus.containsKey(cdnew)&&classStatus.get(cdnew)==CDINSTANTIATED)
259 initClassDesc(cdnew, CDINSTANTIATED);
261 Stack<ClassDescriptor> tovisit=new Stack<ClassDescriptor>();
264 while(!tovisit.isEmpty()) {
265 ClassDescriptor cdcurr=tovisit.pop();
266 if (!implementationMap.containsKey(cdcurr))
267 implementationMap.put(cdcurr, new HashSet<ClassDescriptor>());
268 if (implementationMap.get(cdcurr).add(cdnew)) {
269 //new implementation...see if it affects implementationmap
270 if (invocationMap.containsKey(cdcurr)) {
271 for(Pair<MethodDescriptor, MethodDescriptor> mdpair : invocationMap.get(cdcurr)) {
272 MethodDescriptor md=mdpair.getFirst();
273 MethodDescriptor callmd=mdpair.getSecond();
274 ClassDescriptor cdactual=cdnew;
277 while(cdactual!=null) {
278 Set possiblematches=cdactual.getMethodTable().getSetFromSameScope(callmd.getSymbol());
279 for(Iterator matchit=possiblematches.iterator(); matchit.hasNext(); ) {
280 MethodDescriptor matchmd=(MethodDescriptor)matchit.next();
281 if (callmd.matches(matchmd)) {
282 //Found the method that will be called
283 if (!discovered.contains(matchmd)) {
284 discovered.add(matchmd);
285 toprocess.push(matchmd);
287 if (!revCallMap.containsKey(matchmd))
288 revCallMap.put(matchmd, new HashSet<MethodDescriptor>());
289 revCallMap.get(matchmd).add(md);
290 callMap.get(md).add(matchmd);
291 canCall.get(callmd).add(matchmd);
296 //Didn't find method...look in super class
297 cdactual=cdactual.getSuperDesc();
302 if (cdcurr.getSuperDesc()!=null)
303 tovisit.push(cdcurr.getSuperDesc());
304 for(Iterator interit=cdcurr.getSuperInterfaces(); interit.hasNext(); ) {
305 ClassDescriptor cdinter=(ClassDescriptor) interit.next();
306 tovisit.push(cdinter);
311 void processFlatMethod(MethodDescriptor md) {
312 if (!callMap.containsKey(md))
313 callMap.put(md, new HashSet<MethodDescriptor>());
315 FlatMethod fm=state.getMethodFlat(md);
316 for(FlatNode fn: fm.getNodeSet()) {
318 case FKind.FlatFieldNode: {
319 FieldDescriptor fd=((FlatFieldNode)fn).getField();
321 ClassDescriptor cd=fd.getClassDescriptor();
322 initClassDesc(cd, CDINIT);
327 case FKind.FlatSetFieldNode: {
328 FieldDescriptor fd=((FlatSetFieldNode)fn).getField();
330 ClassDescriptor cd=fd.getClassDescriptor();
331 initClassDesc(cd, CDINIT);
336 case FKind.FlatCall: {
337 FlatCall fcall=(FlatCall)fn;
338 processCall(md, fcall);
342 case FKind.FlatNew: {
343 FlatNew fnew=(FlatNew)fn;