Robust/src/IR/Tree/JavaBuilder.java

   1 package IR.Tree;
   2 import IR.*;
   3 import IR.Tree.*;
   4 import IR.Flat.*;
   5 import java.util.*;
   6 import java.io.*;
   7 import Util.Pair;
   8 import Analysis.CallGraph.CallGraph;
   9
  10 public class JavaBuilder implements CallGraph {
  11   State state;
  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;
  17   BuildIR bir;
  18   TypeUtil tu;
  19   SemanticCheck sc;
  20   BuildFlat bf;
  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;
  25
  26   /* Maps class/interfaces to all instantiated classes that extend or
  27    * implement those classes or interfaces */
  28
  29   HashMap<ClassDescriptor, Set<ClassDescriptor>> implementationMap=new HashMap<ClassDescriptor, Set<ClassDescriptor>>();
  30
  31   /* Maps methods to the methods they call */
  32
  33   HashMap<MethodDescriptor, Set<MethodDescriptor>> callMap=new HashMap<MethodDescriptor, Set<MethodDescriptor>>();
  34
  35   HashMap<MethodDescriptor, Set<MethodDescriptor>> revCallMap=new HashMap<MethodDescriptor, Set<MethodDescriptor>>();
  36
  37   /* Invocation map */
  38   HashMap<ClassDescriptor, Set<Pair<MethodDescriptor, MethodDescriptor>>> invocationMap=new HashMap<ClassDescriptor, Set<Pair<MethodDescriptor, MethodDescriptor>>>();
  39
  40   public Set getAllMethods(Descriptor d) {
  41     HashSet tovisit=new HashSet();
  42     tovisit.add(d);
  43     HashSet callable=new HashSet();
  44     while(!tovisit.isEmpty()) {
  45       Descriptor md=(Descriptor)tovisit.iterator().next();
  46       tovisit.remove(md);
  47       Set s=getCalleeSet(md);
  48
  49       if (s!=null) {
  50         for(Iterator it=s.iterator(); it.hasNext(); ) {
  51           MethodDescriptor md2=(MethodDescriptor)it.next();
  52           if( !callable.contains(md2) ) {
  53             callable.add(md2);
  54             tovisit.add(md2);
  55           }
  56         }
  57       }
  58     }
  59     return callable;
  60   }
  61
  62   public Set getMethods(MethodDescriptor md, TypeDescriptor type) {
  63     if (canCall.containsKey(md))
  64       return canCall.get(md);
  65     else
  66       return new HashSet();
  67   }
  68
  69   public Set getMethods(MethodDescriptor md) {
  70     return getMethods(md, null);
  71   }
  72
  73   public Set getMethodCalls(Descriptor d) {
  74     Set set=getAllMethods(d);
  75     set.add(d);
  76     return set;
  77   }
  78
  79   public boolean isCalled(MethodDescriptor md) {
  80     return !getMethods(md).isEmpty();
  81   }
  82
  83   public boolean isCallable(MethodDescriptor md) {
  84     return !getCallerSet(md).isEmpty()||md==mainMethod;
  85   }
  86
  87   public Set getCalleeSet(Descriptor d) {
  88     Set calleeset=callMap.get((MethodDescriptor)d);
  89     if (calleeset==null)
  90       return new HashSet();
  91     else
  92       return calleeset;
  93   }
  94
  95   public Set getCallerSet(MethodDescriptor md) {
  96     Set callerset=revCallMap.get(md);
  97     if (callerset==null)
  98       return new HashSet();
  99     else
 100       return callerset;
 101   }
 102
 103   public Set getFirstReachableMethodContainingSESE(Descriptor d,
 104                                                    Set<MethodDescriptor> methodsContainingSESEs) {
 105     throw new Error("");
 106   }
 107
 108   public boolean hasLayout(ClassDescriptor cd) {
 109     return sc.hasLayout(cd);
 110   }
 111
 112   public JavaBuilder(State state) {
 113     this.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);
 118   }
 119
 120   public TypeUtil getTypeUtil() {
 121     return tu;
 122   }
 123
 124   public BuildFlat getBuildFlat() {
 125     return bf;
 126   }
 127
 128   public void build() {
 129     //Initialize Strings to keep runtime happy
 130     ClassDescriptor stringClass=sc.getClass(null, TypeUtil.StringClass, SemanticCheck.INIT);
 131     instantiateClass(stringClass);
 132
 133     ClassDescriptor mainClass=sc.getClass(null, state.main, SemanticCheck.INIT);
 134     mainMethod=tu.getMain();
 135
 136     canCall.put(mainMethod, new HashSet<MethodDescriptor>());
 137     canCall.get(mainMethod).add(mainMethod);
 138
 139     toprocess.push(mainMethod);
 140     computeFixPoint();
 141     tu.createFullTable();
 142   }
 143
 144   void checkMethod(MethodDescriptor md) {
 145     try {
 146       sc.checkMethodBody(md.getClassDesc(), md);
 147     } catch( Error e ) {
 148       System.out.println("Error in "+md);
 149       throw e;
 150     }
 151   }
 152
 153   public boolean isInit(ClassDescriptor cd) {
 154     return classStatus.get(cd)!=null&&classStatus.get(cd)>=CDINIT;
 155   }
 156
 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);
 164         }
 165       }
 166       classStatus.put(cd, init);
 167     }
 168   }
 169
 170   void computeFixPoint() {
 171     while(!toprocess.isEmpty()) {
 172       MethodDescriptor md=toprocess.pop();
 173       checkMethod(md);
 174       initClassDesc(md.getClassDesc(), CDINIT);
 175       bf.flattenMethod(md.getClassDesc(), md);
 176       processFlatMethod(md);
 177     }
 178
 179     //make sure every called method descriptor has a flat method
 180     for(MethodDescriptor callmd : canCall.keySet())
 181       bf.addJustFlatMethod(callmd);
 182   }
 183
 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>());
 189
 190     //First handle easy cases...
 191     if (callmd.isStatic()||callmd.isConstructor()) {
 192       if (!discovered.contains(callmd)) {
 193         discovered.add(callmd);
 194         toprocess.push(callmd);
 195       }
 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);
 201       return;
 202     }
 203
 204     //Otherwise, handle virtual dispatch...
 205     ClassDescriptor cn=callmd.getClassDesc();
 206     Set<ClassDescriptor> impSet=implementationMap.get(cn);
 207
 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));
 211
 212     if (impSet!=null) {
 213       for(ClassDescriptor cdactual : impSet) {
 214         searchimp :
 215         while(cdactual!=null) {
 216           Set possiblematches=cdactual.getMethodTable().getSetFromSameScope(callmd.getSymbol());
 217
 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);
 225               }
 226
 227               if (!revCallMap.containsKey(matchmd))
 228                 revCallMap.put(matchmd, new HashSet<MethodDescriptor>());
 229               revCallMap.get(matchmd).add(md);
 230
 231               callMap.get(md).add(matchmd);
 232               canCall.get(callmd).add(matchmd);
 233               break searchimp;
 234             }
 235           }
 236
 237           //Didn't find method...look in super class
 238           cdactual=cdactual.getSuperDesc();
 239         }
 240       }
 241     }
 242   }
 243
 244   void processNew(FlatNew fnew) {
 245     TypeDescriptor tdnew=fnew.getType();
 246     if (!tdnew.isClass())
 247       return;
 248     ClassDescriptor cdnew=tdnew.getClassDesc();
 249     //Make sure class is fully initialized
 250     sc.checkClass(cdnew, SemanticCheck.INIT);
 251     instantiateClass(cdnew);
 252   }
 253
 254   void instantiateClass(ClassDescriptor cdnew) {
 255     if (classStatus.containsKey(cdnew)&&classStatus.get(cdnew)==CDINSTANTIATED)
 256       return;
 257     initClassDesc(cdnew, CDINSTANTIATED);
 258
 259     Stack<ClassDescriptor> tovisit=new Stack<ClassDescriptor>();
 260     tovisit.add(cdnew);
 261
 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;
 273
 274 searchimp:
 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);
 284                   }
 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);
 290                   break searchimp;
 291                 }
 292               }
 293
 294               //Didn't find method...look in super class
 295               cdactual=cdactual.getSuperDesc();
 296             }
 297           }
 298         }
 299       }
 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);
 305       }
 306     }
 307   }
 308
 309   void processFlatMethod(MethodDescriptor md) {
 310     if (!callMap.containsKey(md))
 311       callMap.put(md, new HashSet<MethodDescriptor>());
 312
 313     FlatMethod fm=state.getMethodFlat(md);
 314     for(FlatNode fn : fm.getNodeSet()) {
 315       switch(fn.kind()) {
 316       case FKind.FlatCall : {
 317           FlatCall fcall=(FlatCall)fn;
 318           processCall(md, fcall);
 319           break;
 320       }
 321
 322       case FKind.FlatNew: {
 323         FlatNew fnew=(FlatNew)fn;
 324         processNew(fnew);
 325         break;
 326       }
 327       }
 328     }
 329   }
 330 }