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