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