Robust/src/IR/TypeUtil.java

   1 package IR;
   2 import java.util.*;
   3
   4 import IR.Flat.FlatNode;
   5 import IR.Tree.*;
   6 import java.io.File;
   7 import Main.Main;
   8
   9 public class TypeUtil {
  10   public static final String StringClass="String";
  11   public static final String ObjectClass="Object";
  12   public static final String StartupClass="StartupObject";
  13   public static final String TagClass="TagDescriptor";
  14   public static final String ThreadClass="Thread";
  15   public static final String TaskClass="Task";
  16   State state;
  17   Hashtable supertable;
  18   Hashtable subclasstable;
  19   BuildIR bir;
  20
  21   // for interfaces
  22   Hashtable<ClassDescriptor, Set<ClassDescriptor>> superIFtbl;
  23
  24   public TypeUtil(State state, BuildIR bir) {
  25     this.state=state;
  26     this.bir=bir;
  27     createTables();
  28   }
  29
  30   public void addNewClass(String cl, Set todo) {
  31     for(int i=0;i<state.classpath.size();i++) {
  32       String path=(String)state.classpath.get(i);
  33       File f=new File(path, cl+".java");
  34       if (f.exists()) {
  35         try {
  36           ParseNode pn=Main.readSourceFile(state, f.getCanonicalPath());
  37           bir.buildtree(pn, todo,f.getCanonicalPath());
  38           return;
  39         } catch (Exception e) {
  40           throw new Error(e);
  41         }
  42       }
  43     }
  44     throw new Error("Couldn't find class "+cl);
  45   }
  46
  47
  48
  49   public ClassDescriptor getClass(String classname) {
  50     ClassDescriptor cd=(ClassDescriptor)state.getClassSymbolTable().get(classname);
  51     return cd;
  52   }
  53
  54   public ClassDescriptor getClass(String classname, HashSet todo) {
  55     ClassDescriptor cd=(ClassDescriptor)state.getClassSymbolTable().get(classname);
  56     if (cd==null) {
  57       //have to find class
  58       addNewClass(classname, todo);
  59       cd=(ClassDescriptor)state.getClassSymbolTable().get(classname);
  60       cd.setClassLibrary();
  61
  62       System.out.println("Build class:"+cd);
  63       todo.add(cd);
  64     }
  65     if (!supertable.containsKey(cd)) {
  66       String superc=cd.getSuper();
  67       if (superc!=null) {
  68         ClassDescriptor cd_super=getClass(superc, todo);
  69         supertable.put(cd,cd_super);
  70       }
  71     }
  72     if (!superIFtbl.containsKey(cd)) {
  73       // add inherited interfaces
  74       superIFtbl.put(cd,new HashSet());
  75       HashSet hs=(HashSet)superIFtbl.get(cd);
  76       Vector<String> superifv = cd.getSuperInterface();
  77       for(int i = 0; i < superifv.size(); i++) {
  78         String superif = superifv.elementAt(i);
  79         ClassDescriptor if_super = getClass(superif, todo);
  80         hs.add(if_super);
  81       }
  82     }
  83     return cd;
  84   }
  85
  86   private void createTables() {
  87     supertable=new Hashtable();
  88     superIFtbl = new Hashtable<ClassDescriptor,Set<ClassDescriptor>>();
  89   }
  90
  91   public ClassDescriptor getMainClass() {
  92     return getClass(state.main);
  93   }
  94
  95   public MethodDescriptor getRun() {
  96     ClassDescriptor cd=getClass(TypeUtil.ThreadClass);
  97     for(Iterator methodit=cd.getMethodTable().getSet("run").iterator(); methodit.hasNext();) {
  98       MethodDescriptor md=(MethodDescriptor) methodit.next();
  99       if (md.numParameters()!=0||md.getModifiers().isStatic())
 100         continue;
 101       return md;
 102     }
 103     throw new Error("Can't find Thread.run");
 104   }
 105
 106   public MethodDescriptor getStaticStart() {
 107     ClassDescriptor cd=getClass(TypeUtil.ThreadClass);
 108     for(Iterator methodit=cd.getMethodTable().getSet("staticStart").iterator(); methodit.hasNext();) {
 109       MethodDescriptor md=(MethodDescriptor) methodit.next();
 110       if (md.numParameters()!=1||!md.getModifiers().isStatic()||!md.getParamType(0).isClass()||md.getParamType(0).getClassDesc()!=cd)
 111         continue;
 112       return md;
 113     }
 114     throw new Error("Can't find Thread.run");
 115   }
 116
 117   public MethodDescriptor getExecute() {
 118     ClassDescriptor cd = getClass(TypeUtil.TaskClass);
 119
 120     if(cd == null && state.DSMTASK)
 121       throw new Error("Task.java is not included");
 122
 123     for(Iterator methodit = cd.getMethodTable().getSet("execute").iterator(); methodit.hasNext();) {
 124       MethodDescriptor md = (MethodDescriptor) methodit.next();
 125       if (md.numParameters()!=0 || md.getModifiers().isStatic())
 126         continue;
 127       return md;
 128     }
 129     throw new Error("Can't find Task.execute");
 130   }
 131
 132
 133   public MethodDescriptor getMain() {
 134     ClassDescriptor cd=getMainClass();
 135     Set mainset=cd.getMethodTable().getSet("main");
 136     for(Iterator mainit=mainset.iterator(); mainit.hasNext();) {
 137       MethodDescriptor md=(MethodDescriptor)mainit.next();
 138       if (md.numParameters()!=1)
 139         continue;
 140       Descriptor pd=md.getParameter(0);
 141       TypeDescriptor tpd=(pd instanceof TagVarDescriptor) ? ((TagVarDescriptor)pd).getType() : ((VarDescriptor)pd)
 142                           .getType();
 143       if (tpd.getArrayCount()!=1)
 144         continue;
 145       if (!tpd.getSymbol().equals("String"))
 146         continue;
 147
 148       if (!md.getModifiers().isStatic())
 149         throw new Error("Error: Non static main");
 150       return md;
 151     }
 152     throw new Error(cd+" has no main");
 153   }
 154
 155   /** Check to see if md1 is more specific than md2...  Informally
 156       if md2 could always be called given the arguments passed into
 157       md1 */
 158
 159   public boolean isMoreSpecific(MethodDescriptor md1, MethodDescriptor md2) {
 160     /* Checks if md1 is more specific than md2 */
 161     if (md1.numParameters()!=md2.numParameters())
 162       throw new Error();
 163     for(int i=0; i<md1.numParameters(); i++) {
 164       if (!this.isSuperorType(md2.getParamType(i), md1.getParamType(i))) {
 165         if(((!md1.getParamType(i).isArray() &&
 166             (md1.getParamType(i).isInt() || md1.getParamType(i).isLong() || md1.getParamType(i).isDouble() || md1.getParamType(i).isFloat()))
 167             && md2.getParamType(i).isClass() && md2.getParamType(i).getClassDesc().getSymbol().equals("Object"))) {
 168           // primitive parameters vs Object
 169         } else {
 170           return false;
 171         }
 172       }
 173     }
 174     if (md1.getReturnType()==null||md2.getReturnType()==null) {
 175         if (md1.getReturnType()!=md2.getReturnType())
 176             return false;
 177     } else
 178         if (!this.isSuperorType(md2.getReturnType(), md1.getReturnType()))
 179             return false;
 180
 181     if (!this.isSuperorType(md2.getClassDesc(), md1.getClassDesc()))
 182       return false;
 183
 184     return true;
 185   }
 186
 187   public MethodDescriptor getMethod(ClassDescriptor cd, String name, TypeDescriptor[] types) {
 188     Set methoddescriptorset=cd.getMethodTable().getSet(name);
 189     MethodDescriptor bestmd=null;
 190 NextMethod:
 191     for(Iterator methodit=methoddescriptorset.iterator(); methodit.hasNext();) {
 192       MethodDescriptor currmd=(MethodDescriptor)methodit.next();
 193       /* Need correct number of parameters */
 194       if (types.length!=currmd.numParameters())
 195         continue;
 196       for(int i=0; i<types.length; i++) {
 197         if (!this.isSuperorType(currmd.getParamType(i),types[i]))
 198           continue NextMethod;
 199       }
 200       /* Method okay so far */
 201       if (bestmd==null)
 202         bestmd=currmd;
 203       else {
 204         if (isMoreSpecific(currmd,bestmd)) {
 205           bestmd=currmd;
 206         } else if (!isMoreSpecific(bestmd, currmd))
 207           throw new Error("No method is most specific");
 208
 209         /* Is this more specific than bestmd */
 210       }
 211     }
 212     if (bestmd==null)
 213       throw new Error("Could find: "+name + " in "+cd);
 214
 215     return bestmd;
 216   }
 217
 218   public void createFullTable() {
 219     subclasstable=new Hashtable();
 220     HashSet tovisit=new HashSet();
 221     HashSet visited=new HashSet();
 222
 223     Iterator classit=state.getClassSymbolTable().getDescriptorsIterator();
 224     while(classit.hasNext()) {
 225       tovisit.clear();
 226       visited.clear();
 227       ClassDescriptor cd=(ClassDescriptor)classit.next();
 228       ClassDescriptor tmp=cd.getSuperDesc();
 229
 230       // check cd's interface ancestors
 231       {
 232         Iterator it_sifs = cd.getSuperInterfaces();
 233         while(it_sifs.hasNext()) {
 234           ClassDescriptor cdt = (ClassDescriptor)it_sifs.next();
 235           if(!tovisit.contains(cdt)){
 236             tovisit.add(cdt);
 237           }
 238         }
 239       }
 240
 241       while(tmp!=null) {
 242         if (!subclasstable.containsKey(tmp))
 243           subclasstable.put(tmp,new HashSet());
 244         HashSet hs=(HashSet)subclasstable.get(tmp);
 245         hs.add(cd);
 246         // check tmp's interface ancestors
 247         Iterator it_sifs = tmp.getSuperInterfaces();
 248         while(it_sifs.hasNext()) {
 249           ClassDescriptor cdt = (ClassDescriptor)it_sifs.next();
 250           if(!tovisit.contains(cdt)){
 251             tovisit.add(cdt);
 252           }
 253         }
 254
 255         tmp=tmp.getSuperDesc();
 256       }
 257
 258       while(!tovisit.isEmpty()) {
 259         ClassDescriptor sif = (ClassDescriptor)tovisit.iterator().next();
 260         tovisit.remove(sif);
 261
 262         if(!visited.contains(sif)) {
 263           if(!this.subclasstable.containsKey(sif)) {
 264             this.subclasstable.put(sif, new HashSet());
 265           }
 266           HashSet hs = (HashSet)this.subclasstable.get(sif);
 267           hs.add(cd);
 268
 269           Iterator it_sifs = sif.getSuperInterfaces();
 270           while(it_sifs.hasNext()) {
 271             ClassDescriptor siftmp = (ClassDescriptor)it_sifs.next();
 272             if(!tovisit.contains(siftmp)){
 273               tovisit.add(siftmp);
 274             }
 275           }
 276           visited.add(sif);
 277         }
 278       }
 279     }
 280   }
 281
 282   public Set getSubClasses(ClassDescriptor cd) {
 283     return (Set)subclasstable.get(cd);
 284   }
 285
 286   public ClassDescriptor getSuper(ClassDescriptor cd) {
 287     return (ClassDescriptor)supertable.get(cd);
 288   }
 289
 290   public Set<ClassDescriptor> getSuperIFs(ClassDescriptor cd) {
 291     return superIFtbl.get(cd);
 292   }
 293
 294   public boolean isCastable(TypeDescriptor original, TypeDescriptor casttype) {
 295     if (original.isChar()&&
 296         (casttype.isByte()||
 297          casttype.isShort()))
 298       return true;
 299
 300     if (casttype.isChar()&&
 301         (original.isByte()||
 302          original.isShort()||
 303          original.isInt()||
 304          original.isLong()||
 305          original.isFloat()||
 306          original.isDouble()))
 307       return true;
 308
 309     return false;
 310   }
 311
 312   public boolean isSuperorType(TypeDescriptor possiblesuper, TypeDescriptor cd2) {
 313     if (possiblesuper.isOffset() || cd2.isOffset()) return true;
 314     //Matching type are always okay
 315     if (possiblesuper.equals(cd2))
 316       return true;
 317
 318     if ((possiblesuper.isTag() && !cd2.isTag())||
 319         (!possiblesuper.isTag() && cd2.isTag()))
 320       return false;
 321
 322     //Handle arrays
 323     if (cd2.isArray()||possiblesuper.isArray()) {
 324       // Object is super class of all arrays
 325       if (possiblesuper.getSymbol().equals(ObjectClass)&&!possiblesuper.isArray())
 326         return true;
 327
 328       // If we have the same dimensionality of arrays & both are classes, we can default to the normal test
 329       if (cd2.isClass()&&possiblesuper.isClass()
 330           &&(possiblesuper.getArrayCount()==cd2.getArrayCount())&&
 331           isSuperorType(possiblesuper.getClassDesc(), cd2.getClassDesc()))
 332         return true;
 333
 334       // Object is superclass of all array classes
 335       if (possiblesuper.getSymbol().equals(ObjectClass)&&cd2.isClass()
 336           &&(possiblesuper.getArrayCount()<cd2.getArrayCount()))
 337         return true;
 338
 339       //Allow arraytype=null statements
 340       if (possiblesuper.isArray()&&cd2.isNull())
 341         return true;
 342
 343       return false;
 344     }
 345
 346     if (possiblesuper.isClass()&&
 347         cd2.isClass())
 348       return isSuperorType(possiblesuper.getClassDesc(), cd2.getClassDesc());
 349     else if (possiblesuper.isClass()&&
 350              cd2.isNull())
 351       return true;
 352     else if (possiblesuper.isNull())
 353       throw new Error();       //not sure when this case would occur
 354     else if (possiblesuper.isPrimitive()&&
 355              cd2.isPrimitive()) {
 356       ///Primitive widenings from 5.1.2
 357       if (cd2.isByte()&&(possiblesuper.isByte()||possiblesuper.isShort()||
 358                          possiblesuper.isInt()||possiblesuper.isLong()||
 359                          possiblesuper.isFloat()||possiblesuper.isDouble()))
 360         return true;
 361       if (cd2.isShort()&&(possiblesuper.isShort()||
 362                           possiblesuper.isInt()||possiblesuper.isLong()||
 363                           possiblesuper.isFloat()||possiblesuper.isDouble()))
 364         return true;
 365       if (cd2.isChar()&&(possiblesuper.isChar()||
 366                          possiblesuper.isInt()||possiblesuper.isLong()||
 367                          possiblesuper.isFloat()||possiblesuper.isDouble()))
 368         return true;
 369       if (cd2.isInt()&&(possiblesuper.isInt()||possiblesuper.isLong()||
 370                         possiblesuper.isFloat()||possiblesuper.isDouble()
 371                         ||possiblesuper.isEnum()))
 372         return true;
 373       if (cd2.isEnum()&&(possiblesuper.isInt()||possiblesuper.isLong()||
 374                          possiblesuper.isFloat()||possiblesuper.isDouble()))
 375         return true;
 376       if(cd2.isEnum()&&possiblesuper.isEnum()&&cd2.class_desc.equals(possiblesuper.class_desc))
 377         return true;
 378       if (cd2.isLong()&&(possiblesuper.isLong()||
 379                          possiblesuper.isFloat()||possiblesuper.isDouble()))
 380         return true;
 381       if (cd2.isFloat()&&(possiblesuper.isFloat()||possiblesuper.isDouble()))
 382         return true;
 383       if (cd2.isDouble()&&possiblesuper.isDouble())
 384
 385         return true;
 386       if (cd2.isBoolean()&&possiblesuper.isBoolean())
 387         return true;
 388
 389       return false;
 390     } else if (possiblesuper.isPrimitive()&&(!possiblesuper.isArray())&&
 391                cd2.isPtr())
 392       return false;
 393     else if (cd2.isPrimitive()&&(!cd2.isArray())&&
 394              possiblesuper.isPtr())
 395       return false;
 396     else
 397       throw new Error("Case not handled:"+possiblesuper+" "+cd2);
 398   }
 399
 400   public TypeDescriptor mostSpecific(TypeDescriptor td1, TypeDescriptor td2) {
 401     if( isSuperorType( td1, td2 ) ) {
 402       return td2;
 403     }
 404     if( isSuperorType( td2, td1 ) ) {
 405       return td1;
 406     }
 407     throw new Error( td1+" and "+td2+" have no superclass relationship" );
 408   }
 409
 410   public TypeDescriptor mostSpecific(TypeDescriptor td1, TypeDescriptor td2, TypeDescriptor td3) {
 411     return mostSpecific( td1, mostSpecific( td2, td3 ) );
 412   }
 413
 414   public boolean isSuperorType(ClassDescriptor possiblesuper, ClassDescriptor cd2) {
 415     if (possiblesuper==cd2)
 416       return true;
 417     else
 418       return isSuper(possiblesuper, cd2);
 419   }
 420
 421   private boolean isSuper(ClassDescriptor possiblesuper, ClassDescriptor cd2) {
 422     HashSet tovisit=new HashSet();
 423     HashSet visited=new HashSet();
 424
 425     {
 426       // check cd2's interface ancestors
 427       Iterator<ClassDescriptor> it_sifs = getSuperIFs(cd2).iterator();
 428       while(it_sifs.hasNext()) {
 429         ClassDescriptor cd = it_sifs.next();
 430         if(cd == possiblesuper) {
 431           return true;
 432         } else if(!tovisit.contains(cd)){
 433           tovisit.add(cd);
 434         }
 435       }
 436     }
 437
 438     while(cd2!=null) {
 439       cd2=getSuper(cd2);
 440       if (cd2==possiblesuper)
 441         return true;
 442
 443       // check cd2's interface ancestors
 444       if(cd2 != null) {
 445         Iterator it_sifs = getSuperIFs(cd2).iterator();
 446         while(it_sifs.hasNext()) {
 447           ClassDescriptor cd = (ClassDescriptor)it_sifs.next();
 448           if(cd == possiblesuper) {
 449             return true;
 450           } else if(!tovisit.contains(cd)){
 451             tovisit.add(cd);
 452           }
 453         }
 454       }
 455     }
 456
 457     while(!tovisit.isEmpty()) {
 458       ClassDescriptor cd = (ClassDescriptor)tovisit.iterator().next();
 459       tovisit.remove(cd);
 460
 461       if(!visited.contains(cd)) {
 462         Iterator it_sifs = getSuperIFs(cd).iterator();
 463         while(it_sifs.hasNext()) {
 464           ClassDescriptor cdt = (ClassDescriptor)it_sifs.next();
 465           if(cdt == possiblesuper) {
 466             return true;
 467           } else if(!tovisit.contains(cdt)){
 468             tovisit.add(cdt);
 469           }
 470         }
 471         visited.add(cd);
 472       }
 473     }
 474     return false;
 475   }
 476 }