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