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