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 */