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