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