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 public boolean isCalled(MethodDescriptor md) {
80 return !getMethods(md).isEmpty();
83 public boolean isCallable(MethodDescriptor md) {
84 return !getCallerSet(md).isEmpty()||md==mainMethod;
87 public Set getCalleeSet(Descriptor d) {
88 Set calleeset=callMap.get((MethodDescriptor)d);
95 public Set getCallerSet(MethodDescriptor md) {
96 Set callerset=revCallMap.get(md);
103 public Set getFirstReachableMethodContainingSESE(Descriptor d,
104 Set<MethodDescriptor> methodsContainingSESEs) {
108 public boolean hasLayout(ClassDescriptor cd) {
109 return sc.hasLayout(cd);
112 public JavaBuilder(State state) {
114 bir=new BuildIR(state);
115 tu=new TypeUtil(state, bir);
116 sc=new SemanticCheck(state, tu, false);
117 bf=new BuildFlat(state,tu);
120 public TypeUtil getTypeUtil() {
124 public BuildFlat getBuildFlat() {
128 public void build() {
129 //Initialize Strings to keep runtime happy
130 ClassDescriptor stringClass=sc.getClass(null, TypeUtil.StringClass, SemanticCheck.INIT);
131 instantiateClass(stringClass);
133 ClassDescriptor mainClass=sc.getClass(null, state.main, SemanticCheck.INIT);
134 mainMethod=tu.getMain();
136 canCall.put(mainMethod, new HashSet<MethodDescriptor>());
137 canCall.get(mainMethod).add(mainMethod);
139 toprocess.push(mainMethod);
141 tu.createFullTable();
144 void checkMethod(MethodDescriptor md) {
146 sc.checkMethodBody(md.getClassDesc(), md);
148 System.out.println( "Error in "+md );
153 public boolean isInit(ClassDescriptor cd) {
154 return classStatus.get(cd)!=null&&classStatus.get(cd)>=CDINIT;
157 void initClassDesc(ClassDescriptor cd, int init) {
158 if (classStatus.get(cd)==null||classStatus.get(cd)!=init) {
159 if (classStatus.get(cd)==null) {
160 MethodDescriptor mdstaticinit = (MethodDescriptor)cd.getMethodTable().get("staticblocks");
161 if (mdstaticinit!=null) {
162 discovered.add(mdstaticinit);
163 toprocess.push(mdstaticinit);
166 classStatus.put(cd, init);
170 void computeFixPoint() {
171 while(!toprocess.isEmpty()) {
172 MethodDescriptor md=toprocess.pop();
174 initClassDesc(md.getClassDesc(), CDINIT);
175 bf.flattenMethod(md.getClassDesc(), md);
176 processFlatMethod(md);
179 //make sure every called method descriptor has a flat method
180 for(MethodDescriptor callmd:canCall.keySet())
181 bf.addJustFlatMethod(callmd);
184 void processCall(MethodDescriptor md, FlatCall fcall) {
185 MethodDescriptor callmd=fcall.getMethod();
186 //make sure we have a FlatMethod for the base method...
187 if (!canCall.containsKey(callmd))
188 canCall.put(callmd, new HashSet<MethodDescriptor>());
190 //First handle easy cases...
191 if (callmd.isStatic()||callmd.isConstructor()) {
192 if (!discovered.contains(callmd)) {
193 discovered.add(callmd);
194 toprocess.push(callmd);
196 if (!revCallMap.containsKey(callmd))
197 revCallMap.put(callmd, new HashSet<MethodDescriptor>());
198 revCallMap.get(callmd).add(md);
199 callMap.get(md).add(callmd);
200 canCall.get(callmd).add(callmd);
204 //Otherwise, handle virtual dispatch...
205 ClassDescriptor cn=callmd.getClassDesc();
206 Set<ClassDescriptor> impSet=implementationMap.get(cn);
208 if (!invocationMap.containsKey(cn))
209 invocationMap.put(cn, new HashSet<Pair<MethodDescriptor,MethodDescriptor>>());
210 invocationMap.get(cn).add(new Pair<MethodDescriptor, MethodDescriptor>(md, callmd));
213 for(ClassDescriptor cdactual:impSet) {
215 while(cdactual!=null) {
216 Set possiblematches=cdactual.getMethodTable().getSetFromSameScope(callmd.getSymbol());
218 for(Iterator matchit=possiblematches.iterator(); matchit.hasNext();) {
219 MethodDescriptor matchmd=(MethodDescriptor)matchit.next();
220 if (callmd.matches(matchmd)) {
221 //Found the method that will be called
222 if (!discovered.contains(matchmd)) {
223 discovered.add(matchmd);
224 toprocess.push(matchmd);
227 if (!revCallMap.containsKey(matchmd))
228 revCallMap.put(matchmd, new HashSet<MethodDescriptor>());
229 revCallMap.get(matchmd).add(md);
231 callMap.get(md).add(matchmd);
232 canCall.get(callmd).add(matchmd);
237 //Didn't find method...look in super class
238 cdactual=cdactual.getSuperDesc();
244 void processNew(FlatNew fnew) {
245 TypeDescriptor tdnew=fnew.getType();
246 if (!tdnew.isClass())
248 ClassDescriptor cdnew=tdnew.getClassDesc();
249 //Make sure class is fully initialized
250 sc.checkClass(cdnew, SemanticCheck.INIT);
251 instantiateClass(cdnew);
254 void instantiateClass(ClassDescriptor cdnew) {
255 if (classStatus.containsKey(cdnew)&&classStatus.get(cdnew)==CDINSTANTIATED)
257 initClassDesc(cdnew, CDINSTANTIATED);
259 Stack<ClassDescriptor> tovisit=new Stack<ClassDescriptor>();
262 while(!tovisit.isEmpty()) {
263 ClassDescriptor cdcurr=tovisit.pop();
264 if (!implementationMap.containsKey(cdcurr))
265 implementationMap.put(cdcurr, new HashSet<ClassDescriptor>());
266 if (implementationMap.get(cdcurr).add(cdnew)) {
267 //new implementation...see if it affects implementationmap
268 if (invocationMap.containsKey(cdcurr)) {
269 for(Pair<MethodDescriptor, MethodDescriptor> mdpair:invocationMap.get(cdcurr)) {
270 MethodDescriptor md=mdpair.getFirst();
271 MethodDescriptor callmd=mdpair.getSecond();
272 ClassDescriptor cdactual=cdnew;
275 while(cdactual!=null) {
276 Set possiblematches=cdactual.getMethodTable().getSetFromSameScope(callmd.getSymbol());
277 for(Iterator matchit=possiblematches.iterator(); matchit.hasNext();) {
278 MethodDescriptor matchmd=(MethodDescriptor)matchit.next();
279 if (callmd.matches(matchmd)) {
280 //Found the method that will be called
281 if (!discovered.contains(matchmd)) {
282 discovered.add(matchmd);
283 toprocess.push(matchmd);
285 if (!revCallMap.containsKey(matchmd))
286 revCallMap.put(matchmd, new HashSet<MethodDescriptor>());
287 revCallMap.get(matchmd).add(md);
288 callMap.get(md).add(matchmd);
289 canCall.get(callmd).add(matchmd);
294 //Didn't find method...look in super class
295 cdactual=cdactual.getSuperDesc();
300 if (cdcurr.getSuperDesc()!=null)
301 tovisit.push(cdcurr.getSuperDesc());
302 for(Iterator interit=cdcurr.getSuperInterfaces();interit.hasNext();) {
303 ClassDescriptor cdinter=(ClassDescriptor) interit.next();
304 tovisit.push(cdinter);
309 void processFlatMethod(MethodDescriptor md) {
310 if (!callMap.containsKey(md))
311 callMap.put(md, new HashSet<MethodDescriptor>());
313 FlatMethod fm=state.getMethodFlat(md);
314 for(FlatNode fn:fm.getNodeSet()) {
316 case FKind.FlatCall: {
317 FlatCall fcall=(FlatCall)fn;
318 processCall(md, fcall);
321 case FKind.FlatNew: {
322 FlatNew fnew=(FlatNew)fn;