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