001 /* Copyright 2000, 2001, Compaq Computer Corporation */ 002 003 package javafe.tc; 004 005 import java.util.Enumeration; 006 import javafe.ast.*; 007 import javafe.util.Set; 008 import javafe.util.Assert; 009 import javafe.util.Info; 010 011 import javafe.tc.TagConstants; // resolve ambiguity 012 013 /** 014 * The <code>TypeCheck</code> class contains methods to disambiguate, resolve, 015 * and check type declarations. (Before methods in this class can be called, the 016 * {@link TypeSig} class must be initialized.) 017 * 018 * <h3> Overview of checking, resolution, and disambiguation </h3> 019 * 020 * <p> This description is out of date, particularly with respect to the names 021 * of classes. </P> 022 * 023 * <p> <em>Checking</em> involves performing the static checks specified by the Java 024 * language specification. </p> 025 * 026 * <p> <em>Resolution</em> involves connecting symbolic references in the parse tree 027 * to objects representing declarations of the referred-to entities. The parser 028 * generates a number of nodes -- instances of {@link Identifier}, {@link FieldAccess}, 029 * and {@link MethodDecl} -- containing identifiers found in the input plus a 030 * <code>decl</code> field which is initially <code>null</code>. Resolution sets 031 * these <code>decl</code> fields to point to the declaration referred to by the 032 * identifiers. Similarly, {@link TypeName} nodes have a <code>sig</code> field 033 * which is initially <code>null</code> and which must be resolved to an instance of 034 * {@link TypeSig}. For example, the name <code>java.lang.String</code> appearing in 035 * a type context would be parsed to a {@link TypeName}; resolution of this node 036 * would point its <code>sig</code> field to the {@link TypeSig} object representing 037 * Java's standard {@link String} type. </p> 038 * 039 * <p> <em>Disambiguation</em> deals with "ambiguous names" in Java (see Section Six 040 * of the Java language specification, or <a 041 * href="http://src-www.pa.dec.com/~stata/ESCJava/naming.html">this document</a>). 042 * These are qualified names of the form <code>I1.I2...In</code> that appear in an 043 * expression context. For such a name, <code>I1</code> could be a local variable or 044 * a field of <code>this</code>, or some prefix of the name could be the 045 * fully-qualified name of a type, as in <code>java.lang.String.concat</code>. </p> 046 * 047 * <p> When it encounters an ambiguous name, the parser generates either an {@link 048 * AmbiguousVariableAccess} or {@link AmbiguousMethodInvocation} node depending on the context. These are leaf 049 * nodes. In these cases, disambiguation involves replacing these nodes with 050 * appropriate {@link VariableAccess} or {@link MethodInvocation} nodes; these are non-leaf 051 * nodes, and in general the replacement might be fairly deep. </p> 052 * 053 * <p> As an example of disambiguation, assume the name <code>x.y</code> is parsed as 054 * an {@link AmbiguousVariableAccess}. Assume further that no local named <code>x</code> is in 055 * scope, the current scope is in an instance method for a class that has a field 056 * named <code>x</code>. In this case, disambiguation would replace this {@link 057 * AmbiguousVariableAccess} with: 058 * 059 * <blockquote> 060 * <code>(FieldAccess (FieldAccess this x) y)</code> 061 * </blockquote> 062 * 063 * that is, an instance of {@link FieldAccess} whose <code>id</code> field was 064 * <code>y</code> and whose <code>expr</code> field was another {@link 065 * FieldAccess} whose <code>id</code> field was <code>x</code> and whose 066 * <code>expr</code> field was an instance of {@link ThisExpr}. </p> 067 * 068 * <p> An alternative design for disambiguation and resolution was considered. In 069 * this design, the {@link Name} class, the three subclasses of {@link FieldAccess}, 070 * and the three subclasses of {@link MethodInvocation} would be replaced with a new 071 * expression class that looked something like: 072 * 073 * <blockquote> 074 * <pre> 075 * class DotExpr extends Expr { 076 * int tag; // Indicates the kind of dot 077 * Expr expr; 078 * Identifier id; 079 * } 080 * </pre> 081 * </blockquote> 082 * </p> 083 * 084 * <p> When confronted with phrases of the form <code>I1.I2...In</code>, the parser 085 * would generate trees of DotExpr nodes all with the same tag, this tag 086 * indicating that the meaning of the dot was ambiguous. Disambiguation would 087 * involve replacing this ambiguous tag with a tag whose meaning was clear (e.g., a 088 * tag that meant "select a type from a package"). Resolution would involve using 089 * our generic decoration mechanism to link certain of these nodes with the 090 * declarations to which they refer. </p> 091 * 092 * <p> The advantages of this approach over the one we selected is that it is more 093 * conventional (it's been used, for example, in compilers for the Modula family of 094 * languages), it has a simpler class hierarchy, and it does not involve mutating the 095 * structure of the parse tree. The primary advantage of our approach is that we 096 * capture many more invariants in the type system, leaving less to go wrong at 097 * run-time. It is mostly for this reason that we selected it. In addition, our 098 * approach takes less space to represent type names, avoids downcasting (which can 099 * be costly time-wise), and is more friendly to the "visitor" pattern. </p> 100 * 101 * 102 * <h3> Staging the processing of type declarations </h3> 103 * 104 * <p> Resolving and checking a type declaration usually involves looking at other 105 * declarations to which it refers. Finding, reading, and processing referred-to 106 * types makes resolution and checking fairly complicated. As a result, we have 107 * decomposed it up into smaller steps. Type declarations move through a number of 108 * states as the resolution and checking process procedes. In addition to making the 109 * overall processing of type declarations conceptually more manageable, this 110 * decomposition has two other benefits: </p> 111 * 112 * <ul> 113 * 114 * <li> <em>Handling cycles.</em> As mentioned above, processing one type may involve 115 * processing types to which it refers. However, two types may refer to each other, 116 * making it impossible to process any one of them "first." Decomposing the 117 * processing into stages helps us handle such cycles. </li> 118 * 119 * <li> <em>Improving performance.</em> Processing one type declaration does not 120 * always involve fully processing the declarations to which it refers. How much 121 * processing is required of a referred-to type depends on the manner in which it is 122 * referred (e.g., in a method signature versus as a superclass). Decomposing 123 * processing into stages allows us to be lazy in processing referred-to types, that 124 * is, allowing us to process them only to the extent that is necessary and no 125 * further. </li> 126 * 127 * </ul> 128 * 129 * <p> To support the lazy handling of type declarations, type declarations are 130 * represented using two objects: {@link TypeDecl}s and {@link TypeSig}s. {@link 131 * TypeDecl} objects represents the actual parse tree of a declaration. {@link 132 * TypeSig} objects refer to {@link TypeDecl} objects. Rather than point directly to 133 * {@link TypeDecl}, most references to type declarations point to {@link TypeSig} 134 * objects instead. This extra level of indirection allows us to defer parsing of 135 * type declarations until the parse tree is really needed. </p> 136 * 137 * <p> Details of the states of type declarations are found with documentation of the 138 * {@link TypeSig} class. </p> 139 * 140 * @see javafe.tc.TypeSig 141 * @see javafe.tc.Env 142 * @see javafe.ast.TypeDecl 143 * @see javafe.ast.TypeName 144 * @see javafe.ast.FieldAccess 145 */ 146 147 public class TypeCheck 148 { 149 /** A (possibly extended) instance of TypeCheck. */ 150 151 //@ invariant inst != null; 152 public static TypeCheck inst; 153 154 /** Creates a instance of TypeCheck, and sets the <code>inst</code> 155 * field to this instance. Only one instance should be created. 156 * Also initializes {@link PrepTypeDeclaration}. */ 157 158 public TypeCheck() { 159 inst = this; 160 Info.out("[Init TypeCheck.inst to "+inst+"]"); 161 new PrepTypeDeclaration(); 162 } 163 164 /** Called to obtain the algorithm for performing name resolution 165 * and type checking. By default, returns an instance of 166 * {@link javafe.tc.FlowInsensitiveChecks}. */ 167 168 //@ ensures \result != null; 169 public FlowInsensitiveChecks makeFlowInsensitiveChecks() { 170 return new FlowInsensitiveChecks(); 171 } 172 173 /** Moves <code>s</code> into the checked state. If any of the 174 supertypes of <code>s</code> are not prepped, they are prepped 175 first. */ 176 177 //@ requires s != null; 178 public void checkTypeSig(TypeSig s) { 179 s.typecheck(); 180 } 181 182 /** Moves <code>td</code> into the checked state. If any of the 183 supertypes of <code>s</code> are not prepped, they are prepped 184 first. */ 185 186 //@ requires td != null; 187 public void checkTypeDecl(TypeDecl td) { 188 TypeSig sig = TypeSig.getSig(td); 189 checkTypeSig(sig); 190 } 191 192 /** Retrieves the {@link Type} of a {@link VarInit}. This type is 193 * associated with an expression by the typechecking pass. If the 194 * expression does not have an associated type, then 195 * <code>Assert.fail</code> is called. */ 196 197 //@ requires e != null; 198 public Type getType(VarInit e) { 199 return FlowInsensitiveChecks.getType( e ); 200 } 201 202 /** Retrieves the {@link Stmt} target of a {@link BranchStmt}. This 203 * {@link Stmt} may be mentioned either explicitly (as in 204 * <code>break label;</code>), or implicitly (as in 205 * <code>break;</code>) by the {@link BranchStmt}. The correct 206 * {@link Stmt} target is associated with the {@link BranchStmt} by 207 * the typechecking pass. This type is associated with an expression 208 * by the typechecking pass. If the {@link BranchStmt} does not have 209 * an associated {@link Stmt} target, then <code>Assert.fail</code> 210 * is called. */ 211 212 //@ requires s != null; 213 public Stmt getBranchLabel(BranchStmt s) { 214 return FlowInsensitiveChecks.getBranchLabel( s ); 215 } 216 217 /** Retrieves the {@link TypeSig} associated with a particular 218 * {@link TypeDecl}. */ 219 220 //@ requires d != null; 221 //@ ensures \result != null; 222 public TypeSig getSig(TypeDecl d) { 223 return TypeSig.getSig( d ); 224 } 225 226 227 /** 228 * Retrieves the {@link TypeSig} associated with a particular 229 * {@link TypeName}. 230 * 231 * Precondition: n has been resolved. 232 */ 233 //@ ensures \result != null; 234 public TypeSig getSig(/*@ non_null @*/ TypeName n) { 235 return TypeSig.getSig( n ); 236 } 237 238 239 public TypeSig getRawSig(/*@ non_null @*/ TypeName n) { 240 return TypeSig.getRawSig( n ); 241 } 242 243 244 /** 245 * Construct a <code>String</code> listing the signature of a 246 * {@link RoutineDecl}, omitting the return type and throws 247 * causes if any. <p> 248 * 249 * All types are fully qualified if <code>r</code> has 250 * been name resolved.<p> 251 * 252 * Sample output: "(int, javafe.tc.TypeSig, char[])" <p> 253 * 254 * Precondition: PrettyPrint.inst, and r non-null.<p> 255 */ 256 //@ requires r != null; 257 public static String getSignature(RoutineDecl r) { 258 StringBuffer s = new StringBuffer("("); 259 260 for (int i=0; i<r.args.size(); i++) { 261 if (i != 0) 262 s.append(", "); 263 s.append(Types.printName(r.args.elementAt(i).type)); 264 } 265 266 s.append(")"); 267 return s.toString(); 268 } 269 270 271 /** 272 * Returns the user-readable name for a {@link RoutineDecl}. <p> 273 * 274 * Either of the form "method <name>(<argument types>)" or the form 275 * "constructor <classname>(<argument types>)".<p> 276 * 277 * All argument types are fully qualified if 278 * <code>r</code> has been name resolved. The method/constructor 279 * name is not qualified.<p> 280 * 281 * Precondition: PrettyPrint.inst, and r non-null.<p> 282 */ 283 //@ requires r.hasParent; 284 public String getName(/*@ non_null @*/ RoutineDecl r) { 285 String argumentTypes = getSignature(r); 286 287 switch (r.getTag()) { 288 case TagConstants.METHODDECL: 289 MethodDecl md = (MethodDecl)r; 290 return "method " + md.id + argumentTypes; 291 292 case TagConstants.CONSTRUCTORDECL: 293 ConstructorDecl cd = (ConstructorDecl)r; 294 return "constructor " + cd.getParent().id 295 .toString() + argumentTypes; 296 297 default: 298 /*@ unreachable; */ //@ nowarn Reachable; 299 Assert.fail("unreachable point"); 300 return null; // keep compiler happy 301 } 302 } 303 304 /** 305 * Returns the user-readable simple name for a {@link RoutineDecl}. <p> 306 * 307 * Precondition: r non-null.<p> 308 */ 309 //@ requires r.hasParent; 310 public String getRoutineName(/*@ non_null @*/ RoutineDecl r) { 311 switch (r.getTag()) { 312 case TagConstants.METHODDECL: 313 MethodDecl md = (MethodDecl)r; 314 return md.id.toString(); 315 316 case TagConstants.CONSTRUCTORDECL: 317 ConstructorDecl cd = (ConstructorDecl)r; 318 return cd.getParent().id.toString(); 319 320 default: 321 /*@ unreachable; */ //@ nowarn Reachable; 322 Assert.fail("unreachable point"); 323 return null; // keep compiler happy 324 } 325 } 326 327 328 /** 329 * Can a member of type target with modifiers 330 * modifiers/pmodifiers be accessed by code located in from? <p> 331 * 332 * Note: pmodifiers may be null. <p> 333 */ 334 public boolean canAccess(/*@ non_null @*/ TypeSig from, 335 /*@ non_null @*/ TypeSig target, 336 int modifiers, 337 ModifierPragmaVec pmodifiers) { 338 if (Modifiers.isPublic(modifiers)) 339 return true; 340 if (Modifiers.isProtected(modifiers) && from.isSubtypeOf(target)) 341 return true; 342 if (!Modifiers.isPrivate(modifiers)) // aka, protected, package 343 return from.inSamePackageAs(target); 344 345 /* 346 * private case -- have same enclosing class? [1.1]: 347 */ 348 while (from.enclosingType != null) 349 from = from.enclosingType; 350 while (target.enclosingType != null) 351 target = target.enclosingType; 352 return target==from; 353 } 354 355 /** Retrieves the class {@link MethodDecl} that a given class 356 * {@link MethodDecl} overrides. If there is no overridden {@link 357 * MethodDecl} in a superclass, then return <code>null</code>. The 358 * returned {@link MethodDecl} may be abstract. If multiple class 359 * {@link MethodDecl}'s are overridden, it returns the one lowest 360 * in the class hierarchy (furthest away from 361 * java.lang.Object). This information is generated by the 'Prep' 362 * pass. */ 363 364 //@ requires md.parent instanceof ClassDecl; 365 public MethodDecl getOverrides(/*@ non_null @*/ MethodDecl md) { 366 367 Set overrides = PrepTypeDeclaration.inst.getOverrides( md ); 368 369 ClassDecl cd = (ClassDecl)md.parent; 370 for(;;) { 371 // move cd up to parent, if any 372 if( cd.superClass == null ) 373 return null; 374 375 cd = (ClassDecl)( getSig(cd.superClass).getTypeDecl() );//@ nowarn Null,Cast; 376 377 // Find MethodDecl at cd that is overridden 378 Enumeration overridden_methods = overrides.elements(); 379 while( overridden_methods.hasMoreElements() ) { 380 MethodDecl smd = (MethodDecl)overridden_methods.nextElement(); 381 if( smd.parent == cd ) 382 return smd; 383 } 384 } 385 } 386 387 /** Retrieves the set of interface {@link MethodDecl}s that a given 388 * class {@link MethodDecl} implements. This information is 389 * generated by the 'Prep' pass. */ 390 391 //@ requires cd != null && md != null; 392 //@ requires md.parent instanceof ClassDecl; 393 public Set getImplementsSet(ClassDecl cd, MethodDecl md) { 394 Assert.notFalse( md.parent instanceof ClassDecl ); 395 Set result = new Set(); 396 //@ assume result.elementType == \type(MethodDecl); 397 398 TypeSig sig = getSig( cd ); 399 sig.prep(); 400 Set overrides = PrepTypeDeclaration.inst.getOverrides( md ); 401 Enumeration overridden_methods = overrides.elements(); 402 while( overridden_methods.hasMoreElements() ) { 403 MethodDecl smd = (MethodDecl)overridden_methods.nextElement(); 404 if( smd.parent instanceof InterfaceDecl 405 && sig.isSubtypeOf( getSig(smd.parent) ) ) 406 result.add( smd ); 407 } 408 return result; 409 } 410 411 /** Retrieves the set of interface {@link MethodDecl}s that a given 412 * class {@link MethodDecl} implements. This information is 413 * generated by the 'Prep' pass. */ 414 415 //@ requires md != null; 416 //@ requires md.parent instanceof ClassDecl; 417 public Set getAllImplementsSet(MethodDecl md) { 418 Assert.notFalse( md.parent instanceof ClassDecl ); 419 Set result = new Set(); 420 //@ assume result.elementType == \type(MethodDecl); 421 422 Set overrides = PrepTypeDeclaration.inst.getOverrides( md ); 423 Enumeration overridden_methods = overrides.elements(); 424 while( overridden_methods.hasMoreElements() ) { 425 MethodDecl smd = (MethodDecl)overridden_methods.nextElement(); 426 if( smd.parent instanceof InterfaceDecl ) 427 result.add( smd ); 428 } 429 return result; 430 } 431 432 /** Retrieves the set of interface {@link MethodDecl}s that a 433 * given interface {@link MethodDecl} implements. This 434 * information is generated by the 'Prep' pass. */ 435 436 //@ requires md != null; 437 //@ requires md.parent instanceof InterfaceDecl; 438 public Set getImplementsSet(MethodDecl md) { 439 Assert.notFalse( md.parent instanceof InterfaceDecl ); 440 return PrepTypeDeclaration.inst.getOverrides( md ); 441 } 442 443 444 445 /** Retrieves the set of {@link MethodDecl}s that a given 446 * {@link MethodDecl} overrides or hides. This information is 447 * generated by the 'Prep' pass. */ 448 449 //@ requires md != null; 450 //@ ensures \result != null; 451 //@ ensures \result.elementType == \type(MethodDecl); 452 public Set getAllOverrides(MethodDecl md) { 453 return PrepTypeDeclaration.inst.getOverrides( md ); 454 } 455 456 } // end of class TypeCheck 457 458 /* 459 * Local Variables: 460 * Mode: Java 461 * fill-column: 85 462 * End: 463 */